X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/cea532473773fd64de45002a03a507c794e5b1e1..d0d3313d10a28aa6fe77f158d61b84424aa9b3ce:/lib/vbitset.c?ds=sidebyside diff --git a/lib/vbitset.c b/lib/vbitset.c index 8e402408..fbe6e7c0 100644 --- a/lib/vbitset.c +++ b/lib/vbitset.c @@ -1,10 +1,12 @@ /* Variable array bitsets. - Copyright (C) 2002, 2003 Free Software Foundation, Inc. + + Copyright (C) 2002-2006, 2009-2012 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 + 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 + 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, @@ -13,51 +15,45 @@ 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. -*/ + along with this program. If not, see . */ -#ifdef HAVE_CONFIG_H -#include "config.h" -#endif +#include #include "vbitset.h" + #include #include /* This file implements variable size bitsets stored as a variable length array of words. Any unused bits in the last word must be - zero. + zero. Note that binary or ternary operations assume that each bitset operand has the same size. */ -static void vbitset_unused_clear PARAMS ((bitset)); +static void vbitset_unused_clear (bitset); -static void vbitset_set PARAMS ((bitset, bitset_bindex)); -static void vbitset_reset PARAMS ((bitset, bitset_bindex)); -static bool vbitset_test PARAMS ((bitset, bitset_bindex)); -static bitset_bindex vbitset_list PARAMS ((bitset, bitset_bindex *, - bitset_bindex, - bitset_bindex *)); -static bitset_bindex vbitset_list_reverse PARAMS ((bitset, bitset_bindex *, - bitset_bindex, - bitset_bindex *)); +static void vbitset_set (bitset, bitset_bindex); +static void vbitset_reset (bitset, bitset_bindex); +static bool vbitset_test (bitset, bitset_bindex); +static bitset_bindex vbitset_list (bitset, bitset_bindex *, + bitset_bindex, bitset_bindex *); +static bitset_bindex vbitset_list_reverse (bitset, bitset_bindex *, + bitset_bindex, bitset_bindex *); #define VBITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS) #define VBITSET_WORDS(X) ((X)->b.cdata) #define VBITSET_SIZE(X) ((X)->b.csize) #define VBITSET_ASIZE(X) ((X)->v.size) - +#undef min +#undef max #define min(a, b) ((a) > (b) ? (b) : (a)) #define max(a, b) ((a) > (b) ? (a) : (b)) static bitset_bindex -vbitset_resize (src, n_bits) - bitset src; - bitset_bindex n_bits; +vbitset_resize (bitset src, bitset_bindex n_bits) { bitset_windex oldsize; bitset_windex newsize; @@ -72,7 +68,7 @@ vbitset_resize (src, n_bits) { bitset_windex size; - /* The bitset needs to grow. If we already have enough memory + /* The bitset needs to grow. If we already have enough memory allocated, then just zero what we need. */ if (newsize > VBITSET_ASIZE (src)) { @@ -85,13 +81,13 @@ vbitset_resize (src, n_bits) size = newsize; else size = newsize + newsize / 4; - + VBITSET_WORDS (src) = realloc (VBITSET_WORDS (src), size * sizeof (bitset_word)); VBITSET_ASIZE (src) = size; } - memset (VBITSET_WORDS (src) + oldsize, 0, + memset (VBITSET_WORDS (src) + oldsize, 0, (newsize - oldsize) * sizeof (bitset_word)); VBITSET_SIZE (src) = newsize; } @@ -343,8 +339,7 @@ vbitset_unused_clear (dst) static void -vbitset_ones (dst) - bitset dst; +vbitset_ones (bitset dst) { bitset_word *dstp = VBITSET_WORDS (dst); unsigned int bytes; @@ -357,8 +352,7 @@ vbitset_ones (dst) static void -vbitset_zero (dst) - bitset dst; +vbitset_zero (bitset dst) { bitset_word *dstp = VBITSET_WORDS (dst); unsigned int bytes; @@ -370,8 +364,7 @@ vbitset_zero (dst) static bool -vbitset_empty_p (dst) - bitset dst; +vbitset_empty_p (bitset dst) { unsigned int i; bitset_word *dstp = VBITSET_WORDS (dst); @@ -385,9 +378,7 @@ vbitset_empty_p (dst) static void -vbitset_copy1 (dst, src) - bitset dst; - bitset src; +vbitset_copy1 (bitset dst, bitset src) { bitset_word *srcp; bitset_word *dstp; @@ -412,9 +403,7 @@ vbitset_copy1 (dst, src) static void -vbitset_not (dst, src) - bitset dst; - bitset src; +vbitset_not (bitset dst, bitset src) { unsigned int i; bitset_word *srcp; @@ -437,11 +426,9 @@ vbitset_not (dst, src) sizeof (bitset_word) * (dsize - ssize)); } - + static bool -vbitset_equal_p (dst, src) - bitset dst; - bitset src; +vbitset_equal_p (bitset dst, bitset src) { unsigned int i; bitset_word *srcp = VBITSET_WORDS (src); @@ -471,16 +458,14 @@ vbitset_equal_p (dst, src) static bool -vbitset_subset_p (dst, src) - bitset dst; - bitset src; +vbitset_subset_p (bitset dst, bitset src) { unsigned int i; bitset_word *srcp = VBITSET_WORDS (src); bitset_word *dstp = VBITSET_WORDS (dst); bitset_windex ssize = VBITSET_SIZE (src); bitset_windex dsize = VBITSET_SIZE (dst); - + for (i = 0; i < min (ssize, dsize); i++, dstp++, srcp++) if (*dstp != (*srcp | *dstp)) return 0; @@ -497,9 +482,7 @@ vbitset_subset_p (dst, src) static bool -vbitset_disjoint_p (dst, src) - bitset dst; - bitset src; +vbitset_disjoint_p (bitset dst, bitset src) { unsigned int i; bitset_word *srcp = VBITSET_WORDS (src); @@ -516,10 +499,7 @@ vbitset_disjoint_p (dst, src) static void -vbitset_and (dst, src1, src2) - bitset dst; - bitset src1; - bitset src2; +vbitset_and (bitset dst, bitset src1, bitset src2) { unsigned int i; bitset_word *src1p; @@ -540,16 +520,13 @@ vbitset_and (dst, src1, src2) for (i = 0; i < min (ssize1, ssize2); i++) *dstp++ = *src1p++ & *src2p++; - + memset (dstp, 0, sizeof (bitset_word) * (dsize - min (ssize1, ssize2))); } static bool -vbitset_and_cmp (dst, src1, src2) - bitset dst; - bitset src1; - bitset src2; +vbitset_and_cmp (bitset dst, bitset src1, bitset src2) { unsigned int i; int changed = 0; @@ -572,14 +549,14 @@ vbitset_and_cmp (dst, src1, src2) for (i = 0; i < min (ssize1, ssize2); i++, dstp++) { bitset_word tmp = *src1p++ & *src2p++; - + if (*dstp != tmp) { changed = 1; *dstp = tmp; } } - + if (ssize2 > ssize1) { src1p = src2p; @@ -602,10 +579,7 @@ vbitset_and_cmp (dst, src1, src2) static void -vbitset_andn (dst, src1, src2) - bitset dst; - bitset src1; - bitset src2; +vbitset_andn (bitset dst, bitset src1, bitset src2) { unsigned int i; bitset_word *src1p; @@ -626,7 +600,7 @@ vbitset_andn (dst, src1, src2) for (i = 0; i < min (ssize1, ssize2); i++) *dstp++ = *src1p++ & ~(*src2p++); - + if (ssize2 > ssize1) { for (; i < ssize2; i++) @@ -645,10 +619,7 @@ vbitset_andn (dst, src1, src2) static bool -vbitset_andn_cmp (dst, src1, src2) - bitset dst; - bitset src1; - bitset src2; +vbitset_andn_cmp (bitset dst, bitset src1, bitset src2) { unsigned int i; int changed = 0; @@ -671,14 +642,14 @@ vbitset_andn_cmp (dst, src1, src2) for (i = 0; i < min (ssize1, ssize2); i++, dstp++) { bitset_word tmp = *src1p++ & ~(*src2p++); - + if (*dstp != tmp) { changed = 1; *dstp = tmp; } } - + if (ssize2 > ssize1) { for (; i < ssize2; i++, dstp++) @@ -697,7 +668,7 @@ vbitset_andn_cmp (dst, src1, src2) for (; i < ssize1; i++, dstp++) { bitset_word tmp = *src1p++; - + if (*dstp != tmp) { changed = 1; @@ -713,10 +684,7 @@ vbitset_andn_cmp (dst, src1, src2) static void -vbitset_or (dst, src1, src2) - bitset dst; - bitset src1; - bitset src2; +vbitset_or (bitset dst, bitset src1, bitset src2) { unsigned int i; bitset_word *src1p; @@ -737,7 +705,7 @@ vbitset_or (dst, src1, src2) for (i = 0; i < min (ssize1, ssize2); i++) *dstp++ = *src1p++ | *src2p++; - + if (ssize2 > ssize1) { src1p = src2p; @@ -752,10 +720,7 @@ vbitset_or (dst, src1, src2) static bool -vbitset_or_cmp (dst, src1, src2) - bitset dst; - bitset src1; - bitset src2; +vbitset_or_cmp (bitset dst, bitset src1, bitset src2) { unsigned int i; int changed = 0; @@ -778,14 +743,14 @@ vbitset_or_cmp (dst, src1, src2) for (i = 0; i < min (ssize1, ssize2); i++, dstp++) { bitset_word tmp = *src1p++ | *src2p++; - + if (*dstp != tmp) { changed = 1; *dstp = tmp; } } - + if (ssize2 > ssize1) { src1p = src2p; @@ -795,7 +760,7 @@ vbitset_or_cmp (dst, src1, src2) for (; i < ssize1; i++, dstp++) { bitset_word tmp = *src1p++; - + if (*dstp != tmp) { changed = 1; @@ -810,10 +775,7 @@ vbitset_or_cmp (dst, src1, src2) static void -vbitset_xor (dst, src1, src2) - bitset dst; - bitset src1; - bitset src2; +vbitset_xor (bitset dst, bitset src1, bitset src2) { unsigned int i; bitset_word *src1p; @@ -834,7 +796,7 @@ vbitset_xor (dst, src1, src2) for (i = 0; i < min (ssize1, ssize2); i++) *dstp++ = *src1p++ ^ *src2p++; - + if (ssize2 > ssize1) { src1p = src2p; @@ -849,10 +811,7 @@ vbitset_xor (dst, src1, src2) static bool -vbitset_xor_cmp (dst, src1, src2) - bitset dst; - bitset src1; - bitset src2; +vbitset_xor_cmp (bitset dst, bitset src1, bitset src2) { unsigned int i; int changed = 0; @@ -875,14 +834,14 @@ vbitset_xor_cmp (dst, src1, src2) for (i = 0; i < min (ssize1, ssize2); i++, dstp++) { bitset_word tmp = *src1p++ ^ *src2p++; - + if (*dstp != tmp) { changed = 1; *dstp = tmp; } } - + if (ssize2 > ssize1) { src1p = src2p; @@ -892,7 +851,7 @@ vbitset_xor_cmp (dst, src1, src2) for (; i < ssize1; i++, dstp++) { bitset_word tmp = *src1p++; - + if (*dstp != tmp) { changed = 1; @@ -910,11 +869,7 @@ vbitset_xor_cmp (dst, src1, src2) bitsets. */ static void -vbitset_and_or (dst, src1, src2, src3) - bitset dst; - bitset src1; - bitset src2; - bitset src3; +vbitset_and_or (bitset dst, bitset src1, bitset src2, bitset src3) { unsigned int i; bitset_word *src1p; @@ -922,7 +877,7 @@ vbitset_and_or (dst, src1, src2, src3) bitset_word *src3p; bitset_word *dstp; bitset_windex size; - + if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2) || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3)) { @@ -944,11 +899,7 @@ vbitset_and_or (dst, src1, src2, src3) static bool -vbitset_and_or_cmp (dst, src1, src2, src3) - bitset dst; - bitset src1; - bitset src2; - bitset src3; +vbitset_and_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3) { unsigned int i; int changed = 0; @@ -957,7 +908,7 @@ vbitset_and_or_cmp (dst, src1, src2, src3) bitset_word *src3p; bitset_word *dstp; bitset_windex size; - + if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2) || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3)) return bitset_and_or_cmp_ (dst, src1, src2, src3); @@ -969,11 +920,11 @@ vbitset_and_or_cmp (dst, src1, src2, src3) src3p = VBITSET_WORDS (src3); dstp = VBITSET_WORDS (dst); size = VBITSET_SIZE (dst); - + for (i = 0; i < size; i++, dstp++) { bitset_word tmp = (*src1p++ & *src2p++) | *src3p++; - + if (*dstp != tmp) { changed = 1; @@ -985,11 +936,7 @@ vbitset_and_or_cmp (dst, src1, src2, src3) static void -vbitset_andn_or (dst, src1, src2, src3) - bitset dst; - bitset src1; - bitset src2; - bitset src3; +vbitset_andn_or (bitset dst, bitset src1, bitset src2, bitset src3) { unsigned int i; bitset_word *src1p; @@ -997,7 +944,7 @@ vbitset_andn_or (dst, src1, src2, src3) bitset_word *src3p; bitset_word *dstp; bitset_windex size; - + if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2) || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3)) { @@ -1019,11 +966,7 @@ vbitset_andn_or (dst, src1, src2, src3) static bool -vbitset_andn_or_cmp (dst, src1, src2, src3) - bitset dst; - bitset src1; - bitset src2; - bitset src3; +vbitset_andn_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3) { unsigned int i; int changed = 0; @@ -1032,7 +975,7 @@ vbitset_andn_or_cmp (dst, src1, src2, src3) bitset_word *src3p; bitset_word *dstp; bitset_windex size; - + if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2) || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3)) return bitset_andn_or_cmp_ (dst, src1, src2, src3); @@ -1044,11 +987,11 @@ vbitset_andn_or_cmp (dst, src1, src2, src3) src3p = VBITSET_WORDS (src3); dstp = VBITSET_WORDS (dst); size = VBITSET_SIZE (dst); - + for (i = 0; i < size; i++, dstp++) { bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++; - + if (*dstp != tmp) { changed = 1; @@ -1060,11 +1003,7 @@ vbitset_andn_or_cmp (dst, src1, src2, src3) static void -vbitset_or_and (dst, src1, src2, src3) - bitset dst; - bitset src1; - bitset src2; - bitset src3; +vbitset_or_and (bitset dst, bitset src1, bitset src2, bitset src3) { unsigned int i; bitset_word *src1p; @@ -1072,7 +1011,7 @@ vbitset_or_and (dst, src1, src2, src3) bitset_word *src3p; bitset_word *dstp; bitset_windex size; - + if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2) || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3)) { @@ -1087,18 +1026,14 @@ vbitset_or_and (dst, src1, src2, src3) src3p = VBITSET_WORDS (src3); dstp = VBITSET_WORDS (dst); size = VBITSET_SIZE (dst); - + for (i = 0; i < size; i++) *dstp++ = (*src1p++ | *src2p++) & *src3p++; } static bool -vbitset_or_and_cmp (dst, src1, src2, src3) - bitset dst; - bitset src1; - bitset src2; - bitset src3; +vbitset_or_and_cmp (bitset dst, bitset src1, bitset src2, bitset src3) { unsigned int i; int changed = 0; @@ -1107,7 +1042,7 @@ vbitset_or_and_cmp (dst, src1, src2, src3) bitset_word *src3p; bitset_word *dstp; bitset_windex size; - + if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2) || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3)) return bitset_or_and_cmp_ (dst, src1, src2, src3); @@ -1119,11 +1054,11 @@ vbitset_or_and_cmp (dst, src1, src2, src3) src3p = VBITSET_WORDS (src3); dstp = VBITSET_WORDS (dst); size = VBITSET_SIZE (dst); - + for (i = 0; i < size; i++, dstp++) { bitset_word tmp = (*src1p++ | *src2p++) & *src3p++; - + if (*dstp != tmp) { changed = 1; @@ -1134,10 +1069,8 @@ vbitset_or_and_cmp (dst, src1, src2, src3) } -void -vbitset_copy (dst, src) - bitset dst; - bitset src; +static void +vbitset_copy (bitset dst, bitset src) { if (BITSET_COMPATIBLE_ (dst, src)) vbitset_copy1 (dst, src);