Create a function to search for the next set bit in bit field.HEADmaster

2 files changed, 102 insertions, 0 deletions

diff --git a/src/common/bits.c b/src/common/bits.c
index 0e5afc8..3d0004c 100644
--- a/src/common/bits.c
+++ b/src/common/bits.c
@@ -49,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);
 
@@ -903,7 +907,102 @@ 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. *
 *                                                                             *
diff --git a/src/common/bits.h b/src/common/bits.h
index cd71681..608db39 100644
--- a/src/common/bits.h
+++ b/src/common/bits.h
@@ -96,6 +96,9 @@ 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 *);