GME  13
BitSet.cpp
Go to the documentation of this file.
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