summaryrefslogtreecommitdiff
path: root/src/common
diff options
context:
space:
mode:
authorCyrille Bagard <nocbos@gmail.com>2024-04-17 20:56:39 (GMT)
committerCyrille Bagard <nocbos@gmail.com>2024-04-17 20:56:39 (GMT)
commite97dda4a993713aea7452a604086c9e4f0ebdd7e (patch)
treeaf675891f6dc93a38c4ccb00801d13e490eddd6a /src/common
parent6b06aa505ee0b183894d0c785f4f4a81839cb906 (diff)
Create a function to search for the next set bit in bit field.HEADmaster
Diffstat (limited to 'src/common')
-rw-r--r--src/common/bits.c99
-rw-r--r--src/common/bits.h3
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 *);