| Index: bison/src/bison/2.4.1/bison-2.4.1-src/lib/abitset.c
|
| ===================================================================
|
| --- bison/src/bison/2.4.1/bison-2.4.1-src/lib/abitset.c (revision 0)
|
| +++ bison/src/bison/2.4.1/bison-2.4.1-src/lib/abitset.c (revision 0)
|
| @@ -0,0 +1,825 @@
|
| +/* Array bitsets.
|
| + Copyright (C) 2002, 2003, 2006 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 3 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, see <http://www.gnu.org/licenses/>. */
|
| +
|
| +#include <config.h>
|
| +
|
| +#include "abitset.h"
|
| +#include <stddef.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. */
|
| +
|
| +#define ABITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS)
|
| +#define ABITSET_WORDS(X) ((X)->a.words)
|
| +
|
| +
|
| +static bitset_bindex
|
| +abitset_resize (bitset src, bitset_bindex size)
|
| +{
|
| + /* These bitsets have a fixed size. */
|
| + if (BITSET_SIZE_ (src) != size)
|
| + abort ();
|
| +
|
| + return size;
|
| +}
|
| +
|
| +/* 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 bitset_bindex
|
| +abitset_small_list (bitset src, bitset_bindex *list,
|
| + bitset_bindex num, bitset_bindex *next)
|
| +{
|
| + bitset_bindex bitno;
|
| + bitset_bindex count;
|
| + bitset_windex size;
|
| + bitset_word word;
|
| +
|
| + word = ABITSET_WORDS (src)[0];
|
| +
|
| + /* Short circuit common case. */
|
| + if (!word)
|
| + return 0;
|
| +
|
| + size = BITSET_SIZE_ (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
|
| +abitset_set (bitset dst ATTRIBUTE_UNUSED, bitset_bindex bitno ATTRIBUTE_UNUSED)
|
| +{
|
| + /* This should never occur for abitsets since we should always hit
|
| + the cache. It is likely someone is trying to access outside the
|
| + bounds of the bitset. */
|
| + abort ();
|
| +}
|
| +
|
| +
|
| +/* Reset bit BITNO in bitset DST. */
|
| +static void
|
| +abitset_reset (bitset dst ATTRIBUTE_UNUSED,
|
| + bitset_bindex bitno ATTRIBUTE_UNUSED)
|
| +{
|
| + /* This should never occur for abitsets since we should always hit
|
| + the cache. It is likely someone is trying to access outside the
|
| + bounds of the bitset. Since the bit is zero anyway, let it pass. */
|
| +}
|
| +
|
| +
|
| +/* Test bit BITNO in bitset SRC. */
|
| +static bool
|
| +abitset_test (bitset src ATTRIBUTE_UNUSED,
|
| + bitset_bindex bitno ATTRIBUTE_UNUSED)
|
| +{
|
| + /* This should never occur for abitsets since we should always
|
| + hit the cache. */
|
| + return false;
|
| +}
|
| +
|
| +
|
| +/* 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 bitset_bindex
|
| +abitset_list_reverse (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 *srcp = ABITSET_WORDS (src);
|
| + bitset_bindex n_bits = BITSET_SIZE_ (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;
|
| +
|
| + do
|
| + {
|
| + bitset_word word;
|
| +
|
| + 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;
|
| + }
|
| + bitoff -= BITSET_WORD_BITS;
|
| + bitcnt = BITSET_WORD_BITS - 1;
|
| + }
|
| + while (windex--);
|
| +
|
| + *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 bitset_bindex
|
| +abitset_list (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 = ABITSET_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 >= BITSET_SIZE_ (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
|
| +abitset_unused_clear (bitset dst)
|
| +{
|
| + unsigned int last_bit;
|
| +
|
| + last_bit = BITSET_SIZE_ (dst) % BITSET_WORD_BITS;
|
| + if (last_bit)
|
| + ABITSET_WORDS (dst)[dst->b.csize - 1] &=
|
| + ((bitset_word) 1 << last_bit) - 1;
|
| +}
|
| +
|
| +
|
| +static void
|
| +abitset_ones (bitset dst)
|
| +{
|
| + bitset_word *dstp = ABITSET_WORDS (dst);
|
| + size_t bytes;
|
| +
|
| + bytes = sizeof (bitset_word) * dst->b.csize;
|
| +
|
| + memset (dstp, -1, bytes);
|
| + abitset_unused_clear (dst);
|
| +}
|
| +
|
| +
|
| +static void
|
| +abitset_zero (bitset dst)
|
| +{
|
| + bitset_word *dstp = ABITSET_WORDS (dst);
|
| + size_t bytes;
|
| +
|
| + bytes = sizeof (bitset_word) * dst->b.csize;
|
| +
|
| + memset (dstp, 0, bytes);
|
| +}
|
| +
|
| +
|
| +static bool
|
| +abitset_empty_p (bitset dst)
|
| +{
|
| + bitset_windex i;
|
| + bitset_word *dstp = ABITSET_WORDS (dst);
|
| +
|
| + for (i = 0; i < dst->b.csize; i++)
|
| + if (dstp[i])
|
| + return false;
|
| +
|
| + return true;
|
| +}
|
| +
|
| +
|
| +static void
|
| +abitset_copy1 (bitset dst, bitset src)
|
| +{
|
| + bitset_word *srcp = ABITSET_WORDS (src);
|
| + bitset_word *dstp = ABITSET_WORDS (dst);
|
| + bitset_windex size = dst->b.csize;
|
| +
|
| + if (srcp == dstp)
|
| + return;
|
| + memcpy (dstp, srcp, sizeof (bitset_word) * size);
|
| +}
|
| +
|
| +
|
| +static void
|
| +abitset_not (bitset dst, bitset src)
|
| +{
|
| + bitset_windex i;
|
| + bitset_word *srcp = ABITSET_WORDS (src);
|
| + bitset_word *dstp = ABITSET_WORDS (dst);
|
| + bitset_windex size = dst->b.csize;
|
| +
|
| + for (i = 0; i < size; i++)
|
| + *dstp++ = ~(*srcp++);
|
| + abitset_unused_clear (dst);
|
| +}
|
| +
|
| +
|
| +static bool
|
| +abitset_equal_p (bitset dst, bitset src)
|
| +{
|
| + bitset_windex i;
|
| + bitset_word *srcp = ABITSET_WORDS (src);
|
| + bitset_word *dstp = ABITSET_WORDS (dst);
|
| + bitset_windex size = dst->b.csize;
|
| +
|
| + for (i = 0; i < size; i++)
|
| + if (*srcp++ != *dstp++)
|
| + return false;
|
| + return true;
|
| +}
|
| +
|
| +
|
| +static bool
|
| +abitset_subset_p (bitset dst, bitset src)
|
| +{
|
| + bitset_windex i;
|
| + bitset_word *srcp = ABITSET_WORDS (src);
|
| + bitset_word *dstp = ABITSET_WORDS (dst);
|
| + bitset_windex size = dst->b.csize;
|
| +
|
| + for (i = 0; i < size; i++, dstp++, srcp++)
|
| + if (*dstp != (*srcp | *dstp))
|
| + return false;
|
| + return true;
|
| +}
|
| +
|
| +
|
| +static bool
|
| +abitset_disjoint_p (bitset dst, bitset src)
|
| +{
|
| + bitset_windex i;
|
| + bitset_word *srcp = ABITSET_WORDS (src);
|
| + bitset_word *dstp = ABITSET_WORDS (dst);
|
| + bitset_windex size = dst->b.csize;
|
| +
|
| + for (i = 0; i < size; i++)
|
| + if (*srcp++ & *dstp++)
|
| + return false;
|
| +
|
| + return true;
|
| +}
|
| +
|
| +
|
| +static void
|
| +abitset_and (bitset dst, bitset src1, bitset src2)
|
| +{
|
| + bitset_windex i;
|
| + bitset_word *src1p = ABITSET_WORDS (src1);
|
| + bitset_word *src2p = ABITSET_WORDS (src2);
|
| + bitset_word *dstp = ABITSET_WORDS (dst);
|
| + bitset_windex size = dst->b.csize;
|
| +
|
| + for (i = 0; i < size; i++)
|
| + *dstp++ = *src1p++ & *src2p++;
|
| +}
|
| +
|
| +
|
| +static bool
|
| +abitset_and_cmp (bitset dst, bitset src1, bitset src2)
|
| +{
|
| + bitset_windex i;
|
| + bool changed = false;
|
| + bitset_word *src1p = ABITSET_WORDS (src1);
|
| + bitset_word *src2p = ABITSET_WORDS (src2);
|
| + bitset_word *dstp = ABITSET_WORDS (dst);
|
| + bitset_windex size = dst->b.csize;
|
| +
|
| + for (i = 0; i < size; i++, dstp++)
|
| + {
|
| + bitset_word tmp = *src1p++ & *src2p++;
|
| +
|
| + if (*dstp != tmp)
|
| + {
|
| + changed = true;
|
| + *dstp = tmp;
|
| + }
|
| + }
|
| + return changed;
|
| +}
|
| +
|
| +
|
| +static void
|
| +abitset_andn (bitset dst, bitset src1, bitset src2)
|
| +{
|
| + bitset_windex i;
|
| + bitset_word *src1p = ABITSET_WORDS (src1);
|
| + bitset_word *src2p = ABITSET_WORDS (src2);
|
| + bitset_word *dstp = ABITSET_WORDS (dst);
|
| + bitset_windex size = dst->b.csize;
|
| +
|
| + for (i = 0; i < size; i++)
|
| + *dstp++ = *src1p++ & ~(*src2p++);
|
| +}
|
| +
|
| +
|
| +static bool
|
| +abitset_andn_cmp (bitset dst, bitset src1, bitset src2)
|
| +{
|
| + bitset_windex i;
|
| + bool changed = false;
|
| + bitset_word *src1p = ABITSET_WORDS (src1);
|
| + bitset_word *src2p = ABITSET_WORDS (src2);
|
| + bitset_word *dstp = ABITSET_WORDS (dst);
|
| + bitset_windex size = dst->b.csize;
|
| +
|
| + for (i = 0; i < size; i++, dstp++)
|
| + {
|
| + bitset_word tmp = *src1p++ & ~(*src2p++);
|
| +
|
| + if (*dstp != tmp)
|
| + {
|
| + changed = true;
|
| + *dstp = tmp;
|
| + }
|
| + }
|
| + return changed;
|
| +}
|
| +
|
| +
|
| +static void
|
| +abitset_or (bitset dst, bitset src1, bitset src2)
|
| +{
|
| + bitset_windex i;
|
| + bitset_word *src1p = ABITSET_WORDS (src1);
|
| + bitset_word *src2p = ABITSET_WORDS (src2);
|
| + bitset_word *dstp = ABITSET_WORDS (dst);
|
| + bitset_windex size = dst->b.csize;
|
| +
|
| + for (i = 0; i < size; i++)
|
| + *dstp++ = *src1p++ | *src2p++;
|
| +}
|
| +
|
| +
|
| +static bool
|
| +abitset_or_cmp (bitset dst, bitset src1, bitset src2)
|
| +{
|
| + bitset_windex i;
|
| + bool changed = false;
|
| + bitset_word *src1p = ABITSET_WORDS (src1);
|
| + bitset_word *src2p = ABITSET_WORDS (src2);
|
| + bitset_word *dstp = ABITSET_WORDS (dst);
|
| + bitset_windex size = dst->b.csize;
|
| +
|
| + for (i = 0; i < size; i++, dstp++)
|
| + {
|
| + bitset_word tmp = *src1p++ | *src2p++;
|
| +
|
| + if (*dstp != tmp)
|
| + {
|
| + changed = true;
|
| + *dstp = tmp;
|
| + }
|
| + }
|
| + return changed;
|
| +}
|
| +
|
| +
|
| +static void
|
| +abitset_xor (bitset dst, bitset src1, bitset src2)
|
| +{
|
| + bitset_windex i;
|
| + bitset_word *src1p = ABITSET_WORDS (src1);
|
| + bitset_word *src2p = ABITSET_WORDS (src2);
|
| + bitset_word *dstp = ABITSET_WORDS (dst);
|
| + bitset_windex size = dst->b.csize;
|
| +
|
| + for (i = 0; i < size; i++)
|
| + *dstp++ = *src1p++ ^ *src2p++;
|
| +}
|
| +
|
| +
|
| +static bool
|
| +abitset_xor_cmp (bitset dst, bitset src1, bitset src2)
|
| +{
|
| + bitset_windex i;
|
| + bool changed = false;
|
| + bitset_word *src1p = ABITSET_WORDS (src1);
|
| + bitset_word *src2p = ABITSET_WORDS (src2);
|
| + bitset_word *dstp = ABITSET_WORDS (dst);
|
| + bitset_windex size = dst->b.csize;
|
| +
|
| + for (i = 0; i < size; i++, dstp++)
|
| + {
|
| + bitset_word tmp = *src1p++ ^ *src2p++;
|
| +
|
| + if (*dstp != tmp)
|
| + {
|
| + changed = true;
|
| + *dstp = tmp;
|
| + }
|
| + }
|
| + return changed;
|
| +}
|
| +
|
| +
|
| +static void
|
| +abitset_and_or (bitset dst, bitset src1, bitset src2, bitset src3)
|
| +{
|
| + bitset_windex i;
|
| + bitset_word *src1p = ABITSET_WORDS (src1);
|
| + bitset_word *src2p = ABITSET_WORDS (src2);
|
| + bitset_word *src3p = ABITSET_WORDS (src3);
|
| + bitset_word *dstp = ABITSET_WORDS (dst);
|
| + bitset_windex size = dst->b.csize;
|
| +
|
| + for (i = 0; i < size; i++)
|
| + *dstp++ = (*src1p++ & *src2p++) | *src3p++;
|
| +}
|
| +
|
| +
|
| +static bool
|
| +abitset_and_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
|
| +{
|
| + bitset_windex i;
|
| + bool changed = false;
|
| + bitset_word *src1p = ABITSET_WORDS (src1);
|
| + bitset_word *src2p = ABITSET_WORDS (src2);
|
| + bitset_word *src3p = ABITSET_WORDS (src3);
|
| + bitset_word *dstp = ABITSET_WORDS (dst);
|
| + bitset_windex size = dst->b.csize;
|
| +
|
| + for (i = 0; i < size; i++, dstp++)
|
| + {
|
| + bitset_word tmp = (*src1p++ & *src2p++) | *src3p++;
|
| +
|
| + if (*dstp != tmp)
|
| + {
|
| + changed = true;
|
| + *dstp = tmp;
|
| + }
|
| + }
|
| + return changed;
|
| +}
|
| +
|
| +
|
| +static void
|
| +abitset_andn_or (bitset dst, bitset src1, bitset src2, bitset src3)
|
| +{
|
| + bitset_windex i;
|
| + bitset_word *src1p = ABITSET_WORDS (src1);
|
| + bitset_word *src2p = ABITSET_WORDS (src2);
|
| + bitset_word *src3p = ABITSET_WORDS (src3);
|
| + bitset_word *dstp = ABITSET_WORDS (dst);
|
| + bitset_windex size = dst->b.csize;
|
| +
|
| + for (i = 0; i < size; i++)
|
| + *dstp++ = (*src1p++ & ~(*src2p++)) | *src3p++;
|
| +}
|
| +
|
| +
|
| +static bool
|
| +abitset_andn_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
|
| +{
|
| + bitset_windex i;
|
| + bool changed = false;
|
| + bitset_word *src1p = ABITSET_WORDS (src1);
|
| + bitset_word *src2p = ABITSET_WORDS (src2);
|
| + bitset_word *src3p = ABITSET_WORDS (src3);
|
| + bitset_word *dstp = ABITSET_WORDS (dst);
|
| + bitset_windex size = dst->b.csize;
|
| +
|
| + for (i = 0; i < size; i++, dstp++)
|
| + {
|
| + bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++;
|
| +
|
| + if (*dstp != tmp)
|
| + {
|
| + changed = true;
|
| + *dstp = tmp;
|
| + }
|
| + }
|
| + return changed;
|
| +}
|
| +
|
| +
|
| +static void
|
| +abitset_or_and (bitset dst, bitset src1, bitset src2, bitset src3)
|
| +{
|
| + bitset_windex i;
|
| + bitset_word *src1p = ABITSET_WORDS (src1);
|
| + bitset_word *src2p = ABITSET_WORDS (src2);
|
| + bitset_word *src3p = ABITSET_WORDS (src3);
|
| + bitset_word *dstp = ABITSET_WORDS (dst);
|
| + bitset_windex size = dst->b.csize;
|
| +
|
| + for (i = 0; i < size; i++)
|
| + *dstp++ = (*src1p++ | *src2p++) & *src3p++;
|
| +}
|
| +
|
| +
|
| +static bool
|
| +abitset_or_and_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
|
| +{
|
| + bitset_windex i;
|
| + bool changed = false;
|
| + bitset_word *src1p = ABITSET_WORDS (src1);
|
| + bitset_word *src2p = ABITSET_WORDS (src2);
|
| + bitset_word *src3p = ABITSET_WORDS (src3);
|
| + bitset_word *dstp = ABITSET_WORDS (dst);
|
| + bitset_windex size = dst->b.csize;
|
| +
|
| + for (i = 0; i < size; i++, dstp++)
|
| + {
|
| + bitset_word tmp = (*src1p++ | *src2p++) & *src3p++;
|
| +
|
| + if (*dstp != tmp)
|
| + {
|
| + changed = true;
|
| + *dstp = tmp;
|
| + }
|
| + }
|
| + return changed;
|
| +}
|
| +
|
| +
|
| +static void
|
| +abitset_copy (bitset dst, bitset src)
|
| +{
|
| + if (BITSET_COMPATIBLE_ (dst, src))
|
| + abitset_copy1 (dst, src);
|
| + else
|
| + bitset_copy_ (dst, src);
|
| +}
|
| +
|
| +
|
| +/* Vector of operations for single word bitsets. */
|
| +struct bitset_vtable abitset_small_vtable = {
|
| + abitset_set,
|
| + abitset_reset,
|
| + bitset_toggle_,
|
| + abitset_test,
|
| + abitset_resize,
|
| + bitset_size_,
|
| + bitset_count_,
|
| + abitset_empty_p,
|
| + abitset_ones,
|
| + abitset_zero,
|
| + abitset_copy,
|
| + abitset_disjoint_p,
|
| + abitset_equal_p,
|
| + abitset_not,
|
| + abitset_subset_p,
|
| + abitset_and,
|
| + abitset_and_cmp,
|
| + abitset_andn,
|
| + abitset_andn_cmp,
|
| + abitset_or,
|
| + abitset_or_cmp,
|
| + abitset_xor,
|
| + abitset_xor_cmp,
|
| + abitset_and_or,
|
| + abitset_and_or_cmp,
|
| + abitset_andn_or,
|
| + abitset_andn_or_cmp,
|
| + abitset_or_and,
|
| + abitset_or_and_cmp,
|
| + abitset_small_list,
|
| + abitset_list_reverse,
|
| + NULL,
|
| + BITSET_ARRAY
|
| +};
|
| +
|
| +
|
| +/* Vector of operations for multiple word bitsets. */
|
| +struct bitset_vtable abitset_vtable = {
|
| + abitset_set,
|
| + abitset_reset,
|
| + bitset_toggle_,
|
| + abitset_test,
|
| + abitset_resize,
|
| + bitset_size_,
|
| + bitset_count_,
|
| + abitset_empty_p,
|
| + abitset_ones,
|
| + abitset_zero,
|
| + abitset_copy,
|
| + abitset_disjoint_p,
|
| + abitset_equal_p,
|
| + abitset_not,
|
| + abitset_subset_p,
|
| + abitset_and,
|
| + abitset_and_cmp,
|
| + abitset_andn,
|
| + abitset_andn_cmp,
|
| + abitset_or,
|
| + abitset_or_cmp,
|
| + abitset_xor,
|
| + abitset_xor_cmp,
|
| + abitset_and_or,
|
| + abitset_and_or_cmp,
|
| + abitset_andn_or,
|
| + abitset_andn_or_cmp,
|
| + abitset_or_and,
|
| + abitset_or_and_cmp,
|
| + abitset_list,
|
| + abitset_list_reverse,
|
| + NULL,
|
| + BITSET_ARRAY
|
| +};
|
| +
|
| +
|
| +size_t
|
| +abitset_bytes (bitset_bindex n_bits)
|
| +{
|
| + bitset_windex size;
|
| + size_t bytes;
|
| + size_t header_size = offsetof (union bitset_union, a.words);
|
| + struct bitset_align_struct { char a; union bitset_union b; };
|
| + size_t bitset_alignment = offsetof (struct bitset_align_struct, b);
|
| +
|
| + size = ABITSET_N_WORDS (n_bits);
|
| + bytes = header_size + size * sizeof (bitset_word);
|
| +
|
| + /* Align the size properly for a vector of abitset objects. */
|
| + if (header_size % bitset_alignment != 0
|
| + || sizeof (bitset_word) % bitset_alignment != 0)
|
| + {
|
| + bytes += bitset_alignment - 1;
|
| + bytes -= bytes % bitset_alignment;
|
| + }
|
| +
|
| + return bytes;
|
| +}
|
| +
|
| +
|
| +bitset
|
| +abitset_init (bitset bset, bitset_bindex n_bits)
|
| +{
|
| + bitset_windex size;
|
| +
|
| + size = ABITSET_N_WORDS (n_bits);
|
| + BITSET_NBITS_ (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.vtable = &abitset_small_vtable;
|
| + else
|
| + bset->b.vtable = &abitset_vtable;
|
| +
|
| + bset->b.cindex = 0;
|
| + bset->b.csize = size;
|
| + bset->b.cdata = ABITSET_WORDS (bset);
|
| + return bset;
|
| +}
|
|
|
| Property changes on: bison\src\bison\2.4.1\bison-2.4.1-src\lib\abitset.c
|
| ___________________________________________________________________
|
| Added: svn:eol-style
|
| + LF
|
|
|
|
|