1ANTLR_BEGIN_NAMESPACE()
2
3template <class ImplTraits>
4ANTLR_INLINE BitsetList<ImplTraits>::BitsetList()
5{
6	m_bits = NULL;
7	m_length  = 0;
8}
9
10template <class ImplTraits>
11ANTLR_INLINE BitsetList<ImplTraits>::BitsetList( ANTLR_BITWORD* bits, ANTLR_UINT32 length )
12{
13	m_bits = bits;
14	m_length  = length;
15}
16
17template <class ImplTraits>
18ANTLR_INLINE ANTLR_BITWORD* BitsetList<ImplTraits>::get_bits() const
19{
20	return m_bits;
21}
22
23template <class ImplTraits>
24ANTLR_INLINE ANTLR_UINT32 BitsetList<ImplTraits>::get_length() const
25{
26	return m_length;
27}
28
29template <class ImplTraits>
30ANTLR_INLINE void BitsetList<ImplTraits>::set_bits( ANTLR_BITWORD* bits )
31{
32	m_bits = bits;
33}
34
35template <class ImplTraits>
36ANTLR_INLINE void BitsetList<ImplTraits>::set_length( ANTLR_UINT32 length )
37{
38	m_length = length;
39}
40
41template <class ImplTraits>
42typename BitsetList<ImplTraits>::BitsetType* BitsetList<ImplTraits>::bitsetLoad()
43{
44	// Allocate memory for the bitset structure itself
45	// the input parameter is the bit number (0 based)
46	// to include in the bitset, so we need at at least
47	// bit + 1 bits. If any arguments indicate a
48	// a bit higher than the default number of bits (0 means default size)
49	// then Add() will take care
50	// of it.
51	//
52	BitsetType* bitset  = new BitsetType();
53
54	if	(this != NULL)
55	{
56		// Now we can add the element bits into the set
57		//
58		ANTLR_UINT32 count=0;
59		while (count < m_length)
60		{
61			if( bitset->get_blist().get_length() <= count)
62				bitset->grow(count+1);
63
64			typename ImplTraits::BitsetListType& blist = bitset->get_blist();
65			blist.m_bits[count] = *(m_bits+count);
66			count++;
67		}
68	}
69
70	// return the new bitset
71	//
72	return  bitset;
73}
74
75template <class ImplTraits>
76typename BitsetList<ImplTraits>::BitsetType* BitsetList<ImplTraits>::bitsetCopy()
77{
78	BitsetType*  bitset;
79	ANTLR_UINT32 numElements = m_length;
80
81    // Avoid memory thrashing at the expense of a few more bytes
82    //
83    if	(numElements < 8)
84		numElements = 8;
85
86    // Allocate memory for the bitset structure itself
87    //
88    bitset  = new Bitset<ImplTraits>(numElements);
89	memcpy(bitset->get_blist().get_bits(), m_bits, numElements * sizeof(ANTLR_BITWORD));
90
91    // All seems good
92    //
93    return  bitset;
94}
95
96template <class ImplTraits>
97Bitset<ImplTraits>::Bitset( ANTLR_UINT32 numBits )
98{
99	// Avoid memory thrashing at the up front expense of a few bytes
100	if	(numBits < (8 * ANTLR_BITSET_BITS))
101		numBits = 8 * ANTLR_BITSET_BITS;
102
103	// No we need to allocate the memory for the number of bits asked for
104	// in multiples of ANTLR3_UINT64.
105	//
106	ANTLR_UINT32 numelements	= ((numBits -1) >> ANTLR_BITSET_LOG_BITS) + 1;
107
108	m_blist.set_bits( (ANTLR_BITWORD*) AllocPolicyType::alloc0(numelements * sizeof(ANTLR_BITWORD)));
109
110	m_blist.set_length( numelements );
111}
112
113template <class ImplTraits>
114Bitset<ImplTraits>::Bitset( const Bitset& bitset )
115	:m_blist(bitset.m_blist)
116{
117}
118
119template <class ImplTraits>
120ANTLR_INLINE Bitset<ImplTraits>*  Bitset<ImplTraits>::clone() const
121{
122	Bitset*  bitset;
123
124    // Allocate memory for the bitset structure itself
125    //
126    bitset  = new Bitset( ANTLR_BITSET_BITS * m_blist.get_length() );
127
128    // Install the actual bits in the source set
129    //
130    memcpy(bitset->m_blist.get_bits(), m_blist.get_bits(),
131				m_blist.get_length() * sizeof(ANTLR_BITWORD) );
132
133    // All seems good
134    //
135    return  bitset;
136}
137
138template <class ImplTraits>
139Bitset<ImplTraits>*  Bitset<ImplTraits>::bor(Bitset* bitset2)
140{
141	Bitset*  bitset;
142
143    if	(this == NULL)
144		return bitset2->clone();
145
146    if	(bitset2 == NULL)
147		return	this->clone();
148
149    // Allocate memory for the newly ordered bitset structure itself.
150    //
151    bitset  = this->clone();
152    bitset->bitsetORInPlace(bitset2);
153    return  bitset;
154}
155
156template <class ImplTraits>
157void	 Bitset<ImplTraits>::borInPlace(Bitset* bitset2)
158{
159	ANTLR_UINT32   minimum;
160
161    if	(bitset2 == NULL)
162		return;
163
164	// First make sure that the target bitset is big enough
165    // for the new bits to be ored in.
166    //
167    if	( m_blist.get_length() < bitset2->m_blist.get_length() )
168		this->growToInclude( bitset2->m_blist.get_length() * sizeof(ANTLR_BITWORD) );
169
170    // Or the miniimum number of bits after any resizing went on
171    //
172    if	( m_blist.get_length() < bitset2->m_blist.get_length() )
173		minimum = m_blist.get_length();
174	else
175		minimum = bitset2->m_blist.get_length();
176
177	ANTLR_BITWORD* bits1 = m_blist.get_bits();
178	ANTLR_BITWORD* bits2 = bitset2->m_blist.get_bits();
179	for	(ANTLR_UINT32 i = minimum; i > 0; i--)
180		bits1[i-1] |= bits2[i-1];
181}
182
183template <class ImplTraits>
184ANTLR_UINT32 Bitset<ImplTraits>::size() const
185{
186    ANTLR_UINT32   degree;
187    ANTLR_INT32   i;
188    ANTLR_INT8    bit;
189
190    // TODO: Come back to this, it may be faster to & with 0x01
191    // then shift right a copy of the 4 bits, than shift left a constant of 1.
192    // But then again, the optimizer might just work this out
193    // anyway.
194    //
195    degree  = 0;
196	ANTLR_BITWORD* bits = m_blist.get_bits();
197    for	(i = m_blist.get_length() - 1; i>= 0; i--)
198    {
199		if  (bits[i] != 0)
200		{
201			for(bit = ANTLR_BITSET_BITS - 1; bit >= 0; bit--)
202			{
203				if((bits[i] & (((ANTLR_BITWORD)1) << bit)) != 0)
204				{
205					degree++;
206				}
207			}
208		}
209    }
210    return degree;
211}
212
213template <class ImplTraits>
214ANTLR_INLINE void	Bitset<ImplTraits>::add(ANTLR_INT32 bit)
215{
216	ANTLR_UINT32   word = Bitset::WordNumber(bit);
217
218    if	(word	>= m_blist.get_length() )
219		this->growToInclude(bit);
220
221	ANTLR_BITWORD* bits = m_blist.get_bits();
222	bits[word] |= Bitset::BitMask(bit);
223}
224
225template <class ImplTraits>
226void	Bitset<ImplTraits>::grow(ANTLR_INT32 newSize)
227{
228	ANTLR_BITWORD*   newBits;
229
230    // Space for newly sized bitset - TODO: come back to this and use realloc?, it may
231    // be more efficient...
232    //
233    newBits =  (ANTLR_BITWORD*) AllocPolicyType::alloc0(newSize * sizeof(ANTLR_BITWORD) );
234    if	( m_blist.get_bits() != NULL)
235    {
236		// Copy existing bits
237		//
238		memcpy( newBits, m_blist.get_bits(), m_blist.get_length() * sizeof(ANTLR_BITWORD) );
239
240		// Out with the old bits... de de de derrr
241		//
242		AllocPolicyType::free( m_blist.get_bits() );
243    }
244
245    // In with the new bits... keerrrang.
246    //
247    m_blist.set_bits(newBits);
248    m_blist.set_length(newSize);
249}
250
251template <class ImplTraits>
252bool	Bitset<ImplTraits>::equals(Bitset* bitset2) const
253{
254    ANTLR_UINT32   minimum;
255    ANTLR_UINT32   i;
256
257    if	(this == NULL || bitset2 == NULL)
258		return	false;
259
260    // Work out the minimum comparison set
261    //
262    if	( m_blist.get_length() < bitset2->m_blist.get_length() )
263		minimum = m_blist.get_length();
264    else
265		minimum = bitset2->m_blist.get_length();
266
267    // Make sure explict in common bits are equal
268    //
269    for	(i = minimum - 1; i < minimum ; i--)
270    {
271		ANTLR_BITWORD* bits1 = m_blist.get_bits();
272		ANTLR_BITWORD* bits2 = bitset2->m_blist.get_bits();
273		if  ( bits1[i] != bits2[i])
274			return false;
275    }
276
277    // Now make sure the bits of the larger set are all turned
278    // off.
279    //
280    if	( m_blist.get_length() > minimum)
281    {
282		for (i = minimum ; i < m_blist.get_length(); i++)
283		{
284			ANTLR_BITWORD* bits = m_blist.get_bits();
285			if(bits[i] != 0)
286				return false;
287		}
288    }
289    else if (bitset2->m_blist.get_length() > minimum)
290    {
291		ANTLR_BITWORD* bits = m_blist.get_bits();
292		for (i = minimum; i < bitset2->m_blist.get_length(); i++)
293		{
294			if	( bits[i] != 0 )
295				return	false;
296		}
297    }
298
299    return  true;
300}
301
302template <class ImplTraits>
303bool	Bitset<ImplTraits>::isMember(ANTLR_UINT32 bit) const
304{
305    ANTLR_UINT32    wordNo = Bitset::WordNumber(bit);
306
307    if	(wordNo >= m_blist.get_length())
308		return false;
309
310	ANTLR_BITWORD* bits = m_blist.get_bits();
311    if	( (bits[wordNo] & Bitset::BitMask(bit)) == 0)
312		return false;
313    else
314		return true;
315}
316
317template <class ImplTraits>
318ANTLR_INLINE ANTLR_UINT32 Bitset<ImplTraits>::numBits() const
319{
320	return  m_blist.get_length() << ANTLR_BITSET_LOG_BITS;
321}
322
323template <class ImplTraits>
324ANTLR_INLINE typename ImplTraits::BitsetListType& Bitset<ImplTraits>::get_blist()
325{
326	return m_blist;
327}
328
329template <class ImplTraits>
330ANTLR_INLINE void Bitset<ImplTraits>::remove(ANTLR_UINT32 bit)
331{
332    ANTLR_UINT32    wordNo = Bitset::WordNumber(bit);
333
334    if	(wordNo < m_blist.get_length())
335	{
336		ANTLR_BITWORD* bits = m_blist.get_bits();
337		bits[wordNo] &= ~(Bitset::BitMask(bit));
338	}
339}
340
341template <class ImplTraits>
342ANTLR_INLINE bool Bitset<ImplTraits>::isNilNode() const
343{
344	ANTLR_UINT32    i;
345	ANTLR_BITWORD* bits = m_blist.get_bits();
346	for	(i = m_blist.get_length() -1 ; i < m_blist.get_length(); i--)
347	{
348		if(bits[i] != 0)
349			return false;
350	}
351	return  true;
352}
353
354template <class ImplTraits>
355ANTLR_INT32* Bitset<ImplTraits>::toIntList() const
356{
357	ANTLR_UINT32   numInts;	    // How many integers we will need
358    ANTLR_UINT32   numBits;	    // How many bits are in the set
359    ANTLR_UINT32   i;
360    ANTLR_UINT32   index;
361
362    ANTLR_INT32*  intList;
363
364    numInts = this->size() + 1;
365    numBits = this->numBits();
366
367    intList = (ANTLR_INT32*) AllocPolicyType::alloc(numInts * sizeof(ANTLR_INT32));
368
369    intList[0] = numInts;
370
371    // Enumerate the bits that are turned on
372    //
373    for	(i = 0, index = 1; i<numBits; i++)
374    {
375		if  (this->isMember(i) == true)
376			intList[index++]    = i;
377    }
378
379    // Result set
380    //
381    return  intList;
382}
383
384template <class ImplTraits>
385ANTLR_INLINE Bitset<ImplTraits>::~Bitset()
386{
387	if	(m_blist.get_bits() != NULL)
388		AllocPolicyType::free(m_blist.get_bits());
389    return;
390}
391
392template <class ImplTraits>
393void	Bitset<ImplTraits>::growToInclude(ANTLR_INT32 bit)
394{
395	ANTLR_UINT32	bl;
396	ANTLR_UINT32	nw;
397
398	bl = (m_blist.get_length() << 1);
399	nw = Bitset::NumWordsToHold(bit);
400
401	if	(bl > nw)
402		this->grow(bl);
403	else
404		this->grow(nw);
405}
406
407template <class ImplTraits>
408ANTLR_INLINE ANTLR_UINT64	Bitset<ImplTraits>::BitMask(ANTLR_UINT32 bitNumber)
409{
410	return  ((ANTLR_UINT64)1) << (bitNumber & (ANTLR_BITSET_MOD_MASK));
411}
412
413template <class ImplTraits>
414ANTLR_INLINE ANTLR_UINT32	Bitset<ImplTraits>::NumWordsToHold(ANTLR_UINT32 bit)
415{
416	return  (bit >> ANTLR_BITSET_LOG_BITS) + 1;
417}
418
419template <class ImplTraits>
420ANTLR_INLINE ANTLR_UINT32	Bitset<ImplTraits>::WordNumber(ANTLR_UINT32 bit)
421{
422	return  bit >> ANTLR_BITSET_LOG_BITS;
423}
424
425template <class ImplTraits>
426void Bitset<ImplTraits>::bitsetORInPlace(Bitset* bitset2)
427{
428	ANTLR_UINT32   minimum;
429    ANTLR_UINT32   i;
430
431    if	(bitset2 == NULL)
432		return;
433
434    // First make sure that the target bitset is big enough
435    // for the new bits to be ored in.
436    //
437    if	( m_blist.get_length() < bitset2->m_blist.get_length() )
438		this->growToInclude( bitset2->m_blist.get_length() * sizeof(ANTLR_BITWORD) );
439
440    // Or the miniimum number of bits after any resizing went on
441    //
442    if	( m_blist.get_length() < bitset2->m_blist.get_length() )
443		minimum = m_blist.get_length();
444	else
445		minimum = bitset2->m_blist.get_length();
446
447	ANTLR_BITWORD* bits1 = m_blist.get_bits();
448	ANTLR_BITWORD* bits2 = bitset2->m_blist.get_bits();
449    for	(i = minimum; i > 0; i--)
450		bits1[i-1] |= bits2[i-1];
451}
452
453template <class ImplTraits>
454Bitset<ImplTraits>* Bitset<ImplTraits>::BitsetOf(ANTLR_INT32 bit)
455{
456	// Allocate memory for the bitset structure itself
457    // the input parameter is the bit number (0 based)
458    // to include in the bitset, so we need at at least
459    // bit + 1 bits. If any arguments indicate a
460    // a bit higher than the default number of bits (0 menas default size)
461    // then Add() will take care
462    // of it.
463    //
464	Bitset<ImplTraits>* bitset = new Bitset<ImplTraits>(0);
465	bitset->add(bit);
466	return bitset;
467}
468
469template <class ImplTraits>
470Bitset<ImplTraits>* Bitset<ImplTraits>::BitsetOf(ANTLR_INT32 bit1, ANTLR_INT32 bit2)
471{
472	Bitset<ImplTraits>* bitset = Bitset<ImplTraits>::BitsetOf(bit1);
473	bitset->add(bit2);
474	return bitset;
475}
476
477//static
478template <class ImplTraits>
479Bitset<ImplTraits>* Bitset<ImplTraits>::BitsetFromList(const IntListType& list)
480{
481	// We have no idea what exactly is in the list
482    // so create a default bitset and then just add stuff
483    // as we enumerate.
484    //
485    Bitset<ImplTraits>* bitset  = new Bitset<ImplTraits>(0);
486	for( int i = 0; i < list.size(); ++i )
487		bitset->add( list[i] );
488
489	return bitset;
490}
491
492ANTLR_END_NAMESPACE()
493