X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/345cea780a4d3d11673c176cde39e20a043a1dea..500bbfcd816776d0ddbf3555fedd41b529c405b3:/lib/lbitset.c?ds=sidebyside diff --git a/lib/lbitset.c b/lib/lbitset.c index f426c301..d279c5ec 100644 --- a/lib/lbitset.c +++ b/lib/lbitset.c @@ -23,7 +23,9 @@ #include "lbitset.h" #include "obstack.h" +#include #include +#include /* This file implements linked-list bitsets. These bitsets can be of arbitrary length and are more efficient than arrays of bits for @@ -40,9 +42,7 @@ but the more memory wasted for sparse bitsets and the longer the time to search for set bits. */ -#ifndef LBITSET_ELT_WORDS #define LBITSET_ELT_WORDS 2 -#endif typedef bitset_word lbitset_word; @@ -64,22 +64,6 @@ typedef struct lbitset_elt_struct lbitset_elt; -/* Head of lbitset linked list. */ -typedef struct lbitset_struct -{ - lbitset_elt *head; /* First element in linked list. */ - lbitset_elt *tail; /* Last element in linked list. */ -} -*lbitset; - - -struct bitset_struct -{ - struct bbitset_struct b; - struct lbitset_struct l; -}; - - enum lbitset_find_mode { LBITSET_FIND, LBITSET_CREATE, LBITSET_SUBST }; @@ -90,36 +74,10 @@ static struct obstack lbitset_obstack; static int lbitset_obstack_init = 0; static lbitset_elt *lbitset_free_list; /* Free list of bitset elements. */ -static lbitset_elt *lbitset_elt_alloc PARAMS ((void)); -static lbitset_elt *lbitset_elt_calloc PARAMS ((void)); -static void lbitset_elt_link PARAMS ((bitset, lbitset_elt *)); -static void lbitset_elt_unlink PARAMS ((bitset, lbitset_elt *)); -static void lbitset_elt_free PARAMS ((lbitset_elt *)); -static lbitset_elt *lbitset_elt_find PARAMS ((bitset, bitset_windex, - enum lbitset_find_mode)); -static int lbitset_elt_zero_p PARAMS ((lbitset_elt *)); - -static void lbitset_prune PARAMS ((bitset, lbitset_elt *)); -static void lbitset_weed PARAMS ((bitset)); -static void lbitset_zero PARAMS ((bitset)); -static int lbitset_equal_p PARAMS ((bitset, bitset)); -static void lbitset_copy PARAMS ((bitset, bitset)); -static int lbitset_copy_compare PARAMS ((bitset, bitset)); -static void lbitset_set PARAMS ((bitset, bitset_bindex)); -static void lbitset_reset PARAMS ((bitset, bitset_bindex)); -static int lbitset_test PARAMS ((bitset, bitset_bindex)); -static int lbitset_size PARAMS ((bitset)); -static int lbitset_op1 PARAMS ((bitset, enum bitset_ops)); -static int lbitset_op2 PARAMS ((bitset, bitset, enum bitset_ops)); -static int lbitset_op3 PARAMS ((bitset, bitset, bitset, enum bitset_ops)); -static int lbitset_list PARAMS ((bitset, bitset_bindex *, bitset_bindex, - bitset_bindex *)); -static int lbitset_reverse_list -PARAMS ((bitset, bitset_bindex *, bitset_bindex, bitset_bindex *)); -static void lbitset_free PARAMS ((bitset)); - - -#define LBITSET_CURRENT1(X) (lbitset_elt *)((char *)(X) + ((char *)&(((lbitset_elt *)(X))->next) - (char *)&(((lbitset_elt *)(X))->words))) +extern void debug_lbitset PARAMS ((bitset)); + +#define LBITSET_CURRENT1(X) \ + ((lbitset_elt *) (void *) ((char *) (X) - offsetof (lbitset_elt, words))) #define LBITSET_CURRENT(X) LBITSET_CURRENT1((X)->b.cdata) @@ -128,7 +86,7 @@ static void lbitset_free PARAMS ((bitset)); /* Allocate a lbitset element. The bits are not cleared. */ static inline lbitset_elt * -lbitset_elt_alloc () +lbitset_elt_alloc (void) { lbitset_elt *elt; @@ -139,9 +97,6 @@ lbitset_elt_alloc () } else { - /* We can't use gcc_obstack_init to initialize the obstack since - print-rtl.c now calls bitset functions, and bitset is linked - into the gen* functions. */ if (!lbitset_obstack_init) { lbitset_obstack_init = 1; @@ -184,9 +139,9 @@ lbitset_elt_alloc () } -/* Allocate a lbitset element. The bits are not cleared. */ +/* Allocate a lbitset element. The bits are cleared. */ static inline lbitset_elt * -lbitset_elt_calloc () +lbitset_elt_calloc (void) { lbitset_elt *elt; @@ -197,8 +152,7 @@ lbitset_elt_calloc () static inline void -lbitset_elt_free (elt) - lbitset_elt *elt; +lbitset_elt_free (lbitset_elt *elt) { elt->next = lbitset_free_list; lbitset_free_list = elt; @@ -207,9 +161,7 @@ lbitset_elt_free (elt) /* Unlink element ELT from bitset BSET. */ static inline void -lbitset_elt_unlink (bset, elt) - bitset bset; - lbitset_elt *elt; +lbitset_elt_unlink (bitset bset, lbitset_elt *elt) { lbitset_elt *next = elt->next; lbitset_elt *prev = elt->prev; @@ -254,9 +206,7 @@ lbitset_elt_unlink (bset, elt) /* Cut the chain of bitset BSET before element ELT and free the elements. */ static inline void -lbitset_prune (bset, elt) - bitset bset; - lbitset_elt *elt; +lbitset_prune (bitset bset, lbitset_elt *elt) { lbitset_elt *next; @@ -288,8 +238,7 @@ lbitset_prune (bset, elt) /* Return nonzero if all bits in an element are zero. */ static inline int -lbitset_elt_zero_p (elt) - lbitset_elt *elt; +lbitset_elt_zero_p (lbitset_elt *elt) { int i; @@ -303,9 +252,7 @@ lbitset_elt_zero_p (elt) /* Link the bitset element into the current bitset linked list. */ static inline void -lbitset_elt_link (bset, elt) - bitset bset; - lbitset_elt *elt; +lbitset_elt_link (bitset bset, lbitset_elt *elt) { bitset_windex windex = elt->index; lbitset_elt *ptr; @@ -367,10 +314,8 @@ lbitset_elt_link (bset, elt) static lbitset_elt * -lbitset_elt_find (bset, windex, mode) - bitset bset; - bitset_windex windex; - enum lbitset_find_mode mode; +lbitset_elt_find (bitset bset, bitset_windex windex, + enum lbitset_find_mode mode) { lbitset_elt *elt; lbitset_elt *current; @@ -403,7 +348,7 @@ lbitset_elt_find (bset, windex, mode) continue; } - /* `element' is the nearest to the one we want. If it's not the one + /* ELT is the nearest to the one we want. If it's not the one we want, the one we want does not exist. */ if (elt && (windex - elt->index) < LBITSET_ELT_WORDS) { @@ -420,7 +365,7 @@ lbitset_elt_find (bset, windex, mode) return 0; case LBITSET_CREATE: - windex = (windex / (unsigned) LBITSET_ELT_WORDS) * LBITSET_ELT_WORDS; + windex -= windex % LBITSET_ELT_WORDS; elt = lbitset_elt_calloc (); elt->index = windex; @@ -438,8 +383,7 @@ lbitset_elt_find (bset, windex, mode) /* Weed out the zero elements from the list. */ static inline void -lbitset_weed (bset) - bitset bset; +lbitset_weed (bitset bset) { lbitset_elt *elt; lbitset_elt *next; @@ -454,9 +398,8 @@ lbitset_weed (bset) /* Set all bits in the bitset to zero. */ -static inline void -lbitset_zero (bset) - bitset bset; +static void +lbitset_zero (bitset bset) { lbitset_elt *head; @@ -469,10 +412,9 @@ lbitset_zero (bset) } +/* Return 1 if DST == SRC. */ static inline int -lbitset_equal_p (dst, src) - bitset dst; - bitset src; +lbitset_equal_p (bitset dst, bitset src) { lbitset_elt *selt; lbitset_elt *delt; @@ -499,9 +441,7 @@ lbitset_equal_p (dst, src) /* Copy bits from bitset SRC to bitset DST. */ static inline void -lbitset_copy (dst, src) - bitset dst; - bitset src; +lbitset_copy (bitset dst, bitset src) { lbitset_elt *elt; lbitset_elt *head; @@ -543,9 +483,7 @@ lbitset_copy (dst, src) /* Copy bits from bitset SRC to bitset DST. Return non-zero if bitsets different. */ static inline int -lbitset_copy_compare (dst, src) - bitset dst; - bitset src; +lbitset_copy_cmp (bitset dst, bitset src) { if (src == dst) return 0; @@ -565,9 +503,8 @@ lbitset_copy_compare (dst, src) /* Return size in bits of bitset SRC. */ -static int -lbitset_size (src) - bitset src; +static bitset_bindex +lbitset_size (bitset src) { lbitset_elt *elt; @@ -582,30 +519,28 @@ lbitset_size (src) /* Set bit BITNO in bitset DST. */ static void -lbitset_set (dst, bitno) - bitset dst; - bitset_bindex bitno; +lbitset_set (bitset dst, bitset_bindex bitno) { bitset_windex windex = bitno / BITSET_WORD_BITS; lbitset_elt_find (dst, windex, LBITSET_CREATE); - dst->b.cdata[windex - dst->b.cindex] |= (1 << (bitno % BITSET_WORD_BITS)); + dst->b.cdata[windex - dst->b.cindex] |= + (bitset_word) 1 << (bitno % BITSET_WORD_BITS); } /* Reset bit BITNO in bitset DST. */ static void -lbitset_reset (dst, bitno) - bitset dst; - bitset_bindex bitno; +lbitset_reset (bitset dst, bitset_bindex bitno) { bitset_windex windex = bitno / BITSET_WORD_BITS; if (!lbitset_elt_find (dst, windex, LBITSET_FIND)) return; - dst->b.cdata[windex - dst->b.cindex] &= ~(1 << (bitno % BITSET_WORD_BITS)); + dst->b.cdata[windex - dst->b.cindex] &= + ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS)); /* If all the data is zero, perhaps we should unlink it now... */ } @@ -613,23 +548,20 @@ lbitset_reset (dst, bitno) /* Test bit BITNO in bitset SRC. */ static int -lbitset_test (src, bitno) - bitset src; - bitset_bindex bitno; +lbitset_test (bitset src, bitset_bindex bitno) { bitset_windex windex = bitno / BITSET_WORD_BITS; if (!lbitset_elt_find (src, windex, LBITSET_FIND)) return 0; - return (src->b.cdata[windex - src->b.cindex] + return (src->b.cdata[windex - src->b.cindex] >> (bitno % BITSET_WORD_BITS)) & 1; } static void -lbitset_free (bset) - bitset bset; +lbitset_free (bitset bset) { lbitset_zero (bset); } @@ -638,12 +570,9 @@ lbitset_free (bset) /* Find list of up to NUM bits set in BSET starting from and including *NEXT and store in array LIST. Return with actual number of bits found and with *NEXT indicating where search stopped. */ -static int -lbitset_reverse_list (bset, list, num, next) - bitset bset; - bitset_bindex *list; - bitset_bindex num; - bitset_bindex *next; +static bitset_bindex +lbitset_list_reverse (bitset bset, bitset_bindex *list, + bitset_bindex num, bitset_bindex *next) { bitset_bindex rbitno; bitset_bindex bitno; @@ -676,13 +605,24 @@ lbitset_reverse_list (bset, list, num, next) if (!elt) return 0; - /* If num is 1, we could speed things up with a binary search - of the word of interest. */ + if (windex >= elt->index + LBITSET_ELT_WORDS) + { + /* We are trying to start in no-mans land so start + at end of current elt. */ + bcount = BITSET_WORD_BITS - 1; + windex = elt->index + LBITSET_ELT_WORDS - 1; + } + else + { + bcount = bitno % BITSET_WORD_BITS; + } count = 0; - bcount = bitno % BITSET_WORD_BITS; boffset = windex * BITSET_WORD_BITS; + /* If num is 1, we could speed things up with a binary search + of the word of interest. */ + while (elt) { bitset_word *srcp = elt->words; @@ -725,12 +665,9 @@ lbitset_reverse_list (bset, list, num, next) /* Find list of up to NUM bits set in BSET starting from and including *NEXT and store in array LIST. Return with actual number of bits found and with *NEXT indicating where search stopped. */ -static int -lbitset_list (bset, list, num, next) - bitset bset; - bitset_bindex *list; - bitset_bindex num; - bitset_bindex *next; +static bitset_bindex +lbitset_list (bitset bset, bitset_bindex *list, + bitset_bindex num, bitset_bindex *next) { bitset_bindex bitno; bitset_windex windex; @@ -929,168 +866,149 @@ lbitset_list (bset, list, num, next) static int -lbitset_op1 (dst, op) - bitset dst; - enum bitset_ops op; +lbitset_empty_p (bitset dst) { - unsigned int i; - bitset_windex windex; - lbitset_elt *elt; + lbitset_weed (dst); + if (LBITSET_HEAD (dst)) + return 0; + return 1; +} - switch (op) - { - case BITSET_OP_ZERO: - lbitset_zero (dst); - break; - case BITSET_OP_ONES: - /* This is a decidedly unfriendly operation for a linked list - bitset! */ - elt = LBITSET_TAIL (dst); - /* Ignore empty set. */ - if (!elt) - return 0; - - windex = elt->index; - for (i = 0; i < windex; i += LBITSET_ELT_WORDS) - { - /* Create new elements if they cannot be found. */ - elt = lbitset_elt_find (dst, i, LBITSET_CREATE); - memset (elt->words, ~0, sizeof (elt->words)); - } - break; +static void +lbitset_ones (bitset dst) +{ + bitset_windex i; + bitset_windex windex; + lbitset_elt *elt; - case BITSET_OP_EMPTY_P: - lbitset_weed (dst); - if (LBITSET_HEAD (dst)) - return 0; - break; + /* This is a decidedly unfriendly operation for a linked list + bitset! It makes a sparse bitset become dense. An alternative + is to have a flag that indicates that the bitset stores the + complement of what it indicates. */ + elt = LBITSET_TAIL (dst); + /* Ignore empty set. */ + if (!elt) + return; - default: - abort (); + windex = elt->index; + for (i = 0; i < windex; i += LBITSET_ELT_WORDS) + { + /* Create new elements if they cannot be found. */ + elt = lbitset_elt_find (dst, i, LBITSET_CREATE); + memset (elt->words, -1, sizeof (elt->words)); } - - return 1; } -static int -lbitset_op2 (dst, src, op) - bitset dst; - bitset src; - enum bitset_ops op; +static void +lbitset_not (bitset dst, bitset src) { lbitset_elt *elt; lbitset_elt *selt; lbitset_elt *delt; - unsigned int i; + bitset_windex i; unsigned int j; bitset_windex windex; - switch (op) - { - case BITSET_OP_COPY: - lbitset_copy (dst, src); - break; + /* This is another unfriendly operation for a linked list + bitset! */ + elt = LBITSET_TAIL (dst); + /* Ignore empty set. */ + if (!elt) + return; - case BITSET_OP_NOT: - /* This is another unfriendly operation for a linked list - bitset! */ - elt = LBITSET_TAIL (dst); - /* Ignore empty set. */ - if (!elt) - return 0; + windex = elt->index; + for (i = 0; i < windex; i += LBITSET_ELT_WORDS) + { + /* Create new elements for dst if they cannot be found + or substitute zero elements if src elements not found. */ + selt = lbitset_elt_find (src, i, LBITSET_SUBST); + delt = lbitset_elt_find (dst, i, LBITSET_CREATE); - windex = elt->index; - for (i = 0; i < windex; i += LBITSET_ELT_WORDS) - { - /* Create new elements for dst if they cannot be found - or substitute zero elements if src elements not found. */ - selt = lbitset_elt_find (dst, i, LBITSET_SUBST); - delt = lbitset_elt_find (dst, i, LBITSET_CREATE); + for (j = 0; j < LBITSET_ELT_WORDS; j++) + delt->words[j] = ~selt->words[j]; + } + lbitset_weed (dst); + return; +} - for (j = 0; j < LBITSET_ELT_WORDS; j++) - delt->words[j] = ~selt->words[j]; - } - lbitset_weed (dst); - break; - /* Return 1 if DST == SRC. */ - case BITSET_OP_EQUAL_P: - return lbitset_equal_p (dst, src); - break; +/* Return 1 if DST == DST | SRC. */ +static int +lbitset_subset_p (bitset dst, bitset src) +{ + lbitset_elt *selt; + lbitset_elt *delt; + unsigned int j; - /* Return 1 if DST == DST | SRC. */ - case BITSET_OP_SUBSET_P: - for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst); - selt || delt; selt = selt->next, delt = delt->next) + for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst); + selt || delt; selt = selt->next, delt = delt->next) + { + if (!selt) + selt = &lbitset_zero_elts[0]; + else if (!delt) + delt = &lbitset_zero_elts[0]; + else if (selt->index != delt->index) { - if (!selt) - selt = &lbitset_zero_elts[0]; - else if (!delt) - delt = &lbitset_zero_elts[0]; - else if (selt->index != delt->index) + if (selt->index < delt->index) { - if (selt->index < delt->index) - { - lbitset_zero_elts[2].next = delt; - delt = &lbitset_zero_elts[2]; - } - else - { - lbitset_zero_elts[1].next = selt; - selt = &lbitset_zero_elts[1]; - } + lbitset_zero_elts[2].next = delt; + delt = &lbitset_zero_elts[2]; + } + else + { + lbitset_zero_elts[1].next = selt; + selt = &lbitset_zero_elts[1]; } - - for (j = 0; j < LBITSET_ELT_WORDS; j++) - if (delt->words[j] != (selt->words[j] | delt->words[j])) - return 0; } - break; - /* Return 1 if DST & SRC == 0. */ - case BITSET_OP_DISJOINT_P: - for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst); - selt && delt; selt = selt->next, delt = delt->next) + for (j = 0; j < LBITSET_ELT_WORDS; j++) + if (delt->words[j] != (selt->words[j] | delt->words[j])) + return 0; + } + return 1; +} + + +/* Return 1 if DST & SRC == 0. */ +static int +lbitset_disjoint_p (bitset dst, bitset src) +{ + lbitset_elt *selt; + lbitset_elt *delt; + unsigned int j; + + for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst); + selt && delt; selt = selt->next, delt = delt->next) + { + if (selt->index != delt->index) { - if (selt->index != delt->index) + if (selt->index < delt->index) { - if (selt->index < delt->index) - { - lbitset_zero_elts[2].next = delt; - delt = &lbitset_zero_elts[2]; - } - else - { - lbitset_zero_elts[1].next = selt; - selt = &lbitset_zero_elts[1]; - } - /* Since the elements are different, there is no - intersection of these elements. */ - continue; + lbitset_zero_elts[2].next = delt; + delt = &lbitset_zero_elts[2]; } - - for (j = 0; j < LBITSET_ELT_WORDS; j++) - if (selt->words[j] & delt->words[j]) - return 0; + else + { + lbitset_zero_elts[1].next = selt; + selt = &lbitset_zero_elts[1]; + } + /* Since the elements are different, there is no + intersection of these elements. */ + continue; } - break; - default: - abort (); + for (j = 0; j < LBITSET_ELT_WORDS; j++) + if (selt->words[j] & delt->words[j]) + return 0; } - return 1; } static int -lbitset_op3 (dst, src1, src2, op) - bitset dst; - bitset src1; - bitset src2; - enum bitset_ops op; +lbitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op) { lbitset_elt *selt1 = LBITSET_HEAD (src1); lbitset_elt *selt2 = LBITSET_HEAD (src2); @@ -1107,42 +1025,11 @@ lbitset_op3 (dst, src1, src2, op) int changed = 0; unsigned int i; - /* Fast track common, simple cases. */ - if (!selt2) - { - if (op == BITSET_OP_AND) - { - lbitset_weed (dst); - changed = !LBITSET_HEAD (dst); - lbitset_zero (dst); - return changed; - } - else if (op == BITSET_OP_ANDN || op == BITSET_OP_OR - || op == BITSET_OP_XOR) - { - return lbitset_copy_compare (dst, src1); - } - } - else if (!selt1) - { - if (op == BITSET_OP_AND || op == BITSET_OP_ANDN) - { - lbitset_weed (dst); - changed = !LBITSET_HEAD (dst); - lbitset_zero (dst); - return changed; - } - else if (op == BITSET_OP_OR || op == BITSET_OP_XOR) - { - return lbitset_copy_compare (dst, src2); - } - } - LBITSET_HEAD (dst) = 0; dst->b.csize = 0; - windex1 = (selt1) ? selt1->index : BITSET_INDEX_MAX; - windex2 = (selt2) ? selt2->index : BITSET_INDEX_MAX; + windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX; + windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX; while (selt1 || selt2) { @@ -1154,9 +1041,9 @@ lbitset_op3 (dst, src1, src2, op) stmp1 = selt1; stmp2 = selt2; selt1 = selt1->next; - windex1 = (selt1) ? selt1->index : BITSET_INDEX_MAX; + windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX; selt2 = selt2->next; - windex2 = (selt2) ? selt2->index : BITSET_INDEX_MAX; + windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX; } else if (windex1 < windex2) { @@ -1164,7 +1051,7 @@ lbitset_op3 (dst, src1, src2, op) stmp1 = selt1; stmp2 = &lbitset_zero_elts[0]; selt1 = selt1->next; - windex1 = (selt1) ? selt1->index : BITSET_INDEX_MAX; + windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX; } else { @@ -1172,7 +1059,7 @@ lbitset_op3 (dst, src1, src2, op) stmp1 = &lbitset_zero_elts[0]; stmp2 = selt2; selt2 = selt2->next; - windex2 = (selt2) ? selt2->index : BITSET_INDEX_MAX; + windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX; } /* Find the appropriate element from DST. Begin by discarding @@ -1278,46 +1165,174 @@ lbitset_op3 (dst, src1, src2, op) } +static int +lbitset_and_cmp (bitset dst, bitset src1, bitset src2) +{ + lbitset_elt *selt1 = LBITSET_HEAD (src1); + lbitset_elt *selt2 = LBITSET_HEAD (src2); + int changed; + + if (!selt2) + { + lbitset_weed (dst); + changed = !LBITSET_HEAD (dst); + lbitset_zero (dst); + return changed; + } + else if (!selt1) + { + lbitset_weed (dst); + changed = !LBITSET_HEAD (dst); + lbitset_zero (dst); + return changed; + } + return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_AND); +} + + +static void +lbitset_and (bitset dst, bitset src1, bitset src2) +{ + lbitset_and_cmp (dst, src1, src2); +} + + +static int +lbitset_andn_cmp (bitset dst, bitset src1, bitset src2) +{ + lbitset_elt *selt1 = LBITSET_HEAD (src1); + lbitset_elt *selt2 = LBITSET_HEAD (src2); + int changed; + + if (!selt2) + { + return lbitset_copy_cmp (dst, src1); + } + else if (!selt1) + { + lbitset_weed (dst); + changed = !LBITSET_HEAD (dst); + lbitset_zero (dst); + return changed; + } + return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_ANDN); +} + + +static void +lbitset_andn (bitset dst, bitset src1, bitset src2) +{ + lbitset_andn_cmp (dst, src1, src2); +} + + +static int +lbitset_or_cmp (bitset dst, bitset src1, bitset src2) +{ + lbitset_elt *selt1 = LBITSET_HEAD (src1); + lbitset_elt *selt2 = LBITSET_HEAD (src2); + + if (!selt2) + { + return lbitset_copy_cmp (dst, src1); + } + else if (!selt1) + { + return lbitset_copy_cmp (dst, src2); + } + return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_OR); +} + + +static void +lbitset_or (bitset dst, bitset src1, bitset src2) +{ + lbitset_or_cmp (dst, src1, src2); +} + + +static int +lbitset_xor_cmp (bitset dst, bitset src1, bitset src2) +{ + lbitset_elt *selt1 = LBITSET_HEAD (src1); + lbitset_elt *selt2 = LBITSET_HEAD (src2); + + if (!selt2) + { + return lbitset_copy_cmp (dst, src1); + } + else if (!selt1) + { + return lbitset_copy_cmp (dst, src2); + } + return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_XOR); +} + + +static void +lbitset_xor (bitset dst, bitset src1, bitset src2) +{ + lbitset_xor_cmp (dst, src1, src2); +} + + + /* Vector of operations for linked-list bitsets. */ -struct bitset_ops_struct lbitset_ops = { +struct bitset_vtable lbitset_vtable = { lbitset_set, lbitset_reset, + bitset_toggle_, lbitset_test, lbitset_size, - lbitset_op1, - lbitset_op2, - lbitset_op3, - bitset_op4, + bitset_count_, + lbitset_empty_p, + lbitset_ones, + lbitset_zero, + lbitset_copy, + lbitset_disjoint_p, + lbitset_equal_p, + lbitset_not, + lbitset_subset_p, + lbitset_and, + lbitset_and_cmp, + lbitset_andn, + lbitset_andn_cmp, + lbitset_or, + lbitset_or_cmp, + lbitset_xor, + lbitset_xor_cmp, + bitset_and_or_, + bitset_and_or_cmp_, + bitset_andn_or_, + bitset_andn_or_cmp_, + bitset_or_and_, + bitset_or_and_cmp_, lbitset_list, - lbitset_reverse_list, + lbitset_list_reverse, lbitset_free, BITSET_LIST }; /* Return size of initial structure. */ -int -lbitset_bytes (n_bits) - bitset_bindex n_bits ATTRIBUTE_UNUSED; +size_t +lbitset_bytes (bitset_bindex n_bits ATTRIBUTE_UNUSED) { - return sizeof (struct bitset_struct); + return sizeof (struct lbitset_struct); } /* Initialize a bitset. */ - bitset -lbitset_init (bset, n_bits) - bitset bset; - bitset_bindex n_bits ATTRIBUTE_UNUSED; +lbitset_init (bitset bset, bitset_bindex n_bits ATTRIBUTE_UNUSED) { - bset->b.ops = &lbitset_ops; + bset->b.vtable = &lbitset_vtable; return bset; } void -lbitset_release_memory () +lbitset_release_memory (void) { lbitset_free_list = 0; if (lbitset_obstack_init) @@ -1326,3 +1341,33 @@ lbitset_release_memory () obstack_free (&lbitset_obstack, NULL); } } + + +/* Function to be called from debugger to debug lbitset. */ +void +debug_lbitset (bitset bset) +{ + lbitset_elt *elt; + unsigned int i; + + if (!bset) + return; + + for (elt = LBITSET_HEAD (bset); elt; elt = elt->next) + { + fprintf (stderr, "Elt %lu\n", (unsigned long) elt->index); + for (i = 0; i < LBITSET_ELT_WORDS; i++) + { + unsigned int j; + bitset_word word; + + word = elt->words[i]; + + fprintf (stderr, " Word %u:", i); + for (j = 0; j < LBITSET_WORD_BITS; j++) + if ((word & ((bitset_word) 1 << j))) + fprintf (stderr, " %u", j); + fprintf (stderr, "\n"); + } + } +}