| /* |
| * The Apache Software License, Version 1.1 |
| * |
| * Copyright (c) 1999-2000 The Apache Software Foundation. All rights |
| * reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * |
| * 1. Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * |
| * 2. Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in |
| * the documentation and/or other materials provided with the |
| * distribution. |
| * |
| * 3. The end-user documentation included with the redistribution, |
| * if any, must include the following acknowledgment: |
| * "This product includes software developed by the |
| * Apache Software Foundation (http://www.apache.org/)." |
| * Alternately, this acknowledgment may appear in the software itself, |
| * if and wherever such third-party acknowledgments normally appear. |
| * |
| * 4. The names "Xerces" and "Apache Software Foundation" must |
| * not be used to endorse or promote products derived from this |
| * software without prior written permission. For written |
| * permission, please contact apache\@apache.org. |
| * |
| * 5. Products derived from this software may not be called "Apache", |
| * nor may "Apache" appear in their name, without prior written |
| * permission of the Apache Software Foundation. |
| * |
| * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED |
| * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
| * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE |
| * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR |
| * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF |
| * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND |
| * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, |
| * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT |
| * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
| * SUCH DAMAGE. |
| * ==================================================================== |
| * |
| * This software consists of voluntary contributions made by many |
| * individuals on behalf of the Apache Software Foundation, and was |
| * originally based on software copyright (c) 1999, International |
| * Business Machines, Inc., http://www.ibm.com . For more information |
| * on the Apache Software Foundation, please see |
| * <http://www.apache.org/>. |
| */ |
| |
| /* |
| * $Log$ |
| * Revision 1.3 2003/05/15 19:04:35 knoaman |
| * Partial implementation of the configurable memory manager. |
| * |
| * Revision 1.2 2002/11/04 15:22:03 tng |
| * C++ Namespace Support. |
| * |
| * Revision 1.1.1.1 2002/02/01 22:22:10 peiyongz |
| * sane_include |
| * |
| * Revision 1.4 2000/03/02 19:54:38 roddey |
| * This checkin includes many changes done while waiting for the |
| * 1.1.0 code to be finished. I can't list them all here, but a list is |
| * available elsewhere. |
| * |
| * Revision 1.3 2000/02/06 07:48:01 rahulj |
| * Year 2K copyright swat. |
| * |
| * Revision 1.2 1999/12/15 19:38:22 roddey |
| * Simple fix to bit ops comments |
| * |
| * Revision 1.1.1.1 1999/11/09 01:04:09 twl |
| * Initial checkin |
| * |
| * Revision 1.2 1999/11/08 20:45:05 rahul |
| * Swat for adding in Product name and CVS comment log variable. |
| * |
| */ |
| |
| |
| // --------------------------------------------------------------------------- |
| // Includes |
| // --------------------------------------------------------------------------- |
| #include <xercesc/util/BitSet.hpp> |
| #include <xercesc/framework/MemoryManager.hpp> |
| |
| XERCES_CPP_NAMESPACE_BEGIN |
| |
| // --------------------------------------------------------------------------- |
| // Local const data |
| // |
| // kBitsPerUnit |
| // The number of bits in each of our allocation units, which is a 32 |
| // bit value in this case. |
| // |
| // kGrowBy |
| // The minimum allocation units to grow the buffer by. |
| // --------------------------------------------------------------------------- |
| const unsigned int kBitsPerUnit = 32; |
| const unsigned int kGrowBy = 1; |
| |
| |
| |
| // --------------------------------------------------------------------------- |
| // BitSet: Constructors and Destructor |
| // --------------------------------------------------------------------------- |
| BitSet::BitSet( const unsigned int size |
| , MemoryManager* const manager) : |
| |
| fMemoryManager(manager) |
| , fBits(0) |
| , fUnitLen(0) |
| { |
| ensureCapacity(size); |
| } |
| |
| BitSet::BitSet(const BitSet& toCopy) : |
| |
| fMemoryManager(toCopy.fMemoryManager) |
| , fBits(0) |
| , fUnitLen(toCopy.fUnitLen) |
| { |
| fBits = (unsigned long*) fMemoryManager->allocate |
| ( |
| fUnitLen * sizeof(unsigned long) |
| ); //new unsigned long[fUnitLen]; |
| for (unsigned int i = 0; i < fUnitLen; i++) |
| fBits[i] = toCopy.fBits[i]; |
| } |
| |
| BitSet::~BitSet() |
| { |
| fMemoryManager->deallocate(fBits); //delete [] fBits; |
| } |
| |
| |
| // --------------------------------------------------------------------------- |
| // BitSet: Equality methods |
| // --------------------------------------------------------------------------- |
| bool BitSet::equals(const BitSet& other) const |
| { |
| if (this == &other) |
| return true; |
| |
| if (fUnitLen != other.fUnitLen) |
| return false; |
| |
| for (unsigned int i = 0; i < fUnitLen; i++) |
| { |
| if (fBits[i] != other.fBits[i]) |
| return false; |
| } |
| return true; |
| } |
| |
| |
| // --------------------------------------------------------------------------- |
| // BitSet: Getter methods |
| // --------------------------------------------------------------------------- |
| bool BitSet::get(const unsigned int index) const |
| { |
| const unsigned int unitOfBit = (index / kBitsPerUnit); |
| const unsigned int bitWithinUnit = index % kBitsPerUnit; |
| |
| // |
| // If the index is beyond our size, don't actually expand. Just return |
| // false, which is what the state would be if we did expand it. |
| // |
| bool retVal = false; |
| if (unitOfBit <= fUnitLen) |
| { |
| if (fBits[unitOfBit] & (1 << bitWithinUnit)) |
| retVal = true; |
| } |
| return retVal; |
| } |
| |
| |
| unsigned int BitSet::size() const |
| { |
| return fUnitLen * kBitsPerUnit; |
| } |
| |
| |
| |
| // --------------------------------------------------------------------------- |
| // BitSet: Setter methods |
| // --------------------------------------------------------------------------- |
| bool BitSet::allAreCleared() const |
| { |
| for (unsigned int index = 0; index < fUnitLen; index++) |
| { |
| if (fBits[index]) |
| return false; |
| } |
| return true; |
| } |
| |
| bool BitSet::allAreSet() const |
| { |
| for (unsigned int index = 0; index < fUnitLen; index++) |
| { |
| if (fBits[index] != 0xFFFFFFFF) |
| return false; |
| } |
| return true; |
| } |
| |
| void BitSet::clearAll() |
| { |
| // Just zero out all the units |
| for (unsigned int index = 0; index < fUnitLen; index++) |
| fBits[index] = 0; |
| } |
| |
| void BitSet::clear(const unsigned int index) |
| { |
| ensureCapacity(index+1); |
| |
| const int unitOfBit = (index / kBitsPerUnit); |
| const int bitWithinUnit = index % kBitsPerUnit; |
| |
| fBits[unitOfBit] &= ~(1UL << bitWithinUnit); |
| } |
| |
| |
| void BitSet::set(const unsigned int index) |
| { |
| ensureCapacity(index+1); |
| |
| const int unitOfBit = (index / kBitsPerUnit); |
| const int bitWithinUnit = index % kBitsPerUnit; |
| |
| fBits[unitOfBit] |= (1UL << bitWithinUnit); |
| } |
| |
| |
| |
| // --------------------------------------------------------------------------- |
| // BitSet: Bitwise logical methods |
| // --------------------------------------------------------------------------- |
| void BitSet::andWith(const BitSet& other) |
| { |
| if (fUnitLen < other.fUnitLen) |
| ensureCapacity(other.fUnitLen * kBitsPerUnit); |
| |
| for (unsigned int index = 0; index < other.fUnitLen; index++) |
| fBits[index] &= other.fBits[index]; |
| } |
| |
| |
| void BitSet::orWith(const BitSet& other) |
| { |
| if (fUnitLen < other.fUnitLen) |
| ensureCapacity(other.fUnitLen * kBitsPerUnit); |
| |
| for (unsigned int index = 0; index < other.fUnitLen; index++) |
| fBits[index] |= other.fBits[index]; |
| } |
| |
| |
| void BitSet::xorWith(const BitSet& other) |
| { |
| if (fUnitLen < other.fUnitLen) |
| ensureCapacity(other.fUnitLen * kBitsPerUnit); |
| |
| for (unsigned int index = 0; index < other.fUnitLen; index++) |
| fBits[index] ^= other.fBits[index]; |
| } |
| |
| |
| |
| // --------------------------------------------------------------------------- |
| // BitSet: Miscellaneous methods |
| // --------------------------------------------------------------------------- |
| unsigned int BitSet::hash(const unsigned int hashModulus) const |
| { |
| const unsigned char* pBytes = (const unsigned char*)fBits; |
| const int unsigned len = fUnitLen * sizeof(unsigned long); |
| |
| unsigned int hashVal = 0; |
| for (unsigned int index = 0; index < len; index++) |
| { |
| hashVal <<= 1; |
| hashVal ^= *pBytes; |
| } |
| return hashVal % hashModulus; |
| } |
| |
| |
| |
| // --------------------------------------------------------------------------- |
| // BitSet: Private methods |
| // --------------------------------------------------------------------------- |
| void BitSet::ensureCapacity(const unsigned int size) |
| { |
| // Calculate the units required to hold the passed bit count. |
| unsigned int unitsNeeded = size / kBitsPerUnit; |
| if (size % kBitsPerUnit) |
| unitsNeeded++; |
| |
| // If its more than we have, then reallocate |
| if (unitsNeeded > fUnitLen) |
| { |
| // Regrow the unit length by at least the expansion unit |
| if (unitsNeeded < (fUnitLen + kGrowBy)) |
| unitsNeeded = fUnitLen + kGrowBy; |
| |
| // Allocate the array, copy the old stuff, and zero the new stuff |
| unsigned long* newBits = (unsigned long*) fMemoryManager->allocate |
| ( |
| unitsNeeded * sizeof(unsigned long) |
| ); //new unsigned long[unitsNeeded]; |
| |
| unsigned int index; |
| for (index = 0; index < fUnitLen; index++) |
| newBits[index] = fBits[index]; |
| |
| for (; index < unitsNeeded; index++) |
| newBits[index] = 0; |
| |
| fMemoryManager->deallocate(fBits); //delete [] fBits; |
| fBits = newBits; |
| fUnitLen = unitsNeeded; |
| } |
| } |
| |
| XERCES_CPP_NAMESPACE_END |