summaryrefslogtreecommitdiff
path: root/src/common
diff options
context:
space:
mode:
Diffstat (limited to 'src/common')
-rw-r--r--src/common/sort.c120
-rw-r--r--src/common/sort.h9
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 */