]> git.saurik.com Git - bison.git/blobdiff - lib/vbitset.c
projects / bison.git / blobdiff
? search:
summary | shortlog | log | commit | commitdiff | tree
raw | inline | side by side
Merge remote-tracking branch 'origin/maint'
[bison.git] / lib / vbitset.c
diff --git a/lib/vbitset.c b/lib/vbitset.c
index 8b5756ff169563182ab165ab4f4e0a514ed2f375..8c5fd964a1a7c7c230c91c357a9c26e8f1f8732e 100644 (file)
--- a/lib/vbitset.c
+++ b/lib/vbitset.c
@@ -1,7 +1,6 @@
 /* Variable array bitsets.
 
 /* Variable array bitsets.
 
-   Copyright (C) 2002, 2003, 2004, 2005, 2006, 2009, 2010 Free
-   Software Foundation, Inc.
+   Copyright (C) 2002-2006, 2009-2012 Free Software Foundation, Inc.
 
    Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
 
 
    Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
 
@@ -39,9 +38,9 @@ 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 *,
 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 *);
+                                   bitset_bindex, bitset_bindex *);
 static bitset_bindex vbitset_list_reverse (bitset, bitset_bindex *,
 static bitset_bindex vbitset_list_reverse (bitset, bitset_bindex *,
-                                          bitset_bindex, 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_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS)
 #define VBITSET_WORDS(X) ((X)->b.cdata)
@@ -70,38 +69,38 @@ vbitset_resize (bitset src, bitset_bindex n_bits)
       bitset_windex size;
 
       /* The bitset needs to grow.  If we already have enough memory
       bitset_windex size;
 
       /* The bitset needs to grow.  If we already have enough memory
-        allocated, then just zero what we need.  */
+         allocated, then just zero what we need.  */
       if (newsize > VBITSET_ASIZE (src))
       if (newsize > VBITSET_ASIZE (src))
-       {
-         /* We need to allocate more memory.  When oldsize is
-            non-zero this means that we are changing the size, so
-            grow the bitset 25% larger than requested to reduce
-            number of reallocations.  */
-
-         if (oldsize == 0)
-           size = newsize;
-         else
-           size = newsize + newsize / 4;
-
-         VBITSET_WORDS (src)
-           = realloc (VBITSET_WORDS (src), size * sizeof (bitset_word));
-         VBITSET_ASIZE (src) = size;
-       }
+        {
+          /* We need to allocate more memory.  When oldsize is
+             non-zero this means that we are changing the size, so
+             grow the bitset 25% larger than requested to reduce
+             number of reallocations.  */
+
+          if (oldsize == 0)
+            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));
+              (newsize - oldsize) * sizeof (bitset_word));
       VBITSET_SIZE (src) = newsize;
     }
   else
     {
       /* The bitset needs to shrink.  There's no point deallocating
       VBITSET_SIZE (src) = newsize;
     }
   else
     {
       /* The bitset needs to shrink.  There's no point deallocating
-        the memory unless it is shrinking by a reasonable amount.  */
+         the memory unless it is shrinking by a reasonable amount.  */
       if ((oldsize - newsize) >= oldsize / 2)
       if ((oldsize - newsize) >= oldsize / 2)
-       {
-         VBITSET_WORDS (src)
-           = realloc (VBITSET_WORDS (src), newsize * sizeof (bitset_word));
-         VBITSET_ASIZE (src) = newsize;
-       }
+        {
+          VBITSET_WORDS (src)
+            = realloc (VBITSET_WORDS (src), newsize * sizeof (bitset_word));
+          VBITSET_ASIZE (src) = newsize;
+        }
 
       /* Need to prune any excess bits.  FIXME.  */
 
 
       /* Need to prune any excess bits.  FIXME.  */
 
@@ -197,18 +196,18 @@ vbitset_list_reverse (src, list, num, next)
 
       word = srcp[windex] << (BITSET_WORD_BITS - 1 - bitcnt);
       for (; word; bitcnt--)
 
       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;
-       }
+        {
+          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;
     }
       bitoff -= BITSET_WORD_BITS;
       bitcnt = BITSET_WORD_BITS - 1;
     }
