/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: Dan
  • Date: 2011-11-03 00:54:13 UTC
  • Revision ID: dan@waxworlds.org-20111103005413-miheyjsrpm3a0r1e
modified notes

Show diffs side-by-side

added added

removed removed

Lines of Context:
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