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
00030 #include "w_defines.h"
00031
00032
00033
00034 #define W_SOURCE
00035 #ifdef __GNUC__
00036 # pragma implementation
00037 #endif
00038
00039 #include "w_base.h"
00040 #include <cstring>
00041 #include "w_bitmap.h"
00042
00043 inline int div8(long x) { return x >> 3; }
00044 inline int mod8(long x) { return x & 7; }
00045 inline int div32(long x) { return x >> 5; }
00046 inline int mod32(long x) { return x & 31; }
00047
00048 int
00049 w_bitmap_t::bytesForBits(uint4_t numBits)
00050 {
00051 return (div8(numBits -1) + 1);
00052 }
00053
00054
00055 NORET
00056 w_bitmap_t::w_bitmap_t(uint4_t size)
00057 : sz(size), mem_alloc(true)
00058 {
00059 int n = bytesForBits(size);
00060 ptr = new uint1_t[n] ;
00061 if (!ptr) W_FATAL(fcOUTOFMEMORY) ;
00062 }
00063
00064 void
00065 w_bitmap_t::zero()
00066 {
00067 int n = bytesForBits(sz);
00068 memset(ptr, 0, n);
00069 }
00070
00071 void
00072 w_bitmap_t::fill()
00073 {
00074 int n = bytesForBits(sz);
00075 memset(ptr, 0xff, n);
00076 }
00077
00078 bool
00079 w_bitmap_t::is_set(uint4_t offset) const
00080 {
00081 return (ptr[div8(offset)] & (1 << mod8(offset))) != 0;
00082 }
00083
00084 void
00085 w_bitmap_t::set(uint4_t offset)
00086 {
00087 ptr[div8(offset)] |= (1 << mod8(offset));
00088 }
00089
00090 void
00091 w_bitmap_t::clr(uint4_t offset)
00092 {
00093 ptr[div8(offset)] &= ~(1 << mod8(offset));
00094 }
00095
00096 w_base_t::int4_t
00097 w_bitmap_t::first_set(uint4_t start) const
00098 {
00099 w_assert9(start < sz);
00100 register uint1_t* p = ptr + div8(start);
00101 register uint4_t mask = 1 << mod8(start);
00102 register uint4_t size = sz;
00103 for (size -= start; size; start++, size--) {
00104 if (*p & mask) {
00105 w_assert9(is_set(start));
00106 return start;
00107 }
00108 if ((mask <<= 1) == 0x100) {
00109 mask = 1;
00110 p++;
00111 }
00112 }
00113
00114 return -1;
00115 }
00116
00117 w_base_t::int4_t
00118 w_bitmap_t::first_clr(uint4_t start) const
00119 {
00120 w_assert9(start < sz);
00121 register uint1_t* p = ptr + div8(start);
00122 register uint4_t mask = 1 << mod8(start);
00123 register uint4_t size = sz;
00124 for (size -= start; size; start++, size--) {
00125 if ((*p & mask) == 0) {
00126 return start;
00127 }
00128 if ((mask <<= 1) == 0x100) {
00129 mask = 1;
00130 p++;
00131 }
00132 }
00133
00134 return -1;
00135 }
00136
00137 w_base_t::uint4_t
00138 w_bitmap_t::num_set() const
00139 {
00140 uint1_t* p = ptr;
00141 uint4_t size = sz;
00142 int count;
00143 int mask;
00144 for (count = 0, mask = 1; size; size--) {
00145 if (*p & mask) count++;
00146 if ((mask <<= 1) == 0x100) {
00147 mask = 1;
00148 p++;
00149 }
00150 }
00151 return count;
00152 }
00153
00154 ostream& operator<<(ostream& o, const w_bitmap_t& obj)
00155 {
00156 for (register unsigned i = 0; i < obj.sz; i++) {
00157 o << (obj.is_set(i) != 0);
00158 }
00159 return o;
00160 }
00161