Used a fast sorted array to track shared instances instead of a simple hash table.

2 files changed, 124 insertions, 5 deletions

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 <assert.h>
 #include <malloc.h>
 #include <string.h>
 
@@ -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 */