diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/common/bits.c | 99 | ||||
-rw-r--r-- | src/common/bits.h | 3 |
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 *); |