@@ -244,80 +243,80 @@ vbitset_list (src, list, num, next)
     {
       /* Many bitsets are zero, so make this common case fast.  */
       for (windex = 0; windex < size && !srcp[windex]; windex++)
     {
       /* Many bitsets are zero, so make this common case fast.  */
       for (windex = 0; windex < size && !srcp[windex]; windex++)
-       continue;
+        continue;
       if (windex >= size)
       if (windex >= size)
-       return 0;
+        return 0;
 
       /* If num is 1, we could speed things up with a binary search
 
       /* If num is 1, we could speed things up with a binary search
-        of the current word.  */
+         of the current word.  */
 
       bitoff = windex * BITSET_WORD_BITS;
     }
   else
     {
       if (bitno >= BITSET_SIZE_ (src))
 
       bitoff = windex * BITSET_WORD_BITS;
     }
   else
     {
       if (bitno >= BITSET_SIZE_ (src))
-       return 0;
+        return 0;
 
       windex = bitno / BITSET_WORD_BITS;
       bitno = bitno % BITSET_WORD_BITS;
 
       if (bitno)
 
       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++;
-       }
+        {
+          /* 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]))
       bitoff = windex * BITSET_WORD_BITS;
     }
 
   for (; windex < size; windex++, bitoff += BITSET_WORD_BITS)
     {
       if (!(word = srcp[windex]))
-       continue;
+        continue;
 
       if ((count + BITSET_WORD_BITS) < num)
 
       if ((count + BITSET_WORD_BITS) < num)
-       {
-         for (bitno = bitoff; word; bitno++)
-           {
-             if (word & 1)
-               list[count++] = bitno;
-             word >>= 1;
-           }
-       }
+        {
+          for (bitno = bitoff; word; bitno++)
+            {
+              if (word & 1)
+                list[count++] = bitno;
+              word >>= 1;
+            }
+        }
       else
       else
-       {
-         for (bitno = bitoff; word; bitno++)
-           {
-             if (word & 1)
-               {
-                 list[count++] = bitno;
-                 if (count >= num)
-                   {
-                     *next = bitno + 1;
-                     return count;
-                   }
-               }
-             word >>= 1;
-           }
-       }
+        {
+          for (bitno = bitoff; word; bitno++)
+            {
+              if (word & 1)
+                {
+                  list[count++] = bitno;
+                  if (count >= num)
+                    {
+                      *next = bitno + 1;
+                      return count;
+                    }
+                }
+              word >>= 1;
+            }
+        }
     }
 
   *next = bitoff;
     }
 
   *next = bitoff;
@@ -399,7 +398,7 @@ vbitset_copy1 (bitset dst, bitset src)
   memcpy (dstp, srcp, sizeof (bitset_word) * ssize);
 
   memset (dstp + sizeof (bitset_word) * ssize, 0,
   memcpy (dstp, srcp, sizeof (bitset_word) * ssize);
 
   memset (dstp + sizeof (bitset_word) * ssize, 0,
-         sizeof (bitset_word) * (dsize - ssize));
+          sizeof (bitset_word) * (dsize - ssize));
 }
 
 
 }
 
 
@@ -424,7 +423,7 @@ vbitset_not (bitset dst, bitset src)
 
   vbitset_unused_clear (dst);
   memset (dstp + sizeof (bitset_word) * ssize, 0,
 
   vbitset_unused_clear (dst);
   memset (dstp + sizeof (bitset_word) * ssize, 0,
-         sizeof (bitset_word) * (dsize - ssize));
+          sizeof (bitset_word) * (dsize - ssize));
 }
 
 
 }
 
 
@@ -439,19 +438,19 @@ vbitset_equal_p (bitset dst, bitset src)
 
   for (i = 0; i < min (ssize, dsize); i++)
       if (*srcp++ != *dstp++)
 
   for (i = 0; i < min (ssize, dsize); i++)
       if (*srcp++ != *dstp++)
-         return 0;
+          return 0;
 
   if (ssize > dsize)
     {
       for (; i < ssize; i++)
 
   if (ssize > dsize)
     {
       for (; i < ssize; i++)
-       if (*srcp++)
-         return 0;
+        if (*srcp++)
+          return 0;
     }
   else
     {
       for (; i < dsize; i++)
     }
   else
     {
       for (; i < dsize; i++)
-       if (*dstp++)
-         return 0;
+        if (*dstp++)
+          return 0;
     }
 
   return 1;
     }
 
   return 1;
@@ -469,13 +468,13 @@ vbitset_subset_p (bitset dst, bitset src)
 
   for (i = 0; i < min (ssize, dsize); i++, dstp++, srcp++)
       if (*dstp != (*srcp | *dstp))
 
   for (i = 0; i < min (ssize, dsize); i++, dstp++, srcp++)
       if (*dstp != (*srcp | *dstp))
-         return 0;
+          return 0;
 
   if (ssize > dsize)
     {
       for (; i < ssize; i++)
 
   if (ssize > dsize)
     {
       for (; i < ssize; i++)
-       if (*srcp++)
-         return 0;
+        if (*srcp++)
+          return 0;
     }
 
   return 1;
     }
 
   return 1;
@@ -493,7 +492,7 @@ vbitset_disjoint_p (bitset dst, bitset src)
 
   for (i = 0; i < min (ssize, dsize); i++)
       if (*srcp++ & *dstp++)
 
   for (i = 0; i < min (ssize, dsize); i++)
       if (*srcp++ & *dstp++)
-         return 0;
+          return 0;
 
   return 1;
 }
 
   return 1;
 }
@@ -552,10 +551,10 @@ vbitset_and_cmp (bitset dst, bitset src1, bitset src2)
       bitset_word tmp = *src1p++ & *src2p++;
 
       if (*dstp != tmp)
       bitset_word tmp = *src1p++ & *src2p++;
 
       if (*dstp != tmp)
-       {
-         changed = 1;
-         *dstp = tmp;
-       }
+        {
+          changed = 1;
+          *dstp = tmp;
+        }
     }
 
   if (ssize2 > ssize1)
     }
 
   if (ssize2 > ssize1)
@@ -567,10 +566,10 @@ vbitset_and_cmp (bitset dst, bitset src1, bitset src2)
   for (; i < ssize1; i++, dstp++)
     {
       if (*dstp != 0)
   for (; i < ssize1; i++, dstp++)
     {
       if (*dstp != 0)
-       {
-         changed = 1;
-         *dstp = 0;
-       }
+        {
+          changed = 1;
+          *dstp = 0;
+        }
     }
 
   memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
     }
 
   memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
@@ -605,14 +604,14 @@ vbitset_andn (bitset dst, bitset src1, bitset src2)
   if (ssize2 > ssize1)
     {
       for (; i < ssize2; i++)
   if (ssize2 > ssize1)
     {
       for (; i < ssize2; i++)
-       *dstp++ = 0;
+        *dstp++ = 0;
 
       memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize2));
     }
   else
     {
       for (; i < ssize1; i++)
 
       memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize2));
     }
   else
     {
       for (; i < ssize1; i++)
-       *dstp++ = *src1p++;
+        *dstp++ = *src1p++;
 
       memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
     }
 
       memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
     }
@@ -645,37 +644,37 @@ vbitset_andn_cmp (bitset dst, bitset src1, bitset src2)
       bitset_word tmp = *src1p++ & ~(*src2p++);
 
       if (*dstp != tmp)
       bitset_word tmp = *src1p++ & ~(*src2p++);
 
       if (*dstp != tmp)
-       {
-         changed = 1;
-         *dstp = tmp;
-       }
+        {
+          changed = 1;
+          *dstp = tmp;
+        }
     }
 
   if (ssize2 > ssize1)
     {
       for (; i < ssize2; i++, dstp++)
     }
 
   if (ssize2 > ssize1)
     {
       for (; i < ssize2; i++, dstp++)
-       {
-         if (*dstp != 0)
-           {
-             changed = 1;
-             *dstp = 0;
-           }
-       }
+        {
+          if (*dstp != 0)
+            {
+              changed = 1;
+              *dstp = 0;
+            }
+        }
 
       memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize2));
     }
   else
     {
       for (; i < ssize1; i++, dstp++)
 
       memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize2));
     }
   else
     {
       for (; i < ssize1; i++, dstp++)
-       {
-         bitset_word tmp = *src1p++;
+        {
+          bitset_word tmp = *src1p++;
 
 
-         if (*dstp != tmp)
-           {
-             changed = 1;
-             *dstp = tmp;
-           }
-       }
+          if (*dstp != tmp)
+            {
+              changed = 1;
+              *dstp = tmp;
+            }
+        }
 
       memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
     }
 
       memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
     }
@@ -746,10 +745,10 @@ vbitset_or_cmp (bitset dst, bitset src1, bitset src2)
       bitset_word tmp = *src1p++ | *src2p++;
 
       if (*dstp != tmp)
       bitset_word tmp = *src1p++ | *src2p++;
 
       if (*dstp != tmp)
-       {
-         changed = 1;
-         *dstp = tmp;
-       }
+        {
+          changed = 1;
+          *dstp = tmp;
+        }
     }
 
   if (ssize2 > ssize1)
     }
 
   if (ssize2 > ssize1)
@@ -763,10 +762,10 @@ vbitset_or_cmp (bitset dst, bitset src1, bitset src2)
       bitset_word tmp = *src1p++;
 
       if (*dstp != tmp)
       bitset_word tmp = *src1p++;
 
       if (*dstp != tmp)
-       {
-         changed = 1;
-         *dstp = tmp;
-       }
+        {
+          changed = 1;
+          *dstp = tmp;
+        }
     }
 
   memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
     }
 
   memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
@@ -837,10 +836,10 @@ vbitset_xor_cmp (bitset dst, bitset src1, bitset src2)
       bitset_word tmp = *src1p++ ^ *src2p++;
 
       if (*dstp != tmp)
       bitset_word tmp = *src1p++ ^ *src2p++;
 
       if (*dstp != tmp)
-       {
-         changed = 1;
-         *dstp = tmp;
-       }
+        {
+          changed = 1;
+          *dstp = tmp;
+        }
     }
 
   if (ssize2 > ssize1)
     }
 
   if (ssize2 > ssize1)
@@ -854,10 +853,10 @@ vbitset_xor_cmp (bitset dst, bitset src1, bitset src2)
       bitset_word tmp = *src1p++;
 
       if (*dstp != tmp)
       bitset_word tmp = *src1p++;
 
       if (*dstp != tmp)
-       {
-         changed = 1;
-         *dstp = tmp;
-       }
+        {
+          changed = 1;
+          *dstp = tmp;
+        }
     }
 
   memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
     }
 
   memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
@@ -927,10 +926,10 @@ vbitset_and_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
       bitset_word tmp = (*src1p++ & *src2p++) | *src3p++;
 
       if (*dstp != tmp)
       bitset_word tmp = (*src1p++ & *src2p++) | *src3p++;
 
       if (*dstp != tmp)
-       {
-         changed = 1;
-         *dstp = tmp;
-       }
+        {
+          changed = 1;
+          *dstp = tmp;
+        }
     }
   return changed;
 }
     }
   return changed;
 }
@@ -994,10 +993,10 @@ vbitset_andn_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
       bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++;
 
       if (*dstp != tmp)
       bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++;
 
       if (*dstp != tmp)
-       {
-         changed = 1;
-         *dstp = tmp;
-       }
+        {
+          changed = 1;
+          *dstp = tmp;
+        }
     }
   return changed;
 }
     }
   return changed;
 }
@@ -1061,10 +1060,10 @@ vbitset_or_and_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
       bitset_word tmp = (*src1p++ | *src2p++) & *src3p++;
 
       if (*dstp != tmp)
       bitset_word tmp = (*src1p++ | *src2p++) & *src3p++;
 
       if (*dstp != tmp)
-       {
-         changed = 1;
-         *dstp = tmp;
-       }
+        {
+          changed = 1;
+          *dstp = tmp;
+        }
     }
   return changed;
 }
     }
   return changed;
 }
bison