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