1 /*
2 *******************************************************************************
3 * Copyright (C) 2010-2011, International Business Machines
4 * Corporation and others. All Rights Reserved.
5 *******************************************************************************
6 * file name: ucharstriebuilder.h
7 * encoding: US-ASCII
8 * tab size: 8 (not used)
9 * indentation:4
10 *
11 * created on: 2010nov14
12 * created by: Markus W. Scherer
13 */
14
15 #include "unicode/utypes.h"
16 #include "unicode/ucharstrie.h"
17 #include "unicode/ucharstriebuilder.h"
18 #include "unicode/unistr.h"
19 #include "unicode/ustring.h"
20 #include "cmemory.h"
21 #include "uarrsort.h"
22 #include "uassert.h"
23 #include "uhash.h"
24
25 U_NAMESPACE_BEGIN
26
27 /*
28 * Note: This builder implementation stores (string, value) pairs with full copies
29 * of the 16-bit-unit sequences, until the UCharsTrie is built.
30 * It might(!) take less memory if we collected the data in a temporary, dynamic trie.
31 */
32
33 class UCharsTrieElement : public UMemory {
34 public:
35 // Use compiler's default constructor, initializes nothing.
36
37 void setTo(const UnicodeString &s, int32_t val, UnicodeString &strings, UErrorCode &errorCode);
38
getString(const UnicodeString & strings) const39 UnicodeString getString(const UnicodeString &strings) const {
40 int32_t length=strings[stringOffset];
41 return strings.tempSubString(stringOffset+1, length);
42 }
getStringLength(const UnicodeString & strings) const43 int32_t getStringLength(const UnicodeString &strings) const {
44 return strings[stringOffset];
45 }
46
charAt(int32_t index,const UnicodeString & strings) const47 UChar charAt(int32_t index, const UnicodeString &strings) const {
48 return strings[stringOffset+1+index];
49 }
50
getValue() const51 int32_t getValue() const { return value; }
52
53 int32_t compareStringTo(const UCharsTrieElement &o, const UnicodeString &strings) const;
54
55 private:
56 // The first strings unit contains the string length.
57 // (Compared with a stringLength field here, this saves 2 bytes per string.)
58 int32_t stringOffset;
59 int32_t value;
60 };
61
62 void
setTo(const UnicodeString & s,int32_t val,UnicodeString & strings,UErrorCode & errorCode)63 UCharsTrieElement::setTo(const UnicodeString &s, int32_t val,
64 UnicodeString &strings, UErrorCode &errorCode) {
65 if(U_FAILURE(errorCode)) {
66 return;
67 }
68 int32_t length=s.length();
69 if(length>0xffff) {
70 // Too long: We store the length in 1 unit.
71 errorCode=U_INDEX_OUTOFBOUNDS_ERROR;
72 return;
73 }
74 stringOffset=strings.length();
75 strings.append((UChar)length);
76 value=val;
77 strings.append(s);
78 }
79
80 int32_t
compareStringTo(const UCharsTrieElement & other,const UnicodeString & strings) const81 UCharsTrieElement::compareStringTo(const UCharsTrieElement &other, const UnicodeString &strings) const {
82 return getString(strings).compare(other.getString(strings));
83 }
84
UCharsTrieBuilder(UErrorCode &)85 UCharsTrieBuilder::UCharsTrieBuilder(UErrorCode & /*errorCode*/)
86 : elements(NULL), elementsCapacity(0), elementsLength(0),
87 uchars(NULL), ucharsCapacity(0), ucharsLength(0) {}
88
~UCharsTrieBuilder()89 UCharsTrieBuilder::~UCharsTrieBuilder() {
90 delete[] elements;
91 uprv_free(uchars);
92 }
93
94 UCharsTrieBuilder &
add(const UnicodeString & s,int32_t value,UErrorCode & errorCode)95 UCharsTrieBuilder::add(const UnicodeString &s, int32_t value, UErrorCode &errorCode) {
96 if(U_FAILURE(errorCode)) {
97 return *this;
98 }
99 if(ucharsLength>0) {
100 // Cannot add elements after building.
101 errorCode=U_NO_WRITE_PERMISSION;
102 return *this;
103 }
104 if(elementsLength==elementsCapacity) {
105 int32_t newCapacity;
106 if(elementsCapacity==0) {
107 newCapacity=1024;
108 } else {
109 newCapacity=4*elementsCapacity;
110 }
111 UCharsTrieElement *newElements=new UCharsTrieElement[newCapacity];
112 if(newElements==NULL) {
113 errorCode=U_MEMORY_ALLOCATION_ERROR;
114 }
115 if(elementsLength>0) {
116 uprv_memcpy(newElements, elements, elementsLength*sizeof(UCharsTrieElement));
117 }
118 delete[] elements;
119 elements=newElements;
120 elementsCapacity=newCapacity;
121 }
122 elements[elementsLength++].setTo(s, value, strings, errorCode);
123 if(U_SUCCESS(errorCode) && strings.isBogus()) {
124 errorCode=U_MEMORY_ALLOCATION_ERROR;
125 }
126 return *this;
127 }
128
129 U_CDECL_BEGIN
130
131 static int32_t U_CALLCONV
compareElementStrings(const void * context,const void * left,const void * right)132 compareElementStrings(const void *context, const void *left, const void *right) {
133 const UnicodeString *strings=reinterpret_cast<const UnicodeString *>(context);
134 const UCharsTrieElement *leftElement=reinterpret_cast<const UCharsTrieElement *>(left);
135 const UCharsTrieElement *rightElement=reinterpret_cast<const UCharsTrieElement *>(right);
136 return leftElement->compareStringTo(*rightElement, *strings);
137 }
138
139 U_CDECL_END
140
141 UCharsTrie *
build(UStringTrieBuildOption buildOption,UErrorCode & errorCode)142 UCharsTrieBuilder::build(UStringTrieBuildOption buildOption, UErrorCode &errorCode) {
143 buildUChars(buildOption, errorCode);
144 UCharsTrie *newTrie=NULL;
145 if(U_SUCCESS(errorCode)) {
146 newTrie=new UCharsTrie(uchars, uchars+(ucharsCapacity-ucharsLength));
147 if(newTrie==NULL) {
148 errorCode=U_MEMORY_ALLOCATION_ERROR;
149 } else {
150 uchars=NULL; // The new trie now owns the array.
151 ucharsCapacity=0;
152 }
153 }
154 return newTrie;
155 }
156
157 UnicodeString &
buildUnicodeString(UStringTrieBuildOption buildOption,UnicodeString & result,UErrorCode & errorCode)158 UCharsTrieBuilder::buildUnicodeString(UStringTrieBuildOption buildOption, UnicodeString &result,
159 UErrorCode &errorCode) {
160 buildUChars(buildOption, errorCode);
161 if(U_SUCCESS(errorCode)) {
162 result.setTo(FALSE, uchars+(ucharsCapacity-ucharsLength), ucharsLength);
163 }
164 return result;
165 }
166
167 void
buildUChars(UStringTrieBuildOption buildOption,UErrorCode & errorCode)168 UCharsTrieBuilder::buildUChars(UStringTrieBuildOption buildOption, UErrorCode &errorCode) {
169 if(U_FAILURE(errorCode)) {
170 return;
171 }
172 if(uchars!=NULL && ucharsLength>0) {
173 // Already built.
174 return;
175 }
176 if(ucharsLength==0) {
177 if(elementsLength==0) {
178 errorCode=U_INDEX_OUTOFBOUNDS_ERROR;
179 return;
180 }
181 if(strings.isBogus()) {
182 errorCode=U_MEMORY_ALLOCATION_ERROR;
183 return;
184 }
185 uprv_sortArray(elements, elementsLength, (int32_t)sizeof(UCharsTrieElement),
186 compareElementStrings, &strings,
187 FALSE, // need not be a stable sort
188 &errorCode);
189 if(U_FAILURE(errorCode)) {
190 return;
191 }
192 // Duplicate strings are not allowed.
193 UnicodeString prev=elements[0].getString(strings);
194 for(int32_t i=1; i<elementsLength; ++i) {
195 UnicodeString current=elements[i].getString(strings);
196 if(prev==current) {
197 errorCode=U_ILLEGAL_ARGUMENT_ERROR;
198 return;
199 }
200 prev.fastCopyFrom(current);
201 }
202 }
203 // Create and UChar-serialize the trie for the elements.
204 ucharsLength=0;
205 int32_t capacity=strings.length();
206 if(capacity<1024) {
207 capacity=1024;
208 }
209 if(ucharsCapacity<capacity) {
210 uprv_free(uchars);
211 uchars=reinterpret_cast<UChar *>(uprv_malloc(capacity*2));
212 if(uchars==NULL) {
213 errorCode=U_MEMORY_ALLOCATION_ERROR;
214 ucharsCapacity=0;
215 return;
216 }
217 ucharsCapacity=capacity;
218 }
219 StringTrieBuilder::build(buildOption, elementsLength, errorCode);
220 if(uchars==NULL) {
221 errorCode=U_MEMORY_ALLOCATION_ERROR;
222 }
223 }
224
225 int32_t
getElementStringLength(int32_t i) const226 UCharsTrieBuilder::getElementStringLength(int32_t i) const {
227 return elements[i].getStringLength(strings);
228 }
229
230 UChar
getElementUnit(int32_t i,int32_t unitIndex) const231 UCharsTrieBuilder::getElementUnit(int32_t i, int32_t unitIndex) const {
232 return elements[i].charAt(unitIndex, strings);
233 }
234
235 int32_t
getElementValue(int32_t i) const236 UCharsTrieBuilder::getElementValue(int32_t i) const {
237 return elements[i].getValue();
238 }
239
240 int32_t
getLimitOfLinearMatch(int32_t first,int32_t last,int32_t unitIndex) const241 UCharsTrieBuilder::getLimitOfLinearMatch(int32_t first, int32_t last, int32_t unitIndex) const {
242 const UCharsTrieElement &firstElement=elements[first];
243 const UCharsTrieElement &lastElement=elements[last];
244 int32_t minStringLength=firstElement.getStringLength(strings);
245 while(++unitIndex<minStringLength &&
246 firstElement.charAt(unitIndex, strings)==
247 lastElement.charAt(unitIndex, strings)) {}
248 return unitIndex;
249 }
250
251 int32_t
countElementUnits(int32_t start,int32_t limit,int32_t unitIndex) const252 UCharsTrieBuilder::countElementUnits(int32_t start, int32_t limit, int32_t unitIndex) const {
253 int32_t length=0; // Number of different units at unitIndex.
254 int32_t i=start;
255 do {
256 UChar unit=elements[i++].charAt(unitIndex, strings);
257 while(i<limit && unit==elements[i].charAt(unitIndex, strings)) {
258 ++i;
259 }
260 ++length;
261 } while(i<limit);
262 return length;
263 }
264
265 int32_t
skipElementsBySomeUnits(int32_t i,int32_t unitIndex,int32_t count) const266 UCharsTrieBuilder::skipElementsBySomeUnits(int32_t i, int32_t unitIndex, int32_t count) const {
267 do {
268 UChar unit=elements[i++].charAt(unitIndex, strings);
269 while(unit==elements[i].charAt(unitIndex, strings)) {
270 ++i;
271 }
272 } while(--count>0);
273 return i;
274 }
275
276 int32_t
indexOfElementWithNextUnit(int32_t i,int32_t unitIndex,UChar unit) const277 UCharsTrieBuilder::indexOfElementWithNextUnit(int32_t i, int32_t unitIndex, UChar unit) const {
278 while(unit==elements[i].charAt(unitIndex, strings)) {
279 ++i;
280 }
281 return i;
282 }
283
UCTLinearMatchNode(const UChar * units,int32_t len,Node * nextNode)284 UCharsTrieBuilder::UCTLinearMatchNode::UCTLinearMatchNode(const UChar *units, int32_t len, Node *nextNode)
285 : LinearMatchNode(len, nextNode), s(units) {
286 hash=hash*37+uhash_hashUCharsN(units, len);
287 }
288
289 UBool
operator ==(const Node & other) const290 UCharsTrieBuilder::UCTLinearMatchNode::operator==(const Node &other) const {
291 if(this==&other) {
292 return TRUE;
293 }
294 if(!LinearMatchNode::operator==(other)) {
295 return FALSE;
296 }
297 const UCTLinearMatchNode &o=(const UCTLinearMatchNode &)other;
298 return 0==u_memcmp(s, o.s, length);
299 }
300
301 void
write(StringTrieBuilder & builder)302 UCharsTrieBuilder::UCTLinearMatchNode::write(StringTrieBuilder &builder) {
303 UCharsTrieBuilder &b=(UCharsTrieBuilder &)builder;
304 next->write(builder);
305 b.write(s, length);
306 offset=b.writeValueAndType(hasValue, value, b.getMinLinearMatch()+length-1);
307 }
308
309 StringTrieBuilder::Node *
createLinearMatchNode(int32_t i,int32_t unitIndex,int32_t length,Node * nextNode) const310 UCharsTrieBuilder::createLinearMatchNode(int32_t i, int32_t unitIndex, int32_t length,
311 Node *nextNode) const {
312 return new UCTLinearMatchNode(
313 elements[i].getString(strings).getBuffer()+unitIndex,
314 length,
315 nextNode);
316 }
317
318 UBool
ensureCapacity(int32_t length)319 UCharsTrieBuilder::ensureCapacity(int32_t length) {
320 if(uchars==NULL) {
321 return FALSE; // previous memory allocation had failed
322 }
323 if(length>ucharsCapacity) {
324 int32_t newCapacity=ucharsCapacity;
325 do {
326 newCapacity*=2;
327 } while(newCapacity<=length);
328 UChar *newUChars=reinterpret_cast<UChar *>(uprv_malloc(newCapacity*2));
329 if(newUChars==NULL) {
330 // unable to allocate memory
331 uprv_free(uchars);
332 uchars=NULL;
333 ucharsCapacity=0;
334 return FALSE;
335 }
336 u_memcpy(newUChars+(newCapacity-ucharsLength),
337 uchars+(ucharsCapacity-ucharsLength), ucharsLength);
338 uprv_free(uchars);
339 uchars=newUChars;
340 ucharsCapacity=newCapacity;
341 }
342 return TRUE;
343 }
344
345 int32_t
write(int32_t unit)346 UCharsTrieBuilder::write(int32_t unit) {
347 int32_t newLength=ucharsLength+1;
348 if(ensureCapacity(newLength)) {
349 ucharsLength=newLength;
350 uchars[ucharsCapacity-ucharsLength]=(UChar)unit;
351 }
352 return ucharsLength;
353 }
354
355 int32_t
write(const UChar * s,int32_t length)356 UCharsTrieBuilder::write(const UChar *s, int32_t length) {
357 int32_t newLength=ucharsLength+length;
358 if(ensureCapacity(newLength)) {
359 ucharsLength=newLength;
360 u_memcpy(uchars+(ucharsCapacity-ucharsLength), s, length);
361 }
362 return ucharsLength;
363 }
364
365 int32_t
writeElementUnits(int32_t i,int32_t unitIndex,int32_t length)366 UCharsTrieBuilder::writeElementUnits(int32_t i, int32_t unitIndex, int32_t length) {
367 return write(elements[i].getString(strings).getBuffer()+unitIndex, length);
368 }
369
370 int32_t
writeValueAndFinal(int32_t i,UBool isFinal)371 UCharsTrieBuilder::writeValueAndFinal(int32_t i, UBool isFinal) {
372 if(0<=i && i<=UCharsTrie::kMaxOneUnitValue) {
373 return write(i|(isFinal<<15));
374 }
375 UChar intUnits[3];
376 int32_t length;
377 if(i<0 || i>UCharsTrie::kMaxTwoUnitValue) {
378 intUnits[0]=(UChar)(UCharsTrie::kThreeUnitValueLead);
379 intUnits[1]=(UChar)(i>>16);
380 intUnits[2]=(UChar)i;
381 length=3;
382 // } else if(i<=UCharsTrie::kMaxOneUnitValue) {
383 // intUnits[0]=(UChar)(i);
384 // length=1;
385 } else {
386 intUnits[0]=(UChar)(UCharsTrie::kMinTwoUnitValueLead+(i>>16));
387 intUnits[1]=(UChar)i;
388 length=2;
389 }
390 intUnits[0]=(UChar)(intUnits[0]|(isFinal<<15));
391 return write(intUnits, length);
392 }
393
394 int32_t
writeValueAndType(UBool hasValue,int32_t value,int32_t node)395 UCharsTrieBuilder::writeValueAndType(UBool hasValue, int32_t value, int32_t node) {
396 if(!hasValue) {
397 return write(node);
398 }
399 UChar intUnits[3];
400 int32_t length;
401 if(value<0 || value>UCharsTrie::kMaxTwoUnitNodeValue) {
402 intUnits[0]=(UChar)(UCharsTrie::kThreeUnitNodeValueLead);
403 intUnits[1]=(UChar)(value>>16);
404 intUnits[2]=(UChar)value;
405 length=3;
406 } else if(value<=UCharsTrie::kMaxOneUnitNodeValue) {
407 intUnits[0]=(UChar)((value+1)<<6);
408 length=1;
409 } else {
410 intUnits[0]=(UChar)(UCharsTrie::kMinTwoUnitNodeValueLead+((value>>10)&0x7fc0));
411 intUnits[1]=(UChar)value;
412 length=2;
413 }
414 intUnits[0]|=(UChar)node;
415 return write(intUnits, length);
416 }
417
418 int32_t
writeDeltaTo(int32_t jumpTarget)419 UCharsTrieBuilder::writeDeltaTo(int32_t jumpTarget) {
420 int32_t i=ucharsLength-jumpTarget;
421 U_ASSERT(i>=0);
422 if(i<=UCharsTrie::kMaxOneUnitDelta) {
423 return write(i);
424 }
425 UChar intUnits[3];
426 int32_t length;
427 if(i<=UCharsTrie::kMaxTwoUnitDelta) {
428 intUnits[0]=(UChar)(UCharsTrie::kMinTwoUnitDeltaLead+(i>>16));
429 length=1;
430 } else {
431 intUnits[0]=(UChar)(UCharsTrie::kThreeUnitDeltaLead);
432 intUnits[1]=(UChar)(i>>16);
433 length=2;
434 }
435 intUnits[length++]=(UChar)i;
436 return write(intUnits, length);
437 }
438
439 U_NAMESPACE_END
440