/elec/propeller-clock

To get this branch, use:
bzr branch http://bzr.ed.am/elec/propeller-clock

« back to all changes in this revision

Viewing changes to src/utility/bitset

  • Committer: edam
  • Date: 2012-02-25 01:31:43 UTC
  • Revision ID: tim@ed.am-20120225013143-9fet2y2d3fjlrwez
added ulibc

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/utility/bitset
 
1
/*      Copyright (C) 2004 Garrett A. Kajmowicz
 
2
 
 
3
        This file is part of the uClibc++ Library.
 
4
 
 
5
        This library is free software; you can redistribute it and/or
 
6
        modify it under the terms of the GNU Lesser General Public
 
7
        License as published by the Free Software Foundation; either
 
8
        version 2.1 of the License, or (at your option) any later version.
 
9
 
 
10
        This library is distributed in the hope that it will be useful,
 
11
        but WITHOUT ANY WARRANTY; without even the implied warranty of
 
12
        MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 
13
        Lesser General Public License for more details.
 
14
 
 
15
        You should have received a copy of the GNU Lesser General Public
 
16
        License along with this library; if not, write to the Free Software
 
17
        Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
18
*/
 
19
 
 
20
#include <basic_definitions>
 
21
#include <cstddef>
 
22
#include <climits>
 
23
#include <func_exception>
 
24
#include <string>
 
25
#include <iosfwd>
 
26
 
 
27
#ifndef __STD_BITSET_HEADER
 
28
#define __STD_BITSET_HEADER 1
 
29
 
 
30
#pragma GCC visibility push(default)
 
