1ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru/* 2ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru********************************************************************** 3ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru* Copyright (c) 2002-2005, International Business Machines 4ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru* Corporation and others. All Rights Reserved. 5ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru********************************************************************** 6ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru* 2002-09-20 aliu Created. 7ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru*/ 8ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 9ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#include "unicode/utypes.h" 10ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#include "cmemory.h" 11ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#include "bitset.h" 12ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 13ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru// TODO: have a separate capacity, so the len can just be set to 14ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru// zero in the clearAll() method, and growth can be smarter. 15ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 16ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queruconst int32_t SLOP = 8; 17ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 18ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queruconst int32_t BYTES_PER_WORD = sizeof(int32_t); 19ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 20ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste QueruBitSet::BitSet() { 21ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru len = SLOP; 22ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru data = (int32_t*) uprv_malloc(len * BYTES_PER_WORD); 23ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru clearAll(); 24ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru} 25ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 26ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste QueruBitSet::~BitSet() { 27ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru uprv_free(data); 28ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru} 29ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 30ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste QueruUBool BitSet::get(int32_t bitIndex) const { 31ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru uint32_t longIndex = bitIndex >> 5; 32ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru int32_t bitInLong = bitIndex & 0x1F; 33ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru return (longIndex < len) ? (((data[longIndex] >> bitInLong) & 1) != 0) 34ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru : FALSE; 35ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru} 36ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 37ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queruvoid BitSet::set(int32_t bitIndex) { 38ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru uint32_t longIndex = bitIndex >> 5; 39ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru int32_t bitInLong = bitIndex & 0x1F; 40ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if (longIndex >= len) { 41ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru ensureCapacity(longIndex+1); 42ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 43ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru data[longIndex] |= (1 << bitInLong); 44ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru} 45ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 46ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queruvoid BitSet::clearAll() { 47ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru for (uint32_t i=0; i<len; ++i) data[i] = 0; 48ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru} 49ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 50ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queruvoid BitSet::ensureCapacity(uint32_t minLen) { 51ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru uint32_t newLen = len; 52ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru while (newLen < minLen) newLen <<= 1; // grow exponentially 53ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru int32_t* newData = (int32_t*) uprv_malloc(newLen * BYTES_PER_WORD); 54ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru uprv_memcpy(newData, data, len * BYTES_PER_WORD); 55ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru uprv_free(data); 56ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru data = newData; 57ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru int32_t* p = data + len; 58ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru int32_t* limit = data + newLen; 59ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru while (p < limit) *p++ = 0; 60ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru len = newLen; 61ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru} 62ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 63ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru//eof 64