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