source: tags/svn.1.5.4/PROBE_SET/ps_bitset.hxx

Last change on this file was 7811, checked in by westram, 13 years ago

merge from dev [7748] [7749] [7750]

  • comments (C→C++ style)
  • fixed umlauts in TREEGEN
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 12.8 KB
Line 
1#ifndef PS_BITSET_HXX
2#define PS_BITSET_HXX
3
4#ifndef __SET__
5#include <set>
6#endif
7#ifndef PS_FILEBUFFER_HXX
8#include "ps_filebuffer.hxx"
9#endif
10
11#ifndef NDEBUG
12# define bs_assert(bed) do { if (!(bed)) *(int *)0=0; } while (0)
13# ifndef DEBUG
14#  error DEBUG is NOT defined - but it has to!
15# endif
16#else
17# ifdef DEBUG
18#  error DEBUG is defined - but it should not!
19# endif
20# define bs_assert(bed)
21#endif // NDEBUG
22
23class PS_BitSet : virtual Noncopyable {
24protected:
25
26    unsigned char *data;
27    bool bias;                                                   // preset value for newly allocated memory
28    long max_index;                                              // max. used index
29
30    PS_BitSet(const PS_BitSet&);
31    PS_BitSet();
32    PS_BitSet(const bool _bias, const long _max_index, const long _capacity) {
33        bias      = _bias;
34        max_index = _max_index;
35        capacity  = _capacity;
36    }
37
38public:
39    long capacity;                                               // number of allocated bits
40    typedef set<long> IndexSet;
41
42    virtual long getTrueIndices(IndexSet &_index_set, const long _fill_index);
43    virtual long getFalseIndices(IndexSet &_index_set, const long _fill_index);
44    virtual long getCountOfTrues(const long _fill_index = -1);
45    long         getMaxUsedIndex() { return max_index; }
46
47    virtual bool Get(const long _index);
48    virtual bool Set(const long _index, const bool _value);
49    virtual void setTrue(const long _index);
50    virtual void setFalse(const long _index);
51
52    virtual void invert();
53    virtual void x_or(const PS_BitSet *_other_set);
54
55    virtual void print(const bool _header, const long _fill_index);
56    virtual bool save(PS_FileBuffer *_file);
57    virtual bool load(PS_FileBuffer *_file, const long _fill_index);
58
59    virtual bool copy(const PS_BitSet *_other_bitset);
60    virtual bool reserve(const long _capacity);
61
62    explicit PS_BitSet(const bool _bias, const long _capacity) : bias(_bias), max_index(-1), capacity(0) {
63        data = 0;
64        reserve(_capacity);
65    }
66
67    explicit PS_BitSet(PS_FileBuffer *_file, const long _fill_index = -1) : bias(false), max_index(-1), capacity(0) {
68        data = 0;
69        load(_file, _fill_index);
70    }
71
72    virtual ~PS_BitSet() {
73        if (data) free(data);
74    }
75};
76
77//  ############################################################
78//  # PS_BitSet_Fast
79//  ############################################################
80class PS_BitSet_Fast : public PS_BitSet {
81private:
82
83    PS_BitSet_Fast(const PS_BitSet_Fast&);
84    PS_BitSet_Fast();
85
86public:
87
88    virtual bool get(const long _index);
89    virtual bool set(const long _index, const bool _value);
90    virtual void setTrue(const long _index);
91    virtual void setFalse(const long _index);
92
93    virtual bool reserve(const long _capacity);
94
95    explicit PS_BitSet_Fast(PS_FileBuffer *_file, const long _fill_index = -1) : PS_BitSet(false, -1, 0) {
96        data = 0;
97        load(_file, _fill_index);
98    }
99
100    explicit PS_BitSet_Fast(bool _bias, long _capacity) : PS_BitSet(_bias, _capacity) {
101        // we just altered member functions so we don't do anything here
102        // but call correct base class constructor to prevent
103        // the call of PS_BitSet() without parameters
104    }
105};
106
107
108long PS_BitSet::getFalseIndices(PS_BitSet::IndexSet &_index_set, const long _fill_index = -1) {
109    _index_set.clear();
110    // get indices of falses from bitset up to max_index
111    long index      = 0;
112    long byte_index = 0;
113    while (true) {
114        unsigned char byte  = data[byte_index++];       // get a data byte
115        if (!(byte &   1)) _index_set.insert(index); if (index++ >= max_index) break;
116        if (!(byte &   2)) _index_set.insert(index); if (index++ >= max_index) break;
117        if (!(byte &   4)) _index_set.insert(index); if (index++ >= max_index) break;
118        if (!(byte &   8)) _index_set.insert(index); if (index++ >= max_index) break;
119        if (!(byte &  16)) _index_set.insert(index); if (index++ >= max_index) break;
120        if (!(byte &  32)) _index_set.insert(index); if (index++ >= max_index) break;
121        if (!(byte &  64)) _index_set.insert(index); if (index++ >= max_index) break;
122        if (!(byte & 128)) _index_set.insert(index); if (index++ >= max_index) break;
123    }
124    // append indices [max_index+1 .. _fill_index] if bias is set to false
125    if (!bias) {
126        for (; (index <= _fill_index); ++index) {
127            _index_set.insert(index);
128        }
129    }
130    return _index_set.size();
131}
132
133
134long PS_BitSet::getTrueIndices(PS_BitSet::IndexSet &_index_set, const long _fill_index = -1) {
135    _index_set.clear();
136    // get indices of trues from bitset up to max_index
137    long index      = 0;
138    long byte_index = 0;
139    while (true) {
140        unsigned char byte  = data[byte_index++];       // get a data byte
141        if (byte &   1) _index_set.insert(index); if (index++ >= max_index) break;
142        if (byte &   2) _index_set.insert(index); if (index++ >= max_index) break;
143        if (byte &   4) _index_set.insert(index); if (index++ >= max_index) break;
144        if (byte &   8) _index_set.insert(index); if (index++ >= max_index) break;
145        if (byte &  16) _index_set.insert(index); if (index++ >= max_index) break;
146        if (byte &  32) _index_set.insert(index); if (index++ >= max_index) break;
147        if (byte &  64) _index_set.insert(index); if (index++ >= max_index) break;
148        if (byte & 128) _index_set.insert(index); if (index++ >= max_index) break;
149    }
150    // append indices [max_index+1 .. _max_index] if bias is set to true
151    if (bias) {
152        for (; (index <= _fill_index); ++index) {
153            _index_set.insert(index);
154        }
155    }
156    return _index_set.size();
157}
158
159
160long PS_BitSet::getCountOfTrues(const long _fill_index) {
161    long count = 0;
162    // get indices of trues from bitset up to max_index
163    long index      = 0;
164    long byte_index = 0;
165    while (true) {
166        unsigned char byte  = data[byte_index++];       // get a data byte
167        if (byte &   1) ++count; if (index++ >= max_index) break;
168        if (byte &   2) ++count; if (index++ >= max_index) break;
169        if (byte &   4) ++count; if (index++ >= max_index) break;
170        if (byte &   8) ++count; if (index++ >= max_index) break;
171        if (byte &  16) ++count; if (index++ >= max_index) break;
172        if (byte &  32) ++count; if (index++ >= max_index) break;
173        if (byte &  64) ++count; if (index++ >= max_index) break;
174        if (byte & 128) ++count; if (index++ >= max_index) break;
175    }
176    // append indices [max_index+1 .. _max_index] if bias is set to true
177    if (bias && (_fill_index > max_index)) {
178        count += _fill_index-max_index + 1;
179    }
180    return count;
181}
182
183
184bool PS_BitSet::Set(const long _index, const bool _value) {
185    bs_assert(_index >= 0);
186    reserve(_index);
187    bool previous_value = (((data[_index/8] >> (_index % 8)) & 1) == 1);
188    if (_value) {
189        data[_index/8] |= 1 << (_index % 8);
190    }
191    else {
192        data[_index/8] &= ~(1 << (_index % 8));
193    }
194    if (_index > max_index) max_index = _index;
195    return previous_value;
196}
197
198
199void PS_BitSet::setTrue(const long _index) {
200    bs_assert(_index >= 0);
201    reserve(_index);
202    data[_index/8] &= 1 << (_index % 8);
203    if (_index > max_index) max_index = _index;
204}
205
206
207void PS_BitSet::setFalse(const long _index) {
208    bs_assert(_index >= 0);
209    reserve(_index);
210    data[_index/8] &= ~(1 << (_index % 8));
211    if (_index > max_index) max_index = _index;
212}
213
214
215bool PS_BitSet::Get(const long _index) {
216    bs_assert(_index >= 0);
217    reserve(_index);
218    return (((data[_index/8] >> (_index % 8)) & 1) == 1);
219}
220
221
222bool PS_BitSet::copy(const PS_BitSet *_other_bitset) {
223    bias = _other_bitset->bias;
224    if (!reserve(_other_bitset->capacity)) return false;
225    memcpy(data, _other_bitset->data, (capacity>>3));
226    max_index = _other_bitset->max_index;
227    return true;
228}
229
230
231bool PS_BitSet::reserve(const long _capacity) {
232    unsigned char *new_data;
233    long new_capacity_bytes = (_capacity/8)+1;
234    long old_capacity_bytes = (capacity/8)+1;
235    if (capacity > 0) {
236        if (new_capacity_bytes <= old_capacity_bytes) return true;      // smaller or same size requested ?
237    }
238    new_capacity_bytes = ((new_capacity_bytes / 32)+1)*32;              // adjust requested size to bigger chunks
239    new_data = (unsigned char *)malloc(new_capacity_bytes);             // get new memory
240    if (new_data == 0) return false;
241    memset(new_data, bias ? 0xFF : 0, new_capacity_bytes);              // set memory to bias value
242    if (capacity > 0) memcpy(new_data, data, old_capacity_bytes);       // copy old values
243    if (data) free(data);                                               // free old memory
244    data     = new_data;                                                // store new pointer
245    capacity = new_capacity_bytes*8;                                    // store new capacity
246    return true;
247}
248
249
250void PS_BitSet::invert() {
251    for (long i = 0; i < capacity/8; ++i) {
252        data[i] = ~data[i];
253    }
254}
255
256
257void PS_BitSet::x_or(const PS_BitSet *_other_set) {
258    for (long i = 0; i < capacity/8; ++i) {
259        data[i] ^= _other_set->data[i];
260    }
261}
262
263
264void PS_BitSet::print(const bool _header = true, const long _fill_index = -1) {
265    if (_header) printf("PS_BitSet: bias(%1i) max_index(%6li) capacity(%6li) ", bias, max_index, capacity);
266    for (long i = 0; i <= max_index; ++i) {
267        printf(Get(i) ? "+" : "_");
268    }
269    for (long i = max_index+1; i <= _fill_index; ++i) {
270        printf(".");
271    }
272    printf(" %li\n", max_index);
273}
274
275
276bool PS_BitSet::save(PS_FileBuffer *_file) {
277    if (_file->isReadonly()) return false;
278    // save max_index
279    _file->put_long(max_index);
280    // save bias
281    _file->put_char((bias) ? '1' : '0');
282    // save bitset
283    long bytes = (max_index / 8)+1;
284    long i = 0;
285    while ((bytes-i) >= PS_FileBuffer::BUFFER_SIZE) {
286        _file->put(&(data[i]), PS_FileBuffer::BUFFER_SIZE);
287        i += PS_FileBuffer::BUFFER_SIZE;
288    }
289    _file->put(&(data[i]), (bytes-i));
290    return true;
291}
292
293
294bool PS_BitSet::load(PS_FileBuffer *_file, const long _fill_index = -1) {
295    // load max_index
296    _file->get_long(max_index);
297    // load bias
298    bias = (_file->get_char() == '1');
299    // initialize bitset
300    capacity = 0;
301    if (!reserve((max_index > _fill_index) ? max_index : _fill_index)) return false;
302    // load bitset
303    long bytes = (max_index / 8)+1;
304    long i = 0;
305    while ((bytes-i) >= PS_FileBuffer::BUFFER_SIZE) {
306        _file->get(&(data[i]), PS_FileBuffer::BUFFER_SIZE);
307        i += PS_FileBuffer::BUFFER_SIZE;
308    }
309    _file->get(&(data[i]), (bytes-i));
310    return true;
311}
312
313
314bool PS_BitSet_Fast::get(const long _index) {
315    if (_index >= capacity) printf("PS_BitSet_Fast::get( %li ) exceeds capacity %li\n", _index, capacity);
316    if (_index > max_index) max_index = _index;
317    return (((data[_index/8] >> (_index % 8)) & 1) == 1);
318}
319
320
321bool PS_BitSet_Fast::set(const long _index, const bool _value) {
322    if (_index >= capacity) printf("PS_BitSet_Fast::set( %li,%1i ) exceeds capacity %li\n", _index, _value, capacity);
323    bool previous_value = (((data[_index/8] >> (_index % 8)) & 1) == 1);
324    if (_value) {
325        data[_index/8] |= 1 << (_index % 8);
326    }
327    else {
328        data[_index/8] &= ~(1 << (_index % 8));
329    }
330    if (_index > max_index) max_index = _index;
331    return previous_value;
332}
333
334
335void PS_BitSet_Fast::setTrue(const long _index) {
336    if (_index >= capacity) printf("PS_BitSet_Fast::setTrue( %li ) exceeds capacity %li\n", _index, capacity);
337    data[_index/8] |= 1 << (_index % 8);
338    if (_index > max_index) max_index = _index;
339}
340
341
342void PS_BitSet_Fast::setFalse(const long _index) {
343    if (_index >= capacity) printf("PS_BitSet_Fast::setFalse( %li ) exceeds capacity %li\n", _index, capacity);
344    data[_index/8] &= ~(1 << (_index % 8));
345    if (_index > max_index) max_index = _index;
346}
347
348
349//   as i assume that a user of the _FAST variant knows how much
350//   data will be stored in the set we don't adjust the given
351//   capacity to bigger chunks as PS_BitSet::reserve does
352bool PS_BitSet_Fast::reserve(const long _capacity) {
353    unsigned char *new_data;
354    long new_capacity_bytes = (_capacity/8)+1;
355    long old_capacity_bytes = (capacity/8)+1;
356    if (capacity > 0) {
357        if (new_capacity_bytes <= old_capacity_bytes) return true;      // smaller or same size requested ?
358    }
359    new_data = (unsigned char *)malloc(new_capacity_bytes);             // get new memory
360    if (new_data == 0) return false;
361    memset(new_data, bias ? 0xFF : 0, new_capacity_bytes);              // set memory to bias value
362    if (capacity > 0) memcpy(new_data, data, old_capacity_bytes);       // copy old values
363    if (data) free(data);                                               // free old memory
364    data     = new_data;                                                // store new pointer
365    capacity = new_capacity_bytes*8;                                    // store new capacity
366    return true;
367}
368#else
369#error ps_bitset.hxx included twice
370#endif
Note: See TracBrowser for help on using the repository browser.