summaryrefslogtreecommitdiff
path: root/parse/bitset.c
diff options
context:
space:
mode:
Diffstat (limited to 'parse/bitset.c')
-rw-r--r--parse/bitset.c240
1 files changed, 118 insertions, 122 deletions
diff --git a/parse/bitset.c b/parse/bitset.c
index 7450515..ac72f6e 100644
--- a/parse/bitset.c
+++ b/parse/bitset.c
@@ -8,7 +8,7 @@
#include "parse.h"
-#define Sizetbits (CHAR_BIT*sizeof(size_t)) /* used in graph reprs */
+#define Sizetbits (CHAR_BIT * sizeof(size_t)) /* used in graph reprs */
/* Equalizes the size of a and b by
* growing the smaller to the size of the
@@ -19,91 +19,91 @@
*/
static void eqsz(Bitset *a, Bitset *b)
{
- size_t sz;
- size_t i;
- size_t *p;
-
- if (a->nchunks > b->nchunks)
- sz = a->nchunks;
- else
- sz = b->nchunks;
-
- if (a->nchunks != sz) {
- p = zalloc(sz * sizeof(size_t));
- for (i = 0; i < a->nchunks; i++)
- p[i] = a->chunks[i];
- free(a->chunks);
- a->chunks = p;
- a->nchunks = sz;
- }
-
- if (b->nchunks != sz) {
- p = zalloc(sz * sizeof(size_t));
- for (i = 0; i < b->nchunks; i++)
- p[i] = b->chunks[i];
- free(b->chunks);
- b->chunks = p;
- b->nchunks = sz;
- }
+ size_t sz;
+ size_t i;
+ size_t *p;
+
+ if (a->nchunks > b->nchunks)
+ sz = a->nchunks;
+ else
+ sz = b->nchunks;
+
+ if (a->nchunks != sz) {
+ p = zalloc(sz * sizeof(size_t));
+ for (i = 0; i < a->nchunks; i++)
+ p[i] = a->chunks[i];
+ free(a->chunks);
+ a->chunks = p;
+ a->nchunks = sz;
+ }
+
+ if (b->nchunks != sz) {
+ p = zalloc(sz * sizeof(size_t));
+ for (i = 0; i < b->nchunks; i++)
+ p[i] = b->chunks[i];
+ free(b->chunks);
+ b->chunks = p;
+ b->nchunks = sz;
+ }
}
/* Creates a new all-zero bit set */
Bitset *mkbs()
{
- Bitset *bs;
+ Bitset *bs;
- bs = xalloc(sizeof(Bitset));
- bs->nchunks = 1;
- bs->chunks = zalloc(1*sizeof(size_t));
- return bs;
+ bs = xalloc(sizeof(Bitset));
+ bs->nchunks = 1;
+ bs->chunks = zalloc(1 * sizeof(size_t));
+ return bs;
}
/* Frees a bitset. Safe to call on NULL. */
void bsfree(Bitset *bs)
{
- if (!bs)
- return;
- free(bs->chunks);
- free(bs);
+ if (!bs)
+ return;
+ free(bs->chunks);
+ free(bs);
}
/* Duplicates a bitset. NULL is duplicated to NULL. */
Bitset *bsdup(Bitset *a)
{
- Bitset *bs;
-
- if (!a)
- return NULL;
- bs = xalloc(sizeof(Bitset));
- bs->nchunks = a->nchunks;
- bs->chunks = xalloc(a->nchunks*sizeof(size_t));
- memcpy(bs->chunks, a->chunks, a->nchunks*sizeof(size_t));
- return bs;
+ Bitset *bs;
+
+ if (!a)
+ return NULL;
+ bs = xalloc(sizeof(Bitset));
+ bs->nchunks = a->nchunks;
+ bs->chunks = xalloc(a->nchunks * sizeof(size_t));
+ memcpy(bs->chunks, a->chunks, a->nchunks * sizeof(size_t));
+ return bs;
}
/* Zeroes all values in a bit set */
Bitset *bsclear(Bitset *bs)
{
- size_t i;
+ size_t i;
- if (!bs)
- return mkbs();
- for (i = 0; i < bs->nchunks; i++)
- bs->chunks[i] = 0;
- return bs;
+ if (!bs)
+ return mkbs();
+ for (i = 0; i < bs->nchunks; i++)
+ bs->chunks[i] = 0;
+ return bs;
}
/* Counts the number of values held in a bit set */
size_t bscount(Bitset *bs)
{
- size_t i, j, n;
-
- n = 0;
- for (i = 0; i < bs->nchunks; i++)
- for (j = 0; j < sizeof(size_t)*CHAR_BIT; j++)
- if (bs->chunks[i] & 1ULL << j)
- n++;
- return n;
+ size_t i, j, n;
+
+ n = 0;
+ for (i = 0; i < bs->nchunks; i++)
+ for (j = 0; j < sizeof(size_t) * CHAR_BIT; j++)
+ if (bs->chunks[i] & 1ULL << j)
+ n++;
+ return n;
}
/* A slightly tricky function to iterate over the contents
@@ -116,8 +116,8 @@ size_t bscount(Bitset *bs)
*
* Typical usage of this function:
*
- * for (i = 0; bsiter(set, &i); i++)
- * use(i);
+ * for (i = 0; bsiter(set, &i); i++)
+ * use(i);
*
* The increment of 'i' in the for loop is needed in order
* to prevent the function from returning the same value
@@ -125,105 +125,101 @@ size_t bscount(Bitset *bs)
*/
int bsiter(Bitset *bs, size_t *elt)
{
- size_t i;
-
- for (i = *elt; i < bsmax(bs); i++) {
- while (i < bsmax(bs) && !bs->chunks[i/Sizetbits])
- i = (i + Sizetbits) & ~(Sizetbits - 1);
- if (bshas(bs, i)) {
- *elt = i;
- return 1;
- }
- }
- return 0;
+ size_t i;
+
+ for (i = *elt; i < bsmax(bs); i++) {
+ while (i < bsmax(bs) && !bs->chunks[i / Sizetbits])
+ i = (i + Sizetbits) & ~(Sizetbits - 1);
+ if (bshas(bs, i)) {
+ *elt = i;
+ return 1;
+ }
+ }
+ return 0;
}
/* Returns the largest value that the bitset can possibly
* hold. It's conservative, but scanning the entire bitset
* is a bit slow. This is mostly an aid to iterate over it. */
-size_t bsmax(Bitset *bs)
-{
- return bs->nchunks*Sizetbits;
-}
+size_t bsmax(Bitset *bs) { return bs->nchunks * Sizetbits; }
void bsput(Bitset *bs, size_t elt)
{
- size_t sz;
- if (elt >= bs->nchunks*Sizetbits) {
- sz = (elt/Sizetbits)+1;
- bs->chunks = zrealloc(bs->chunks, bs->nchunks*sizeof(size_t), sz*sizeof(size_t));
- bs->nchunks = sz;
- }
- bs->chunks[elt/Sizetbits] |= 1ULL << (elt % Sizetbits);
+ size_t sz;
+ if (elt >= bs->nchunks * Sizetbits) {
+ sz = (elt / Sizetbits) + 1;
+ bs->chunks = zrealloc(bs->chunks, bs->nchunks * sizeof(size_t), sz * sizeof(size_t));
+ bs->nchunks = sz;
+ }
+ bs->chunks[elt / Sizetbits] |= 1ULL << (elt % Sizetbits);
}
void bsdel(Bitset *bs, size_t elt)
{
- if (elt < bs->nchunks*Sizetbits)
- bs->chunks[elt/Sizetbits] &= ~(1ULL << (elt % Sizetbits));
+ if (elt < bs->nchunks * Sizetbits)
+ bs->chunks[elt / Sizetbits] &= ~(1ULL << (elt % Sizetbits));
}
-
void bsunion(Bitset *a, Bitset *b)
{
- size_t i;
+ size_t i;
- eqsz(a, b);
- for (i = 0; i < a->nchunks; i++)
- a->chunks[i] |= b->chunks[i];
+ eqsz(a, b);
+ for (i = 0; i < a->nchunks; i++)
+ a->chunks[i] |= b->chunks[i];
}
void bsintersect(Bitset *a, Bitset *b)
{
- size_t i;
+ size_t i;
- eqsz(a, b);
- for (i = 0; i < a->nchunks; i++)
- a->chunks[i] &= b->chunks[i];
+ eqsz(a, b);
+ for (i = 0; i < a->nchunks; i++)
+ a->chunks[i] &= b->chunks[i];
}
void bsdiff(Bitset *a, Bitset *b)
{
- size_t i;
+ size_t i;
- eqsz(a, b);
- for (i = 0; i < a->nchunks; i++)
- a->chunks[i] &= ~b->chunks[i];
+ eqsz(a, b);
+ for (i = 0; i < a->nchunks; i++)
+ a->chunks[i] &= ~b->chunks[i];
}
int bseq(Bitset *a, Bitset *b)
{
- size_t i;
-
- if (!a || !b)
- return bsisempty(a) && bsisempty(b);
- eqsz(a, b);
- for (i = 0; i < a->nchunks; i++) {
- if (a->chunks[i] != b->chunks[i])
- return 0;
- }
- return 1;
+ size_t i;
+
+ if (!a || !b)
+ return bsisempty(a) && bsisempty(b);
+ eqsz(a, b);
+ for (i = 0; i < a->nchunks; i++) {
+ if (a->chunks[i] != b->chunks[i])
+ return 0;
+ }
+ return 1;
}
int bsissubset(Bitset *set, Bitset *sub)
{
- size_t i;
+ size_t i;
- eqsz(set, sub);
- for (i = 0; i < set->nchunks; i++)
- if ((sub->chunks[i] & set->chunks[i]) != set->chunks[i])
- return 0;
- return 1;
+ eqsz(set, sub);
+ for (i = 0; i < set->nchunks; i++)
+ if ((sub->chunks[i] & set->chunks[i]) != set->chunks[i])
+ return 0;
+ return 1;
}
int bsisempty(Bitset *set)
{
- size_t i;
-
- if (!set)
- return 1;
- for (i = 0; i < set->nchunks; i++)
- if (set->chunks[i])
- return 0;
- return 1;
+ size_t i;
+
+ if (!set)
+ return 1;
+ for (i = 0; i < set->nchunks; i++)
+ if (set->chunks[i])
+ return 0;
+ return 1;
}