1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
|
// Binary digit (bit) vector -*- c++ -*-
#ifndef BITVECTOR_H_
# define BITVECTOR_H_
# ifdef __GNUC__
# pragma interface
# endif // __GNUC__
# include <limits.h>
# include <string.h>
# include <assert.h>
/** @file BitVector.h
* Bit vector
*/
/* Copyright 2000-2002 Marko Mkel (msmakela@tcs.hut.fi).
This file is part of MARIA, a reachability analyzer and model checker
for high-level Petri nets.
MARIA is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.
MARIA is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License for more details.
The GNU General Public License is often shipped with GNU software, and
is generally kept in a file called COPYING or LICENSE. If you do not
have a copy of the license, write to the Free Software Foundation,
59 Temple Place, Suite 330, Boston, MA 02111 USA. */
/** Binary digit (bit) vector */
class BitVector
{
public:
/** machine word */
typedef unsigned word_t;
/** Constructor
* @param size number of elements in the vector
*/
explicit BitVector (unsigned size = 0) :
mySize (0), myAllocated (1), myBits (new word_t[1]) {
*myBits = 0;
setSize (size);
}
/** Copy constructor */
explicit BitVector (const class BitVector& old) :
mySize (old.mySize), myAllocated (getNumWords (old.mySize)), myBits (0) {
memcpy (myBits = new word_t[myAllocated], old.myBits,
myAllocated * sizeof (word_t));
}
private:
/** Assignment operator */
class BitVector& operator= (const class BitVector& old);
public:
/** Destructor */
~BitVector () { delete[] myBits; }
/** Determine the number of words the specified amount of bits occupy */
static unsigned getNumWords (unsigned bits) {
const unsigned bitsPerWord = CHAR_BIT * sizeof (word_t);
return (bits + bitsPerWord - 1) / bitsPerWord;
}
/** Clear the vector */
void clear () {
memset (myBits, 0, myAllocated * sizeof *myBits);
}
/** Truncate the vector
* @param size number of elements to leave in the vector
*/
void truncate (unsigned size = 0) {
if (mySize <= size) return;
mySize = size;
const unsigned init = getNumWords (size);
if (const unsigned rest = size % (CHAR_BIT * sizeof (word_t)))
assert (init >= 1), myBits[init - 1] &= (1u << rest) - 1;
memset (myBits, 0, (myAllocated - init) * sizeof *myBits);
}
/** Set the size of the vector */
void setSize (unsigned size) {
const unsigned numWords = getNumWords (size);
if (myAllocated < numWords) {
while (myAllocated < numWords)
myAllocated <<= 1;
word_t* bits = new word_t[myAllocated];
const unsigned init = getNumWords (mySize);
memcpy (bits, myBits, init * sizeof *myBits);
memset (bits + init, 0, (myAllocated - init) * sizeof *myBits);
delete[] myBits;
myBits = bits;
}
mySize = size;
}
/** Determine the size of the vector */
unsigned getSize () const { return mySize; }
/** Read a binary digit
* @param i zero-based index of the element
* @return value of the ternary digit
*/
bool operator[] (unsigned i) const {
assert (i < mySize);
return myBits[i / (CHAR_BIT * sizeof (word_t))] &
(1u << (i % (CHAR_BIT * sizeof (word_t))));
}
/** Assign a binary digit
* @param i zero-based index of the element
* @param b new value of the digit
*/
void assign (unsigned i, bool b) {
assert (i < mySize);
word_t& word = myBits[i / (CHAR_BIT * sizeof (word_t))];
word_t bit = 1u << (i % (CHAR_BIT * sizeof (word_t)));
if (b)
word |= bit;
else
word &= ~bit;
}
/** Test and set: read and set a binary digit
* @param i zero-based index of the element
* @return whether the element already was set
*/
bool tset (unsigned i) {
assert (i < mySize);
word_t& word = myBits[i / (CHAR_BIT * sizeof (word_t))];
word_t bit = 1u << (i % (CHAR_BIT * sizeof (word_t)));
if (word & bit)
return true;
word |= bit;
return false;
}
/** Test and reset: read and reset a binary digit
* @param i zero-based index of the element
* @return whether the element already was set
*/
bool treset (unsigned i) {
assert (i < mySize);
word_t& word = myBits[i / (CHAR_BIT * sizeof (word_t))];
word_t bit = 1u << (i % (CHAR_BIT * sizeof (word_t)));
if (!(word & bit))
return false;
word &= ~bit;
return true;
}
/** Assign a binary digit, extending the vector with zeros if required
* @param i zero-based index of the element
* @param b new value of the digit
*/
void extend (unsigned i, bool b) {
if (i >= mySize) setSize (i + 1);
assign (i, b);
}
/** Determine whether the whole vector is filled with zero bits */
bool allClear () const {
unsigned i = mySize / (CHAR_BIT * sizeof (word_t));
if (mySize && (myBits[i] &
((1u << (mySize % (CHAR_BIT * sizeof (word_t)))) - 1)))
return false;
while (i--) if (myBits[i]) return false;
return true;
}
/** Determine whether the whole vector is filled with zero bits */
bool allSet () const {
unsigned i = mySize / (CHAR_BIT * sizeof (word_t));
if (mySize && ~(myBits[i] |
~((1u << (mySize % (CHAR_BIT * sizeof (word_t)))) - 1)))
return false;
while (i--) if (~myBits[i]) return false;
return true;
}
/** Compute bit wise disjunction with the complement of a bit vector
* @param other bit vector whose complement is to be ORed with this
*/
void orNot (const class BitVector& other) {
assert (mySize == other.mySize);
for (unsigned i = getNumWords (mySize); i--; )
myBits[i] |= ~other.myBits[i];
}
/** Compute bit wise conjunction with the complement of a bit vector
* @param other bit vector whose complement is to be ANDed with this
* @return true if any bits were left '1' after the operation
*/
bool andNot (const class BitVector& other) {
assert (mySize == other.mySize);
bool someset = false;
for (unsigned i = getNumWords (mySize); i--; )
if (myBits[i] &= ~other.myBits[i])
someset = true;
return someset;
}
private:
/** Number of elements in the vector */
unsigned mySize;
/** Size of the allocated vector in words */
unsigned myAllocated;
/** The vector */
word_t* myBits;
};
#endif // BITVECTOR_H_
|
