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