summaryrefslogtreecommitdiff
path: root/src/common
diff options
context:
space:
mode:
Diffstat (limited to 'src/common')
-rw-r--r--src/common/bits.c414
-rw-r--r--src/common/bits.h19
-rw-r--r--src/common/dllist.c195
-rw-r--r--src/common/dllist.h34
-rw-r--r--src/common/sort.c85
-rw-r--r--src/common/sort.h6
-rw-r--r--src/common/szstr.h5
7 files changed, 727 insertions, 31 deletions
diff --git a/src/common/bits.c b/src/common/bits.c
index a037078..3d0004c 100644
--- a/src/common/bits.c
+++ b/src/common/bits.c
@@ -38,7 +38,9 @@
struct _bitfield_t
{
size_t length; /* Nombre de bits représentés */
- size_t requested; /* Nombre de mots alloués */
+
+ size_t allocated_words; /* Nombre de mots alloués */
+ size_t used_words; /* Nombre de mots utilisés */
bool default_state; /* Etat d'initialisation */
@@ -47,6 +49,10 @@ struct _bitfield_t
};
+/* Taille des mots intégrés */
+#define BF_WORD_SIZE (sizeof(unsigned long) * 8)
+
+
/* Crée un champ de bits initialisé à zéro. */
static bitfield_t *_create_bit_field(size_t);
@@ -73,18 +79,20 @@ static bool test_state_within_bit_field(const bitfield_t *, size_t, const bitfie
static bitfield_t *_create_bit_field(size_t length)
{
bitfield_t *result; /* Création à retourner */
- size_t requested; /* Nombre de mots à allouer */
+ size_t needed; /* Nombre de mots à allouer */
size_t base; /* Allocation de base en octets*/
- requested = length / (sizeof(unsigned long) * 8);
- if (length % (sizeof(unsigned long) * 8) != 0) requested++;
+ needed = length / (sizeof(unsigned long) * 8);
+ if (length % (sizeof(unsigned long) * 8) != 0) needed++;
- base = sizeof(bitfield_t) + requested * sizeof(unsigned long);
+ base = sizeof(bitfield_t) + needed * sizeof(unsigned long);
result = (bitfield_t *)malloc(base);
result->length = length;
- result->requested = requested;
+
+ result->allocated_words = needed;
+ result->used_words = needed;
return result;
@@ -140,7 +148,7 @@ bitfield_t *dup_bit_field(const bitfield_t *field)
result = _create_bit_field(field->length);
- memcpy(result->bits, field->bits, result->requested * sizeof(unsigned long));
+ memcpy(result->bits, field->bits, result->used_words * sizeof(unsigned long));
return result;
@@ -183,7 +191,45 @@ void copy_bit_field(bitfield_t *dest, const bitfield_t *src)
{
assert(dest->length == src->length);
- memcpy(dest->bits, src->bits, dest->requested * sizeof(unsigned long));
+ memcpy(dest->bits, src->bits, dest->used_words * sizeof(unsigned long));
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : field = champ de bits à modifier. [OUT] *
+* length = nouveau nombre de bits du champ à représenter. *
+* *
+* Description : Réduit ou étend la taille d'un champ en évitant l'allocation.*
+* *
+* Retour : - *
+* *
+* Remarques : Les éventuels bits supplémentaires ou disparus ne sont pas *
+* (ré)initialisés. *
+* *
+******************************************************************************/
+
+void truncate_bit_field(bitfield_t **field, size_t length)
+{
+ bitfield_t *_field; /* Commodité d'accès */
+ size_t needed; /* Nombre de mots à allouer */
+
+ _field = *field;
+
+ needed = length / (sizeof(unsigned long) * 8);
+ if (length % (sizeof(unsigned long) * 8) != 0) needed++;
+
+ if (needed <= _field->allocated_words)
+ {
+ _field->length = length;
+
+ _field->used_words = needed;
+
+ }
+
+ else
+ resize_bit_field(field, length);
}
@@ -204,7 +250,7 @@ void copy_bit_field(bitfield_t *dest, const bitfield_t *src)
void resize_bit_field(bitfield_t **field, size_t length)
{
bitfield_t *_field; /* Commodité d'accès */
- size_t requested; /* Nombre de mots à allouer */
+ size_t needed; /* Nombre de mots à allouer */
size_t base; /* Allocation de base en octets*/
size_t remaining; /* Nombre de derniers bits */
size_t last; /* Dernier mot utilisé */
@@ -217,18 +263,18 @@ void resize_bit_field(bitfield_t **field, size_t length)
{
/* Redimensionnement */
- requested = length / (sizeof(unsigned long) * 8);
- if (length % (sizeof(unsigned long) * 8) != 0) requested++;
-
- base = sizeof(bitfield_t) + requested * sizeof(unsigned long);
+ needed = length / (sizeof(unsigned long) * 8);
+ if (length % (sizeof(unsigned long) * 8) != 0) needed++;
- *field = realloc(_field, base);
- _field = *field;
+ base = sizeof(bitfield_t) + needed * sizeof(unsigned long);
/* Initialisation, si nécessaire */
if (_field->length < length)
{
+ *field = realloc(_field, base);
+ _field = *field;
+
last = _field->length / (sizeof(unsigned long) * 8);
remaining = _field->length % (sizeof(unsigned long) * 8);
@@ -245,7 +291,7 @@ void resize_bit_field(bitfield_t **field, size_t length)
}
- for (i = last; i < requested; i++)
+ for (i = last; i < needed; i++)
{
if (_field->default_state)
_field->bits[i] = ~0ul;
@@ -258,7 +304,9 @@ void resize_bit_field(bitfield_t **field, size_t length)
/* Actualisation des tailles */
_field->length = length;
- _field->requested = requested;
+
+ _field->allocated_words = needed;
+ _field->used_words = needed;
}
@@ -326,12 +374,12 @@ int compare_bit_fields(const bitfield_t *a, const bitfield_t *b)
else
final = (1 << final) - 1;
- for (i = 0; i < a->requested && result == 0; i++)
+ for (i = 0; i < a->used_words && result == 0; i++)
{
val_a = a->bits[i];
val_b = b->bits[i];
- if ((i + 1) == a->requested)
+ if ((i + 1) == a->used_words)
{
val_a &= final;
val_b &= final;
@@ -366,7 +414,7 @@ int compare_bit_fields(const bitfield_t *a, const bitfield_t *b)
void reset_all_in_bit_field(bitfield_t *field)
{
- memset(field->bits, 0u, field->requested * sizeof(unsigned long));
+ memset(field->bits, 0u, field->used_words * sizeof(unsigned long));
}
@@ -385,7 +433,7 @@ void reset_all_in_bit_field(bitfield_t *field)
void set_all_in_bit_field(bitfield_t *field)
{
- memset(field->bits, ~0u, field->requested * sizeof(unsigned long));
+ memset(field->bits, ~0u, field->used_words * sizeof(unsigned long));
}
@@ -483,7 +531,7 @@ void and_bit_field(bitfield_t *dest, const bitfield_t *src)
assert(dest->length == src->length);
- for (i = 0; i < dest->requested; i++)
+ for (i = 0; i < dest->used_words; i++)
dest->bits[i] &= src->bits[i];
}
@@ -508,7 +556,7 @@ void or_bit_field(bitfield_t *dest, const bitfield_t *src)
assert(dest->length == src->length);
- for (i = 0; i < dest->requested; i++)
+ for (i = 0; i < dest->used_words; i++)
dest->bits[i] |= src->bits[i];
}
@@ -545,14 +593,13 @@ void or_bit_field_at(bitfield_t *dest, const bitfield_t *src, size_t first)
remaining = (first + src->length) % (sizeof(unsigned long) * 8);
if ((first + src->length) % (sizeof(unsigned long) * 8) > 0)
- last_iter = src->requested;
+ last_iter = src->used_words;
else
- last_iter = src->requested - 1;
-
+ last_iter = src->used_words - 1;
for (i = 0; i <= last_iter; i++)
{
- if (i < src->requested)
+ if (i < src->used_words)
word = src->bits[i] << offset;
else
word = 0;
@@ -603,6 +650,42 @@ bool test_in_bit_field(const bitfield_t *field, size_t n)
/******************************************************************************
* *
+* Paramètres : field = champ de bits à consulter. *
+* n = indice du bit à traiter. *
+* *
+* Description : Détermine si un bit est à 1 dans un champ puis le définit. *
+* *
+* Retour : true si le bit correspondant était déjà à l'état haut. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+bool test_and_set_in_bit_field(bitfield_t *field, size_t n)
+{
+ bool result; /* Valeur retrouvée à renvoyer */
+ size_t index; /* Cellule de tableau visée */
+ size_t remaining; /* Nombre de bits restants */
+ unsigned long *bits; /* Accès mis en commun */
+
+ assert(n < field->length);
+
+ index = n / (sizeof(unsigned long) * 8);
+ remaining = n % (sizeof(unsigned long) * 8);
+
+ bits = field->bits + index;
+
+ result = *bits & (1ul << remaining);
+
+ *bits |= (1ul << remaining);
+
+ return result;
+
+}
+
+
+/******************************************************************************
+* *
* Paramètres : field = champ de bits à modifier. *
* first = indice du premier bit à traiter. *
* count = nombre de bits à marquer. *
@@ -736,7 +819,7 @@ static bool test_state_within_bit_field(const bitfield_t *field, size_t first, c
else
finalcut = (1lu << remaining) - 1;
- for (i = 0; i < mask->requested && result; i++)
+ for (i = 0; i < mask->used_words && result; i++)
{
windex = start + i;
@@ -746,7 +829,7 @@ static bool test_state_within_bit_field(const bitfield_t *field, size_t first, c
else
{
word = field->bits[windex] >> offset;
- if ((windex + 1) < field->requested)
+ if ((windex + 1) < field->used_words)
word |= field->bits[windex + 1] << (sizeof(unsigned long) * 8 - offset);
}
@@ -756,7 +839,7 @@ static bool test_state_within_bit_field(const bitfield_t *field, size_t first, c
test &= bitmask;
- if ((i + 1) == mask->requested)
+ if ((i + 1) == mask->used_words)
{
bitmask &= finalcut;
test &= finalcut;
@@ -824,6 +907,223 @@ bool test_ones_within_bit_field(const bitfield_t *field, size_t first, const bit
/******************************************************************************
* *
* Paramètres : field = champ de bits à consulter. *
+* prev = indice rapporté avec une itération précédente. *
+* *
+* Description : Recherche un prochain bit défini dans un champ de bits. *
+* *
+* Retour : Position d'un bit à 1 ou taille du champ si plus aucun. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+size_t find_next_set_in_bit_field(const bitfield_t *field, const size_t *prev)
+{
+ size_t result; /* Indice à retourner */
+ size_t i; /* Boucle de parcours */
+ unsigned long word; /* Espace de travail courant */
+ size_t last_pos; /* Position précédente locale */
+ int found; /* Bian de recherche locale */
+
+ /* Travaux sur le premier mot, nécessitant potentiellement un masque */
+
+ if (prev == NULL)
+ {
+ i = 0;
+ word = field->bits[0];
+ }
+ else
+ {
+ i = *prev / BF_WORD_SIZE;
+
+ if (i >= field->used_words)
+ {
+ result = field->length;
+ goto nothing_to_do;
+ }
+
+ word = field->bits[i];
+
+ last_pos = *prev % BF_WORD_SIZE;
+
+ if ((last_pos + 1) == BF_WORD_SIZE)
+ goto next_word;
+
+ word &= ~((1lu << (last_pos + 1)) - 1);
+
+ }
+
+ found = __builtin_ffsl(word);
+
+ if (found > 0)
+ {
+ result = i * BF_WORD_SIZE + found - 1;
+ goto done;
+ }
+
+ /* Extension aux autres mots suivantes au besoin */
+
+ next_word:
+
+ result = field->length;
+
+ for (i++; i < field->used_words; i++)
+ {
+ found = __builtin_ffsl(field->bits[i]);
+
+ if (found > 0)
+ {
+ result = i * BF_WORD_SIZE + found - 1;
+
+ /**
+ * Validation des bornes finales, pour le dernier mot.
+ */
+ if (result > field->length)
+ result = field->length;
+
+ goto done;
+
+ }
+
+ }
+
+ /* Sortie */
+
+ done:
+
+ nothing_to_do:
+
+ return result;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : field = champ de bits à consulter. *
+* extra = champ de bits à placer. *
+* first = mémorisation d'un point de départ entre appels. [OUT]*
+* *
+* Description : Recherche l'indice idéal pour placer un champ dans un autre. *
+* *
+* Retour : Position du premier bit à insérer. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+size_t find_interleaving_index_for_acism(const bitfield_t *field, const bitfield_t *extra, size_t *first)
+{
+ size_t result; /* Dimension à retourner */
+ size_t i; /* Boucle de parcours #1 */
+ const unsigned long *bits; /* Itérateurs sur les bits */
+ size_t init_k; /* Point de départ optimal */
+ size_t k; /* Boucle de parcours #2 */
+ unsigned long mask; /* Valeur à comparer */
+ size_t j; /* Boucle de parcours #3 */
+
+ /**
+ * La procédure s'appuie sur deux particularité du contexte d'exécution (scan ACISM) :
+ * - il y a toujours au moins 257 bits (taille maximale du champs "extra") libres
+ * en fin de champs "field" ;
+ * - le premier bit du champ "extra" est toujours fixé à 1.
+ */
+
+ result = 0;
+
+ for (i = *first; i < field->used_words; i++)
+ {
+ /* S'il ne reste plus aucune place */
+ if (field->bits[i] != ~0lu)
+ break;
+ }
+
+ *first = i;
+
+ bits = field->bits + i;
+
+ for (; i < field->used_words; i++, bits++)
+ {
+ /* S'il ne reste plus aucune place */
+ if (*bits == ~0lu)
+ continue;
+
+ init_k = __builtin_ffsl(~*bits) - 1;
+
+ for (k = init_k; k < __WORDSIZE; k++)
+ {
+ /**
+ * Le champs de bits à placer ne comporte pas forcément au moins
+ * 32/64 bits, mais les bits non comptabilisés du mot sont toujours
+ * initialisés à zéro.
+ *
+ * Aucune prise en compte particulière d'un champ de petite taille
+ * n'est donc à réaliser ici.
+ */
+
+ mask = (extra->bits[0] << k);
+
+ /* Si tous les bits nécessaires au début sont libres... */
+ if ((*bits & mask) == 0)
+ {
+ for (j = 1; j < extra->used_words; j++)
+ {
+ if (k == 0)
+ mask = extra->bits[j];
+
+ else
+ {
+ /* Portion du mot courant */
+ mask = (extra->bits[j] << k);
+
+ /* Relicat du mot précédent */
+ mask |= (extra->bits[j - 1] >> (__WORDSIZE - k));
+
+ }
+
+ if (mask == 0)
+ continue;
+
+ if ((bits[j] & mask) != 0)
+ break;
+
+ }
+
+ if (j == extra->used_words)
+ {
+ /* Eventuelle dernière bribe débordant sur un dernier mot ? */
+ if (k > 0)
+ {
+ mask = (extra->bits[j - 1] >> (__WORDSIZE - k));
+
+ if ((bits[j] & mask) != 0)
+ continue;
+
+ }
+
+ result = i * __WORDSIZE + k;
+ goto found;
+
+ }
+
+ }
+
+ }
+
+ }
+
+ found:
+
+ assert(result > 0);
+
+ return result;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : field = champ de bits à consulter. *
* *
* Description : Détermine le nombre de bits à 1 dans un champ. *
* *
@@ -844,7 +1144,7 @@ size_t popcount_for_bit_field(const bitfield_t *field)
remaining = field->length;
- for (i = 0; i < field->requested; i++)
+ for (i = 0; i < field->used_words; i++)
{
value = field->bits[i];
@@ -866,3 +1166,55 @@ size_t popcount_for_bit_field(const bitfield_t *field)
return result;
}
+
+
+#if 0
+
+/******************************************************************************
+* *
+* Paramètres : field = champ de bits à consulter. *
+* *
+* Description : Imprime sur la sortie standard la valeur représentée. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+void output_bit_field(const bitfield_t *field)
+{
+ size_t i; /* Boucle de parcours #1 */
+ unsigned long value; /* Valeur masquée à traiter */
+ size_t k; /* Boucle de parcours #2 */
+
+ printf("[len=%zu] \n", field->length);
+
+#define MAX_BITS (sizeof(unsigned long) * 8)
+
+ for (i = 0; i < field->used_words; i++)
+ {
+ value = field->bits[i];
+
+ if (i > 0)
+ printf("| ");
+
+ for (k = 0; k < MAX_BITS; k++)
+ {
+ if ((i * MAX_BITS + k) >= field->length)
+ break;
+
+ printf("%c", value & (1lu << k) ? '1' : '.');
+
+ if ((k + 1) % 8 == 0)
+ printf(" ");
+
+ }
+
+ }
+
+ printf("\n");
+
+}
+
+#endif
diff --git a/src/common/bits.h b/src/common/bits.h
index 58fa0fe..608db39 100644
--- a/src/common/bits.h
+++ b/src/common/bits.h
@@ -45,6 +45,9 @@ void delete_bit_field(bitfield_t *);
/* Copie un champ de bits dans un autre. */
void copy_bit_field(bitfield_t *, const bitfield_t *);
+/* Réduit ou étend la taille d'un champ en évitant l'allocation. */
+void truncate_bit_field(bitfield_t **, size_t);
+
/* Redimensionne un champ de bits. */
void resize_bit_field(bitfield_t **, size_t);
@@ -78,6 +81,9 @@ void or_bit_field_at(bitfield_t *, const bitfield_t *, size_t);
/* Détermine si un bit est à 1 dans un champ de bits. */
bool test_in_bit_field(const bitfield_t *, size_t);
+/* Détermine si un bit est à 1 dans un champ puis le définit. */
+bool test_and_set_in_bit_field(bitfield_t *, size_t);
+
/* Détermine si un ensemble de bits est à 0 dans un champ. */
bool test_none_in_bit_field(const bitfield_t *, size_t, size_t);
@@ -90,9 +96,22 @@ bool test_zeros_within_bit_field(const bitfield_t *, size_t, const bitfield_t *)
/* Teste l'état à 1 de bits selon un masque de bits. */
bool test_ones_within_bit_field(const bitfield_t *, size_t, const bitfield_t *);
+/* Recherche un prochain bit défini dans un champ de bits. */
+size_t find_next_set_in_bit_field(const bitfield_t *, const size_t *);
+
+/* Recherche l'indice idéal pour placer un champ dans un autre. */
+size_t find_interleaving_index_for_acism(const bitfield_t *, const bitfield_t *, size_t *);
+
/* Détermine le nombre de bits à 1 dans un champ. */
size_t popcount_for_bit_field(const bitfield_t *);
+#if 0
+
+/* Imprime sur la sortie standard la valeur représentée. */
+void output_bit_field(const bitfield_t *);
+
+#endif
+
#endif /* _COMMON_BITS_H */
diff --git a/src/common/dllist.c b/src/common/dllist.c
index a953ad0..1ee7b0d 100644
--- a/src/common/dllist.c
+++ b/src/common/dllist.c
@@ -24,6 +24,17 @@
#include "dllist.h"
+#include <assert.h>
+
+
+
+/* Découpe une liste en deux parties. */
+static void split_dl_lists(dl_list_head, dl_list_head *, dl_list_head *);
+
+/* Trie une liste chaînée en supprimant les éléments identiques. */
+static dl_list_head sort_and_merge_dl_lists_no_dup(dl_list_head *, dl_list_head *, size_t *, __dl_item_compar_fn_t, dl_list_head *);
+
+
/******************************************************************************
* *
@@ -79,3 +90,187 @@ void __dl_list_del(dl_list_item *item, dl_list_head *head)
}
}
+
+
+/******************************************************************************
+* *
+* Paramètres : list = liste à découper. *
+* part1 = première partie constituée. [OUT] *
+* part2 = seconde partie constituée. [OUT] *
+* *
+* Description : Découpe une liste en deux parties. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static void split_dl_lists(dl_list_head list, dl_list_head *part1, dl_list_head *part2)
+{
+ dl_list_item *iter_slow; /* Boucle de parcours #1 */
+ dl_list_item *iter_fast; /* Boucle de parcours #2 */
+
+ *part1 = list;
+
+ iter_slow = list;
+ iter_fast = _dl_list_next(iter_slow, list);
+
+ while (iter_fast != NULL)
+ {
+ iter_fast = _dl_list_next(iter_fast, list);
+
+ if (iter_fast != NULL)
+ {
+ iter_slow = _dl_list_next(iter_slow, list);
+ iter_fast = _dl_list_next(iter_fast, list);
+ }
+
+ }
+
+ *part2 = _dl_list_next(iter_slow, list);
+
+ /* Réalisation d'une coupure */
+
+ if (*part2 != NULL)
+ {
+ (*part2)->prev = (*part1)->prev;
+ (*part2)->prev->next = (*part2);
+ }
+
+ iter_slow->next = *part1;
+ (*part1)->prev = iter_slow;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : head = tête de la liste à trier. *
+* length = taille de la liste fournie. *
+* compar = méthode de comparaison des éléments. *
+* duplicated = liste des éléments présents en double. [OUT] *
+* *
+* Description : Trie une liste chaînée en supprimant les éléments identiques.*
+* *
+* Retour : Nouvelle liste obtenue. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static dl_list_head sort_and_merge_dl_lists_no_dup(dl_list_head *a, dl_list_head *b, size_t *length, __dl_item_compar_fn_t compar, dl_list_head *duplicated)
+{
+ dl_list_head result; /* Liste fusionnée à renvoyer */
+ int ret; /* Bilan d'une comparaison */
+ dl_list_head next; /* Maillons de liste suivants */
+
+ if (dl_list_empty(*a))
+ result = *b;
+
+ else if (dl_list_empty(*b))
+ result = *a;
+
+ else
+ {
+ ret = compar(*a, *b);
+
+ if (ret < 0)
+ {
+ result = *a;
+ __dl_list_del(result, a);
+ DL_LIST_ITEM_INIT(result);
+
+ next = sort_and_merge_dl_lists_no_dup(a, b, length, compar, duplicated);
+ assert(!dl_list_empty(next));
+ _dl_list_merge(result, next);
+
+ }
+
+ else if (ret == 0)
+ {
+ result = *a;
+ __dl_list_del(result, a);
+ DL_LIST_ITEM_INIT(result);
+
+ if (length != NULL)
+ (*length)--;
+
+ if (duplicated != NULL)
+ {
+ /**
+ * L'élément est ici ajouté à la liste sans respect d'un ordre particulier.
+ */
+
+ if (dl_list_empty(*duplicated))
+ *duplicated = result;
+ else
+ __dl_list_add(result, duplicated, (*duplicated)->prev, *duplicated);
+
+ }
+
+ result = *b;
+ __dl_list_del(result, b);
+ DL_LIST_ITEM_INIT(result);
+
+ next = sort_and_merge_dl_lists_no_dup(a, b, length, compar, duplicated);
+ if (!dl_list_empty(next))
+ _dl_list_merge(result, next);
+
+ }
+
+ else
+ {
+ result = *b;
+ __dl_list_del(result, b);
+ DL_LIST_ITEM_INIT(result);
+
+ next = sort_and_merge_dl_lists_no_dup(a, b, length, compar, duplicated);
+ assert(!dl_list_empty(next));
+ _dl_list_merge(result, next);
+
+ }
+
+ }
+
+ return result;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : head = tête de la liste à trier. *
+* length = taille de la liste fournie. *
+* compar = méthode de comparaison des éléments. *
+* duplicated = liste des éléments présents en double. [OUT] *
+* *
+* Description : Trie une liste chaînée en notant les éléments identiques. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+void sort_dl_list_no_dup(dl_list_head *head, size_t *length, __dl_item_compar_fn_t compar, dl_list_head *duplicated)
+{
+ dl_list_head part1; /* Première moitiée à traiter */
+ dl_list_head part2; /* Seconde moitiée à traiter */
+
+ /* S'il y a réellement quelque chose à faire */
+ if (!dl_list_empty(*head) && !_dl_list_is_last(*head, *head))
+ {
+ /* Découpage en deux sous-listes */
+ split_dl_lists(*head, &part1, &part2);
+
+ /* Tri des deux listes obtenues */
+ sort_dl_list_no_dup(&part1, length, compar, duplicated);
+ sort_dl_list_no_dup(&part2, length, compar, duplicated);
+
+ /* Fusion des deux listes triées */
+ *head = sort_and_merge_dl_lists_no_dup(&part1, &part2, length, compar, duplicated);
+
+ }
+
+}
diff --git a/src/common/dllist.h b/src/common/dllist.h
index 111843b..1fb010a 100644
--- a/src/common/dllist.h
+++ b/src/common/dllist.h
@@ -62,6 +62,12 @@ void __dl_list_del(dl_list_item *, dl_list_head *);
#define dl_list_empty(head) \
((head) == NULL)
+#define _dl_list_is_last(item, head) \
+ ((item)->next == head)
+
+#define dl_list_is_last(item, head, member) \
+ item->member.next == &head->member
+
#define dl_list_last(head, type, member) \
(dl_list_empty(head) ? NULL : (type *)container_of(head->member.prev, type, member))
@@ -108,6 +114,17 @@ void __dl_list_del(dl_list_item *, dl_list_head *);
} \
while(0)
+#define _dl_list_merge(head1, head2) \
+ do \
+ { \
+ dl_list_item *mid = head1->prev; \
+ mid->next = head2; \
+ head1->prev = head2->prev; \
+ head2->prev->next = head1; \
+ head2->prev = mid; \
+ } \
+ while(0)
+
#define dl_list_merge(head1, head2, type, member) \
do \
{ \
@@ -134,6 +151,16 @@ void __dl_list_del(dl_list_item *, dl_list_head *);
_result; \
})
+#define _dl_list_next(iter, head) \
+ ({ \
+ dl_list_item *__next; \
+ __next = iter->next; \
+ if (__next == head) \
+ __next = NULL; \
+ __next; \
+ })
+
+
#define dl_list_next_iter(iter, head, type, member) \
(iter->member.next == &head->member ? \
NULL : container_of(iter->member.next, type, member))
@@ -164,5 +191,12 @@ void __dl_list_del(dl_list_item *, dl_list_head *);
pos = dl_list_prev_iter(pos, (head), type, member))
+/* Prototype pour un comparateur d'éléments */
+typedef int (*__dl_item_compar_fn_t) (const dl_list_item *, const dl_list_item *);
+
+/* Trie une liste chaînée en notant les éléments identiques. */
+void sort_dl_list_no_dup(dl_list_head *, size_t *, __dl_item_compar_fn_t, dl_list_head *);
+
+
#endif /* _COMMON_DLLIST_H */
diff --git a/src/common/sort.c b/src/common/sort.c
index fe5bd38..d79d71a 100644
--- a/src/common/sort.c
+++ b/src/common/sort.c
@@ -432,6 +432,91 @@ void *qinsert_multi(void *base, size_t *nmemb, size_t size, __compar_fn_t compar
/******************************************************************************
* *
+* Paramètres : base = adresse du tableau à parcourir. *
+* nmemb = nombre d'éléments présents au total. [OUT] *
+* allocated = taille déjà allouée pour le tableau. [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_managed(void *base, size_t *nmemb, size_t *allocated, size_t size, void *new, size_t index)
+{
+ void *result; /* Tableau trié à retourner */
+
+ if (*nmemb == *allocated)
+ {
+ if (*allocated == 0)
+ *allocated = 1024 * 8;
+ else
+ *allocated *= 2;
+
+ result = realloc(base, *allocated * size);
+
+ }
+ else
+ result = base;
+
+ 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] *
+* allocated = taille déjà allouée pour le tableau. [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_managed(void *base, size_t *nmemb, size_t *allocated, 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);
+#else
+ bsearch_index(new, base, *nmemb, size, compar, &index);
+#endif
+
+ result = _qinsert_managed(base, nmemb, allocated, size, new, index);
+
+ return result;
+
+}
+
+
+/******************************************************************************
+* *
* Paramètres : base = adresse du tableau à parcourir. *
* nmem = nombre d'éléments présents au total. [OUT] *
* size = taille de chaque élément du tableau. *
diff --git a/src/common/sort.h b/src/common/sort.h
index 4b2ae94..39a6f33 100644
--- a/src/common/sort.h
+++ b/src/common/sort.h
@@ -64,6 +64,12 @@ void *qinsert(void *, size_t *, size_t, __compar_fn_t, void *);
/* Ajoute au bon endroit un élément dans un tableau trié. */
void *qinsert_multi(void *, size_t *, size_t, __compar_fn_t, void *);
+/* Ajoute à l'endroit indiqué un élément dans un tableau. */
+void *_qinsert_managed(void *, size_t *, size_t *, size_t, void *, size_t);
+
+/* Ajoute au bon endroit un élément dans un tableau trié. */
+void *qinsert_managed(void *, size_t *, size_t *, size_t, __compar_fn_t, void *);
+
/* Supprime un élément dans un tableau trié. */
void *_qdelete(void *, size_t *, size_t, size_t);
diff --git a/src/common/szstr.h b/src/common/szstr.h
index aad1920..406a9f1 100644
--- a/src/common/szstr.h
+++ b/src/common/szstr.h
@@ -38,8 +38,13 @@
typedef struct _sized_string_t
{
union {
+
const char *static_data; /* Données non modifiées */
char *data; /* Chaîne de caractères */
+
+ const bin_t *static_bin_data; /* Données brutes non modifiées*/
+ bin_t *bin_data; /* Données brutes */
+
};
size_t len; /* Taille correspondante */
generated by cgit v0.11.2-87-g4458 at 2025-12-16 13:39:05 (GMT)