summaryrefslogtreecommitdiff
path: root/src/common
diff options
context:
space:
mode:
Diffstat (limited to 'src/common')
-rw-r--r--src/common/bits.c293
-rw-r--r--src/common/bits.h22
2 files changed, 95 insertions, 220 deletions
diff --git a/src/common/bits.c b/src/common/bits.c
index d4d5074..4d4731a 100644
--- a/src/common/bits.c
+++ b/src/common/bits.c
@@ -37,22 +37,13 @@ struct _bitfield_t
size_t length; /* Nombre de bits représentés */
size_t requested; /* Nombre de mots alloués */
- void *tail; /* Limite du tableau de bits */
-
- GMutex mutex; /* Garantie d'atomicité */
unsigned long bits[0]; /* Mémoire d'accès associée */
};
/* Crée un champ de bits initialisé à zéro. */
-static bitfield_t *_create_bit_field(size_t, bool, size_t);
-
-/* Crée une copie de champ de bits initialisé à zéro. */
-static bitfield_t *_create_bit_field_from(const bitfield_t *, bool, size_t);
-
-/* Crée une copie d'un champ de bits classique. */
-static bitfield_t *_dup_bit_field(const bitfield_t *, size_t);
+static bitfield_t *_create_bit_field(size_t);
/* Détermine si un ensemble de bits est homogène dans un champ. */
static bool test_state_in_bit_field(const bitfield_t *, size_t, size_t, bool);
@@ -62,8 +53,6 @@ static bool test_state_in_bit_field(const bitfield_t *, size_t, size_t, bool);
/******************************************************************************
* *
* Paramètres : length = nom de bits du champ à représenter. *
-* state = état initial de chaque des bits. *
-* extra = espace mémoire supplémentaire à ajouter au final. *
* *
* Description : Crée un champ de bits initialisé à zéro. *
* *
@@ -73,31 +62,22 @@ static bool test_state_in_bit_field(const bitfield_t *, size_t, size_t, bool);
* *
******************************************************************************/
-static bitfield_t *_create_bit_field(size_t length, bool state, size_t extra)
+static bitfield_t *_create_bit_field(size_t length)
{
bitfield_t *result; /* Création à retourner */
size_t requested; /* Nombre de mots à allouer */
size_t base; /* Allocation de base en octets*/
- requested = length / sizeof(unsigned long);
- if (length % sizeof(unsigned long) != 0) requested++;
+ requested = length / (sizeof(unsigned long) * 8);
+ if (length % (sizeof(unsigned long) * 8) != 0) requested++;
base = sizeof(bitfield_t) + requested * sizeof(unsigned long);
- result = (bitfield_t *)malloc(base + extra);
+ result = (bitfield_t *)malloc(base);
result->length = length;
result->requested = requested;
- result->tail = ((char *)result) + base;
-
- g_mutex_init(&result->mutex);
-
- if (state)
- set_all_in_bit_field(result);
- else
- reset_all_in_bit_field(result);
-
return result;
}
@@ -105,7 +85,7 @@ static bitfield_t *_create_bit_field(size_t length, bool state, size_t extra)
/******************************************************************************
* *
-* Paramètres : length = nom de bits du champ à représenter. *
+* Paramètres : length = nombre de bits du champ à représenter. *
* state = état initial de chaque des bits. *
* *
* Description : Crée un champ de bits initialisé. *
@@ -118,38 +98,25 @@ static bitfield_t *_create_bit_field(size_t length, bool state, size_t extra)
bitfield_t *create_bit_field(size_t length, bool state)
{
- return _create_bit_field(length, state, 0);
-
-}
+ bitfield_t *result; /* Création à retourner */
+ result = _create_bit_field(length);
-/******************************************************************************
-* *
-* Paramètres : field = champde bits à prendre pour modèle. *
-* state = état initial de chaque des bits. *
-* extra = espace mémoire supplémentaire à ajouter au final. *
-* *
-* Description : Crée une copie de champ de bits initialisé à zéro. *
-* *
-* Retour : Champ de bits mis en place. *
-* *
-* Remarques : - *
-* *
-******************************************************************************/
+ if (state)
+ set_all_in_bit_field(result);
+ else
+ reset_all_in_bit_field(result);
-static bitfield_t *_create_bit_field_from(const bitfield_t *field, bool state, size_t extra)
-{
- return _create_bit_field(field->length, state, extra);
+ return result;
}
/******************************************************************************
* *
-* Paramètres : field = champde bits à prendre pour modèle. *
-* state = état initial de chaque des bits. *
+* Paramètres : field = champ de bits à dupliquer. *
* *
-* Description : Crée une copie de champ de bits initialisé à zéro. *
+* Description : Crée une copie d'un champ de bits classique. *
* *
* Retour : Champ de bits mis en place. *
* *
@@ -157,9 +124,15 @@ static bitfield_t *_create_bit_field_from(const bitfield_t *field, bool state, s
* *
******************************************************************************/
-bitfield_t *create_bit_field_from(const bitfield_t *field, bool state)
+bitfield_t *dup_bit_field(const bitfield_t *field)
{
- return _create_bit_field_from(field, state, 0);
+ bitfield_t *result; /* Copie à retourner */
+
+ result = _create_bit_field(field->length);
+
+ memcpy(result->bits, field->bits, result->requested * sizeof(unsigned long));
+
+ return result;
}
@@ -178,8 +151,6 @@ bitfield_t *create_bit_field_from(const bitfield_t *field, bool state)
void delete_bit_field(bitfield_t *field)
{
- g_mutex_clear(&field->mutex);
-
free(field);
}
@@ -209,49 +180,64 @@ void copy_bit_field(bitfield_t *dest, const bitfield_t *src)
/******************************************************************************
* *
-* Paramètres : field = champ de bits à dupliquer. *
-* extra = espace mémoire supplémentaire à ajouter au final. *
+* Paramètres : a = premier champ à analyser. *
+* b = second champ à analyser. *
* *
-* Description : Crée une copie d'un champ de bits classique. *
+* Description : Compare deux champs de bits entre eux. *
* *
-* Retour : Champ de bits mis en place. *
+* Retour : Bilan de la comparaison. *
* *
* Remarques : - *
* *
******************************************************************************/
-static bitfield_t *_dup_bit_field(const bitfield_t *field, size_t extra)
+int compare_bit_fields(const bitfield_t *a, const bitfield_t *b)
{
- bitfield_t *result; /* Copie à retourner */
- size_t requested; /* Nombre de mots à allouer */
+ int result; /* Bilan à retourner */
+ unsigned long final; /* Masque de la partie finale */
+ size_t i; /* Boucle de parcours */
+ unsigned long val_a; /* Valeur d'un mot de A */
+ unsigned long val_b; /* Valeur d'un mot de B */
- result = _create_bit_field(field->length, false, extra);
+ result = 0;
- requested = field->length / sizeof(unsigned long);
- if (field->length % sizeof(unsigned long) != 0) requested++;
+ if (a->length > b->length)
+ result = 1;
- memcpy(result->bits, field->bits, requested * sizeof(unsigned long));
+ else if (a->length < b->length)
+ result = -1;
- return result;
+ if (result == 0)
+ {
+ final = a->length % sizeof(unsigned long);
-}
+ if (final == 0)
+ final = ~0lu;
+ else
+ final = (1 << final) - 1;
+ for (i = 0; i < a->requested && result == 0; i++)
+ {
+ val_a = a->bits[i];
+ val_b = b->bits[i];
-/******************************************************************************
-* *
-* Paramètres : field = champ de bits à dupliquer. *
-* *
-* Description : Crée une copie d'un champ de bits classique. *
-* *
-* Retour : Champ de bits mis en place. *
-* *
-* Remarques : - *
-* *
-******************************************************************************/
+ if ((i + 1) == a->requested)
+ {
+ val_a &= final;
+ val_b &= final;
+ }
-bitfield_t *dup_bit_field(const bitfield_t *field)
-{
- return _dup_bit_field(field, 0);
+ if (val_a > val_b)
+ result = 1;
+
+ else if (val_a < val_b)
+ result = -1;
+
+ }
+
+ }
+
+ return result;
}
@@ -300,7 +286,7 @@ void set_all_in_bit_field(bitfield_t *field)
* first = indice du premier bit à traiter. *
* count = nombre de bits à marquer. *
* *
-* Description : Bascule à 1 une partie d'un champ de bits. *
+* Description : Bascule à 0 une partie d'un champ de bits. *
* *
* Retour : - *
* *
@@ -308,7 +294,7 @@ void set_all_in_bit_field(bitfield_t *field)
* *
******************************************************************************/
-void set_in_bit_field(bitfield_t *field, size_t first, size_t count)
+void reset_in_bit_field(bitfield_t *field, size_t first, size_t count)
{
size_t last; /* Point d'arrêt de la boucle */
size_t i; /* Boucle de parcours */
@@ -324,7 +310,7 @@ void set_in_bit_field(bitfield_t *field, size_t first, size_t count)
index = i / (sizeof(unsigned long) * 8);
remaining = i % (sizeof(unsigned long) * 8);
- field->bits[index] |= (1ul << remaining);
+ field->bits[index] &= ~(1ul << remaining);
}
@@ -337,79 +323,34 @@ void set_in_bit_field(bitfield_t *field, size_t first, size_t count)
* first = indice du premier bit à traiter. *
* count = nombre de bits à marquer. *
* *
-* Description : Bascule à 1 de façon atomique une partie d'un champ de bits. *
+* Description : Bascule à 1 une partie d'un champ de bits. *
* *
-* Retour : true si la zone traitée était entièrement vierge. *
+* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
-bool set_atomic_in_bit_field(bitfield_t *field, size_t first, size_t count)
+void set_in_bit_field(bitfield_t *field, size_t first, size_t count)
{
- bool result; /* Bilan à retourner */
- size_t start; /* Mot de départ */
- size_t end; /* Mot d'arrivée */
+ size_t last; /* Point d'arrêt de la boucle */
+ size_t i; /* Boucle de parcours */
+ size_t index; /* Cellule de tableau visée */
size_t remaining; /* Nombre de bits restants */
- unsigned long mask; /* Nouvelle valeur à insérer */
- unsigned long oldval; /* Ancienne valeur présente */
-
- start = first / (sizeof(unsigned long) * 8);
- end = (first + count - 1) / (sizeof(unsigned long) * 8);
-
- if (start == end)
- {
- remaining = first % (sizeof(unsigned long) * 8);
- assert(count > 0 && count <= (sizeof(unsigned long) * 8));
-
- if (count == 64)
- {
- assert(remaining == 0);
- mask = ~0lu;
- }
- else
- {
- mask = (1lu << count) - 1;
- mask <<= remaining;
- }
-
- /**
- * Pour une raison inconnue, l'appel suivant est parfois sans effet :
- *
- * oldval = g_atomic_pointer_or(&field->bits[start], mask);
- *
- * On bascule donc dans l'équivalent plus long à exécuter...
- */
-
- g_mutex_lock(&field->mutex);
-
- oldval = field->bits[start];
-
- field->bits[start] |= mask;
-
- g_mutex_unlock(&field->mutex);
-
- result = ((oldval & mask) == 0);
+ last = first + count;
- assert(test_all_in_bit_field(field, first, count));
+ assert(last <= field->length);
- }
- else
+ for (i = first; i < last; i++)
{
- g_mutex_lock(&field->mutex);
-
- result = test_none_in_bit_field(field, first, count);
-
- if (result)
- set_in_bit_field(field, first, count);
+ index = i / (sizeof(unsigned long) * 8);
+ remaining = i % (sizeof(unsigned long) * 8);
- g_mutex_unlock(&field->mutex);
+ field->bits[index] |= (1ul << remaining);
}
- return result;
-
}
@@ -465,7 +406,7 @@ void or_bit_field(bitfield_t *dest, const bitfield_t *src)
/******************************************************************************
* *
-* Paramètres : field = champ de bits à modifier. *
+* Paramètres : field = champ de bits à consulter. *
* n = indice du bit à traiter. *
* *
* Description : Détermine si un bit est à 1 dans un champ de bits. *
@@ -503,7 +444,7 @@ bool test_in_bit_field(const bitfield_t *field, size_t n)
* *
* Description : Détermine si un ensemble de bits est homogène dans un champ. *
* *
-* Retour : true si le bit correspondant est à l'état haut. *
+* Retour : true si les bits correspondants sont à l'état indiqué. *
* *
* Remarques : - *
* *
@@ -539,13 +480,13 @@ static bool test_state_in_bit_field(const bitfield_t *field, size_t first, size_
/******************************************************************************
* *
-* Paramètres : field = champ de bits à modifier. *
+* Paramètres : field = champ de bits à consulter. *
* first = indice du premier bit à traiter. *
-* count = nombre de bits à marquer. *
+* count = nombre de bits à analyser. *
* *
* Description : Détermine si un ensemble de bits est à 0 dans un champ. *
* *
-* Retour : true si le bit correspondant est à l'état haut. *
+* Retour : true si les bits correspondants sont à l'état bas. *
* *
* Remarques : - *
* *
@@ -564,13 +505,13 @@ bool test_none_in_bit_field(const bitfield_t *field, size_t first, size_t count)
/******************************************************************************
* *
-* Paramètres : field = champ de bits à modifier. *
+* Paramètres : field = champ de bits à consulter. *
* first = indice du premier bit à traiter. *
-* count = nombre de bits à marquer. *
+* count = nombre de bits à analyser. *
* *
* Description : Détermine si un ensemble de bits est à 1 dans un champ. *
* *
-* Retour : true si le bit correspondant est à l'état haut. *
+* Retour : true si les bits correspondants sont à l'état haut. *
* *
* Remarques : - *
* *
@@ -585,61 +526,3 @@ bool test_all_in_bit_field(const bitfield_t *field, size_t first, size_t count)
return result;
}
-
-
-/******************************************************************************
-* *
-* Paramètres : a = premier champ de bits à comparer. *
-* b = second champ de bits à comparer. *
-* *
-* Description : Indique si deux champs de bits sont identiques ou non. *
-* *
-* Retour : true si les champs de bits sont égaux ou false sinon. *
-* *
-* Remarques : - *
-* *
-******************************************************************************/
-
-bool is_bit_field_equal_to(const bitfield_t *a, const bitfield_t *b)
-{
- bool result; /* Résultat à retourner */
- size_t i; /* Boucle de parcours */
- size_t remaining; /* Nombre de bits restants */
-
- if (a->length != b->length)
- return false;
-
- result = true;
-
- for (i = 0; i < (a->requested - 1) && result; i++)
- result = (a->bits[i] == b->bits[i]);
-
- if (result)
- {
- remaining = a->length % sizeof(unsigned long);
-
- if (remaining == 0)
- result = (a->bits[i] == b->bits[i]);
-
- else
- {
- remaining = (1 << (remaining + 1)) - 1;
-
- result = ((a->bits[i] & remaining) == (b->bits[i] & remaining));
-
- }
-
- }
-
- return result;
-
-}
-
-
-
-
-unsigned long gfw(const bitfield_t *field)
-{
- return field->bits[0];
-
-}
diff --git a/src/common/bits.h b/src/common/bits.h
index 4a2937f..b9fc0e6 100644
--- a/src/common/bits.h
+++ b/src/common/bits.h
@@ -36,8 +36,8 @@ typedef struct _bitfield_t bitfield_t;
/* Crée un champ de bits initialisé. */
bitfield_t *create_bit_field(size_t, bool);
-/* Crée une copie de champ de bits initialisé à zéro. */
-bitfield_t *create_bit_field_from(const bitfield_t *, bool);
+/* Crée une copie d'un champ de bits classique. */
+bitfield_t *dup_bit_field(const bitfield_t *);
/* Supprime de la mémoire un champ de bits donné. */
void delete_bit_field(bitfield_t *);
@@ -45,8 +45,8 @@ void delete_bit_field(bitfield_t *);
/* Copie un champ de bits dans un autre. */
void copy_bit_field(bitfield_t *, const bitfield_t *);
-/* Crée une copie d'un champ de bits classique. */
-bitfield_t *dup_bit_field(const bitfield_t *);
+/* Compare deux champs de bits entre eux. */
+int compare_bit_fields(const bitfield_t *, const bitfield_t *);
/* Bascule à 0 un champ de bits dans son intégralité. */
void reset_all_in_bit_field(bitfield_t *);
@@ -54,12 +54,12 @@ void reset_all_in_bit_field(bitfield_t *);
/* Bascule à 1 un champ de bits dans son intégralité. */
void set_all_in_bit_field(bitfield_t *);
+/* Bascule à 0 une partie d'un champ de bits. */
+void reset_in_bit_field(bitfield_t *, size_t, size_t);
+
/* Bascule à 1 une partie d'un champ de bits. */
void set_in_bit_field(bitfield_t *, size_t, size_t);
-/* Bascule à 1 de façon atomique une partie d'un champ de bits. */
-bool set_atomic_in_bit_field(bitfield_t *, size_t, size_t);
-
/* Réalise une opération ET logique entre deux champs de bits. */
void and_bit_field(bitfield_t *, const bitfield_t *);
@@ -75,14 +75,6 @@ bool test_none_in_bit_field(const bitfield_t *, size_t, size_t);
/* Détermine si un ensemble de bits est à 1 dans un champ. */
bool test_all_in_bit_field(const bitfield_t *, size_t, size_t);
-/* Indique si deux champs de bits sont identiques ou non. */
-bool is_bit_field_equal_to(const bitfield_t *, const bitfield_t *);
-
-
-
-
-unsigned long gfw(const bitfield_t *);
-
#endif /* _COMMON_BITS_H */