bundles/org.simantics.databoard/cpp/DataBoardTest/libantlr3c-3.2/src/antlr3bitset.c

   1 ///\r
   2 /// \file\r
   3 /// Contains the C implementation of ANTLR3 bitsets as adapted from Terence Parr's\r
   4 /// Java implementation.\r
   5 ///\r
   6 \r
   7 // [The "BSD licence"]\r
   8 // Copyright (c) 2005-2009 Jim Idle, Temporal Wave LLC\r
   9 // http://www.temporal-wave.com\r
  10 // http://www.linkedin.com/in/jimidle\r
  11 //\r
  12 // All rights reserved.\r
  13 //\r
  14 // Redistribution and use in source and binary forms, with or without\r
  15 // modification, are permitted provided that the following conditions\r
  16 // are met:\r
  17 // 1. Redistributions of source code must retain the above copyright\r
  18 //    notice, this list of conditions and the following disclaimer.\r
  19 // 2. Redistributions in binary form must reproduce the above copyright\r
  20 //    notice, this list of conditions and the following disclaimer in the\r
  21 //    documentation and/or other materials provided with the distribution.\r
  22 // 3. The name of the author may not be used to endorse or promote products\r
  23 //    derived from this software without specific prior written permission.\r
  24 //\r
  25 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR\r
  26 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES\r
  27 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.\r
  28 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,\r
  29 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT\r
  30 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,\r
  31 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY\r
  32 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT\r
  33 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF\r
  34 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\r
  35 \r
  36 #include    <antlr3bitset.h>\r
  37 \r
  38 // External interface\r
  39 //\r
  40 \r
  41 static  pANTLR3_BITSET  antlr3BitsetClone               (pANTLR3_BITSET inSet);\r
  42 static  pANTLR3_BITSET  antlr3BitsetOR                  (pANTLR3_BITSET bitset1, pANTLR3_BITSET bitset2);\r
  43 static  void                    antlr3BitsetORInPlace   (pANTLR3_BITSET bitset, pANTLR3_BITSET bitset2);\r
  44 static  ANTLR3_UINT32   antlr3BitsetSize                (pANTLR3_BITSET bitset);\r
  45 static  void                    antlr3BitsetAdd                 (pANTLR3_BITSET bitset, ANTLR3_INT32 bit);\r
  46 static  ANTLR3_BOOLEAN  antlr3BitsetEquals              (pANTLR3_BITSET bitset1, pANTLR3_BITSET bitset2);\r
  47 static  ANTLR3_BOOLEAN  antlr3BitsetMember              (pANTLR3_BITSET bitset, ANTLR3_UINT32 bit);\r
  48 static  ANTLR3_UINT32   antlr3BitsetNumBits             (pANTLR3_BITSET bitset);\r
  49 static  void                    antlr3BitsetRemove              (pANTLR3_BITSET bitset, ANTLR3_UINT32 bit);\r
  50 static  ANTLR3_BOOLEAN  antlr3BitsetIsNil               (pANTLR3_BITSET bitset);\r
  51 static  pANTLR3_INT32   antlr3BitsetToIntList   (pANTLR3_BITSET bitset);\r
  52 \r
  53 // Local functions\r
  54 //\r
  55 static  void                    growToInclude           (pANTLR3_BITSET bitset, ANTLR3_INT32 bit);\r
  56 static  void                    grow                            (pANTLR3_BITSET bitset, ANTLR3_INT32 newSize);\r
  57 static  ANTLR3_UINT64   bitMask                         (ANTLR3_UINT32 bitNumber);\r
  58 static  ANTLR3_UINT32   numWordsToHold          (ANTLR3_UINT32 bit);\r
  59 static  ANTLR3_UINT32   wordNumber                      (ANTLR3_UINT32 bit);\r
  60 static  void                    antlr3BitsetFree        (pANTLR3_BITSET bitset);\r
  61 \r
  62 static void\r
  63 antlr3BitsetFree(pANTLR3_BITSET bitset)\r
  64 {\r
  65     if  (bitset->blist.bits != NULL)\r
  66     {\r
  67                 ANTLR3_FREE(bitset->blist.bits);\r
  68                 bitset->blist.bits = NULL;\r
  69     }\r
  70     ANTLR3_FREE(bitset);\r
  71 \r
  72     return;\r
  73 }\r
  74 \r
  75 ANTLR3_API pANTLR3_BITSET\r
  76 antlr3BitsetNew(ANTLR3_UINT32 numBits)\r
  77 {\r
  78         pANTLR3_BITSET  bitset;\r
  79 \r
  80         ANTLR3_UINT32   numelements;\r
  81 \r
  82         // Allocate memory for the bitset structure itself\r
  83         //\r
  84         bitset  = (pANTLR3_BITSET) ANTLR3_MALLOC((size_t)sizeof(ANTLR3_BITSET));\r
  85 \r
  86         if      (bitset == NULL)\r
  87         {\r
  88                 return  NULL;\r
  89         }\r
  90 \r
  91         // Avoid memory thrashing at the up front expense of a few bytes\r
  92         //\r
  93         if      (numBits < (8 * ANTLR3_BITSET_BITS))\r
  94         {\r
  95                 numBits = 8 * ANTLR3_BITSET_BITS;\r
  96         }\r
  97 \r
  98         // No we need to allocate the memory for the number of bits asked for\r
  99         // in multiples of ANTLR3_UINT64. \r
 100         //\r
 101         numelements     = ((numBits -1) >> ANTLR3_BITSET_LOG_BITS) + 1;\r
 102 \r
 103         bitset->blist.bits    = (pANTLR3_BITWORD) ANTLR3_MALLOC((size_t)(numelements * sizeof(ANTLR3_BITWORD)));\r
 104         memset(bitset->blist.bits, 0, (size_t)(numelements * sizeof(ANTLR3_BITWORD)));\r
 105         bitset->blist.length  = numelements;\r
 106 \r
 107         if      (bitset->blist.bits == NULL)\r
 108         {\r
 109                 ANTLR3_FREE(bitset);\r
 110                 return  NULL;\r
 111         }\r
 112 \r
 113         antlr3BitsetSetAPI(bitset);\r
 114 \r
 115 \r
 116         // All seems good\r
 117         //\r
 118         return  bitset;\r
 119 }\r
 120 \r
 121 ANTLR3_API void\r
 122 antlr3BitsetSetAPI(pANTLR3_BITSET bitset)\r
 123 {\r
 124     bitset->clone               =    antlr3BitsetClone;\r
 125     bitset->bor                 =    antlr3BitsetOR;\r
 126     bitset->borInPlace  =    antlr3BitsetORInPlace;\r
 127     bitset->size                =    antlr3BitsetSize;\r
 128     bitset->add                 =    antlr3BitsetAdd;\r
 129     bitset->grow                =    grow;\r
 130     bitset->equals              =    antlr3BitsetEquals;\r
 131     bitset->isMember    =    antlr3BitsetMember;\r
 132     bitset->numBits             =    antlr3BitsetNumBits;\r
 133     bitset->remove              =    antlr3BitsetRemove;\r
 134     bitset->isNilNode           =    antlr3BitsetIsNil;\r
 135     bitset->toIntList   =    antlr3BitsetToIntList;\r
 136 \r
 137     bitset->free                =    antlr3BitsetFree;\r
 138 }\r
 139 \r
 140 ANTLR3_API pANTLR3_BITSET\r
 141 antlr3BitsetCopy(pANTLR3_BITSET_LIST blist)\r
 142 {\r
 143     pANTLR3_BITSET  bitset;\r
 144         int                             numElements;\r
 145 \r
 146     // Allocate memory for the bitset structure itself\r
 147     //\r
 148     bitset  = (pANTLR3_BITSET) ANTLR3_MALLOC((size_t)sizeof(ANTLR3_BITSET));\r
 149 \r
 150     if  (bitset == NULL)\r
 151     {\r
 152                 return  NULL;\r
 153     }\r
 154 \r
 155         numElements = blist->length;\r
 156 \r
 157     // Avoid memory thrashing at the expense of a few more bytes\r
 158     //\r
 159     if  (numElements < 8)\r
 160     {\r
 161                 numElements = 8;\r
 162     }\r
 163 \r
 164     // Install the length in ANTLR3_UINT64 units\r
 165     //\r
 166     bitset->blist.length  = numElements;\r
 167 \r
 168     bitset->blist.bits    = (pANTLR3_BITWORD)ANTLR3_MALLOC((size_t)(numElements * sizeof(ANTLR3_BITWORD)));\r
 169 \r
 170     if  (bitset->blist.bits == NULL)\r
 171     {\r
 172                 ANTLR3_FREE(bitset);\r
 173                 return  NULL;\r
 174     }\r
 175 \r
 176         ANTLR3_MEMCPY(bitset->blist.bits, blist->bits, (ANTLR3_UINT64)(numElements * sizeof(ANTLR3_BITWORD)));\r
 177 \r
 178     // All seems good\r
 179     //\r
 180     return  bitset;\r
 181 }\r
 182 \r
 183 static pANTLR3_BITSET\r
 184 antlr3BitsetClone(pANTLR3_BITSET inSet)\r
 185 {\r
 186     pANTLR3_BITSET  bitset;\r
 187 \r
 188     // Allocate memory for the bitset structure itself\r
 189     //\r
 190     bitset  = antlr3BitsetNew(ANTLR3_BITSET_BITS * inSet->blist.length);\r
 191 \r
 192     if  (bitset == NULL)\r
 193     {\r
 194                 return  NULL;\r
 195     }\r
 196 \r
 197     // Install the actual bits in the source set\r
 198     //\r
 199     ANTLR3_MEMCPY(bitset->blist.bits, inSet->blist.bits, (ANTLR3_UINT64)(inSet->blist.length * sizeof(ANTLR3_BITWORD)));\r
 200 \r
 201     // All seems good\r
 202     //\r
 203     return  bitset;\r
 204 }\r
 205 \r
 206 \r
 207 ANTLR3_API pANTLR3_BITSET\r
 208 antlr3BitsetList(pANTLR3_HASH_TABLE list)\r
 209 {\r
 210     pANTLR3_BITSET              bitSet;\r
 211     pANTLR3_HASH_ENUM   en;\r
 212     pANTLR3_HASH_KEY    key;\r
 213     ANTLR3_UINT64               bit;\r
 214 \r
 215     // We have no idea what exactly is in the list\r
 216     // so create a default bitset and then just add stuff\r
 217     // as we enumerate.\r
 218     //\r
 219     bitSet  = antlr3BitsetNew(0);\r
 220 \r
 221     en          = antlr3EnumNew(list);\r
 222 \r
 223     while   (en->next(en, &key, (void **)(&bit)) == ANTLR3_SUCCESS)\r
 224     {\r
 225                 bitSet->add(bitSet, (ANTLR3_UINT32)bit);\r
 226     }\r
 227     en->free(en);\r
 228 \r
 229     return NULL;\r
 230 }\r
 231 \r
 232 ///\r
 233 /// \brief\r
 234 /// Creates a new bitset with at least one 64 bit bset of bits, but as\r
 235 /// many 64 bit sets as are required.\r
 236 ///\r
 237 /// \param[in] bset\r
 238 /// A variable number of bits to add to the set, ending in -1 (impossible bit).\r
 239 /// \r
 240 /// \returns\r
 241 /// A new bit set with all of the specified bitmaps in it and the API\r
 242 /// initialized.\r
 243 /// \r
 244 /// Call as:\r
 245 ///  - pANTLR3_BITSET = antlrBitsetLoad(bset, bset11, ..., -1);\r
 246 ///  - pANTLR3_BITSET = antlrBitsetOf(-1);  Create empty bitset \r
 247 ///\r
 248 /// \remarks\r
 249 /// Stdargs function - must supply -1 as last paremeter, which is NOT\r
 250 /// added to the set.\r
 251 /// \r
 252 ///\r
 253 ANTLR3_API pANTLR3_BITSET\r
 254 antlr3BitsetLoad(pANTLR3_BITSET_LIST inBits)\r
 255 {\r
 256         pANTLR3_BITSET  bitset;\r
 257         ANTLR3_UINT32  count;\r
 258 \r
 259         // Allocate memory for the bitset structure itself\r
 260         // the input parameter is the bit number (0 based)\r
 261         // to include in the bitset, so we need at at least\r
 262         // bit + 1 bits. If any arguments indicate a \r
 263         // a bit higher than the default number of bits (0 means default size)\r
 264         // then Add() will take care\r
 265         // of it.\r
 266         //\r
 267         bitset  = antlr3BitsetNew(0);\r
 268 \r
 269         if      (bitset == NULL)\r
 270         {\r
 271                 return  NULL;\r
 272         }\r
 273 \r
 274         if      (inBits != NULL)\r
 275         {\r
 276                 // Now we can add the element bits into the set\r
 277                 //\r
 278                 count=0;\r
 279                 while (count < inBits->length)\r
 280                 {\r
 281                         if  (bitset->blist.length <= count)\r
 282                         {\r
 283                                 bitset->grow(bitset, count+1);\r
 284                         }\r
 285 \r
 286                         bitset->blist.bits[count] = *((inBits->bits)+count);\r
 287                         count++;\r
 288                 }\r
 289         }\r
 290 \r
 291         // return the new bitset\r
 292         //\r
 293         return  bitset;\r
 294 }\r
 295 \r
 296 ///\r
 297 /// \brief\r
 298 /// Creates a new bitset with at least one element, but as\r
 299 /// many elements are required.\r
 300 /// \r
 301 /// \param[in] bit\r
 302 /// A variable number of bits to add to the set, ending in -1 (impossible bit).\r
 303 /// \r
 304 /// \returns\r
 305 /// A new bit set with all of the specified elements added into it.\r
 306 /// \r
 307 /// Call as:\r
 308 ///  - pANTLR3_BITSET = antlrBitsetOf(n, n1, n2, -1);\r
 309 ///  - pANTLR3_BITSET = antlrBitsetOf(-1);  Create empty bitset \r
 310 ///\r
 311 /// \remarks\r
 312 /// Stdargs function - must supply -1 as last paremeter, which is NOT\r
 313 /// added to the set.\r
 314 /// \r
 315 ///\r
 316 ANTLR3_API pANTLR3_BITSET\r
 317 antlr3BitsetOf(ANTLR3_INT32 bit, ...)\r
 318 {\r
 319     pANTLR3_BITSET  bitset;\r
 320 \r
 321     va_list ap;\r
 322 \r
 323     // Allocate memory for the bitset structure itself\r
 324     // the input parameter is the bit number (0 based)\r
 325     // to include in the bitset, so we need at at least\r
 326     // bit + 1 bits. If any arguments indicate a \r
 327     // a bit higher than the default number of bits (0 menas default size)\r
 328     // then Add() will take care\r
 329     // of it.\r
 330     //\r
 331     bitset  = antlr3BitsetNew(0);\r
 332 \r
 333     if  (bitset == NULL)\r
 334     {\r
 335                 return  NULL;\r
 336     }\r
 337 \r
 338     // Now we can add the element bits into the set\r
 339     //\r
 340     va_start(ap, bit);\r
 341     while   (bit != -1)\r
 342     {\r
 343                 antlr3BitsetAdd(bitset, bit);\r
 344                 bit = va_arg(ap, ANTLR3_UINT32);\r
 345     }\r
 346     va_end(ap);\r
 347 \r
 348     // return the new bitset\r
 349     //\r
 350     return  bitset;\r
 351 }\r
 352 \r
 353 static pANTLR3_BITSET\r
 354 antlr3BitsetOR(pANTLR3_BITSET bitset1, pANTLR3_BITSET bitset2)\r
 355 {\r
 356     pANTLR3_BITSET  bitset;\r
 357 \r
 358     if  (bitset1 == NULL)\r
 359     {\r
 360                 return antlr3BitsetClone(bitset2);\r
 361     }\r
 362 \r
 363     if  (bitset2 == NULL)\r
 364     {\r
 365                 return  antlr3BitsetClone(bitset1);\r
 366     }\r
 367 \r
 368     // Allocate memory for the newly ordered bitset structure itself.\r
 369     //\r
 370     bitset  = antlr3BitsetClone(bitset1);\r
 371     \r
 372     antlr3BitsetORInPlace(bitset, bitset2);\r
 373 \r
 374     return  bitset;\r
 375 \r
 376 }\r
 377 \r
 378 static void\r
 379 antlr3BitsetAdd(pANTLR3_BITSET bitset, ANTLR3_INT32 bit)\r
 380 {\r
 381     ANTLR3_UINT32   word;\r
 382 \r
 383     word    = wordNumber(bit);\r
 384 \r
 385     if  (word   >= bitset->blist.length)\r
 386     {\r
 387                 growToInclude(bitset, bit);\r
 388     }\r
 389 \r
 390     bitset->blist.bits[word] |= bitMask(bit);\r
 391 \r
 392 }\r
 393 \r
 394 static void\r
 395 grow(pANTLR3_BITSET bitset, ANTLR3_INT32 newSize)\r
 396 {\r
 397     pANTLR3_BITWORD   newBits;\r
 398 \r
 399     // Space for newly sized bitset - TODO: come back to this and use realloc?, it may\r
 400     // be more efficient...\r
 401     //\r
 402     newBits = (pANTLR3_BITWORD) ANTLR3_CALLOC(1, (size_t)(newSize * sizeof(ANTLR3_BITWORD)));\r
 403     if  (bitset->blist.bits != NULL)\r
 404     {\r
 405                 // Copy existing bits\r
 406                 //\r
 407                 ANTLR3_MEMCPY((void *)newBits, (const void *)bitset->blist.bits, (size_t)(bitset->blist.length * sizeof(ANTLR3_BITWORD)));\r
 408 \r
 409                 // Out with the old bits... de de de derrr\r
 410                 //\r
 411                 ANTLR3_FREE(bitset->blist.bits);\r
 412     }\r
 413 \r
 414     // In with the new bits... keerrrang.\r
 415     //\r
 416     bitset->blist.bits      = newBits;\r
 417     bitset->blist.length    = newSize;\r
 418 }\r
 419 \r
 420 static void\r
 421 growToInclude(pANTLR3_BITSET bitset, ANTLR3_INT32 bit)\r
 422 {\r
 423         ANTLR3_UINT32   bl;\r
 424         ANTLR3_UINT32   nw;\r
 425 \r
 426         bl = (bitset->blist.length << 1);\r
 427         nw = numWordsToHold(bit);\r
 428 \r
 429         if      (bl > nw)\r
 430         {\r
 431                 bitset->grow(bitset, bl);\r
 432         }\r
 433         else\r
 434         {\r
 435                 bitset->grow(bitset, nw);\r
 436         }\r
 437 }\r
 438 \r
 439 static void\r
 440 antlr3BitsetORInPlace(pANTLR3_BITSET bitset, pANTLR3_BITSET bitset2)\r
 441 {\r
 442     ANTLR3_UINT32   minimum;\r
 443     ANTLR3_UINT32   i;\r
 444 \r
 445     if  (bitset2 == NULL)\r
 446     {\r
 447                 return;\r
 448     }\r
 449 \r
 450 \r
 451     // First make sure that the target bitset is big enough\r
 452     // for the new bits to be ored in.\r
 453     //\r
 454     if  (bitset->blist.length < bitset2->blist.length)\r
 455     {\r
 456                 growToInclude(bitset, (bitset2->blist.length * sizeof(ANTLR3_BITWORD)));\r
 457     }\r
 458     \r
 459     // Or the miniimum number of bits after any resizing went on\r
 460     //\r
 461     if  (bitset->blist.length < bitset2->blist.length)\r
 462         {\r
 463                 minimum = bitset->blist.length;\r
 464         }\r
 465         else\r
 466         {\r
 467                 minimum = bitset2->blist.length;\r
 468         }\r
 469 \r
 470     for (i = minimum; i > 0; i--)\r
 471     {\r
 472                 bitset->blist.bits[i-1] |= bitset2->blist.bits[i-1];\r
 473     }\r
 474 }\r
 475 \r
 476 static ANTLR3_UINT64\r
 477 bitMask(ANTLR3_UINT32 bitNumber)\r
 478 {\r
 479     return  ((ANTLR3_UINT64)1) << (bitNumber & (ANTLR3_BITSET_MOD_MASK));\r
 480 }\r
 481 \r
 482 static ANTLR3_UINT32\r
 483 antlr3BitsetSize(pANTLR3_BITSET bitset)\r
 484 {\r
 485     ANTLR3_UINT32   degree;\r
 486     ANTLR3_INT32   i;\r
 487     ANTLR3_INT8    bit;\r
 488     \r
 489     // TODO: Come back to this, it may be faster to & with 0x01\r
 490     // then shift right a copy of the 4 bits, than shift left a constant of 1.\r
 491     // But then again, the optimizer might just work this out\r
 492     // anyway.\r
 493     //\r
 494     degree  = 0;\r
 495     for (i = bitset->blist.length - 1; i>= 0; i--)\r
 496     {\r
 497                 if  (bitset->blist.bits[i] != 0)\r
 498                 {\r
 499                         for     (bit = ANTLR3_BITSET_BITS - 1; bit >= 0; bit--)\r
 500                         {\r
 501                                 if  ((bitset->blist.bits[i] & (((ANTLR3_BITWORD)1) << bit)) != 0)\r
 502                                 {\r
 503                                         degree++;\r
 504                                 }\r
 505                         }\r
 506                 }\r
 507     }\r
 508     return degree;\r
 509 }\r
 510 \r
 511 static ANTLR3_BOOLEAN\r
 512 antlr3BitsetEquals(pANTLR3_BITSET bitset1, pANTLR3_BITSET bitset2)\r
 513 {\r
 514     ANTLR3_INT32   minimum;\r
 515     ANTLR3_INT32   i;\r
 516 \r
 517     if  (bitset1 == NULL || bitset2 == NULL)\r
 518     {\r
 519         return  ANTLR3_FALSE;\r
 520     }\r
 521 \r
 522     // Work out the minimum comparison set\r
 523     //\r
 524     if  (bitset1->blist.length < bitset2->blist.length)\r
 525     {\r
 526                 minimum = bitset1->blist.length;\r
 527     }\r
 528     else\r
 529     {\r
 530                 minimum = bitset2->blist.length;\r
 531     }\r
 532 \r
 533     // Make sure explict in common bits are equal\r
 534     //\r
 535     for (i = minimum - 1; i >=0 ; i--)\r
 536     {\r
 537                 if  (bitset1->blist.bits[i] != bitset2->blist.bits[i])\r
 538                 {\r
 539                         return  ANTLR3_FALSE;\r
 540                 }\r
 541     }\r
 542 \r
 543     // Now make sure the bits of the larger set are all turned\r
 544     // off.\r
 545     //\r
 546     if  (bitset1->blist.length > (ANTLR3_UINT32)minimum)\r
 547     {\r
 548                 for (i = minimum ; (ANTLR3_UINT32)i < bitset1->blist.length; i++)\r
 549                 {\r
 550                         if      (bitset1->blist.bits[i] != 0)\r
 551                         {\r
 552                                 return  ANTLR3_FALSE;\r
 553                         }\r
 554                 }\r
 555     }\r
 556     else if (bitset2->blist.length > (ANTLR3_UINT32)minimum)\r
 557     {\r
 558                 for (i = minimum; (ANTLR3_UINT32)i < bitset2->blist.length; i++)\r
 559                 {\r
 560                         if      (bitset2->blist.bits[i] != 0)\r
 561                         {\r
 562                                 return  ANTLR3_FALSE;\r
 563                         }\r
 564                 }\r
 565     }\r
 566 \r
 567     return  ANTLR3_TRUE;\r
 568 }\r
 569 \r
 570 static ANTLR3_BOOLEAN\r
 571 antlr3BitsetMember(pANTLR3_BITSET bitset, ANTLR3_UINT32 bit)\r
 572 {\r
 573     ANTLR3_UINT32    wordNo;\r
 574 \r
 575     wordNo  = wordNumber(bit);\r
 576 \r
 577     if  (wordNo >= bitset->blist.length)\r
 578     {\r
 579                 return  ANTLR3_FALSE;\r
 580     }\r
 581     \r
 582     if  ((bitset->blist.bits[wordNo] & bitMask(bit)) == 0)\r
 583     {\r
 584                 return  ANTLR3_FALSE;\r
 585     }\r
 586     else\r
 587     {\r
 588                 return  ANTLR3_TRUE;\r
 589     }\r
 590 }\r
 591 \r
 592 static void\r
 593 antlr3BitsetRemove(pANTLR3_BITSET bitset, ANTLR3_UINT32 bit)\r
 594 {\r
 595     ANTLR3_UINT32    wordNo;\r
 596 \r
 597     wordNo  = wordNumber(bit);\r
 598 \r
 599     if  (wordNo < bitset->blist.length)\r
 600     {\r
 601                 bitset->blist.bits[wordNo] &= ~(bitMask(bit));\r
 602     }\r
 603 }\r
 604 static ANTLR3_BOOLEAN\r
 605 antlr3BitsetIsNil(pANTLR3_BITSET bitset)\r
 606 {\r
 607    ANTLR3_INT32    i;\r
 608 \r
 609    for  (i = bitset->blist.length -1; i>= 0; i--)\r
 610    {\r
 611        if   (bitset->blist.bits[i] != 0)\r
 612        {\r
 613                         return ANTLR3_FALSE;\r
 614        }\r
 615    }\r
 616    \r
 617    return   ANTLR3_TRUE;\r
 618 }\r
 619 \r
 620 static ANTLR3_UINT32\r
 621 numWordsToHold(ANTLR3_UINT32 bit)\r
 622 {\r
 623     return  (bit >> ANTLR3_BITSET_LOG_BITS) + 1;\r
 624 }\r
 625 \r
 626 static  ANTLR3_UINT32\r
 627 wordNumber(ANTLR3_UINT32 bit)\r
 628 {\r
 629     return  bit >> ANTLR3_BITSET_LOG_BITS;\r
 630 }\r
 631 \r
 632 static ANTLR3_UINT32\r
 633 antlr3BitsetNumBits(pANTLR3_BITSET bitset)\r
 634 {\r
 635     return  bitset->blist.length << ANTLR3_BITSET_LOG_BITS;\r
 636 }\r
 637 \r
 638 /** Produce an integer list of all the bits that are turned on\r
 639  *  in this bitset. Used for error processing in the main as the bitset\r
 640  *  reresents a number of integer tokens which we use for follow sets\r
 641  *  and so on.\r
 642  *\r
 643  *  The first entry is the number of elements following in the list.\r
 644  */\r
 645 static  pANTLR3_INT32   \r
 646 antlr3BitsetToIntList   (pANTLR3_BITSET bitset)\r
 647 {\r
 648     ANTLR3_UINT32   numInts;        // How many integers we will need\r
 649     ANTLR3_UINT32   numBits;        // How many bits are in the set\r
 650     ANTLR3_UINT32   i;\r
 651     ANTLR3_UINT32   index;\r
 652 \r
 653     pANTLR3_INT32  intList;\r
 654 \r
 655     numInts = bitset->size(bitset) + 1;\r
 656     numBits = bitset->numBits(bitset);\r
 657  \r
 658     intList = (pANTLR3_INT32)ANTLR3_MALLOC(numInts * sizeof(ANTLR3_INT32));\r
 659 \r
 660     if  (intList == NULL)\r
 661     {\r
 662                 return NULL;    // Out of memory\r
 663     }\r
 664 \r
 665     intList[0] = numInts;\r
 666 \r
 667     // Enumerate the bits that are turned on\r
 668     //\r
 669     for (i = 0, index = 1; i<numBits; i++)\r
 670     {\r
 671                 if  (bitset->isMember(bitset, i) == ANTLR3_TRUE)\r
 672                 {\r
 673                         intList[index++]    = i;\r
 674                 }\r
 675     }\r
 676 \r
 677     // Result set\r
 678     //\r
 679     return  intList;\r
 680 }\r
 681 \r