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