source: tags/ms_r18q1/PROBE_SET/ps_bitset.hxx

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