X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/d08290769c798befc27e9f8bbc3f1a3da12d1f08..4bfd5e4e5373627074d31ec2f15b2eb1947b8f5c:/lib/lbitset.c diff --git a/lib/lbitset.c b/lib/lbitset.c index 2e5b2081..a405b8cf 100644 --- a/lib/lbitset.c +++ b/lib/lbitset.c @@ -1,5 +1,5 @@ /* Functions to support link list bitsets. - Copyright (C) 2002, 2003 Free Software Foundation, Inc. + Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc. Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz). This program is free software; you can redistribute it and/or modify @@ -26,6 +26,7 @@ #include #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,7 +41,10 @@ /* Number of words to use for each element. The larger the value the greater the size of the cache and the shorter the time to find a given bit but the more memory wasted for sparse bitsets and the longer the time - to search for set bits. */ + to search for set bits. + + The routines that dominate timing profiles are lbitset_elt_find + and lbitset_elt_link, especially when accessing the bits randomly. */ #define LBITSET_ELT_WORDS 2 @@ -50,7 +54,7 @@ typedef bitset_word lbitset_word; /* Number of bits stored in each element. */ #define LBITSET_ELT_BITS \ - ((unsigned) (LBITSET_ELT_WORDS * LBITSET_WORD_BITS)) + ((unsigned int) (LBITSET_ELT_WORDS * LBITSET_WORD_BITS)) /* Lbitset element. We use an array of bits for each element. These are linked together in a doubly-linked list. */ @@ -74,7 +78,7 @@ static struct obstack lbitset_obstack; static bool lbitset_obstack_init = false; static lbitset_elt *lbitset_free_list; /* Free list of bitset elements. */ -extern void debug_lbitset PARAMS ((bitset)); +extern void debug_lbitset (bitset); #define LBITSET_CURRENT1(X) \ ((lbitset_elt *) (void *) ((char *) (X) - offsetof (lbitset_elt, words))) @@ -123,9 +127,7 @@ lbitset_elt_alloc (void) obstack_specify_allocation (&lbitset_obstack, OBSTACK_CHUNK_SIZE, __alignof__ (lbitset_elt), - (void *(*)PARAMS ((long))) OBSTACK_CHUNK_ALLOC, - (void (*)PARAMS ((void *))) OBSTACK_CHUNK_FREE); } @@ -502,21 +504,15 @@ lbitset_copy_cmp (bitset dst, bitset src) } -/* Return size in bits of bitset SRC. */ static bitset_bindex -lbitset_size (bitset src) +lbitset_resize (bitset src, bitset_bindex size) { - lbitset_elt *elt; - - elt = LBITSET_TAIL (src); - if (!elt) - return 0; + BITSET_NBITS_ (src) = size; - /* Return current size of bitset in bits. */ - return (elt->index + LBITSET_ELT_WORDS) * BITSET_WORD_BITS; + /* Need to prune any excess bits. FIXME. */ + return size; } - /* Set bit BITNO in bitset DST. */ static void lbitset_set (bitset dst, bitset_bindex bitno) @@ -867,8 +863,48 @@ lbitset_list (bitset bset, bitset_bindex *list, static bool lbitset_empty_p (bitset dst) { - lbitset_weed (dst); - return !LBITSET_HEAD (dst); + lbitset_elt *elt; + lbitset_elt *next; + + for (elt = LBITSET_HEAD (dst); elt; elt = next) + { + next = elt->next; + if (!lbitset_elt_zero_p (elt)) + return 0; + /* Weed as we go. */ + lbitset_elt_unlink (dst, elt); + } + + return 1; +} + + +/* Ensure that any unused bits within the last element are clear. */ +static inline void +lbitset_unused_clear (bitset dst) +{ + unsigned int last_bit; + bitset_bindex n_bits; + + n_bits = BITSET_SIZE_ (dst); + last_bit = n_bits % LBITSET_ELT_BITS; + + if (last_bit) + { + lbitset_elt *elt; + bitset_windex windex; + bitset_word *srcp; + + elt = LBITSET_TAIL (dst); + srcp = elt->words; + windex = n_bits / BITSET_WORD_BITS; + + srcp[windex - elt->index] &= ((bitset_word) 1 << last_bit) - 1; + windex++; + + for (; (windex - elt->index) < LBITSET_ELT_WORDS; windex++) + srcp[windex - elt->index] = 0; + } } @@ -883,18 +919,17 @@ lbitset_ones (bitset dst) 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; - windex = elt->index; + windex = (BITSET_SIZE_ (dst) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS; + 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)); } + + lbitset_unused_clear (dst); } @@ -911,11 +946,9 @@ lbitset_not (bitset dst, bitset src) /* This is another unfriendly operation for a linked list bitset! */ elt = LBITSET_TAIL (dst); - /* Ignore empty set. */ - if (!elt) - return; - windex = elt->index; + windex = (BITSET_SIZE_ (dst) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS; + for (i = 0; i < windex; i += LBITSET_ELT_WORDS) { /* Create new elements for dst if they cannot be found @@ -926,6 +959,7 @@ lbitset_not (bitset dst, bitset src) for (j = 0; j < LBITSET_ELT_WORDS; j++) delt->words[j] = ~selt->words[j]; } + lbitset_unused_clear (dst); lbitset_weed (dst); return; } @@ -1280,7 +1314,8 @@ struct bitset_vtable lbitset_vtable = { lbitset_reset, bitset_toggle_, lbitset_test, - lbitset_size, + lbitset_resize, + bitset_size_, bitset_count_, lbitset_empty_p, lbitset_ones, @@ -1323,6 +1358,7 @@ lbitset_bytes (bitset_bindex n_bits ATTRIBUTE_UNUSED) bitset lbitset_init (bitset bset, bitset_bindex n_bits ATTRIBUTE_UNUSED) { + BITSET_NBITS_ (bset) = n_bits; bset->b.vtable = &lbitset_vtable; return bset; } @@ -1352,7 +1388,7 @@ debug_lbitset (bitset bset) for (elt = LBITSET_HEAD (bset); elt; elt = elt->next) { - fprintf (stderr, "Elt %lu\n", (unsigned long) elt->index); + fprintf (stderr, "Elt %lu\n", (unsigned long int) elt->index); for (i = 0; i < LBITSET_ELT_WORDS; i++) { unsigned int j;