Use a global allocator to store (partial) matches.

2 files changed, 91 insertions, 0 deletions

diff --git a/src/common/sort.c b/src/common/sort.c
index fe5bd38..d79d71a 100644
--- a/src/common/sort.c
+++ b/src/common/sort.c
@@ -432,6 +432,91 @@ void *qinsert_multi(void *base, size_t *nmemb, size_t size, __compar_fn_t compar
 
 /******************************************************************************
 *                                                                             *
+*  Paramètres  : base      = adresse du tableau à parcourir.                  *
+*                nmemb     = nombre d'éléments présents au total. [OUT]       *
+*                allocated = taille déjà allouée pour le tableau. [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_managed(void *base, size_t *nmemb, size_t *allocated, size_t size, void *new, size_t index)
+{
+    void *result;                           /* Tableau trié à retourner    */
+
+    if (*nmemb == *allocated)
+    {
+        if (*allocated == 0)
+            *allocated = 1024 * 8;
+        else
+            *allocated *= 2;
+
+        result = realloc(base, *allocated * size);
+
+    }
+    else
+        result = base;
+
+    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]       *
+*                allocated = taille déjà allouée pour le tableau. [OUT]       *
+*                size      = taille de chaque élément du tableau.             *
+*                compar    = méthode de comparaison entre éléments.           *
+*                new       = nouvel élément à insérer.                        *
+*                                                                             *
+*  Description : Ajoute au bon endroit un élément dans un tableau trié.       *
+*                                                                             *
+*  Retour      : Nouvel emplacement du tableau agrandi.                       *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+void *qinsert_managed(void *base, size_t *nmemb, size_t *allocated, 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);
+#else
+    bsearch_index(new, base, *nmemb, size, compar, &index);
+#endif
+
+    result = _qinsert_managed(base, nmemb, allocated, size, new, index);
+
+    return result;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
 *  Paramètres  : base  = adresse du tableau à parcourir.                      *
 *                nmem  = nombre d'éléments présents au total. [OUT]           *
 *                size  = taille de chaque élément du tableau.                 *
diff --git a/src/common/sort.h b/src/common/sort.h
index 4b2ae94..39a6f33 100644
--- a/src/common/sort.h
+++ b/src/common/sort.h
@@ -64,6 +64,12 @@ void *qinsert(void *, size_t *, size_t, __compar_fn_t, void *);
 /* Ajoute au bon endroit un élément dans un tableau trié. */
 void *qinsert_multi(void *, size_t *, size_t, __compar_fn_t, void *);
 
+/* Ajoute à l'endroit indiqué un élément dans un tableau. */
+void *_qinsert_managed(void *, size_t *, size_t *, size_t, void *, size_t);
+
+/* Ajoute au bon endroit un élément dans un tableau trié. */
+void *qinsert_managed(void *, size_t *, size_t *, size_t, __compar_fn_t, void *);
+
 /* Supprime un élément dans un tableau trié. */
 void *_qdelete(void *, size_t *, size_t, size_t);