diff options
Diffstat (limited to 'src/common')
| -rwxr-xr-x | src/common/Makefile.am | 1 | ||||
| -rw-r--r-- | src/common/sort.c | 139 | ||||
| -rw-r--r-- | src/common/sort.h | 41 |
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 */ |