GME
13
|
00001 /* 00002 * Licensed to the Apache Software Foundation (ASF) under one or more 00003 * contributor license agreements. See the NOTICE file distributed with 00004 * this work for additional information regarding copyright ownership. 00005 * The ASF licenses this file to You under the Apache License, Version 2.0 00006 * (the "License"); you may not use this file except in compliance with 00007 * the License. You may obtain a copy of the License at 00008 * 00009 * http://www.apache.org/licenses/LICENSE-2.0 00010 * 00011 * Unless required by applicable law or agreed to in writing, software 00012 * distributed under the License is distributed on an "AS IS" BASIS, 00013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 00014 * See the License for the specific language governing permissions and 00015 * limitations under the License. 00016 */ 00017 00018 /* 00019 * $Id: BitSet.cpp 676911 2008-07-15 13:27:32Z amassari $ 00020 */ 00021 00022 00023 // --------------------------------------------------------------------------- 00024 // Includes 00025 // --------------------------------------------------------------------------- 00026 #include <xercesc/util/BitSet.hpp> 00027 #include <xercesc/framework/MemoryManager.hpp> 00028 00029 XERCES_CPP_NAMESPACE_BEGIN 00030 00031 // --------------------------------------------------------------------------- 00032 // Local const data 00033 // 00034 // kBitsPerUnit 00035 // The number of bits in each of our allocation units, which is a 32 00036 // bit value in this case. 00037 // 00038 // kGrowBy 00039 // The minimum allocation units to grow the buffer by. 00040 // --------------------------------------------------------------------------- 00041 const XMLSize_t kBitsPerUnit = 32; 00042 const XMLSize_t kGrowBy = 1; 00043 00044 00045 00046 // --------------------------------------------------------------------------- 00047 // BitSet: Constructors and Destructor 00048 // --------------------------------------------------------------------------- 00049 BitSet::BitSet( const XMLSize_t size 00050 , MemoryManager* const manager) : 00051 00052 fMemoryManager(manager) 00053 , fBits(0) 00054 , fUnitLen(0) 00055 { 00056 ensureCapacity(size); 00057 } 00058 00059 BitSet::BitSet(const BitSet& toCopy) : 00060 XMemory(toCopy) 00061 , fMemoryManager(toCopy.fMemoryManager) 00062 , fBits(0) 00063 , fUnitLen(toCopy.fUnitLen) 00064 { 00065 fBits = (unsigned long*) fMemoryManager->allocate 00066 ( 00067 fUnitLen * sizeof(unsigned long) 00068 ); //new unsigned long[fUnitLen]; 00069 for (XMLSize_t i = 0; i < fUnitLen; i++) 00070 fBits[i] = toCopy.fBits[i]; 00071 } 00072 00073 BitSet::~BitSet() 00074 { 00075 fMemoryManager->deallocate(fBits); //delete [] fBits; 00076 } 00077 00078 00079 // --------------------------------------------------------------------------- 00080 // BitSet: Equality methods 00081 // --------------------------------------------------------------------------- 00082 bool BitSet::equals(const BitSet& other) const 00083 { 00084 if (this == &other) 00085 return true; 00086 00087 if (fUnitLen != other.fUnitLen) 00088 return false; 00089 00090 for (XMLSize_t i = 0; i < fUnitLen; i++) 00091 { 00092 if (fBits[i] != other.fBits[i]) 00093 return false; 00094 } 00095 return true; 00096 } 00097 00098 00099 // --------------------------------------------------------------------------- 00100 // BitSet: Getter methods 00101 // --------------------------------------------------------------------------- 00102 bool BitSet::get(const XMLSize_t index) const 00103 { 00104 const XMLSize_t unitOfBit = (index / kBitsPerUnit); 00105 const XMLSize_t bitWithinUnit = index % kBitsPerUnit; 00106 00107 // 00108 // If the index is beyond our size, don't actually expand. Just return 00109 // false, which is what the state would be if we did expand it. 00110 // 00111 bool retVal = false; 00112 if (unitOfBit <= fUnitLen) 00113 { 00114 if (fBits[unitOfBit] & (1 << bitWithinUnit)) 00115 retVal = true; 00116 } 00117 return retVal; 00118 } 00119 00120 00121 XMLSize_t BitSet::size() const 00122 { 00123 return fUnitLen * kBitsPerUnit; 00124 } 00125 00126 00127 00128 // --------------------------------------------------------------------------- 00129 // BitSet: Setter methods 00130 // --------------------------------------------------------------------------- 00131 bool BitSet::allAreCleared() const 00132 { 00133 for (XMLSize_t index = 0; index < fUnitLen; index++) 00134 { 00135 if (fBits[index]) 00136 return false; 00137 } 00138 return true; 00139 } 00140 00141 bool BitSet::allAreSet() const 00142 { 00143 for (XMLSize_t index = 0; index < fUnitLen; index++) 00144 { 00145 if (fBits[index] != 0xFFFFFFFF) 00146 return false; 00147 } 00148 return true; 00149 } 00150 00151 void BitSet::clearAll() 00152 { 00153 // Just zero out all the units 00154 for (XMLSize_t index = 0; index < fUnitLen; index++) 00155 fBits[index] = 0; 00156 } 00157 00158 void BitSet::clear(const XMLSize_t index) 00159 { 00160 ensureCapacity(index+1); 00161 00162 const XMLSize_t unitOfBit = (index / kBitsPerUnit); 00163 const XMLSize_t bitWithinUnit = index % kBitsPerUnit; 00164 00165 fBits[unitOfBit] &= ~(1UL << bitWithinUnit); 00166 } 00167 00168 00169 void BitSet::set(const XMLSize_t index) 00170 { 00171 ensureCapacity(index+1); 00172 00173 const XMLSize_t unitOfBit = (index / kBitsPerUnit); 00174 const XMLSize_t bitWithinUnit = index % kBitsPerUnit; 00175 00176 fBits[unitOfBit] |= (1UL << bitWithinUnit); 00177 } 00178 00179 00180 00181 // --------------------------------------------------------------------------- 00182 // BitSet: Bitwise logical methods 00183 // --------------------------------------------------------------------------- 00184 void BitSet::andWith(const BitSet& other) 00185 { 00186 if (fUnitLen < other.fUnitLen) 00187 ensureCapacity(other.fUnitLen * kBitsPerUnit); 00188 00189 for (XMLSize_t index = 0; index < other.fUnitLen; index++) 00190 fBits[index] &= other.fBits[index]; 00191 } 00192 00193 00194 void BitSet::orWith(const BitSet& other) 00195 { 00196 if (fUnitLen < other.fUnitLen) 00197 ensureCapacity(other.fUnitLen * kBitsPerUnit); 00198 00199 for (XMLSize_t index = 0; index < other.fUnitLen; index++) 00200 fBits[index] |= other.fBits[index]; 00201 } 00202 00203 00204 void BitSet::xorWith(const BitSet& other) 00205 { 00206 if (fUnitLen < other.fUnitLen) 00207 ensureCapacity(other.fUnitLen * kBitsPerUnit); 00208 00209 for (XMLSize_t index = 0; index < other.fUnitLen; index++) 00210 fBits[index] ^= other.fBits[index]; 00211 } 00212 00213 00214 00215 // --------------------------------------------------------------------------- 00216 // BitSet: Miscellaneous methods 00217 // --------------------------------------------------------------------------- 00218 XMLSize_t BitSet::hash(const XMLSize_t hashModulus) const 00219 { 00220 const unsigned char* pBytes = (const unsigned char*)fBits; 00221 const XMLSize_t len = fUnitLen * sizeof(unsigned long); 00222 00223 XMLSize_t hashVal = 0; 00224 for (XMLSize_t index = 0; index < len; index++) 00225 { 00226 hashVal <<= 1; 00227 hashVal ^= *pBytes; 00228 } 00229 return hashVal % hashModulus; 00230 } 00231 00232 00233 00234 // --------------------------------------------------------------------------- 00235 // BitSet: Private methods 00236 // --------------------------------------------------------------------------- 00237 void BitSet::ensureCapacity(const XMLSize_t size) 00238 { 00239 // If we have enough space, do nothing 00240 if(fUnitLen * kBitsPerUnit >= size) 00241 return; 00242 00243 // Calculate the units required to hold the passed bit count. 00244 XMLSize_t unitsNeeded = size / kBitsPerUnit; 00245 if (size % kBitsPerUnit) 00246 unitsNeeded++; 00247 00248 // Regrow the unit length by at least the expansion unit 00249 if (unitsNeeded < (fUnitLen + kGrowBy)) 00250 unitsNeeded = fUnitLen + kGrowBy; 00251 00252 // Allocate the array, copy the old stuff, and zero the new stuff 00253 unsigned long* newBits = (unsigned long*) fMemoryManager->allocate 00254 ( 00255 unitsNeeded * sizeof(unsigned long) 00256 ); //new unsigned long[unitsNeeded]; 00257 00258 XMLSize_t index; 00259 for (index = 0; index < fUnitLen; index++) 00260 newBits[index] = fBits[index]; 00261 00262 for (; index < unitsNeeded; index++) 00263 newBits[index] = 0; 00264 00265 fMemoryManager->deallocate(fBits); //delete [] fBits; 00266 fBits = newBits; 00267 fUnitLen = unitsNeeded; 00268 } 00269 00270 XERCES_CPP_NAMESPACE_END