00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029 #ifndef BITVECTOR_H
00030 #define BITVECTOR_H
00031
00032 #include <cstddef>
00033
00034 #include "fwdconf.h"
00035 #include "ft_allocator.h"
00036
00037 class bitvector;
00038 class ibitvector;
00039
00040 typedef unsigned long bv_atom_t;
00041
00042
00043
00044 static const unsigned char bv_atom_bits = sizeof(bv_atom_t) * 8;
00045 static const unsigned char bv_atom_bits_mask = bv_atom_bits - 1;
00046 static const unsigned char bv_atom_bits_shift
00047 = (bv_atom_bits == 32 ? 5 :
00048 (bv_atom_bits == 64 ? 6 :
00049 (bv_atom_bits == 16 ? 4 :
00050 2)));
00051
00056 class bitvector {
00057 public:
00060 bitvector(size_t size);
00061 ~bitvector();
00062
00063 bool test(size_t pos) const;
00064 bool set(size_t pos);
00065
00066 void set(const ibitvector & x);
00067
00068 void clear();
00070 size_t get_count() const;
00072 size_t get_size() const;
00073
00074 private:
00075 bv_atom_t * elements;
00076 const size_t size;
00077 size_t count;
00078
00079 size_t element_size() const;
00080
00081 static size_t set(bv_atom_t * x, bv_atom_t * xe,
00082 const bv_atom_t * y, const bv_atom_t *ye);
00083 };
00084
00089 class ibitvector {
00090 public:
00091 ibitvector();
00092
00093 bool test(size_t pos) const;
00094 bool set(size_t pos, FTAllocator &);
00095
00096 void clear();
00097 size_t get_count() const;
00098 size_t get_size() const;
00099
00100 private:
00101 struct index;
00102 struct block;
00103
00104 static const unsigned int block_size = 16;
00105 static const unsigned int block_shift = 4;
00106 static const unsigned int block_mask = block_size - 1;
00107
00108 static const unsigned int index_size = 16;
00109 static const unsigned int index_shift = 4;
00110 static const unsigned int index_mask = index_size - 1;
00111
00112 union index_or_block {
00113 block * b;
00114 index * i;
00115 };
00116
00117 struct block {
00118 index * up;
00119 bv_atom_t elements[block_size];
00120
00121 block(index *);
00122 };
00123
00124 struct index {
00125 index * up;
00126 index_or_block down[index_size];
00127
00128 index(index *);
00129 };
00130
00131 class iterator {
00132 public:
00133 iterator(const block &);
00134
00135 size_t element_address() const;
00136 const block * next_block();
00137
00138 private:
00139 index * bi;
00140 size_t addr;
00141 unsigned char level;
00142 };
00143
00144 size_t count;
00145 size_t size;
00146 block first_block;
00147
00148 friend class bitvector;
00149 };
00150
00151 #ifdef HAVE_INLINE
00152 #include "bitvector.icc"
00153 #endif
00154
00155 #endif