1 /** 2 * \file 3 * Defines the basic structures of an ANTLR3 bitset. this is a C version of the 4 * cut down Bitset class provided with the java version of antlr 3. 5 * 6 * 7 */ 8 #ifndef _ANTLR3_BITSET_HPP 9 #define _ANTLR3_BITSET_HPP 10 11 // [The "BSD licence"] 12 // Copyright (c) 2005-2009 Gokulakannan Somasundaram, ElectronDB 13 14 // 15 // All rights reserved. 16 // 17 // Redistribution and use in source and binary forms, with or without 18 // modification, are permitted provided that the following conditions 19 // are met: 20 // 1. Redistributions of source code must retain the above copyright 21 // notice, this list of conditions and the following disclaimer. 22 // 2. Redistributions in binary form must reproduce the above copyright 23 // notice, this list of conditions and the following disclaimer in the 24 // documentation and/or other materials provided with the distribution. 25 // 3. The name of the author may not be used to endorse or promote products 26 // derived from this software without specific prior written permission. 27 // 28 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 29 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 30 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 31 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 32 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 33 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 34 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 35 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 36 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 37 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 38 39 #include "antlr3defs.hpp" 40 41 ANTLR_BEGIN_NAMESPACE() 42 43 /** How many bits in the elements 44 */ 45 static const ANTLR_UINT32 ANTLR_BITSET_BITS = 64; 46 47 /** How many bits in a nible of bits 48 */ 49 static const ANTLR_UINT32 ANTLR_BITSET_NIBBLE = 4; 50 51 /** log2 of ANTLR3_BITSET_BITS 2^ANTLR3_BITSET_LOG_BITS = ANTLR3_BITSET_BITS 52 */ 53 static const ANTLR_UINT32 ANTLR_BITSET_LOG_BITS = 6; 54 55 /** We will often need to do a mod operator (i mod nbits). 56 * For powers of two, this mod operation is the 57 * same as: 58 * - (i & (nbits-1)). 59 * 60 * Since mod is relatively slow, we use an easily 61 * precomputed mod mask to do the mod instead. 62 */ 63 static const ANTLR_UINT32 ANTLR_BITSET_MOD_MASK = ANTLR_BITSET_BITS - 1; 64 65 template <class ImplTraits> 66 class BitsetList : public ImplTraits::AllocPolicyType 67 { 68 public: 69 typedef typename ImplTraits::AllocPolicyType AllocPolicyType; 70 typedef typename ImplTraits::BitsetType BitsetType; 71 72 private: 73 /// Pointer to the allocated array of bits for this bit set, which 74 /// is an array of 64 bit elements (of the architecture). If we find a 75 /// machine/C compiler that does not know anything about 64 bit values 76 /// then it should be easy enough to produce a 32 bit (or less) version 77 /// of the bitset code. Note that the pointer here may be static if laid down 78 /// by the code generation, and it must be copied if it is to be manipulated 79 /// to perform followset calculations. 80 /// 81 ANTLR_BITWORD* m_bits; 82 83 /// Length of the current bit set in ANTLR3_UINT64 units. 84 /// 85 ANTLR_UINT32 m_length; 86 87 public: 88 BitsetList(); 89 BitsetList( ANTLR_BITWORD* bits, ANTLR_UINT32 length ); 90 91 ANTLR_BITWORD* get_bits() const; 92 ANTLR_UINT32 get_length() const; 93 void set_bits( ANTLR_BITWORD* bits ); 94 void set_length( ANTLR_UINT32 length ); 95 96 /// 97 /// \brief 98 /// Creates a new bitset with at least one 64 bit bset of bits, but as 99 /// many 64 bit sets as are required. 100 /// 101 /// \param[in] bset 102 /// A variable number of bits to add to the set, ending in -1 (impossible bit). 103 /// 104 /// \returns 105 /// A new bit set with all of the specified bitmaps in it and the API 106 /// initialized. 107 /// 108 /// Call as: 109 /// - pANTLR3_BITSET = antlrBitsetLoad(bset, bset11, ..., -1); 110 /// - pANTLR3_BITSET = antlrBitsetOf(-1); Create empty bitset 111 /// 112 /// \remarks 113 /// Stdargs function - must supply -1 as last paremeter, which is NOT 114 /// added to the set. 115 /// 116 /// 117 BitsetType* bitsetLoad(); 118 119 BitsetType* bitsetCopy(); 120 121 }; 122 123 template <class ImplTraits> 124 class Bitset : public ImplTraits::AllocPolicyType 125 { 126 public: 127 typedef typename ImplTraits::AllocPolicyType AllocPolicyType; 128 typedef typename AllocPolicyType::template ListType<ANTLR_UINT32> IntListType; 129 typedef typename ImplTraits::BitsetListType BitsetListType; 130 131 private: 132 /// The actual bits themselves 133 /// 134 BitsetListType m_blist; 135 136 public: 137 Bitset( ANTLR_UINT32 nbits=0 ); 138 Bitset( const Bitset& bitset ); 139 Bitset* clone() const; 140 Bitset* bor(Bitset* bitset2); 141 142 BitsetListType& get_blist(); 143 void borInPlace(Bitset* bitset2); 144 ANTLR_UINT32 size() const; 145 void add(ANTLR_INT32 bit); 146 void grow(ANTLR_INT32 newSize); 147 bool equals(Bitset* bitset2) const; 148 bool isMember(ANTLR_UINT32 bit) const; 149 ANTLR_UINT32 numBits() const; 150 void remove(ANTLR_UINT32 bit); 151 bool isNilNode() const; 152 153 /** Produce an integer list of all the bits that are turned on 154 * in this bitset. Used for error processing in the main as the bitset 155 * reresents a number of integer tokens which we use for follow sets 156 * and so on. 157 * 158 * The first entry is the number of elements following in the list. 159 */ 160 ANTLR_INT32* toIntList() const; 161 162 /// 163 /// \brief 164 /// Creates a new bitset with at least one element, but as 165 /// many elements are required. 166 /// 167 /// \param[in] bit 168 /// A variable number of bits to add to the set, ending in -1 (impossible bit). 169 /// 170 /// \returns 171 /// A new bit set with all of the specified elements added into it. 172 /// 173 /// Call as: 174 /// - pANTLR3_BITSET = antlrBitsetOf(n, n1, n2, -1); 175 /// - pANTLR3_BITSET = antlrBitsetOf(-1); Create empty bitset 176 /// 177 /// \remarks 178 /// Stdargs function - must supply -1 as last paremeter, which is NOT 179 /// added to the set. 180 /// 181 /// 182 //C++ doesn't like variable length arguments. so use function overloading 183 static Bitset* BitsetOf(ANTLR_INT32 bit); 184 static Bitset* BitsetOf(ANTLR_INT32 bit1, ANTLR_INT32 bit2); 185 186 /// 187 /// \brief 188 /// Creates a new bitset with at least one 64 bit bset of bits, but as 189 /// many 64 bit sets as are required. 190 /// 191 /// \param[in] bset 192 /// A variable number of bits to add to the set, ending in -1 (impossible bit). 193 /// 194 /// \returns 195 /// A new bit set with all of the specified bitmaps in it and the API 196 /// initialized. 197 /// 198 /// Call as: 199 /// - pANTLR3_BITSET = antlrBitsetLoad(bset, bset11, ..., -1); 200 /// - pANTLR3_BITSET = antlrBitsetOf(-1); Create empty bitset 201 /// 202 /// \remarks 203 /// Stdargs function - must supply -1 as last paremeter, which is NOT 204 /// added to the set. 205 /// 206 ///antlr3BitsetList 207 static Bitset* BitsetFromList(const IntListType& list); 208 ~Bitset(); 209 210 private: 211 void growToInclude(ANTLR_INT32 bit); 212 static ANTLR_UINT64 BitMask(ANTLR_UINT32 bitNumber); 213 static ANTLR_UINT32 NumWordsToHold(ANTLR_UINT32 bit); 214 static ANTLR_UINT32 WordNumber(ANTLR_UINT32 bit); 215 void bitsetORInPlace(Bitset* bitset2); 216 217 }; 218 219 ANTLR_END_NAMESPACE() 220 221 #include "antlr3bitset.inl" 222 223 #endif 224 225