1324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/**
2324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * \file
3324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Defines the basic structures of an ANTLR3 bitset. this is a C version of the
4324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * cut down Bitset class provided with the java version of antlr 3.
5324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *
6324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *
7324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */
8324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver#ifndef	_ANTLR3_BITSET_H
9324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver#define	_ANTLR3_BITSET_H
10324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver
11324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// [The "BSD licence"]
12324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// Copyright (c) 2005-2009 Jim Idle, Temporal Wave LLC
13324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// http://www.temporal-wave.com
14324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// http://www.linkedin.com/in/jimidle
15324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver//
16324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// All rights reserved.
17324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver//
18324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// Redistribution and use in source and binary forms, with or without
19324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// modification, are permitted provided that the following conditions
20324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// are met:
21324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// 1. Redistributions of source code must retain the above copyright
22324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver//    notice, this list of conditions and the following disclaimer.
23324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// 2. Redistributions in binary form must reproduce the above copyright
24324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver//    notice, this list of conditions and the following disclaimer in the
25324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver//    documentation and/or other materials provided with the distribution.
26324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// 3. The name of the author may not be used to endorse or promote products
27324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver//    derived from this software without specific prior written permission.
28324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver//
29324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
30324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
31324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
32324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
33324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
34324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
35324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
36324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
37324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
38324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
39324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver
40324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver#include    <antlr3defs.h>
41324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver#include    <antlr3collections.h>
42324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver
43324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/** How many bits in the elements
44324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */
45324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver#define	ANTLR3_BITSET_BITS	64
46324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver
47324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/** How many bits in a nible of bits
48324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */
49324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver#define	ANTLR3_BITSET_NIBBLE	4
50324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver
51324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/** log2 of ANTLR3_BITSET_BITS 2^ANTLR3_BITSET_LOG_BITS = ANTLR3_BITSET_BITS
52324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */
53324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver#define	ANTLR3_BITSET_LOG_BITS	6
54324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver
55324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/** We will often need to do a mod operator (i mod nbits).
56324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *  For powers of two, this mod operation is the
57324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *  same as:
58324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *   - (i & (nbits-1)).
59324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *
60324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Since mod is relatively slow, we use an easily
61324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * precomputed mod mask to do the mod instead.
62324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */
63324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver#define	ANTLR3_BITSET_MOD_MASK	ANTLR3_BITSET_BITS - 1
64324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver
65324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver#ifdef __cplusplus
66324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverextern "C" {
67324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver#endif
68324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver
69324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruvertypedef struct ANTLR3_BITSET_LIST_struct
70324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{
71324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	/// Pointer to the allocated array of bits for this bit set, which
72324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    /// is an array of 64 bit elements (of the architecture). If we find a
73324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    /// machine/C compiler that does not know anything about 64 bit values
74324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    ///	then it should be easy enough to produce a 32 bit (or less) version
75324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    /// of the bitset code. Note that the pointer here may be static if laid down
76324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	/// by the code generation, and it must be copied if it is to be manipulated
77324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	/// to perform followset calculations.
78324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    ///
79324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    pANTLR3_BITWORD   bits;
80324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver
81324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    /// Length of the current bit set in ANTLR3_UINT64 units.
82324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    ///
83324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    ANTLR3_UINT32    length;
84324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver}
85324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	ANTLR3_BITSET_LIST;
86324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver
87324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruvertypedef	struct ANTLR3_BITSET_struct
88324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{
89324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	/// The actual bits themselves
90324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	///
91324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	ANTLR3_BITSET_LIST				blist;
92324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver
93324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    pANTLR3_BITSET					(*clone)	    (struct ANTLR3_BITSET_struct  * inSet);
94324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    pANTLR3_BITSET					(*bor)			(struct ANTLR3_BITSET_struct  * bitset1, struct ANTLR3_BITSET_struct * bitset2);
95324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    void							(*borInPlace)   (struct ANTLR3_BITSET_struct  * bitset,  struct ANTLR3_BITSET_struct * bitset2);
96324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    ANTLR3_UINT32					(*size)			(struct ANTLR3_BITSET_struct  * bitset);
97324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    void							(*add)			(struct ANTLR3_BITSET_struct  * bitset, ANTLR3_INT32 bit);
98324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    void							(*grow)			(struct ANTLR3_BITSET_struct  * bitset, ANTLR3_INT32 newSize);
99324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    ANTLR3_BOOLEAN					(*equals)	    (struct ANTLR3_BITSET_struct  * bitset1, struct ANTLR3_BITSET_struct * bitset2);
100324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    ANTLR3_BOOLEAN					(*isMember)	    (struct ANTLR3_BITSET_struct  * bitset, ANTLR3_UINT32 bit);
101324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    ANTLR3_UINT32					(*numBits)	    (struct ANTLR3_BITSET_struct  * bitset);
102324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    void							(*remove)	    (struct ANTLR3_BITSET_struct  * bitset, ANTLR3_UINT32 bit);
103324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    ANTLR3_BOOLEAN					(*isNilNode)	    (struct ANTLR3_BITSET_struct  * bitset);
104324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    pANTLR3_INT32					(*toIntList)    (struct ANTLR3_BITSET_struct  * bitset);
105324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver
106324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    void							(*free)			(struct ANTLR3_BITSET_struct  * bitset);
107324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver
108324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver
109324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver}
110324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    ANTLR3_BITSET;
111324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver
112324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver#ifdef __cplusplus
113324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver}
114324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver#endif
115324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver
116324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver
117324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver
118324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver#endif
119324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver
120