2 **********************************************************************
3 * Copyright (C) 2007, International Business Machines
4 * Corporation and others. All Rights Reserved.
5 **********************************************************************
6 * file name: bitset.cpp
8 * tab size: 8 (not used)
11 * created on: 2007jan15
12 * created by: Markus Scherer
14 * Idea for a "compiled", fast, read-only (immutable) version of a UnicodeSet
15 * using a folded bit set consisting of a 1k-entry index table and a
16 * compacted array of 64-bit words.
17 * Uses a simple hash table for compaction.
18 * Uses the original set for supplementary code points.
21 #include "unicode/utypes.h"
25 * Hash table for up to 1k 64-bit words, for 1 bit per BMP code point.
26 * Hashes 64-bit words and maps them to 16-bit integers which are
27 * assigned in order of new incoming words for subsequent storage
28 * in a contiguous array.
30 struct BMPBitHash
: public UObject
{
31 int64_t keys
[0x800]; // 2k
32 uint16_t values
[0x800];
33 uint16_t reverse
[0x400];
35 const int32_t prime
=1301; // Less than 2k.
37 BMPBitHash() : count(0) {
38 // Fill values[] with 0xffff.
39 uprv_memset(values
, 0xff, sizeof(values
));
43 * Map a key to an integer count.
44 * Map at most 1k=0x400 different keys with this data structure.
46 uint16_t map(int64_t key
) {
47 int32_t hash
=(int32_t)(key
>>55)&0x1ff;
48 hash
^=(int32_t)(key
>>44)&0x7ff;
49 hash
^=(int32_t)(key
>>33)&0x7ff;
50 hash
^=(int32_t)(key
>>22)&0x7ff;
51 hash
^=(int32_t)(key
>>11)&0x7ff;
52 hash
^=(int32_t)key
&0x7ff;
54 if(values
[hash
]==0xffff) {
58 return values
[hash
]=count
++;
59 } else if(keys
[hash
]==key
) {
60 // Found a slot with this key.
63 // Used slot with a different key, move to another slot.
64 hash
=(hash
+prime
)&0x7ff;
69 uint16_t countKeys() const { return count
; }
72 * Invert the hash map: Fill an array of length countKeys() with the keys
73 * indexed by their mapped values.
75 void invert(int64_t *k
) const {
78 for(i
=0; i
<count
; ++i
) {
79 k
[i
]=keys
[reverse
[i
]];
84 class BitSet
: public UObject
, public UnicodeContainable
{
86 BitSet(const UnicodeSet
&set
, UErrorCode
&errorCode
) : bits(shortBits
), restSet(set
.clone()) {
87 if(U_FAILURE(errorCode
)) {
90 BMPBitHash
*bitHash
=new BMPBitHash
;
91 if(bitHash
==NULL
|| restSet
==NULL
) {
92 errorCode
=U_MEMORY_ALLOCATION_ERROR
;
96 UnicodeSetIterator
iter(set
);
99 int32_t prevIndex
, i
, j
;
101 b
=0; // Not necessary but makes compilers happy.
104 if(iter
.nextRange() && !iter
.isString()) {
105 start
=iter
.getCodepoint();
106 end
=iter
.getCodepointEnd();
112 // Finish the end of the previous range.
116 index
[prevIndex
++]=bitHash
->map(b
);
118 // Fill all-zero entries between ranges.
120 uint16_t zero
=bitHash
->map(0);
122 index
[prevIndex
++]=zero
;
123 } while(prevIndex
<i
);
130 b
|=~((INT64_C(1)<<(start
&0x3f))-1);
133 // Set bits for the start of the range.
134 index
[i
++]=bitHash
->map(b
);
135 // Fill all-one entries inside the range.
137 uint16_t all
=bitHash
->map(INT64_C(0xffffffffffffffff));
142 b
=INT64_C(0xffffffffffffffff);
145 b
&=(INT64_C(1)<<(end
&0x3f))-1;
149 if(bitHash
->countKeys()>LENGTHOF(shortBits
)) {
150 bits
=(int64_t *)uprv_malloc(bitHash
->countKeys()*8);
153 bitHash
->invert(bits
);
156 errorCode
=U_MEMORY_ALLOCATION_ERROR
;
160 latin1Set
[0]=(uint32_t)bits
[0];
161 latin1Set
[1]=(uint32_t)(bits
[0]>>32);
162 latin1Set
[2]=(uint32_t)bits
[1];
163 latin1Set
[3]=(uint32_t)(bits
[1]>>32);
164 latin1Set
[4]=(uint32_t)bits
[2];
165 latin1Set
[5]=(uint32_t)(bits
[2]>>32);
166 latin1Set
[6]=(uint32_t)bits
[3];
167 latin1Set
[7]=(uint32_t)(bits
[3]>>32);
169 restSet
.remove(0, 0xffff);
173 if(bits
!=shortBits
) {
179 UBool
contains(UChar32 c
) const {
180 if((uint32_t)c
<=0xff) {
181 return (UBool
)((latin1Set
[c
>>5]&((uint32_t)1<<(c
&0x1f)))!=0);
182 } else if((uint32_t)c
<0xffff) {
183 return (UBool
)((bits
[c
>>6]&(INT64_C(1)<<(c
&0x3f)))!=0);
185 return restSet
->contains(c
);
190 uint16_t index
[0x400];
191 int64_t shortBits
[32];
194 uint32_t latin1Bits
[8];