diff options
Diffstat (limited to 'src/common')
| -rw-r--r-- | src/common/sort.c | 120 | ||||
| -rw-r--r-- | src/common/sort.h | 9 |
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 */ |