31
 
 
32
namespace std{
 
33
        template <size_t N> class bitset;
 
34
 
 
35
 
 
36
        template <size_t N> bitset<N> operator&(const bitset<N>&, const bitset<N>&);
 
37
        template <size_t N> bitset<N> operator|(const bitset<N>&, const bitset<N>&);
 
38
        template <size_t N> bitset<N> operator^(const bitset<N>&, const bitset<N>&);
 
39
        template <class charT, class traits, size_t N> basic_istream<charT, traits>& 
 
40
                operator>>(basic_istream<charT, traits>& is, bitset<N>& x);
 
41
 
 
42
        template <class charT, class traits, size_t N> basic_ostream<charT, traits>& 
 
43
                operator<<(basic_ostream<charT, traits>& os, const bitset<N>& x);
 
44
        
 
45
        //Actual Code
 
46
 
 
47
 
 
48
        template<size_t N> class _UCXXEXPORT bitset {
 
49
        private:
 
50
                //Number of characters allocated to hold the bits
 
51
                static const size_t WORD_SIZE = CHAR_BIT;               //Use int maybe?
 
52
                static const size_t num_bytes = (N + WORD_SIZE - 1) / WORD_SIZE;
 
53
 
 
54
                //From the bit number, figure out which byte we are working with
 
55
                size_t byte_num(size_t bit_num) const{ 
 
56
                        if(WORD_SIZE == 8){
 
57
                                return (bit_num >> 3);
 
58
                        }
 
59
                        if(WORD_SIZE == 16){
 
60
                                return (bit_num >> 4);
 
61
                        }
 
62
                        if(WORD_SIZE == 32){
 
63
                                return (bit_num >> 5);
 
64
                        }
 
65
                        if(WORD_SIZE == 64){
 
66
                                return (bit_num >> 6);
 
67
                        }
 
68
                        return bit_num / WORD_SIZE;
 
69
                }
 
70
                //From the bit number, figure out which bit inside the byte we need
 
71
                size_t bit_num(const size_t bit_num) const{
 
72
                        return bit_num % WORD_SIZE;
 
73
                }
 
74
 
 
75
 
 
76
                //Point to the actual data
 
77
                char data[num_bytes];
 
78
        public:
 
79
 
 
80
                class _UCXXEXPORT reference {
 
81
                        friend class bitset;
 
82
                        reference() : bit_num(0), parent(0) {  }
 
83
                        size_t bit_num;
 
84
                        bitset * parent;
 
85
                public:
 
86
                        ~reference() {  }
 
87
                        reference& operator=(bool x){                   // for b[i] = x;
 
88
                                parent->set(bit_num, x);
 
89
                                return *this;
 
90
                        }
 
91
                        reference& operator=(const reference& x){       // for b[i] = b[j];
 
92
                                parent->set(bit_num, x);
 
93
                                return *this;
 
94
                        }
 
95
                        bool operator~() const{                         // flips the bit
 
96
                                return !parent->test(bit_num);
 
97
                        }
 
98
                        operator bool() const{                          // for x = b[i];
 
99
                                return parent->test(bit_num);
 
100
                        }
 
101
                        reference& flip(){                              // for b[i].flip();
 
102
                                parent->flip(bit_num);
 
103
                                return *this;
 
104
                        }
 
105
                };
 
106
 
 
107
                bitset(){
 
108
                        reset();
 
109
                }
 
110
                bitset(unsigned long val){
 
111
                        reset();
 
112
                        size_t count = sizeof(val) * CHAR_BIT;
 
113
                        if(count > N){
 
114
                                count = N;
 
115
                        }
 
116
                        for(size_t i = 0; i < count; ++i){
 
117
                                set(i, ((val >> i) & 1));
 
118
                        }
 
119
                }
 
120
 
 
121
                bitset(const bitset & val){
 
122
                        for(size_t i = 0; i < num_bytes; ++i){
 
123
                                data[i] = val.data[i];
 
124
                        }
 
125
                }
 
126
 
 
127
                template<class charT, class traits, class Allocator> _UCXXEXPORT
 
128
                explicit bitset(
 
129
                        const basic_string<charT,traits,Allocator>& str,
 
130
                        typename basic_string<charT,traits,Allocator>::size_type pos = 0,
 
131
                        typename basic_string<charT,traits,Allocator>::size_type n =
 
132
                        basic_string<charT>::npos
 
133
                        
 
134
                ){
 
135
                        reset();
 
136
                        if(n > str.length()){
 
137
                                n = str.length();
 
138
                        }
 
139
                        size_t width = n;
 
140
                        if (width + pos > str.length()){
 
141
                                width = str.length() - pos;
 
142
                        }
 
143
 
 
144
                        for(size_t i = 0; i < width; ++i){
 
145
                                switch(str[pos + width - i - 1]){
 
146
                                        case '0':
 
147
                                                break;
 
148
                                        case '1':
 
149
                                                set(i);
 
150
                                                break;
 
151
                                        default:
 
152
                                                __throw_invalid_argument();
 
153
                                }
 
154
                        }
 
155
                }
 
156
 
 
157
                bitset<N>& operator&=(const bitset<N>& rhs){
 
158
                        for(size_t i =0; i < num_bytes; ++i){
 
159
                                data[i] &= rhs.data[i];
 
160
                        }
 
161
                        return *this;
 
162
                }
 
163
 
 
164
                bitset<N>& operator|=(const bitset<N>& rhs){
 
165
                        for(size_t i =0; i < num_bytes; ++i){
 
166
                                data[i] |= rhs.data[i];
 
167
                        }
 
168
                        return *this;
 
169
                }
 
170
                bitset<N>& operator^=(const bitset<N>& rhs){
 
171
                        for(size_t i=0; i < num_bytes; ++i){
 
172
                                data[i] ^= rhs.data[i];
 
173
                        }
 
174
                        return *this;
 
175
                }
 
176
 
 
177
                bitset<N>& operator<<=(size_t pos){
 
178
                        for(size_t i = N-1; i >=pos; --i){
 
179
                                set(i, test(i - pos));
 
180
                        }
 
181
                        for(size_t i = 0; i < pos; ++i){
 
182
                                reset(i);
 
183
                        }
 
184
                        return *this;
 
185
                }
 
186
 
 
187
                bitset<N>& operator>>=(size_t pos){
 
188
                        for(size_t i = 0; i < (N - pos); ++i){
 
189
                                set(i, test(i + pos));
 
190
                        }
 
191
                        for(size_t i = pos; i > 0; --i){
 
192
                                reset(N - i);
 
193
                        }
 
194
                        return *this;
 
195
                }
 
196
 
 
197
                bitset<N>& set(){
 
198
                        size_t i;
 
199
                        for(i = 0; i < N ; ++i){
 
200
                                data[byte_num(i)] |= (1<<bit_num(i));
 
201
                        }
 
202
                        return *this;
 
203
                }
 
204
                bitset<N>& set(size_t pos, int val = true){
 
205
                        if(val == true){
 
206
                                data[byte_num(pos)] |= (1<<bit_num(pos));
 
207
                        }else{
 
208
                                data[byte_num(pos)] &= ~(1<<bit_num(pos));
 
209
                        }
 
210
                        return *this;
 
211
                }
 
212
                bitset<N>& reset(){
 
213
                        for(size_t i = 0; i <= num_bytes; ++i){
 
214
                                data[i] = 0;
 
215
                        }
 
216
                        return *this;
 
217
                }
 
218
                bitset<N>& reset(size_t pos){
 
219
                        data[byte_num(pos)] &= ~(1<<bit_num(pos));
 
220
                        return *this;
 
221
                }
 
222
                bitset<N>  operator~() const{
 
223
                        bitset<N> retval(*this);
 
224
                        retval.flip();
 
225
                        return retval;
 
226
                }
 
227
 
 
228
                bitset<N>& flip(){
 
229
                        for(size_t i = 0; i <= num_bytes; ++i){
 
230
                                data[i] =  ~data[i];
 
231
                        }
 
232
                        return *this;
 
233
                }
 
234
                bitset<N>& flip(size_t pos){
 
235
                        char temp = data[byte_num(pos)] & (1 << bit_num(pos));
 
236
                        if(temp == 0){  //Bit was 0
 
237
                                data[byte_num(pos)] |= (1 << bit_num(pos));
 
238
                        }else{          //Bit was 1
 
239
                                data[byte_num(pos)] &= ~(1<<bit_num(pos));
 
240
                        }
 
241
                        return *this;
 
242
                }
 
243
 
 
244
                reference operator[](size_t pos){   // for b[i];
 
245
                        reference retval;
 
246
                        retval.parent = this;
 
247
                        retval.bit_num = pos;
 
248
                        return retval;
 
249
                }
 
250
 
 
251
                unsigned long to_ulong() const{
 
252
                        if(N > sizeof(unsigned long) * CHAR_BIT){
 
253
                                __throw_overflow_error();
 
254
                        }
 
255
                        unsigned long retval = 0;
 
256
                        size_t count = N;
 
257
                        for(size_t i = count; i > 0; --i){
 
258
                                if(test(i)){
 
259
                                        retval +=1;
 
260
                                }
 
261
                                retval<<=1;
 
262
                        }
 
263
                        if(test(0)){
 
264
                                retval +=1;
 
265
                        }
 
266
                        return retval;
 
267
                }
 
268
 
 
269
                template <class charT, class traits, class Allocator>
 
270
                        basic_string<charT, traits, Allocator> to_string() const
 
271
                {
 
272
                        basic_string<charT, traits, Allocator> retval;
 
273
                        retval.reserve(N);
 
274
                        for(size_t i = N ; i > 0; --i){
 
275
                                if(test(i-1) == true){
 
276
                                        retval.append("1");
 
277
                                }else{
 
278
                                        retval.append("0");
 
279
                                }
 
280
                        }
 
281
                        return retval;
 
282
                }
 
283
 
 
284
 
 
285
                size_t count() const{
 
286
                        size_t retval = 0;
 
287
                        for(size_t i =0; i < N; ++i){
 
288
                                if(test(i)){
 
289
                                        ++retval;
 
290
                                }
 
291
                        }
 
292
                        return retval;
 
293
                }
 
294
                size_t size()  const{
 
295
                        return N;
 
296
                }
 
297
 
 
298
                bitset<N>& operator=(const bitset<N> & rhs){
 
299
                        if(&rhs == this){
 
300
                                return *this;
 
301
                        }
 
302
                        for(size_t i = 0; i <= byte_num(N); ++i){
 
303
                                data[i] = rhs.data[i];
 
304
                        }
 
305
                        return *this;
 
306
                }
 
307
 
 
308
 
 
309
                bool operator==(const bitset<N>& rhs) const{
 
310
                        for(size_t i =0; i< N; ++i){
 
311
                                if(test(i) != rhs.test(i)){
 
312
                                        return false;
 
313
                                }
 
314
                        }
 
315
                        return true;
 
316
                }
 
317
 
 
318
                bool operator!=(const bitset<N>& rhs) const{
 
319
                        for(size_t i =0; i< N; ++i){
 
320
                                if(test(i) != rhs.test(i)){
 
321
                                        return true;
 
322
                                }
 
323
                        }
 
324
                        return false;
 
325
                }
 
326
 
 
327
                bool test(size_t pos) const{
 
328
                        return (data[byte_num(pos)] & (1<<bit_num(pos)) ) != 0;
 
329
                }
 
330
 
 
331
                bool any() const{
 
332
                        for(size_t i = 0; i< N; ++i){
 
333
                                if(test(i)==true){
 
334
                                        return true;
 
335
                                }
 
336
                        }
 
337
                        return false;
 
338
                }
 
339
 
 
340
                bool none() const{
 
341
                        if(any() == true){
 
342
                                return false;
 
343
                        }
 
344
                        return true;
 
345
                }
 
346
 
 
347
                bitset<N> operator<<(size_t pos) const{
 
348
                        bitset retval(*this);
 
349
                        retval<<=pos;
 
350
                        return retval;
 
351
                }
 
352
                bitset<N> operator>>(size_t pos) const{
 
353
                        bitset retval(*this);
 
354
                        retval>>=pos;
 
355
                        return retval;
 
356
                }
 
357
        };
 
358
 
 
359
        //Non-member functions
 
360
 
 
361
 
 
362
        template <size_t N> _UCXXEXPORT bitset<N> operator&(const bitset<N>& lhs, const bitset<N>& rhs){
 
363
                bitset<N> retval(lhs);
 
364
                retval &= rhs;
 
365
                return retval;
 
366
        }
 
367
 
 
368
        template <size_t N> _UCXXEXPORT bitset<N> operator|(const bitset<N>& lhs, const bitset<N>& rhs){
 
369
                bitset<N> retval(lhs);
 
370
                retval |= rhs;
 
371
                return retval;
 
372
        }
 
373
 
 
374
        template <size_t N> _UCXXEXPORT bitset<N> operator^(const bitset<N>& lhs, const bitset<N>& rhs){
 
375
                bitset<N> retval(lhs);
 
376
                retval ^= rhs;
 
377
                return retval;
 
378
        }
 
379
 
 
380
        template <class charT, class traits, size_t N> _UCXXEXPORT basic_istream<charT, traits>& 
 
381
                operator>>(basic_istream<charT, traits>& is, bitset<N>& x)
 
382
        {
 
383
                string s;
 
384
                charT c;
 
385
                for(size_t i = 0; i < N; ++i){
 
386
                        is.get(c);
 
387
                        if(!is.good()){
 
388
                                break;
 
389
                        }
 
390
                        if(c != '1' && c !='0'){
 
391
                                is.putback(c);
 
392
                                break;
 
393
                        }
 
394
                        s+=c;
 
395
                }
 
396
                bitset<N> temp(s);
 
397
                x = temp;
 
398
                
 
399
                return is;
 
400
        }
 
401
 
 
402
        template <class charT, class traits, size_t N> _UCXXEXPORT basic_ostream<charT, traits>& 
 
403
                operator<<(basic_ostream<charT, traits>& os, const bitset<N>& x)
 
404
        {
 
405
                for(size_t i = N ; i > 0; --i){
 
406
                        if(x.test(i-1) == true){
 
407
                                os << "1";
 
408
                        }else{
 
409
                                os << "0";
 
410
                        }
 
411
                }
 
412
                return os;
 
413
        }
 
414
 
 
415
 
 
416
 
 
417
 
 
418
}
 
419
 
 
420
#pragma GCC visibility pop
 
421
 
 
422
#endif
 
423