ref: 16461118be707834c1b2b43774a350fe6f6cc45c
parent: 0b5023c54b5310de851219ebbcd5f27876a005fb
author: Ori Bernstein <ori@eigenstate.org>
date: Wed Feb 24 06:28:18 EST 2016
Move bitset.c to util dir.
--- a/parse/Makefile
+++ b/parse/Makefile
@@ -1,6 +1,5 @@
LIB=libparse.a
OBJ=\
- bitset.o \
dump.o \
err.o \
fold.o \
--- a/parse/bitset.c
+++ /dev/null
@@ -1,226 +1,0 @@
-#include <stdlib.h>
-#include <stdio.h>
-#include <stdarg.h>
-#include <inttypes.h>
-#include <assert.h>
-#include <limits.h>
-#include <string.h>
-
-#include "util.h"
-#include "parse.h"
-
-#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
- * larger, zeroing out the new elements.
- * This allows the code to simply iterate
- * over both without keeping track of the
- * minimum size.
- */
-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;
- }
-}
-
-/* Creates a new all-zero bit set */
-Bitset *mkbs()
-{- Bitset *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);
-}
-
-/* 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;
-}
-
-/* Zeroes all values in a bit set */
-Bitset *bsclear(Bitset *bs)
-{- size_t i;
-
- 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;
-}
-
-/* A slightly tricky function to iterate over the contents
- * of a bitset. It returns true immediately if 'elt' is in
- * the bitset, otherwise it seeks forward to the next value
- * held in the bitset and stores it in elt. If there are no
- * more values, it returns false to stop iteration. Note,
- * this means that you need to increment elt every time you
- * pass through.
- *
- * Typical usage of this function:
- *
- * 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
- * repeatedly.
- */
-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;
-}
-
-/* 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; }-
-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);
-}
-
-void bsdel(Bitset *bs, size_t elt)
-{- if (elt < bs->nchunks * Sizetbits)
- bs->chunks[elt / Sizetbits] &= ~(1ULL << (elt % Sizetbits));
-}
-
-void bsunion(Bitset *a, Bitset *b)
-{- size_t 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;
-
- 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;
-
- 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;
-}
-
-int bsissubset(Bitset *set, Bitset *sub)
-{- 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;
-}
-
-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;
-}
--- a/parse/parse.h
+++ b/parse/parse.h
@@ -365,32 +365,6 @@
extern char *litstr[];
extern char *tidstr[];
-/* data structures */
-Bitset *mkbs(void);
-void bsfree(Bitset *bs);
-Bitset *bsdup(Bitset *bs);
-Bitset *bsclear(Bitset *bs);
-void delbs(Bitset *bs);
-void bsput(Bitset *bs, size_t elt);
-void bsdel(Bitset *bs, size_t elt);
-void bsunion(Bitset *a, Bitset *b);
-void bsintersect(Bitset *a, Bitset *b);
-void bsdiff(Bitset *a, Bitset *b);
-int bseq(Bitset *a, Bitset *b);
-int bsissubset(Bitset *set, Bitset *sub);
-int bsisempty(Bitset *set);
-int bsiter(Bitset *bs, size_t *elt);
-size_t bsmax(Bitset *bs);
-size_t bscount(Bitset *bs);
-/* inline for speed */
-static inline int bshas(Bitset *bs, size_t elt)
-{- if (elt >= bs->nchunks * 8 * sizeof(size_t))
- return 0;
- return (bs->chunks[elt / (8 * sizeof(size_t))] & (1ULL << (elt % (8 * sizeof(size_t))))) !=
- 0;
-}
-
/* useful key types */
int liteq(Node *a, Node *b);
int litvaleq(Node *a, Node *b);
--- a/util/Makefile
+++ b/util/Makefile
@@ -1,6 +1,7 @@
LIB=libutil.a
OBJ= \
alloc.o \
+ bitset.o \
htab.o \
pack.o \
util.o \
--- /dev/null
+++ b/util/bitset.c
@@ -1,0 +1,225 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <stdarg.h>
+#include <inttypes.h>
+#include <assert.h>
+#include <limits.h>
+#include <string.h>
+
+#include "util.h"
+
+#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
+ * larger, zeroing out the new elements.
+ * This allows the code to simply iterate
+ * over both without keeping track of the
+ * minimum size.
+ */
+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;
+ }
+}
+
+/* Creates a new all-zero bit set */
+Bitset *mkbs()
+{+ Bitset *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);
+}
+
+/* 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;
+}
+
+/* Zeroes all values in a bit set */
+Bitset *bsclear(Bitset *bs)
+{+ size_t i;
+
+ 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;
+}
+
+/* A slightly tricky function to iterate over the contents
+ * of a bitset. It returns true immediately if 'elt' is in
+ * the bitset, otherwise it seeks forward to the next value
+ * held in the bitset and stores it in elt. If there are no
+ * more values, it returns false to stop iteration. Note,
+ * this means that you need to increment elt every time you
+ * pass through.
+ *
+ * Typical usage of this function:
+ *
+ * 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
+ * repeatedly.
+ */
+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;
+}
+
+/* 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; }+
+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);
+}
+
+void bsdel(Bitset *bs, size_t elt)
+{+ if (elt < bs->nchunks * Sizetbits)
+ bs->chunks[elt / Sizetbits] &= ~(1ULL << (elt % Sizetbits));
+}
+
+void bsunion(Bitset *a, Bitset *b)
+{+ size_t 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;
+
+ 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;
+
+ 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;
+}
+
+int bsissubset(Bitset *set, Bitset *sub)
+{+ 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;
+}
+
+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;
+}
--- a/util/util.h
+++ b/util/util.h
@@ -66,6 +66,36 @@
void sbputs(Strbuf *sb, char *s);
void sbputb(Strbuf *sb, char b);
+/* bit sets */
+Bitset *mkbs(void);
+void bsfree(Bitset *bs);
+Bitset *bsdup(Bitset *bs);
+Bitset *bsclear(Bitset *bs);
+void delbs(Bitset *bs);
+void bsput(Bitset *bs, size_t elt);
+void bsdel(Bitset *bs, size_t elt);
+void bsunion(Bitset *a, Bitset *b);
+void bsintersect(Bitset *a, Bitset *b);
+void bsdiff(Bitset *a, Bitset *b);
+int bseq(Bitset *a, Bitset *b);
+int bsissubset(Bitset *set, Bitset *sub);
+int bsisempty(Bitset *set);
+int bsiter(Bitset *bs, size_t *elt);
+size_t bsmax(Bitset *bs);
+size_t bscount(Bitset *bs);
+/* inline for speed */
+static inline int bshas(Bitset *bs, size_t elt)
+{+ size_t eltidx, eltshift;
+
+ if (elt >= bs->nchunks * 8 * sizeof(size_t))
+ return 0;
+ eltidx = elt / (8 * sizeof(size_t));
+ eltshift = elt % (8 * sizeof(size_t));
+ return (bs->chunks[eltidx] & (1ULL << (elt % (8 * sizeof(size_t))))) != 0;
+}
+
+
/* hash tables */
Htab *mkht(ulong (*hash)(void *key), int (*cmp)(void *k1, void *k2));
void htfree(Htab *ht);