+++ /dev/null
-/* Simple bitsets.
- Copyright (C) 2002 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
- it under the terms of the GNU General Public License as published by
- the Free Software Foundation; either version 2 of the License, or
- (at your option) any later version.
-
- This program is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- GNU General Public License for more details.
-
- You should have received a copy of the GNU General Public License
- along with this program; if not, write to the Free Software
- Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
-*/
-
-#ifdef HAVE_CONFIG_H
-#include "config.h"
-#endif
-
-#include "sbitset.h"
-#include <stdlib.h>
-#include <string.h>
-
-/* This file implements fixed size bitsets stored as an array
- of words. Any unused bits in the last word must be zero. */
-
-typedef struct sbitset_struct
-{
- unsigned int n_bits; /* Number of bits. */
- bitset_word words[1]; /* The array of bits. */
-}
-*sbitset;
-
-
-struct bitset_struct
-{
- struct bbitset_struct b;
- struct sbitset_struct s;
-};
-
-static void sbitset_unused_clear PARAMS ((bitset));
-
-static int sbitset_small_list PARAMS ((bitset, bitset_bindex *, bitset_bindex,
- bitset_bindex *));
-
-static void sbitset_set PARAMS ((bitset, bitset_bindex));
-static void sbitset_reset PARAMS ((bitset, bitset_bindex));
-static int sbitset_test PARAMS ((bitset, bitset_bindex));
-static int sbitset_size PARAMS ((bitset));
-static int sbitset_op1 PARAMS ((bitset, enum bitset_ops));
-static int sbitset_op2 PARAMS ((bitset, bitset, enum bitset_ops));
-static int sbitset_op3 PARAMS ((bitset, bitset, bitset, enum bitset_ops));
-static int sbitset_op4 PARAMS ((bitset, bitset, bitset, bitset,
- enum bitset_ops));
-static int sbitset_list PARAMS ((bitset, bitset_bindex *, bitset_bindex,
- bitset_bindex *));
-static int sbitset_reverse_list
-PARAMS ((bitset, bitset_bindex *, bitset_bindex, bitset_bindex *));
-
-#define SBITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS)
-#define SBITSET_WORDS(X) ((X)->s.words)
-#define SBITSET_N_BITS(X) ((X)->s.n_bits)
-
-
-/* Return size in bits of bitset SRC. */
-static int
-sbitset_size (src)
- bitset src;
-{
- return SBITSET_N_BITS (src);
-}
-
-
-/* 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
-sbitset_small_list (src, list, num, next)
- bitset src;
- bitset_bindex *list;
- bitset_bindex num;
- bitset_bindex *next;
-{
- bitset_bindex bitno;
- bitset_bindex count;
- bitset_windex size;
- bitset_word word;
-
- word = SBITSET_WORDS (src)[0];
-
- /* Short circuit common case. */
- if (!word)
- return 0;
-
- size = SBITSET_N_BITS (src);
- bitno = *next;
- if (bitno >= size)
- return 0;
-
- word >>= bitno;
-
- /* If num is 1, we could speed things up with a binary search
- of the word of interest. */
-
- if (num >= BITSET_WORD_BITS)
- {
- for (count = 0; word; bitno++)
- {
- if (word & 1)
- list[count++] = bitno;
- word >>= 1;
- }
- }
- else
- {
- for (count = 0; word; bitno++)
- {
- if (word & 1)
- {
- list[count++] = bitno;
- if (count >= num)
- {
- bitno++;
- break;
- }
- }
- word >>= 1;
- }
- }
-
- *next = bitno;
- return count;
-}
-
-
-/* Set bit BITNO in bitset DST. */
-static void
-sbitset_set (dst, bitno)
- bitset dst ATTRIBUTE_UNUSED;
- bitset_bindex bitno ATTRIBUTE_UNUSED;
-{
- /* This should never occur for sbitsets. */
- abort ();
-}
-
-
-/* Reset bit BITNO in bitset DST. */
-static void
-sbitset_reset (dst, bitno)
- bitset dst ATTRIBUTE_UNUSED;
- bitset_bindex bitno ATTRIBUTE_UNUSED;
-{
- /* This should never occur for sbitsets. */
- abort ();
-}
-
-
-/* Test bit BITNO in bitset SRC. */
-static int
-sbitset_test (src, bitno)
- bitset src ATTRIBUTE_UNUSED;
- bitset_bindex bitno ATTRIBUTE_UNUSED;
-{
- /* This should never occur for sbitsets. */
- abort ();
- return 0;
-}
-
-
-/* Find list of up to NUM bits set in BSET in reverse order, 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
-sbitset_reverse_list (src, list, num, next)
- bitset src;
- bitset_bindex *list;
- bitset_bindex num;
- bitset_bindex *next;
-{
- bitset_bindex bitno;
- bitset_bindex rbitno;
- bitset_bindex count;
- bitset_windex windex;
- unsigned int bitcnt;
- bitset_bindex bitoff;
- bitset_word word;
- bitset_word *srcp = SBITSET_WORDS (src);
- bitset_bindex n_bits = SBITSET_N_BITS (src);
-
- rbitno = *next;
-
- /* If num is 1, we could speed things up with a binary search
- of the word of interest. */
-
- if (rbitno >= n_bits)
- return 0;
-
- count = 0;
-
- bitno = n_bits - (rbitno + 1);
-
- windex = bitno / BITSET_WORD_BITS;
- bitcnt = bitno % BITSET_WORD_BITS;
- bitoff = windex * BITSET_WORD_BITS;
-
- for (; windex != ~0U; windex--, bitoff -= BITSET_WORD_BITS,
- bitcnt = BITSET_WORD_BITS - 1)
- {
- word = srcp[windex] << (BITSET_WORD_BITS - 1 - bitcnt);
- for (; word; bitcnt--)
- {
- if (word & BITSET_MSB)
- {
- list[count++] = bitoff + bitcnt;
- if (count >= num)
- {
- *next = n_bits - (bitoff + bitcnt);
- return count;
- }
- }
- word <<= 1;
- }
- }
-
- *next = n_bits - (bitoff + 1);
- return count;
-}
-
-
-/* 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
-sbitset_list (src, list, num, next)
- bitset src;
- bitset_bindex *list;
- bitset_bindex num;
- bitset_bindex *next;
-{
- bitset_bindex bitno;
- bitset_bindex count;
- bitset_windex windex;
- bitset_bindex bitoff;
- bitset_windex size = src->b.csize;
- bitset_word *srcp = SBITSET_WORDS (src);
- bitset_word word;
-
- bitno = *next;
-
- count = 0;
- if (!bitno)
- {
- /* Many bitsets are zero, so make this common case fast. */
- for (windex = 0; windex < size && !srcp[windex]; windex++)
- continue;
- if (windex >= size)
- return 0;
-
- /* If num is 1, we could speed things up with a binary search
- of the current word. */
-
- bitoff = windex * BITSET_WORD_BITS;
- }
- else
- {
- if (bitno >= SBITSET_N_BITS (src))
- return 0;
-
- windex = bitno / BITSET_WORD_BITS;
- bitno = bitno % BITSET_WORD_BITS;
-
- if (bitno)
- {
- /* Handle the case where we start within a word.
- Most often, this is executed with large bitsets
- with many set bits where we filled the array
- on the previous call to this function. */
-
- bitoff = windex * BITSET_WORD_BITS;
- word = srcp[windex] >> bitno;
- for (bitno = bitoff + bitno; word; bitno++)
- {
- if (word & 1)
- {
- list[count++] = bitno;
- if (count >= num)
- {
- *next = bitno + 1;
- return count;
- }
- }
- word >>= 1;
- }
- windex++;
- }
- bitoff = windex * BITSET_WORD_BITS;
- }
-
- for (; windex < size; windex++, bitoff += BITSET_WORD_BITS)
- {
- if (!(word = srcp[windex]))
- continue;
-
- if ((count + BITSET_WORD_BITS) < num)
- {
- for (bitno = bitoff; word; bitno++)
- {
- if (word & 1)
- list[count++] = bitno;
- word >>= 1;
- }
- }
- else
- {
- for (bitno = bitoff; word; bitno++)
- {
- if (word & 1)
- {
- list[count++] = bitno;
- if (count >= num)
- {
- *next = bitno + 1;
- return count;
- }
- }
- word >>= 1;
- }
- }
- }
-
- *next = bitoff;
- return count;
-}
-
-
-/* Ensure that any unused bits within the last word are clear. */
-static inline void
-sbitset_unused_clear (dst)
- bitset dst;
-{
- unsigned int last_bit;
-
- last_bit = SBITSET_N_BITS (dst) % BITSET_WORD_BITS;
- if (last_bit)
- SBITSET_WORDS (dst)[dst->b.csize - 1] &=
- (bitset_word) ((1 << last_bit) - 1);
-}
-
-
-static int
-sbitset_op1 (dst, op)
- bitset dst;
- enum bitset_ops op;
-{
- unsigned int i;
- bitset_word *dstp = SBITSET_WORDS (dst);
- unsigned int bytes;
-
- bytes = sizeof (bitset_word) * dst->b.csize;
-
- switch (op)
- {
- case BITSET_OP_ZERO:
- memset (dstp, 0, bytes);
- break;
-
- case BITSET_OP_ONES:
- memset (dstp, ~0, bytes);
- sbitset_unused_clear (dst);
- break;
-
- case BITSET_OP_EMPTY_P:
- for (i = 0; i < dst->b.csize; i++)
- if (dstp[i])
- return 0;
- break;
-
- default:
- abort ();
- }
-
- return 1;
-}
-
-
-static int
-sbitset_op2 (dst, src, op)
- bitset dst;
- bitset src;
- enum bitset_ops op;
-{
- unsigned int i;
- bitset_word *srcp = SBITSET_WORDS (src);
- bitset_word *dstp = SBITSET_WORDS (dst);
- bitset_windex size = dst->b.csize;
-
-#ifdef ENABLE_CHECKING
- /* Check for compatiblity. */
- if (SBITSET_N_BITS (src) != SBITSET_N_BITS (dst))
- abort ();
-#endif
-
- switch (op)
- {
- case BITSET_OP_COPY:
- if (srcp == dstp)
- break;
- memcpy (dstp, srcp, sizeof (bitset_word) * size);
- break;
-
- case BITSET_OP_NOT:
- for (i = 0; i < size; i++)
- *dstp++ = ~(*srcp++);
- sbitset_unused_clear (dst);
- break;
-
- case BITSET_OP_EQUAL_P:
- for (i = 0; i < size; i++)
- if (*srcp++ != *dstp++)
- return 0;
- break;
-
- case BITSET_OP_SUBSET_P:
- for (i = 0; i < size; i++, dstp++, srcp++)
- if (*dstp != (*srcp | *dstp))
- return 0;
- break;
-
- case BITSET_OP_DISJOINT_P:
- for (i = 0; i < size; i++)
- if (*srcp++ & *dstp++)
- return 0;
- break;
-
- default:
- abort ();
- }
-
- return 1;
-}
-
-
-static int
-sbitset_op3 (dst, src1, src2, op)
- bitset dst;
- bitset src1;
- bitset src2;
- enum bitset_ops op;
-{
- unsigned int i;
- int changed = 0;
- bitset_word *src1p = SBITSET_WORDS (src1);
- bitset_word *src2p = SBITSET_WORDS (src2);
- bitset_word *dstp = SBITSET_WORDS (dst);
- bitset_windex size = dst->b.csize;
-
-#ifdef ENABLE_CHECKING
- /* Check for compatiblity. */
- if (SBITSET_N_BITS (src1) != SBITSET_N_BITS (dst)
- SBITSET_N_BITS (src2) != SBITSET_N_BITS (dst))
- abort ();
-#endif
-
- switch (op)
- {
- case BITSET_OP_OR:
- for (i = 0; i < size; i++, dstp++)
- {
- bitset_word tmp = *src1p++ | *src2p++;
-
- if (*dstp != tmp)
- {
- changed = 1;
- *dstp = tmp;
- }
- }
- break;
-
- case BITSET_OP_AND:
- for (i = 0; i < size; i++, dstp++)
- {
- bitset_word tmp = *src1p++ & *src2p++;
-
- if (*dstp != tmp)
- {
- changed = 1;
- *dstp = tmp;
- }
- }
- break;
-
- case BITSET_OP_XOR:
- for (i = 0; i < size; i++, dstp++)
- {
- bitset_word tmp = *src1p++ ^ *src2p++;
-
- if (*dstp != tmp)
- {
- changed = 1;
- *dstp = tmp;
- }
- }
- break;
-
- case BITSET_OP_ANDN:
- for (i = 0; i < size; i++, dstp++)
- {
- bitset_word tmp = *src1p++ & ~(*src2p++);
-
- if (*dstp != tmp)
- {
- changed = 1;
- *dstp = tmp;
- }
- }
- break;
-
- default:
- abort ();
- }
-
- return changed;
-}
-
-
-static int
-sbitset_op4 (dst, src1, src2, src3, op)
- bitset dst;
- bitset src1;
- bitset src2;
- bitset src3;
- enum bitset_ops op;
-{
- unsigned int i;
- int changed = 0;
- bitset_word *src1p = SBITSET_WORDS (src1);
- bitset_word *src2p = SBITSET_WORDS (src2);
- bitset_word *src3p = SBITSET_WORDS (src3);
- bitset_word *dstp = SBITSET_WORDS (dst);
- bitset_windex size = dst->b.csize;
-
-#ifdef ENABLE_CHECKING
- /* Check for compatiblity. */
- if (SBITSET_N_BITS (src1) != SBITSET_N_BITS (dst)
- || SBITSET_N_BITS (src2) != SBITSET_N_BITS (dst)
- || SBITSET_N_BITS (src3) != SBITSET_N_BITS (dst))
- abort ();
-#endif
-
- switch (op)
- {
- case BITSET_OP_OR_AND:
- for (i = 0; i < size; i++, dstp++)
- {
- bitset_word tmp = (*src1p++ | *src2p++) & *src3p++;
-
- if (*dstp != tmp)
- {
- changed = 1;
- *dstp = tmp;
- }
- }
- break;
-
- case BITSET_OP_AND_OR:
- for (i = 0; i < size; i++, dstp++)
- {
- bitset_word tmp = (*src1p++ & *src2p++) | *src3p++;
-
- if (*dstp != tmp)
- {
- changed = 1;
- *dstp = tmp;
- }
- }
- break;
-
- case BITSET_OP_ANDN_OR:
- for (i = 0; i < size; i++, dstp++)
- {
- bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++;
-
- if (*dstp != tmp)
- {
- changed = 1;
- *dstp = tmp;
- }
- }
- break;
-
- default:
- abort ();
- }
-
- return changed;
-}
-
-
-/* Vector of operations for single word bitsets. */
-struct bitset_ops_struct sbitset_small_ops = {
- sbitset_set,
- sbitset_reset,
- sbitset_test,
- sbitset_size,
- sbitset_op1,
- sbitset_op2,
- sbitset_op3,
- sbitset_op4,
- sbitset_small_list,
- sbitset_reverse_list,
- NULL,
- BITSET_ARRAY
-};
-
-
-/* Vector of operations for multiple word bitsets. */
-struct bitset_ops_struct sbitset_ops = {
- sbitset_set,
- sbitset_reset,
- sbitset_test,
- sbitset_size,
- sbitset_op1,
- sbitset_op2,
- sbitset_op3,
- sbitset_op4,
- sbitset_list,
- sbitset_reverse_list,
- NULL,
- BITSET_ARRAY
-};
-
-
-int
-sbitset_bytes (n_bits)
- bitset_bindex n_bits;
-{
- unsigned int bytes, size;
-
- size = SBITSET_N_WORDS (n_bits);
- bytes = size * sizeof (bitset_word);
- return sizeof (struct bitset_struct) + bytes - sizeof (bitset_word);
-}
-
-
-bitset
-sbitset_init (bset, n_bits)
- bitset bset;
- bitset_bindex n_bits;
-{
- bitset_windex size;
-
- size = SBITSET_N_WORDS (n_bits);
- SBITSET_N_BITS (bset) = n_bits;
-
- /* Use optimized routines if bitset fits within a single word.
- There is probably little merit if using caching since
- the small bitset will always fit in the cache. */
- if (size == 1)
- bset->b.ops = &sbitset_small_ops;
- else
- bset->b.ops = &sbitset_ops;
-
- bset->b.cindex = 0;
- bset->b.csize = size;
- bset->b.cdata = SBITSET_WORDS (bset);
- return bset;
-}
projects / bison.git / blobdiff