summaryrefslogtreecommitdiff
path: root/src/common
diff options
context:
space:
mode:
Diffstat (limited to 'src/common')
-rwxr-xr-xsrc/common/Makefile.am1
-rw-r--r--src/common/sort.c139
-rw-r--r--src/common/sort.h41
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 */