Inserted symbols and routines using an optimized 100 times faster method.

3 files changed, 181 insertions, 0 deletions

diff --git a/src/common/Makefile.am b/src/common/Makefile.am
index 4c9c2a1..9e9969d 100755
--- a/src/common/Makefile.am
+++ b/src/common/Makefile.am
@@ -16,6 +16,7 @@ libcommon_la_SOURCES =					\
 	macros.h							\
 	net.h net.c							\
 	pathname.h pathname.c				\
+	sort.h sort.c						\
 	sqlite.h sqlite.c					\
 	xdg.h xdg.c							\
 	xml.h xml.c
diff --git a/src/common/sort.c b/src/common/sort.c
new file mode 100644
index 0000000..df1df82
--- /dev/null
+++ b/src/common/sort.c
@@ -0,0 +1,139 @@
+
+/* Chrysalide - Outil d'analyse de fichiers binaires
+ * sort.c - opérations sur des tableaux triés
+ *
+ * Copyright (C) 2016 Cyrille Bagard
+ *
+ *  This file is part of Chrysalide.
+ *
+ *  OpenIDA is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 3 of the License, or
+ *  (at your option) any later version.
+ *
+ *  OpenIDA is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with Foobar.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+
+#include "sort.h"
+
+
+#include <malloc.h>
+#include <string.h>
+
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : key    = élément de comparaison à retrouver ou approcher.    *
+*                base   = adresse du tableau à parcourir.                     *
+*                nmemb  = nombre d'éléments présents au total.                *
+*                size   = taille de chaque élément du tableau.                *
+*                compar = méthode de comparaison entre éléments.              *
+*                index  = indice de cellule d'insertion.                      *
+*                                                                             *
+*  Description : Effectue une recherche dichotomique dans un tableau.         *
+*                                                                             *
+*  Retour      : true si l'élément visé à été trouvé, false sinon.            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+bool bsearch_index(const void *key, const void *base, size_t nmemb, size_t size, __compar_fn_t compar, size_t *index)
+{
+    bool result;                            /* Bilan à faire remonter      */
+    size_t lower;                           /* Borne inférieure de fenêtre */
+    size_t upper;                           /* Borne supérieure qde fenêtre*/
+    size_t idx;                             /* Indice de cellule analysée  */
+    const void *cell;                       /* Cellule en question         */
+    int status;                             /* Bilan d'une comparaison     */
+
+    if (nmemb == 0)
+    {
+        *index = 0;
+        return false;
+    }
+
+    /* Parcours minimal */
+
+    lower = 0;
+    upper = nmemb;
+
+    while (lower < upper)
+    {
+        idx = (lower + upper) / 2;
+        cell = (void *)(((const char *)base) + (idx * size));
+
+        status = (*compar)(key, cell);
+
+        if (status < 0)
+            upper = idx;
+
+        else if (status > 0)
+            lower = idx + 1;
+
+        else
+            break;
+
+    }
+
+    /* Bilan des recherches */
+
+    result = (status == 0);
+
+    if (status < 0)
+        *index = idx;
+
+    else if (status > 0)
+        *index = idx + 1;
+
+    else
+        *index = idx;
+
+    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.                *
+*                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(void *base, size_t *nmemb, size_t size, __compar_fn_t compar, void *new)
+{
+    void *result;                           /* Tableau trié à retourner    */
+    size_t index;                           /* Indice du point d'insertion */
+
+    bsearch_index(&new, base, *nmemb, size, compar, &index);
+
+    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;
+
+}
diff --git a/src/common/sort.h b/src/common/sort.h
new file mode 100644
index 0000000..4f41313
--- /dev/null
+++ b/src/common/sort.h
@@ -0,0 +1,41 @@
+
+/* Chrysalide - Outil d'analyse de fichiers binaires
+ * sort.h - prototypes pour les opérations sur des tableaux triés
+ *
+ * Copyright (C) 2016 Cyrille Bagard
+ *
+ *  This file is part of Chrysalide.
+ *
+ *  OpenIDA is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 3 of the License, or
+ *  (at your option) any later version.
+ *
+ *  OpenIDA is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with Foobar.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+
+#ifndef _COMMON_SORT_H
+#define _COMMON_SORT_H
+
+
+#include <stdbool.h>
+#include <stdlib.h>
+
+
+
+/* Effectue une recherche dichotomique dans un tableau. */
+bool bsearch_index(const void *, const void *, size_t, size_t, __compar_fn_t, size_t *);
+
+/* Ajoute au bon endroit un élément dans un tableau trié. */
+void *qinsert(void *, size_t *, size_t, __compar_fn_t, void *);
+
+
+
+#endif  /* _COMMON_SORT_H */