From d50544a3de540727137f2b13010ca4450f8ea10f Mon Sep 17 00:00:00 2001 From: Cyrille Bagard Date: Sun, 18 Dec 2016 22:36:14 +0100 Subject: Used a fast sorted array to track shared instances instead of a simple hash table. --- ChangeLog | 31 ++++++++++ src/analysis/decomp/il.c | 2 +- src/arch/dalvik/operands/args.c | 54 +++++----------- src/arch/dalvik/operands/pool.c | 52 +++++----------- src/arch/dalvik/operands/register.c | 51 +++++---------- src/arch/dalvik/register.c | 101 ++++++++++-------------------- src/arch/dalvik/register.h | 3 + src/arch/operand-int.h | 3 +- src/arch/operand.c | 40 +++++++----- src/arch/operand.h | 2 +- src/arch/register-int.h | 3 +- src/arch/register.c | 60 ++++++------------ src/arch/register.h | 5 +- src/arch/sharing/instance-int.h | 12 ++-- src/arch/sharing/instance.c | 55 +++++------------ src/arch/sharing/instance.h | 9 +-- src/arch/sharing/manager.c | 100 ++++++++++++++---------------- src/arch/sharing/manager.h | 4 +- src/common/sort.c | 120 ++++++++++++++++++++++++++++++++++-- src/common/sort.h | 9 +++ 20 files changed, 360 insertions(+), 356 deletions(-) diff --git a/ChangeLog b/ChangeLog index eb93ae5..5061ad9 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,36 @@ 16-12-18 Cyrille Bagard + * src/analysis/decomp/il.c: + Disable old call code. + + * src/arch/dalvik/operands/args.c: + * src/arch/dalvik/operands/pool.c: + * src/arch/dalvik/operands/register.c: + * src/arch/dalvik/register.c: + * src/arch/dalvik/register.h: + * src/arch/operand-int.h: + * src/arch/operand.c: + * src/arch/operand.h: + * src/arch/register-int.h: + * src/arch/register.c: + * src/arch/register.h: + * src/arch/sharing/instance-int.h: + * src/arch/sharing/instance.c: + * src/arch/sharing/instance.h: + Define a new comparison process for operands with more precise results. + + * src/arch/sharing/manager.c: + * src/arch/sharing/manager.h: + Use a fast sorted array to track shared instances instead of a simple + hash table. + + * src/common/sort.c: + * src/common/sort.h: + Provide a generic way to compare numbers. Add a method to quicly delete + an item from a sorted array. + +16-12-18 Cyrille Bagard + * configure.ac: Add an option to dump share statistics to the compilation configuration. diff --git a/src/analysis/decomp/il.c b/src/analysis/decomp/il.c index bc56e0c..ad6f702 100644 --- a/src/analysis/decomp/il.c +++ b/src/analysis/decomp/il.c @@ -538,7 +538,7 @@ static void build_ite_branches(GITEInstruction *decomp, GFlowBlock *block, GDecC sub_parent = g_instr_block_get_links_block(G_INSTR_BLOCK(block)); sub_shared = g_hash_table_new_full((GHashFunc)g_arch_register_hash, - (GEqualFunc)g_arch_register_equal, + (GEqualFunc)NULL,//g_arch_register_equal, g_object_unref, g_object_unref); true_dinstr = NULL; diff --git a/src/arch/dalvik/operands/args.c b/src/arch/dalvik/operands/args.c index 9e75604..5ba552b 100644 --- a/src/arch/dalvik/operands/args.c +++ b/src/arch/dalvik/operands/args.c @@ -30,6 +30,7 @@ #include "../../operand-int.h" #include "../../sharing/manager.h" +#include "../../../common/sort.h" @@ -70,11 +71,8 @@ static void g_dalvik_args_operand_finalize(GDalvikArgsOperand *); /* Initialise un nouvel objet partagé avec des informations. */ static bool g_dalvik_args_operand_do_init(GDalvikArgsOperand *, const GDalvikArgsOperand *); -/* Indique l'objet partagé correspond à une description donnée. */ -static gboolean g_dalvik_args_operand_compare_info(const GDalvikArgsOperand *, const GDalvikArgsOperand *); - /* Compare un opérande avec un autre. */ -static bool g_dalvik_args_operand_compare(const GDalvikArgsOperand *, const GDalvikArgsOperand *); +static int g_dalvik_args_operand_compare(const GDalvikArgsOperand * const *, const GDalvikArgsOperand * const *); /* Traduit un opérande en version humainement lisible. */ static void g_dalvik_args_operand_print(const GDalvikArgsOperand *, GBufferLine *, AsmSyntax); @@ -122,7 +120,6 @@ static void g_dalvik_args_operand_class_init(GDalvikArgsOperandClass *klass) object->finalize = (GObjectFinalizeFunc)g_dalvik_args_operand_finalize; operand->init = (init_shared_fc)g_dalvik_args_operand_do_init; - operand->cmp_info = (compare_shared_info_fc)g_dalvik_args_operand_compare_info; operand->compare = (operand_compare_fc)g_dalvik_args_operand_compare; operand->print = (operand_print_fc)g_dalvik_args_operand_print; @@ -253,30 +250,6 @@ static bool g_dalvik_args_operand_do_init(GDalvikArgsOperand *operand, const GDa /****************************************************************************** * * -* Paramètres : operand = objet partagé à consulter. * -* fake = coquille vide contenant les infos à comparer. * -* * -* Description : Indique l'objet partagé correspond à une description donnée. * -* * -* Retour : TRUE si les détails centraux sont partagés, FALSE sinon. * -* * -* Remarques : - * -* * -******************************************************************************/ - -static gboolean g_dalvik_args_operand_compare_info(const GDalvikArgsOperand *operand, const GDalvikArgsOperand *fake) -{ - gboolean result; /* Bilan à retourner */ - - result = g_dalvik_args_operand_compare(operand, fake); - - return result; - -} - - -/****************************************************************************** -* * * Paramètres : a = premier opérande à consulter. * * b = second opérande à consulter. * * * @@ -288,20 +261,26 @@ static gboolean g_dalvik_args_operand_compare_info(const GDalvikArgsOperand *ope * * ******************************************************************************/ -static bool g_dalvik_args_operand_compare(const GDalvikArgsOperand *a, const GDalvikArgsOperand *b) +static int g_dalvik_args_operand_compare(const GDalvikArgsOperand * const *a, const GDalvikArgsOperand * const *b) { - bool result; /* Bilan à renvoyer */ + int result; /* Bilan à renvoyer */ + const GDalvikArgsOperand *_a; /* Accès rapide à l'élément A */ + const GDalvikArgsOperand *_b; /* Accès rapide à l'élément B */ size_t i; /* Boucle de parcours */ - if (b == NULL) - result = (a->count == 0); + _a = *a; + _b = *b; + + if (_b == NULL) + result = sort_unsigned_long(_a->count, 0); else { - result = (a->count == b->count); + result = sort_unsigned_long(_a->count, _b->count); - for (i = 0; i < a->count && result; i++) - result = g_arch_operand_compare(a->args[i], b->args[i]); + for (i = 0; i < _a->count && result == 0; i++) + result = g_arch_operand_compare((const GArchOperand * const *)&_a->args[i], + (const GArchOperand * const *)&_b->args[i]); } @@ -377,7 +356,8 @@ GDalvikArgsOperand *g_dalvik_args_operand_add(GDalvikArgsOperand *operand, GArch fake.args[i] = arg; - result = g_share_manager_update(_dalvik_args_operand_manager, G_SHARED_INSTANCE(operand), &fake, container); + result = g_share_manager_update(_dalvik_args_operand_manager, G_SHARED_INSTANCE(operand), + (GSharedInstance *)&fake, container); free(fake.args); diff --git a/src/arch/dalvik/operands/pool.c b/src/arch/dalvik/operands/pool.c index 4884867..be38ca3 100644 --- a/src/arch/dalvik/operands/pool.c +++ b/src/arch/dalvik/operands/pool.c @@ -33,6 +33,7 @@ #include "../../operand-int.h" #include "../../sharing/manager.h" +#include "../../../common/sort.h" #include "../../../format/dex/pool.h" @@ -75,11 +76,8 @@ static void g_dalvik_pool_operand_finalize(GDalvikPoolOperand *); /* Initialise un nouvel objet partagé avec des informations. */ static bool g_dalvik_pool_operand_do_init(GDalvikPoolOperand *, const GDalvikPoolOperand *); -/* Indique l'objet partagé correspond à une description donnée. */ -static gboolean g_dalvik_pool_operand_compare_info(const GDalvikPoolOperand *, const GDalvikPoolOperand *); - /* Compare un opérande avec un autre. */ -static bool g_dalvik_pool_operand_compare(const GDalvikPoolOperand *, const GDalvikPoolOperand *); +static int g_dalvik_pool_operand_compare(const GDalvikPoolOperand * const *, const GDalvikPoolOperand * const *); /* Traduit un opérande en version humainement lisible. */ static void g_dalvik_pool_operand_print(const GDalvikPoolOperand *, GBufferLine *, AsmSyntax); @@ -128,7 +126,6 @@ static void g_dalvik_pool_operand_class_init(GDalvikPoolOperandClass *klass) operand = G_ARCH_OPERAND_CLASS(klass); operand->init = (init_shared_fc)g_dalvik_pool_operand_do_init; - operand->cmp_info = (compare_shared_info_fc)g_dalvik_pool_operand_compare_info; operand->compare = (operand_compare_fc)g_dalvik_pool_operand_compare; operand->print = (operand_print_fc)g_dalvik_pool_operand_print; @@ -241,7 +238,7 @@ GArchOperand *g_dalvik_pool_operand_new(GDexFormat *format, DalvikPoolType type, fake.type = type; fake.index = (size == MDS_8_BITS ? index8 : index16); - result = G_ARCH_OPERAND(g_share_manager_get(_dalvik_pool_operand_manager, &fake)); + result = G_ARCH_OPERAND(g_share_manager_get(_dalvik_pool_operand_manager, (GSharedInstance *)&fake)); gdpon_exit: @@ -278,30 +275,6 @@ static bool g_dalvik_pool_operand_do_init(GDalvikPoolOperand *operand, const GDa /****************************************************************************** * * -* Paramètres : operand = objet partagé à consulter. * -* fake = coquille vide contenant les infos à comparer. * -* * -* Description : Indique l'objet partagé correspond à une description donnée. * -* * -* Retour : TRUE si les détails centraux sont partagés, FALSE sinon. * -* * -* Remarques : - * -* * -******************************************************************************/ - -static gboolean g_dalvik_pool_operand_compare_info(const GDalvikPoolOperand *operand, const GDalvikPoolOperand *fake) -{ - gboolean result; /* Bilan à retourner */ - - result = g_dalvik_pool_operand_compare(operand, fake); - - return result; - -} - - -/****************************************************************************** -* * * Paramètres : a = premier opérande à consulter. * * b = second opérande à consulter. * * * @@ -313,13 +286,22 @@ static gboolean g_dalvik_pool_operand_compare_info(const GDalvikPoolOperand *ope * * ******************************************************************************/ -static bool g_dalvik_pool_operand_compare(const GDalvikPoolOperand *a, const GDalvikPoolOperand *b) +static int g_dalvik_pool_operand_compare(const GDalvikPoolOperand * const *a, const GDalvikPoolOperand * const *b) { - bool result; /* Bilan à renvoyer */ + int result; /* Bilan à renvoyer */ + const GDalvikPoolOperand *_a; /* Accès rapide à l'élément A */ + const GDalvikPoolOperand *_b; /* Accès rapide à l'élément B */ + + _a = *a; + _b = *b; + + result = sort_unsigned_long((unsigned long)_a->format, (unsigned long)_b->format); + + if (result == 0) + result = sort_unsigned_long(_a->type, _b->type); - result = (a->format == b->format); - result &= (a->type == b->type); - result &= (a->index == b->index); + if (result == 0) + result = sort_unsigned_long(_a->index, _b->index); return result; diff --git a/src/arch/dalvik/operands/register.c b/src/arch/dalvik/operands/register.c index dcdcbac..613e0d4 100644 --- a/src/arch/dalvik/operands/register.c +++ b/src/arch/dalvik/operands/register.c @@ -65,13 +65,10 @@ static void g_dalvik_register_operand_dispose(GDalvikRegisterOperand *); static void g_dalvik_register_operand_finalize(GDalvikRegisterOperand *); /* Initialise un nouvel objet partagé avec des informations. */ -static bool g_dalvik_register_operand_do_init(GDalvikRegisterOperand *, const GDalvikRegister *); - -/* Indique l'objet partagé correspond à une description donnée. */ -static gboolean g_dalvik_register_operand_compare_info(const GDalvikRegisterOperand *, const GDalvikRegister *); +static bool g_dalvik_register_operand_do_init(GDalvikRegisterOperand *, const GDalvikRegisterOperand *); /* Compare un opérande avec un autre. */ -static bool g_dalvik_register_operand_compare(const GDalvikRegisterOperand *, const GDalvikRegisterOperand *); +static int g_dalvik_register_operand_compare(const GDalvikRegisterOperand * const *, const GDalvikRegisterOperand * const *); /* Traduit un opérande en version humainement lisible. */ static void g_dalvik_register_operand_print(const GDalvikRegisterOperand *, GBufferLine *, AsmSyntax); @@ -120,7 +117,6 @@ static void g_dalvik_register_operand_class_init(GDalvikRegisterOperandClass *kl operand = G_ARCH_OPERAND_CLASS(klass); operand->init = (init_shared_fc)g_dalvik_register_operand_do_init; - operand->cmp_info = (compare_shared_info_fc)g_dalvik_register_operand_compare_info; operand->compare = (operand_compare_fc)g_dalvik_register_operand_compare; operand->print = (operand_print_fc)g_dalvik_register_operand_print; @@ -275,8 +271,11 @@ GArchOperand *g_dalvik_register_operand_new(const GBinContent *content, vmpa2t * GArchOperand *g_dalvik_register_operand_new_from_existing(GDalvikRegister *reg) { GArchOperand *result; /* Structure à retourner */ + GDalvikRegisterOperand fake; /* Transport d'informations */ + + fake.reg = reg; - result = G_ARCH_OPERAND(g_share_manager_get(_dalvik_register_operand_manager, reg)); + result = G_ARCH_OPERAND(g_share_manager_get(_dalvik_register_operand_manager, (GSharedInstance *)&fake)); return result; @@ -286,7 +285,7 @@ GArchOperand *g_dalvik_register_operand_new_from_existing(GDalvikRegister *reg) /****************************************************************************** * * * Paramètres : operand = objet partagé à initialiser. * -* reg = registre Dalvik à associer à l'opérande. * +* fake = coquille vide contenant les infos à enregistrer. * * * * Description : Initialise un nouvel objet partagé avec des informations. * * * @@ -296,9 +295,9 @@ GArchOperand *g_dalvik_register_operand_new_from_existing(GDalvikRegister *reg) * * ******************************************************************************/ -static bool g_dalvik_register_operand_do_init(GDalvikRegisterOperand *operand, const GDalvikRegister *reg) +static bool g_dalvik_register_operand_do_init(GDalvikRegisterOperand *operand, const GDalvikRegisterOperand *fake) { - operand->reg = reg; + operand->reg = fake->reg; return true; @@ -307,30 +306,6 @@ static bool g_dalvik_register_operand_do_init(GDalvikRegisterOperand *operand, c /****************************************************************************** * * -* Paramètres : operand = objet partagé à consulter. * -* reg = registre Dalvik utilisé comme description. * -* * -* Description : Indique l'objet partagé correspond à une description donnée. * -* * -* Retour : TRUE si les détails centraux sont partagés, FALSE sinon. * -* * -* Remarques : - * -* * -******************************************************************************/ - -static gboolean g_dalvik_register_operand_compare_info(const GDalvikRegisterOperand *operand, const GDalvikRegister *reg) -{ - gboolean result; /* Bilan à retourner */ - - result = g_arch_register_equal(G_ARCH_REGISTER(operand->reg), G_ARCH_REGISTER(reg)); - - return result; - -} - - -/****************************************************************************** -* * * Paramètres : a = premier opérande à consulter. * * b = second opérande à consulter. * * * @@ -342,9 +317,13 @@ static gboolean g_dalvik_register_operand_compare_info(const GDalvikRegisterOper * * ******************************************************************************/ -static bool g_dalvik_register_operand_compare(const GDalvikRegisterOperand *a, const GDalvikRegisterOperand *b) +static int g_dalvik_register_operand_compare(const GDalvikRegisterOperand * const *a, const GDalvikRegisterOperand * const *b) { - return (g_arch_register_compare(G_ARCH_REGISTER(a->reg), G_ARCH_REGISTER(b->reg)) == 0); + int result; /* Bilan à retourner */ + + result = g_dalvik_register_compare(&(*a)->reg, &(*b)->reg); + + return result; } diff --git a/src/arch/dalvik/register.c b/src/arch/dalvik/register.c index d455eb2..d11b4d0 100644 --- a/src/arch/dalvik/register.c +++ b/src/arch/dalvik/register.c @@ -29,6 +29,7 @@ #include "../register-int.h" #include "../sharing/manager.h" +#include "../../common/sort.h" @@ -69,17 +70,11 @@ static void g_dalvik_register_dispose(GDalvikRegister *); static void g_dalvik_register_finalize(GDalvikRegister *); /* Initialise un nouvel objet partagé avec des informations. */ -static bool g_dalvik_register_do_init(GDalvikRegister *, const uint16_t *); - -/* Indique l'objet partagé correspond à une description donnée. */ -static gboolean g_dalvik_register_compare_info(const GDalvikRegister *, const uint16_t *); +static bool g_dalvik_register_do_init(GDalvikRegister *, const GDalvikRegister *); /* Produit une empreinte à partir d'un registre. */ static guint g_dalvik_register_hash(const GDalvikRegister *); -/* Compare un registre avec un autre. */ -static int g_dalvik_register_compare(const GDalvikRegister *, const GDalvikRegister *); - /* Traduit un registre en version humainement lisible. */ static void g_dalvik_register_print(const GDalvikRegister *, GBufferLine *, AsmSyntax); @@ -127,7 +122,6 @@ static void g_dalvik_register_class_init(GDalvikRegisterClass *klass) register_class = G_ARCH_REGISTER_CLASS(klass); register_class->init = (init_shared_fc)g_dalvik_register_do_init; - register_class->cmp_info = (compare_shared_info_fc)g_dalvik_register_compare_info; register_class->hash = (reg_hash_fc)g_dalvik_register_hash; register_class->compare = (reg_compare_fc)g_dalvik_register_compare; @@ -207,8 +201,11 @@ static void g_dalvik_register_finalize(GDalvikRegister *reg) GDalvikRegister *g_dalvik_register_new(uint16_t index) { GDalvikRegister *result; /* Structure à retourner */ + GDalvikRegister fake; /* Transport d'informations */ + + fake.index = index; - result = G_DALVIK_REGISTER(g_share_manager_get(_dalvik_register_manager, &index)); + result = G_DALVIK_REGISTER(g_share_manager_get(_dalvik_register_manager, (GSharedInstance *)&fake)); return result; @@ -217,8 +214,8 @@ GDalvikRegister *g_dalvik_register_new(uint16_t index) /****************************************************************************** * * -* Paramètres : reg = objet partagé à initialiser. * -* index = indice du registre correspondant. * +* Paramètres : reg = objet partagé à initialiser. * +* fake = coquille vide contenant les infos à enregistrer. * * * * Description : Initialise un nouvel objet partagé avec des informations. * * * @@ -228,9 +225,9 @@ GDalvikRegister *g_dalvik_register_new(uint16_t index) * * ******************************************************************************/ -static bool g_dalvik_register_do_init(GDalvikRegister *reg, const uint16_t *index) +static bool g_dalvik_register_do_init(GDalvikRegister *reg, const GDalvikRegister *fake) { - reg->index = *index; + reg->index = fake->index; return true; @@ -239,30 +236,6 @@ static bool g_dalvik_register_do_init(GDalvikRegister *reg, const uint16_t *inde /****************************************************************************** * * -* Paramètres : reg = objet partagé à consulter. * -* index = indice du registre correspondant. * -* * -* Description : Indique l'objet partagé correspond à une description donnée. * -* * -* Retour : TRUE si les détails centraux sont partagés, FALSE sinon. * -* * -* Remarques : - * -* * -******************************************************************************/ - -static gboolean g_dalvik_register_compare_info(const GDalvikRegister *reg, const uint16_t *index) -{ - gboolean result; /* Bilan à retourner */ - - result = (reg->index == *index); - - return result; - -} - - -/****************************************************************************** -* * * Paramètres : reg = opérande à consulter pour le calcul. * * * * Description : Produit une empreinte à partir d'un registre. * @@ -282,37 +255,6 @@ static guint g_dalvik_register_hash(const GDalvikRegister *reg) /****************************************************************************** * * -* Paramètres : a = premier opérande à consulter. * -* b = second opérande à consulter. * -* * -* Description : Compare un registre avec un autre. * -* * -* Retour : Bilan de la comparaison. * -* * -* Remarques : - * -* * -******************************************************************************/ - -static int g_dalvik_register_compare(const GDalvikRegister *a, const GDalvikRegister *b) -{ - int result; /* Bilan à retourner */ - - if (a->index < b->index) - result = -1; - - else if (a->index > b->index) - result = 1; - - else - result = 0; - - return result; - -} - - -/****************************************************************************** -* * * Paramètres : reg = registre à transcrire. * * line = ligne tampon où imprimer l'opérande donné. * * syntax = type de représentation demandée. * @@ -370,6 +312,29 @@ uint16_t g_dalvik_register_get_index(const GDalvikRegister *reg) } +/****************************************************************************** +* * +* Paramètres : a = premier opérande à consulter. * +* b = second opérande à consulter. * +* * +* Description : Compare un registre avec un autre. * +* * +* Retour : Bilan de la comparaison. * +* * +* Remarques : - * +* * +******************************************************************************/ + +int g_dalvik_register_compare(const GDalvikRegister * const *a, const GDalvikRegister * const *b) +{ + int result; /* Bilan à retourner */ + + result = sort_unsigned_long((*a)->index, (*b)->index); + + return result; + +} + /* ---------------------------------------------------------------------------------- */ /* PARTAGES DE CONTENUS UNIQUES */ diff --git a/src/arch/dalvik/register.h b/src/arch/dalvik/register.h index 03faf76..78523f7 100644 --- a/src/arch/dalvik/register.h +++ b/src/arch/dalvik/register.h @@ -61,6 +61,9 @@ GDalvikRegister *g_dalvik_register_new(uint16_t); /* Fournit l'indice d'un registre Dalvik. */ uint16_t g_dalvik_register_get_index(const GDalvikRegister *); +/* Compare un registre avec un autre. */ +int g_dalvik_register_compare(const GDalvikRegister * const *, const GDalvikRegister * const *); + /* -------------------------- PARTAGES DE CONTENUS UNIQUES -------------------------- */ diff --git a/src/arch/operand-int.h b/src/arch/operand-int.h index 3d3ffc9..b2f5eda 100644 --- a/src/arch/operand-int.h +++ b/src/arch/operand-int.h @@ -31,7 +31,7 @@ /* Compare un opérande avec un autre. */ -typedef bool (* operand_compare_fc) (const GArchOperand *, const GArchOperand *); +typedef int (* operand_compare_fc) (const GArchOperand * const *, const GArchOperand * const *); /* Traduit un opérande en version humainement lisible. */ typedef void (* operand_print_fc) (const GArchOperand *, GBufferLine *, AsmSyntax); @@ -57,7 +57,6 @@ struct _GArchOperandClass GObjectClass parent; /* A laisser en premier */ init_shared_fc init; /* Mise en place via interface */ - compare_shared_info_fc cmp_info; /* Comparaison des détails */ operand_compare_fc compare; /* Comparaison d'opérandes */ operand_print_fc print; /* Texte humain équivalent */ diff --git a/src/arch/operand.c b/src/arch/operand.c index ec970ea..1ec4e4f 100644 --- a/src/arch/operand.c +++ b/src/arch/operand.c @@ -24,11 +24,13 @@ #include "operand.h" +#include #include #include #include "operand-int.h" +#include "../common/sort.h" @@ -59,8 +61,8 @@ static void g_arch_operand_inc_references(GArchOperand *); /* Décrémente le compteur de partage. */ static void g_arch_operand_dec_references(GArchOperand *); -/* Indique l'objet partagé correspond à une description donnée. */ -static gboolean g_arch_operand_compare_info(const GArchOperand *, const void *); +/* Compare de façon accélérée un opérande avec un autre. */ +static int g_arch_operand_quickly_compare(const GArchOperand **, const GArchOperand **); /* Indique le type défini pour un opérande d'architecture. */ @@ -131,8 +133,7 @@ static void g_arch_operand_interface_init(GSharedInstanceInterface *iface) iface->inc_ref = (inc_shared_ref_fc)g_arch_operand_inc_references; iface->dec_ref = (dec_shared_ref_fc)g_arch_operand_dec_references; - iface->cmp_info = (compare_shared_info_fc)g_arch_operand_compare_info; - iface->is_equal = (is_shared_equal_fc)g_arch_operand_compare; + iface->qck_cmp = (qck_compare_shared_fc)g_arch_operand_quickly_compare; } @@ -260,22 +261,22 @@ static void g_arch_operand_dec_references(GArchOperand *operand) /****************************************************************************** * * -* Paramètres : operand = objet partagé à consulter. * -* info = compilation de d'information à analyser. * +* Paramètres : a = premier opérande à consulter. * +* b = second opérande à consulter. * * * -* Description : Indique l'objet partagé correspond à une description donnée. * +* Description : Compare de façon accélérée un opérande avec un autre. * * * -* Retour : true si les détails centraux sont partagés, false sinon. * +* Retour : Bilan de la comparaison. * * * * Remarques : - * * * ******************************************************************************/ -static gboolean g_arch_operand_compare_info(const GArchOperand *operand, const void *info) +static int g_arch_operand_quickly_compare(const GArchOperand **a, const GArchOperand **b) { - bool result; /* Bilan à retourner */ + int result; /* Bilan à faire remonter */ - result = G_ARCH_OPERAND_GET_CLASS(operand)->cmp_info(G_SHARED_INSTANCE(operand), info); + result = G_ARCH_OPERAND_GET_CLASS(*a)->compare(a, b); return result; @@ -295,14 +296,21 @@ static gboolean g_arch_operand_compare_info(const GArchOperand *operand, const v * * ******************************************************************************/ -bool g_arch_operand_compare(const GArchOperand *a, const GArchOperand *b) +int g_arch_operand_compare(const GArchOperand * const *a, const GArchOperand * const *b) { - bool result; /* Bilan à faire remonter */ + int result; /* Bilan à faire remonter */ + GType type_a; /* Type de l'object A */ + GType type_b; /* Type de l'object B */ + + type_a = G_OBJECT_TYPE(G_OBJECT(*a)); + type_b = G_OBJECT_TYPE(G_OBJECT(*b)); + + assert(sizeof(GType) <= sizeof(unsigned long)); - result = (G_OBJECT_TYPE(G_OBJECT(a)) == G_OBJECT_TYPE(G_OBJECT(b))); + result = sort_unsigned_long(type_a, type_b); - if (result) - result = G_ARCH_OPERAND_GET_CLASS(a)->compare(a, b); + if (result == 0) + result = G_ARCH_OPERAND_GET_CLASS(*a)->compare(a, b); return result; diff --git a/src/arch/operand.h b/src/arch/operand.h index 237caf3..941b9a9 100644 --- a/src/arch/operand.h +++ b/src/arch/operand.h @@ -51,7 +51,7 @@ typedef struct _GArchOperandClass GArchOperandClass; GType g_arch_operand_get_type(void); /* Compare un opérande avec un autre. */ -bool g_arch_operand_compare(const GArchOperand *, const GArchOperand *); +int g_arch_operand_compare(const GArchOperand * const *, const GArchOperand * const *); /* Définit une autre représentation textuelle pour l'opérande. */ void g_arch_operand_set_alt_text(GArchOperand *, const char *, RenderingTagType); diff --git a/src/arch/register-int.h b/src/arch/register-int.h index 72c1f84..4f85544 100644 --- a/src/arch/register-int.h +++ b/src/arch/register-int.h @@ -40,7 +40,7 @@ typedef guint (* reg_hash_fc) (const GArchRegister *); /* Compare un registre avec un autre. */ -typedef int (* reg_compare_fc) (const GArchRegister *, const GArchRegister *); +typedef int (* reg_compare_fc) (const GArchRegister * const *, const GArchRegister * const *); /* Traduit un registre en version humainement lisible. */ typedef void (* reg_print_fc) (const GArchRegister *, GBufferLine *, AsmSyntax); @@ -69,7 +69,6 @@ struct _GArchRegisterClass GObjectClass parent; /* A laisser en premier */ init_shared_fc init; /* Mise en place via interface */ - compare_shared_info_fc cmp_info; /* Comparaison des détails */ reg_hash_fc hash; /* Production d'empreinte */ reg_compare_fc compare; /* Comparaison de registres */ diff --git a/src/arch/register.c b/src/arch/register.c index ef593b4..87a07b5 100644 --- a/src/arch/register.c +++ b/src/arch/register.c @@ -58,8 +58,8 @@ static void g_arch_register_inc_references(GArchRegister *); /* Décrémente le compteur de partage. */ static void g_arch_register_dec_references(GArchRegister *); -/* Indique l'objet partagé correspond à une description donnée. */ -static gboolean g_arch_register_compare_info(const GArchRegister *, const void *); +/* Compare de façon accélérée un registre avec un autre. */ +static int g_arch_register_quickly_compare(const GArchRegister **, const GArchRegister **); @@ -79,7 +79,7 @@ static void g_register_operand_dispose(GRegisterOperand *); static void g_register_operand_finalize(GRegisterOperand *); /* Compare un opérande avec un autre. */ -static bool g_register_operand_compare(const GRegisterOperand *, const GRegisterOperand *); +static int g_register_operand_compare(const GRegisterOperand **, const GRegisterOperand **); /* Traduit un opérande en version humainement lisible. */ static void g_register_operand_print(const GRegisterOperand *, GBufferLine *, AsmSyntax); @@ -158,8 +158,7 @@ static void g_arch_register_interface_init(GSharedInstanceInterface *iface) iface->inc_ref = (inc_shared_ref_fc)g_arch_register_inc_references; iface->dec_ref = (dec_shared_ref_fc)g_arch_register_dec_references; - iface->cmp_info = (compare_shared_info_fc)g_arch_register_compare_info; - iface->is_equal = (is_shared_equal_fc)g_arch_register_equal; + iface->qck_cmp = (qck_compare_shared_fc)g_arch_register_quickly_compare; } @@ -285,22 +284,22 @@ static void g_arch_register_dec_references(GArchRegister *reg) /****************************************************************************** * * -* Paramètres : reg = objet partagé à consulter. * -* info = compilation de d'information à analyser. * +* Paramètres : a = premier registre à consulter. * +* b = second registre à consulter. * * * -* Description : Indique l'objet partagé correspond à une description donnée. * +* Description : Compare de façon accélérée un registre avec un autre. * * * -* Retour : true si les détails centraux sont partagés, false sinon. * +* Retour : Bilan de la comparaison. * * * * Remarques : - * * * ******************************************************************************/ -static gboolean g_arch_register_compare_info(const GArchRegister *reg, const void *info) +static int g_arch_register_quickly_compare(const GArchRegister **a, const GArchRegister **b) { - bool result; /* Bilan à retourner */ + int result; /* Bilan à faire remonter */ - result = G_ARCH_REGISTER_GET_CLASS(reg)->cmp_info(G_SHARED_INSTANCE(reg), info); + result = G_ARCH_REGISTER_GET_CLASS(*a)->compare(a, b); return result; @@ -339,33 +338,9 @@ guint g_arch_register_hash(const GArchRegister *reg) * * ******************************************************************************/ -int g_arch_register_compare(const GArchRegister *a, const GArchRegister *b) -{ - return G_ARCH_REGISTER_GET_CLASS(a)->compare(a, b); - -} - - -/****************************************************************************** -* * -* Paramètres : a = premier opérande à consulter. * -* b = second opérande à consulter. * -* * -* Description : Détermine si un registre est égal à un autre. * -* * -* Retour : Bilan de la comparaison. * -* * -* Remarques : - * -* * -******************************************************************************/ - -gboolean g_arch_register_equal(const GArchRegister *a, const GArchRegister *b) +int g_arch_register_compare(const GArchRegister * const *a, const GArchRegister * const *b) { - int ret; /* Comparaison détaillée */ - - ret = g_arch_register_compare(a, b); - - return (ret == 0 ? TRUE : FALSE); + return G_ARCH_REGISTER_GET_CLASS(*a)->compare(a, b); } @@ -598,9 +573,14 @@ GArchRegister *g_register_operand_get_register(const GRegisterOperand *operand) * * ******************************************************************************/ -static bool g_register_operand_compare(const GRegisterOperand *a, const GRegisterOperand *b) +static int g_register_operand_compare(const GRegisterOperand **a, const GRegisterOperand **b) { - return (g_arch_register_compare(a->reg, b->reg) == 0); + int result; /* Bilan à retourner */ + + result = g_arch_register_compare((const GArchRegister * const *)&(*a)->reg, + (const GArchRegister * const *)&(*b)->reg); + + return result; } diff --git a/src/arch/register.h b/src/arch/register.h index 8047e8a..e0259e6 100644 --- a/src/arch/register.h +++ b/src/arch/register.h @@ -60,10 +60,7 @@ GType g_arch_register_get_type(void); guint g_arch_register_hash(const GArchRegister *); /* Compare un registre avec un autre. */ -int g_arch_register_compare(const GArchRegister *, const GArchRegister *); - -/* Détermine si un registre est égal à un autre. */ -gboolean g_arch_register_equal(const GArchRegister *, const GArchRegister *); +int g_arch_register_compare(const GArchRegister * const *, const GArchRegister * const *); /* Traduit un registre en version humainement lisible. */ void g_arch_register_print(const GArchRegister *, GBufferLine *, AsmSyntax); diff --git a/src/arch/sharing/instance-int.h b/src/arch/sharing/instance-int.h index 0b57cc4..0117e05 100644 --- a/src/arch/sharing/instance-int.h +++ b/src/arch/sharing/instance-int.h @@ -30,7 +30,7 @@ /* Initialise un nouvel objet partagé avec des informations. */ -typedef bool (* init_shared_fc) (GSharedInstance *, const void *); +typedef bool (* init_shared_fc) (GSharedInstance *, const GSharedInstance *); /* Fournit la valeur du compteur de partage. */ typedef unsigned int (* get_shared_ref_fc) (const GSharedInstance *); @@ -41,11 +41,8 @@ typedef void (* inc_shared_ref_fc) (GSharedInstance *); /* Décrémente le compteur de partage. */ typedef void (* dec_shared_ref_fc) (GSharedInstance *); -/* Indique l'objet partagé correspond à une description donnée. */ -typedef bool (* compare_shared_info_fc) (const GSharedInstance *, const void *); - -/* Détermine si deux instances partagées sont identiques. */ -typedef gboolean (* is_shared_equal_fc) (const GSharedInstance *, const GSharedInstance *); +/* Procède à l'initialisation de l'interface de partage. */ +typedef int (* qck_compare_shared_fc) (const GSharedInstance **, const GSharedInstance **); /* Règles de partage d'une instance GObject (interface) */ @@ -59,8 +56,7 @@ struct _GSharedInstanceIface inc_shared_ref_fc inc_ref; /* Incrémentation du compteur */ dec_shared_ref_fc dec_ref; /* Décrémentation du compteur */ - compare_shared_info_fc cmp_info; /* Comparaison des détails */ - is_shared_equal_fc is_equal; /* Comparaison d'instance */ + qck_compare_shared_fc qck_cmp; /* Comparaison des détails */ }; diff --git a/src/arch/sharing/instance.c b/src/arch/sharing/instance.c index 956a4c7..a4cfcad 100644 --- a/src/arch/sharing/instance.c +++ b/src/arch/sharing/instance.c @@ -61,7 +61,7 @@ static void g_shared_instance_default_init(GSharedInstanceInterface *iface) /****************************************************************************** * * * Paramètres : instance = objet partagé à initialiser. * -* info = information à utiliser pour la mise en place. * +* template = informations à retrouver intégralement. * * * * Description : Initialise un nouvel objet partagé avec des informations. * * * @@ -71,14 +71,14 @@ static void g_shared_instance_default_init(GSharedInstanceInterface *iface) * * ******************************************************************************/ -bool g_shared_instance_init(GSharedInstance *instance, const void *info) +bool g_shared_instance_init(GSharedInstance *instance, const GSharedInstance *template) { bool result; /* Bilan à retourner */ GSharedInstanceIface *iface; /* Interface utilisée */ iface = G_SHARED_INSTANCE_GET_IFACE(instance); - result = iface->init(instance, info); + result = iface->init(instance, template); return result; @@ -156,54 +156,31 @@ void g_shared_instance_dec_references(GSharedInstance *instance) /****************************************************************************** * * -* Paramètres : instance = objet partagé à consulter. * -* info = compilation de d'information à analyser. * -* * -* Description : Indique l'objet partagé correspond à une description donnée. * -* * -* Retour : true si les détails centraux sont partagés, false sinon. * -* * -* Remarques : - * -* * -******************************************************************************/ - -gboolean g_shared_instance_compare_info(const GSharedInstance *instance, const void *info) -{ - bool result; /* Bilan à retourner */ - GSharedInstanceIface *iface; /* Interface utilisée */ - - iface = G_SHARED_INSTANCE_GET_IFACE(instance); - - result = iface->cmp_info(instance, info); - - return result; - -} - - -/****************************************************************************** -* * -* Paramètres : a = première instance d'objet partagé à comparer. * -* b = second instance d'objet partagé à comparer. * +* Paramètres : a = premier objet partagé à consulter. * +* b = second objet partagé à consulter. * * * -* Description : Détermine si deux instances partagées sont identiques. * +* Description : Compare de façon accélérée un object partagé avec un autre. * * * -* Retour : TRUE si les deux éléments partagés sont identiques, ou FALSE.* +* Retour : Bilan de la comparaison. * * * * Remarques : - * * * ******************************************************************************/ -gboolean g_shared_instance_is_equal(const GSharedInstance *a, const GSharedInstance *b) +int g_shared_instance_quickly_compare(const GSharedInstance **a, const GSharedInstance **b) { - gboolean result; /* Bilan à retourner */ + int result; /* Bilan à faire remonter */ GSharedInstanceIface *iface; /* Interface utilisée */ - assert(G_OBJECT_TYPE(a) == G_OBJECT_TYPE(b)); + /** + * Comme les insertions dans les tableaux triés à l'aide de qinsert() + * font passer la clef en premier argument et que celle ci n'est pas un + * objet valide, on inverse les arguments, puis on inverse le résultat obtenu. + */ - iface = G_SHARED_INSTANCE_GET_IFACE(a); + iface = G_SHARED_INSTANCE_GET_IFACE(*b); - result = iface->is_equal(a, b); + result = iface->qck_cmp(b, a) * -1; return result; diff --git a/src/arch/sharing/instance.h b/src/arch/sharing/instance.h index 8cf8385..81c56ef 100644 --- a/src/arch/sharing/instance.h +++ b/src/arch/sharing/instance.h @@ -49,7 +49,7 @@ typedef struct _GSharedInstanceIface GSharedInstanceIface; GType g_shared_instance_get_type(void) G_GNUC_CONST; /* Initialise un nouvel objet partagé avec des informations. */ -bool g_shared_instance_init(GSharedInstance *, const void *); +bool g_shared_instance_init(GSharedInstance *, const GSharedInstance *); /* Fournit la valeur du compteur de partage. */ unsigned int g_shared_instance_get_references(const GSharedInstance *); @@ -60,11 +60,8 @@ void g_shared_instance_inc_references(GSharedInstance *); /* Décrémente le compteur de partage. */ void g_shared_instance_dec_references(GSharedInstance *); -/* Indique l'objet partagé correspond à une description donnée. */ -gboolean g_shared_instance_compare_info(const GSharedInstance *, const void *); - -/* Détermine si deux instances partagées sont identiques. */ -gboolean g_shared_instance_is_equal(const GSharedInstance *, const GSharedInstance *); +/* Compare de façon accélérée un object partagé avec un autre. */ +int g_shared_instance_quickly_compare(const GSharedInstance **, const GSharedInstance **); diff --git a/src/arch/sharing/manager.c b/src/arch/sharing/manager.c index 2e92766..4c60e72 100644 --- a/src/arch/sharing/manager.c +++ b/src/arch/sharing/manager.c @@ -25,9 +25,14 @@ #include +#include #ifdef DEBUG_DUMP_STATS # include #endif +#include + + +#include "../../common/sort.h" @@ -36,7 +41,8 @@ struct _GShareManager { GObject parent; /* A laisser en premier */ - GHashTable *table; /* Collection de partages */ + GSharedInstance **instances; /* Instances partagées */ + size_t count; /* Quantité de ces instances */ GMutex access; /* Accès à la table */ GType managed; /* Type d'instances gérées */ @@ -107,6 +113,9 @@ static void g_share_manager_class_init(GShareManagerClass *class) static void g_share_manager_init(GShareManager *manager) { + manager->instances = NULL; + manager->count = 0; + g_mutex_init(&manager->access); } @@ -126,7 +135,11 @@ static void g_share_manager_init(GShareManager *manager) static void g_share_manager_dispose(GShareManager *manager) { - g_hash_table_unref(manager->table); + size_t i; /* Boucle de parcours */ + + for (i = 0; i < manager->count; i++) + g_object_unref(G_OBJECT(manager->instances[i])); + g_mutex_clear(&manager->access); G_OBJECT_CLASS(g_share_manager_parent_class)->dispose(G_OBJECT(manager)); @@ -148,6 +161,9 @@ static void g_share_manager_dispose(GShareManager *manager) static void g_share_manager_finalize(GShareManager *manager) { + if (manager->instances != NULL) + free(manager->instances); + G_OBJECT_CLASS(g_share_manager_parent_class)->finalize(G_OBJECT(manager)); } @@ -171,11 +187,6 @@ GShareManager *g_share_manager_new(GType type) result = g_object_new(G_TYPE_SHARE_MANAGER, NULL); - result->table = g_hash_table_new_full((GHashFunc)g_direct_hash, - (GEqualFunc)g_shared_instance_is_equal, - (GDestroyNotify)g_object_unref, - (GDestroyNotify)NULL); - result->managed = type; return result; @@ -185,8 +196,8 @@ GShareManager *g_share_manager_new(GType type) /****************************************************************************** * * -* Paramètres : manager = gestionnaire d'instance à consulter. * -* info = informations à retrouver intégralement. * +* Paramètres : manager = gestionnaire d'instance à consulter. * +* template = informations à retrouver intégralement. * * * * Description : Retrouve ou crée une instance partagée. * * * @@ -196,29 +207,23 @@ GShareManager *g_share_manager_new(GType type) * * ******************************************************************************/ -GSharedInstance *g_share_manager_get(GShareManager *manager, const void *info) +GSharedInstance *g_share_manager_get(GShareManager *manager, GSharedInstance *template) { GSharedInstance *result; /* Trouvaille à retourner */ - gpointer found; /* Elément correspondant ? */ + size_t index; /* Indice d'une instance idéale*/ + bool found; /* Existence de cette instance */ bool status; /* Conclusion d'initialisation */ -#ifndef NDEBUG - gboolean new; /* Présence de partage existant*/ -#endif - - gboolean find_shared_matching_info(const GSharedInstance *key, gpointer unused, const void *nfo) - { - return g_shared_instance_compare_info(key, nfo); - } g_mutex_lock(&manager->access); - found = g_hash_table_find(manager->table, (GHRFunc)find_shared_matching_info, (void *)info); + found = bsearch_index(&template, manager->instances, manager->count, sizeof(GSharedInstance *), + (__compar_fn_t)g_shared_instance_quickly_compare, &index); - if (found == NULL) + if (!found) { result = g_object_new(manager->managed, NULL); - status = g_shared_instance_init(result, info); + status = g_shared_instance_init(result, template); if (!status) { @@ -230,19 +235,15 @@ GSharedInstance *g_share_manager_get(GShareManager *manager, const void *info) { g_shared_instance_inc_references(result); -#ifndef NDEBUG - new = g_hash_table_add(manager->table, result); - assert(new); -#else - g_hash_table_add(manager->table, result); -#endif + manager->instances = (GSharedInstance **)_qinsert(manager->instances, &manager->count, + sizeof(GSharedInstance *), &result, index); } } else - result = G_SHARED_INSTANCE(found); + result = manager->instances[index]; if (result != NULL) { @@ -261,7 +262,7 @@ GSharedInstance *g_share_manager_get(GShareManager *manager, const void *info) * * * Paramètres : manager = gestionnaire d'instance à consulter. * * old = ancienne instance partagée à faire évoluer. * -* info = informations à retrouver intégralement. * +* template = informations à retrouver intégralement. * * container = propriétaire de l'ancienne version à contacter. * * * * Description : Met à jour une instance partagée. * @@ -272,11 +273,11 @@ GSharedInstance *g_share_manager_get(GShareManager *manager, const void *info) * * ******************************************************************************/ -GSharedInstance *g_share_manager_update(GShareManager *manager, GSharedInstance *old, const void *info, GShareContainer *container) +GSharedInstance *g_share_manager_update(GShareManager *manager, GSharedInstance *old, GSharedInstance *template, GShareContainer *container) { GSharedInstance *result; /* Nouvelle instance à renvoyer*/ - result = g_share_manager_get(manager, info); + result = g_share_manager_get(manager, template); if (container != NULL) g_share_container_replace(container, old, result); @@ -303,22 +304,19 @@ GSharedInstance *g_share_manager_update(GShareManager *manager, GSharedInstance void g_share_manager_put(GShareManager *manager, GSharedInstance *shared) { -#ifndef NDEBUG - gboolean found; /* Présence de partage existant*/ -#endif - g_mutex_lock(&manager->access); g_shared_instance_dec_references(shared); if (g_shared_instance_get_references(shared) == 1) { -#ifndef NDEBUG - found = g_hash_table_remove(manager->table, shared); - assert(found); -#else - g_hash_table_remove(manager->table, shared); -#endif + g_object_unref(G_OBJECT(shared)); + + manager->instances = (GSharedInstance **)qdelete(manager->instances, &manager->count, + sizeof(GSharedInstance *), + (__compar_fn_t)g_shared_instance_quickly_compare, + &shared); + } g_mutex_unlock(&manager->access); @@ -341,32 +339,26 @@ void g_share_manager_put(GShareManager *manager, GSharedInstance *shared) void g_share_manager_dump_stats(GShareManager *manager) { unsigned int counter; /* Quantité nécessaire */ + size_t i; /* Boucle de parcours */ GTypeQuery query; /* Informations sur un type */ - guint size; /* Taille de la table */ - - void count_shared_instances(const GSharedInstance *key, gpointer unused, unsigned int *c) - { - *c += g_shared_instance_get_references(key); - } counter = 0; g_mutex_lock(&manager->access); - g_hash_table_foreach(manager->table, (GHFunc)count_shared_instances, &counter); - - size = g_hash_table_size(manager->table); + for (i = 0; i < manager->count; i++) + counter += g_shared_instance_get_references(manager->instances[i]); g_mutex_unlock(&manager->access); g_type_query(manager->managed, &query); - printf("%s: current = %u / %u - needed = %u / %u (size=%u, saved=%u)\n", + printf("%s: current = %zu / %zu - needed = %u / %u (size=%u, saved=%zu)\n", query.type_name, - size, size * query.instance_size, + manager->count, manager->count * query.instance_size, counter, counter * query.instance_size, query.instance_size, - (counter - size) * query.instance_size); + (counter - manager->count) * query.instance_size); } #endif diff --git a/src/arch/sharing/manager.h b/src/arch/sharing/manager.h index 0a44214..2748134 100644 --- a/src/arch/sharing/manager.h +++ b/src/arch/sharing/manager.h @@ -60,10 +60,10 @@ GType g_share_manager_get_type(void); GShareManager *g_share_manager_new(GType); /* Retrouve ou crée une instance partagée. */ -GSharedInstance *g_share_manager_get(GShareManager *, const void *); +GSharedInstance *g_share_manager_get(GShareManager *, GSharedInstance *); /* Met à jour une instance partagée. */ -GSharedInstance *g_share_manager_update(GShareManager *, GSharedInstance *, const void *, GShareContainer *); +GSharedInstance *g_share_manager_update(GShareManager *, GSharedInstance *, GSharedInstance *, GShareContainer *); /* Abandonne un usage d'une instance partagée. */ void g_share_manager_put(GShareManager *, GSharedInstance *); diff --git a/src/common/sort.c b/src/common/sort.c index 8d2ebbf..b65d175 100644 --- a/src/common/sort.c +++ b/src/common/sort.c @@ -24,6 +24,7 @@ #include "sort.h" +#include #include #include @@ -31,6 +32,37 @@ /****************************************************************************** * * +* Paramètres : a = premier élément à consulter et comparer. * +* b = second élément à consulter et comparer. * +* * +* Description : Compare une valeur avec une autre. * +* * +* Retour : Bilan de la comparaison. * +* * +* Remarques : - * +* * +******************************************************************************/ + +int sort_unsigned_long(unsigned long a, unsigned long b) +{ + int result; /* Bilan à renvoyer */ + + if (a < b) + result = -1; + + else if (a > b) + result = 1; + + else + result = 0; + + return result; + +} + + +/****************************************************************************** +* * * Paramètres : key = élément de comparaison à retrouver ou approcher. * * base = adresse du tableau à parcourir. * * nmemb = nombre d'éléments présents au total. * @@ -104,6 +136,40 @@ bool bsearch_index(const void *key, const void *base, size_t nmemb, size_t size, /****************************************************************************** * * +* Paramètres : base = adresse du tableau à parcourir. * +* nmemb = nombre d'éléments présents au total. [OUT] * +* size = taille de chaque élément du tableau. * +* new = nouvel élément à insérer. * +* index = indice du point d'insertion. * +* * +* Description : Ajoute à l'endroit indiqué un élément dans un tableau. * +* * +* Retour : Nouvel emplacement du tableau agrandi. * +* * +* Remarques : - * +* * +******************************************************************************/ + +void *_qinsert(void *base, size_t *nmemb, size_t size, void *new, size_t index) +{ + void *result; /* Tableau trié à retourner */ + + result = realloc(base, (*nmemb + 1) * size); + + if (index < *nmemb) + memmove((char *)result + (index + 1) * size, (char *)result + index * size, (*nmemb - index) * size); + + (*nmemb)++; + + memcpy((char *)result + index * size, new, size); + + return result; + +} + + +/****************************************************************************** +* * * Paramètres : base = adresse du tableau à parcourir. * * nmemb = nombre d'éléments présents au total. [OUT] * * size = taille de chaque élément du tableau. * @@ -121,18 +187,62 @@ bool bsearch_index(const void *key, const void *base, size_t nmemb, size_t size, void *qinsert(void *base, size_t *nmemb, size_t size, __compar_fn_t compar, void *new) { void *result; /* Tableau trié à retourner */ +#ifndef NDEBUG + bool found; /* Présence de partage existant*/ +#endif size_t index; /* Indice du point d'insertion */ +#ifndef NDEBUG + found = bsearch_index(new, base, *nmemb, size, compar, &index); + //assert(!found); FIXME (symboles) +#else bsearch_index(new, base, *nmemb, size, compar, &index); +#endif - result = realloc(base, (*nmemb + 1) * size); + result = _qinsert(base, nmemb, size, new, index); - if (index < *nmemb) - memmove((char *)result + (index + 1) * size, (char *)result + index * size, (*nmemb - index) * size); + return result; - (*nmemb)++; +} - memcpy((char *)result + index * size, new, size); + +/****************************************************************************** +* * +* Paramètres : base = adresse du tableau à parcourir. * +* nmemb = nombre d'éléments présents au total. [OUT] * +* size = taille de chaque élément du tableau. * +* compar = méthode de comparaison entre éléments. * +* target = élément en place à retirer. * +* * +* Description : Supprime un élément dans un tableau trié. * +* * +* Retour : Nouvel emplacement du tableau rétréci. * +* * +* Remarques : - * +* * +******************************************************************************/ + +void *qdelete(void *base, size_t *nmemb, size_t size, __compar_fn_t compar, void *target) +{ + void *result; /* Tableau trié à retourner */ +#ifndef NDEBUG + bool found; /* Présence de partage existant*/ +#endif + size_t index; /* Indice du point d'insertion */ + +#ifndef NDEBUG + found = bsearch_index(target, base, *nmemb, size, compar, &index); + assert(found); +#else + bsearch_index(target, base, *nmemb, size, compar, &index); +#endif + + if ((index + 1) < *nmemb) + memmove((char *)base + index * size, (char *)base + (index + 1) * size, (*nmemb - index - 1) * size); + + (*nmemb)--; + + result = realloc(base, *nmemb * size); return result; diff --git a/src/common/sort.h b/src/common/sort.h index 5b274b4..afae2b3 100644 --- a/src/common/sort.h +++ b/src/common/sort.h @@ -30,12 +30,21 @@ +/* Compare une valeur avec une autre. */ +int sort_unsigned_long(unsigned long, unsigned long); + /* Effectue une recherche dichotomique dans un tableau. */ bool bsearch_index(const void *, const void *, size_t, size_t, __compar_fn_t, size_t *); +/* Ajoute à l'endroit indiqué un élément dans un tableau. */ +void *_qinsert(void *, size_t *, size_t, void *, size_t); + /* Ajoute au bon endroit un élément dans un tableau trié. */ void *qinsert(void *, size_t *, size_t, __compar_fn_t, void *); +/* Supprime un élément dans un tableau trié. */ +void *qdelete(void *, size_t *, size_t, __compar_fn_t, void *); + #endif /* _COMMON_SORT_H */ -- cgit v0.11.2-87-g4458