• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // © 2016 and later: Unicode, Inc. and others.
2 // License & terms of use: http://www.unicode.org/copyright.html
3 /*
4 *******************************************************************************
5 *   Copyright (C) 2010-2012, International Business Machines
6 *   Corporation and others.  All Rights Reserved.
7 *******************************************************************************
8 *   file name:  bytestriebuilder.cpp
9 *   encoding:   UTF-8
10 *   tab size:   8 (not used)
11 *   indentation:4
12 *
13 *   created on: 2010sep25
14 *   created by: Markus W. Scherer
15 */
16 
17 #include "unicode/utypes.h"
18 #include "unicode/bytestrie.h"
19 #include "unicode/bytestriebuilder.h"
20 #include "unicode/stringpiece.h"
21 #include "charstr.h"
22 #include "cmemory.h"
23 #include "uhash.h"
24 #include "uarrsort.h"
25 #include "uassert.h"
26 #include "ustr_imp.h"
27 
28 U_NAMESPACE_BEGIN
29 
30 /*
31  * Note: This builder implementation stores (bytes, value) pairs with full copies
32  * of the byte sequences, until the BytesTrie is built.
33  * It might(!) take less memory if we collected the data in a temporary, dynamic trie.
34  */
35 
36 class BytesTrieElement : public UMemory {
37 public:
38     // Use compiler's default constructor, initializes nothing.
39 
40     void setTo(StringPiece s, int32_t val, CharString &strings, UErrorCode &errorCode);
41 
getString(const CharString & strings) const42     StringPiece getString(const CharString &strings) const {
43         int32_t offset=stringOffset;
44         int32_t length;
45         if(offset>=0) {
46             length=(uint8_t)strings[offset++];
47         } else {
48             offset=~offset;
49             length=((int32_t)(uint8_t)strings[offset]<<8)|(uint8_t)strings[offset+1];
50             offset+=2;
51         }
52         return StringPiece(strings.data()+offset, length);
53     }
getStringLength(const CharString & strings) const54     int32_t getStringLength(const CharString &strings) const {
55         int32_t offset=stringOffset;
56         if(offset>=0) {
57             return (uint8_t)strings[offset];
58         } else {
59             offset=~offset;
60             return ((int32_t)(uint8_t)strings[offset]<<8)|(uint8_t)strings[offset+1];
61         }
62     }
63 
charAt(int32_t index,const CharString & strings) const64     char charAt(int32_t index, const CharString &strings) const { return data(strings)[index]; }
65 
getValue() const66     int32_t getValue() const { return value; }
67 
68     int32_t compareStringTo(const BytesTrieElement &o, const CharString &strings) const;
69 
70 private:
data(const CharString & strings) const71     const char *data(const CharString &strings) const {
72         int32_t offset=stringOffset;
73         if(offset>=0) {
74             ++offset;
75         } else {
76             offset=~offset+2;
77         }
78         return strings.data()+offset;
79     }
80 
81     // If the stringOffset is non-negative, then the first strings byte contains
82     // the string length.
83     // If the stringOffset is negative, then the first two strings bytes contain
84     // the string length (big-endian), and the offset needs to be bit-inverted.
85     // (Compared with a stringLength field here, this saves 3 bytes per string for most strings.)
86     int32_t stringOffset;
87     int32_t value;
88 };
89 
90 void
setTo(StringPiece s,int32_t val,CharString & strings,UErrorCode & errorCode)91 BytesTrieElement::setTo(StringPiece s, int32_t val,
92                         CharString &strings, UErrorCode &errorCode) {
93     if(U_FAILURE(errorCode)) {
94         return;
95     }
96     int32_t length=s.length();
97     if(length>0xffff) {
98         // Too long: We store the length in 1 or 2 bytes.
99         errorCode=U_INDEX_OUTOFBOUNDS_ERROR;
100         return;
101     }
102     int32_t offset=strings.length();
103     if(length>0xff) {
104         offset=~offset;
105         strings.append((char)(length>>8), errorCode);
106     }
107     strings.append((char)length, errorCode);
108     stringOffset=offset;
109     value=val;
110     strings.append(s, errorCode);
111 }
112 
113 int32_t
compareStringTo(const BytesTrieElement & other,const CharString & strings) const114 BytesTrieElement::compareStringTo(const BytesTrieElement &other, const CharString &strings) const {
115     // TODO: add StringPiece::compare(), see ticket #8187
116     StringPiece thisString=getString(strings);
117     StringPiece otherString=other.getString(strings);
118     int32_t lengthDiff=thisString.length()-otherString.length();
119     int32_t commonLength;
120     if(lengthDiff<=0) {
121         commonLength=thisString.length();
122     } else {
123         commonLength=otherString.length();
124     }
125     int32_t diff=uprv_memcmp(thisString.data(), otherString.data(), commonLength);
126     return diff!=0 ? diff : lengthDiff;
127 }
128 
BytesTrieBuilder(UErrorCode & errorCode)129 BytesTrieBuilder::BytesTrieBuilder(UErrorCode &errorCode)
130         : strings(NULL), elements(NULL), elementsCapacity(0), elementsLength(0),
131           bytes(NULL), bytesCapacity(0), bytesLength(0) {
132     if(U_FAILURE(errorCode)) {
133         return;
134     }
135     strings=new CharString();
136     if(strings==NULL) {
137         errorCode=U_MEMORY_ALLOCATION_ERROR;
138     }
139 }
140 
~BytesTrieBuilder()141 BytesTrieBuilder::~BytesTrieBuilder() {
142     delete strings;
143     delete[] elements;
144     uprv_free(bytes);
145 }
146 
147 BytesTrieBuilder &
add(StringPiece s,int32_t value,UErrorCode & errorCode)148 BytesTrieBuilder::add(StringPiece s, int32_t value, UErrorCode &errorCode) {
149     if(U_FAILURE(errorCode)) {
150         return *this;
151     }
152     if(bytesLength>0) {
153         // Cannot add elements after building.
154         errorCode=U_NO_WRITE_PERMISSION;
155         return *this;
156     }
157     if(elementsLength==elementsCapacity) {
158         int32_t newCapacity;
159         if(elementsCapacity==0) {
160             newCapacity=1024;
161         } else {
162             newCapacity=4*elementsCapacity;
163         }
164         BytesTrieElement *newElements=new BytesTrieElement[newCapacity];
165         if(newElements==NULL) {
166             errorCode=U_MEMORY_ALLOCATION_ERROR;
167             return *this; // error instead of dereferencing null
168         }
169         if(elementsLength>0) {
170             uprv_memcpy(newElements, elements, (size_t)elementsLength*sizeof(BytesTrieElement));
171         }
172         delete[] elements;
173         elements=newElements;
174         elementsCapacity=newCapacity;
175     }
176     elements[elementsLength++].setTo(s, value, *strings, errorCode);
177     return *this;
178 }
179 
180 U_CDECL_BEGIN
181 
182 static int32_t U_CALLCONV
compareElementStrings(const void * context,const void * left,const void * right)183 compareElementStrings(const void *context, const void *left, const void *right) {
184     const CharString *strings=static_cast<const CharString *>(context);
185     const BytesTrieElement *leftElement=static_cast<const BytesTrieElement *>(left);
186     const BytesTrieElement *rightElement=static_cast<const BytesTrieElement *>(right);
187     return leftElement->compareStringTo(*rightElement, *strings);
188 }
189 
190 U_CDECL_END
191 
192 BytesTrie *
build(UStringTrieBuildOption buildOption,UErrorCode & errorCode)193 BytesTrieBuilder::build(UStringTrieBuildOption buildOption, UErrorCode &errorCode) {
194     buildBytes(buildOption, errorCode);
195     BytesTrie *newTrie=NULL;
196     if(U_SUCCESS(errorCode)) {
197         newTrie=new BytesTrie(bytes, bytes+(bytesCapacity-bytesLength));
198         if(newTrie==NULL) {
199             errorCode=U_MEMORY_ALLOCATION_ERROR;
200         } else {
201             bytes=NULL;  // The new trie now owns the array.
202             bytesCapacity=0;
203         }
204     }
205     return newTrie;
206 }
207 
208 StringPiece
buildStringPiece(UStringTrieBuildOption buildOption,UErrorCode & errorCode)209 BytesTrieBuilder::buildStringPiece(UStringTrieBuildOption buildOption, UErrorCode &errorCode) {
210     buildBytes(buildOption, errorCode);
211     StringPiece result;
212     if(U_SUCCESS(errorCode)) {
213         result.set(bytes+(bytesCapacity-bytesLength), bytesLength);
214     }
215     return result;
216 }
217 
218 void
buildBytes(UStringTrieBuildOption buildOption,UErrorCode & errorCode)219 BytesTrieBuilder::buildBytes(UStringTrieBuildOption buildOption, UErrorCode &errorCode) {
220     if(U_FAILURE(errorCode)) {
221         return;
222     }
223     if(bytes!=NULL && bytesLength>0) {
224         // Already built.
225         return;
226     }
227     if(bytesLength==0) {
228         if(elementsLength==0) {
229             errorCode=U_INDEX_OUTOFBOUNDS_ERROR;
230             return;
231         }
232         uprv_sortArray(elements, elementsLength, (int32_t)sizeof(BytesTrieElement),
233                       compareElementStrings, strings,
234                       FALSE,  // need not be a stable sort
235                       &errorCode);
236         if(U_FAILURE(errorCode)) {
237             return;
238         }
239         // Duplicate strings are not allowed.
240         StringPiece prev=elements[0].getString(*strings);
241         for(int32_t i=1; i<elementsLength; ++i) {
242             StringPiece current=elements[i].getString(*strings);
243             if(prev==current) {
244                 errorCode=U_ILLEGAL_ARGUMENT_ERROR;
245                 return;
246             }
247             prev=current;
248         }
249     }
250     // Create and byte-serialize the trie for the elements.
251     bytesLength=0;
252     int32_t capacity=strings->length();
253     if(capacity<1024) {
254         capacity=1024;
255     }
256     if(bytesCapacity<capacity) {
257         uprv_free(bytes);
258         bytes=static_cast<char *>(uprv_malloc(capacity));
259         if(bytes==NULL) {
260             errorCode=U_MEMORY_ALLOCATION_ERROR;
261             bytesCapacity=0;
262             return;
263         }
264         bytesCapacity=capacity;
265     }
266     StringTrieBuilder::build(buildOption, elementsLength, errorCode);
267     if(bytes==NULL) {
268         errorCode=U_MEMORY_ALLOCATION_ERROR;
269     }
270 }
271 
272 BytesTrieBuilder &
clear()273 BytesTrieBuilder::clear() {
274     strings->clear();
275     elementsLength=0;
276     bytesLength=0;
277     return *this;
278 }
279 
280 int32_t
getElementStringLength(int32_t i) const281 BytesTrieBuilder::getElementStringLength(int32_t i) const {
282     return elements[i].getStringLength(*strings);
283 }
284 
285 UChar
getElementUnit(int32_t i,int32_t byteIndex) const286 BytesTrieBuilder::getElementUnit(int32_t i, int32_t byteIndex) const {
287     return (uint8_t)elements[i].charAt(byteIndex, *strings);
288 }
289 
290 int32_t
getElementValue(int32_t i) const291 BytesTrieBuilder::getElementValue(int32_t i) const {
292     return elements[i].getValue();
293 }
294 
295 int32_t
getLimitOfLinearMatch(int32_t first,int32_t last,int32_t byteIndex) const296 BytesTrieBuilder::getLimitOfLinearMatch(int32_t first, int32_t last, int32_t byteIndex) const {
297     const BytesTrieElement &firstElement=elements[first];
298     const BytesTrieElement &lastElement=elements[last];
299     int32_t minStringLength=firstElement.getStringLength(*strings);
300     while(++byteIndex<minStringLength &&
301             firstElement.charAt(byteIndex, *strings)==
302             lastElement.charAt(byteIndex, *strings)) {}
303     return byteIndex;
304 }
305 
306 int32_t
countElementUnits(int32_t start,int32_t limit,int32_t byteIndex) const307 BytesTrieBuilder::countElementUnits(int32_t start, int32_t limit, int32_t byteIndex) const {
308     int32_t length=0;  // Number of different bytes at byteIndex.
309     int32_t i=start;
310     do {
311         char byte=elements[i++].charAt(byteIndex, *strings);
312         while(i<limit && byte==elements[i].charAt(byteIndex, *strings)) {
313             ++i;
314         }
315         ++length;
316     } while(i<limit);
317     return length;
318 }
319 
320 int32_t
skipElementsBySomeUnits(int32_t i,int32_t byteIndex,int32_t count) const321 BytesTrieBuilder::skipElementsBySomeUnits(int32_t i, int32_t byteIndex, int32_t count) const {
322     do {
323         char byte=elements[i++].charAt(byteIndex, *strings);
324         while(byte==elements[i].charAt(byteIndex, *strings)) {
325             ++i;
326         }
327     } while(--count>0);
328     return i;
329 }
330 
331 int32_t
indexOfElementWithNextUnit(int32_t i,int32_t byteIndex,UChar byte) const332 BytesTrieBuilder::indexOfElementWithNextUnit(int32_t i, int32_t byteIndex, UChar byte) const {
333     char b=(char)byte;
334     while(b==elements[i].charAt(byteIndex, *strings)) {
335         ++i;
336     }
337     return i;
338 }
339 
BTLinearMatchNode(const char * bytes,int32_t len,Node * nextNode)340 BytesTrieBuilder::BTLinearMatchNode::BTLinearMatchNode(const char *bytes, int32_t len, Node *nextNode)
341         : LinearMatchNode(len, nextNode), s(bytes) {
342     hash=static_cast<int32_t>(
343         static_cast<uint32_t>(hash)*37u + static_cast<uint32_t>(ustr_hashCharsN(bytes, len)));
344 }
345 
346 UBool
operator ==(const Node & other) const347 BytesTrieBuilder::BTLinearMatchNode::operator==(const Node &other) const {
348     if(this==&other) {
349         return TRUE;
350     }
351     if(!LinearMatchNode::operator==(other)) {
352         return FALSE;
353     }
354     const BTLinearMatchNode &o=(const BTLinearMatchNode &)other;
355     return 0==uprv_memcmp(s, o.s, length);
356 }
357 
358 void
write(StringTrieBuilder & builder)359 BytesTrieBuilder::BTLinearMatchNode::write(StringTrieBuilder &builder) {
360     BytesTrieBuilder &b=(BytesTrieBuilder &)builder;
361     next->write(builder);
362     b.write(s, length);
363     offset=b.write(b.getMinLinearMatch()+length-1);
364 }
365 
366 StringTrieBuilder::Node *
createLinearMatchNode(int32_t i,int32_t byteIndex,int32_t length,Node * nextNode) const367 BytesTrieBuilder::createLinearMatchNode(int32_t i, int32_t byteIndex, int32_t length,
368                                         Node *nextNode) const {
369     return new BTLinearMatchNode(
370             elements[i].getString(*strings).data()+byteIndex,
371             length,
372             nextNode);
373 }
374 
375 UBool
ensureCapacity(int32_t length)376 BytesTrieBuilder::ensureCapacity(int32_t length) {
377     if(bytes==NULL) {
378         return FALSE;  // previous memory allocation had failed
379     }
380     if(length>bytesCapacity) {
381         int32_t newCapacity=bytesCapacity;
382         do {
383             newCapacity*=2;
384         } while(newCapacity<=length);
385         char *newBytes=static_cast<char *>(uprv_malloc(newCapacity));
386         if(newBytes==NULL) {
387             // unable to allocate memory
388             uprv_free(bytes);
389             bytes=NULL;
390             bytesCapacity=0;
391             return FALSE;
392         }
393         uprv_memcpy(newBytes+(newCapacity-bytesLength),
394                     bytes+(bytesCapacity-bytesLength), bytesLength);
395         uprv_free(bytes);
396         bytes=newBytes;
397         bytesCapacity=newCapacity;
398     }
399     return TRUE;
400 }
401 
402 int32_t
write(int32_t byte)403 BytesTrieBuilder::write(int32_t byte) {
404     int32_t newLength=bytesLength+1;
405     if(ensureCapacity(newLength)) {
406         bytesLength=newLength;
407         bytes[bytesCapacity-bytesLength]=(char)byte;
408     }
409     return bytesLength;
410 }
411 
412 int32_t
write(const char * b,int32_t length)413 BytesTrieBuilder::write(const char *b, int32_t length) {
414     int32_t newLength=bytesLength+length;
415     if(ensureCapacity(newLength)) {
416         bytesLength=newLength;
417         uprv_memcpy(bytes+(bytesCapacity-bytesLength), b, length);
418     }
419     return bytesLength;
420 }
421 
422 int32_t
writeElementUnits(int32_t i,int32_t byteIndex,int32_t length)423 BytesTrieBuilder::writeElementUnits(int32_t i, int32_t byteIndex, int32_t length) {
424     return write(elements[i].getString(*strings).data()+byteIndex, length);
425 }
426 
427 int32_t
writeValueAndFinal(int32_t i,UBool isFinal)428 BytesTrieBuilder::writeValueAndFinal(int32_t i, UBool isFinal) {
429     if(0<=i && i<=BytesTrie::kMaxOneByteValue) {
430         return write(((BytesTrie::kMinOneByteValueLead+i)<<1)|isFinal);
431     }
432     char intBytes[5];
433     int32_t length=1;
434     if(i<0 || i>0xffffff) {
435         intBytes[0]=(char)BytesTrie::kFiveByteValueLead;
436         intBytes[1]=(char)((uint32_t)i>>24);
437         intBytes[2]=(char)((uint32_t)i>>16);
438         intBytes[3]=(char)((uint32_t)i>>8);
439         intBytes[4]=(char)i;
440         length=5;
441     // } else if(i<=BytesTrie::kMaxOneByteValue) {
442     //     intBytes[0]=(char)(BytesTrie::kMinOneByteValueLead+i);
443     } else {
444         if(i<=BytesTrie::kMaxTwoByteValue) {
445             intBytes[0]=(char)(BytesTrie::kMinTwoByteValueLead+(i>>8));
446         } else {
447             if(i<=BytesTrie::kMaxThreeByteValue) {
448                 intBytes[0]=(char)(BytesTrie::kMinThreeByteValueLead+(i>>16));
449             } else {
450                 intBytes[0]=(char)BytesTrie::kFourByteValueLead;
451                 intBytes[1]=(char)(i>>16);
452                 length=2;
453             }
454             intBytes[length++]=(char)(i>>8);
455         }
456         intBytes[length++]=(char)i;
457     }
458     intBytes[0]=(char)((intBytes[0]<<1)|isFinal);
459     return write(intBytes, length);
460 }
461 
462 int32_t
writeValueAndType(UBool hasValue,int32_t value,int32_t node)463 BytesTrieBuilder::writeValueAndType(UBool hasValue, int32_t value, int32_t node) {
464     int32_t offset=write(node);
465     if(hasValue) {
466         offset=writeValueAndFinal(value, FALSE);
467     }
468     return offset;
469 }
470 
471 int32_t
writeDeltaTo(int32_t jumpTarget)472 BytesTrieBuilder::writeDeltaTo(int32_t jumpTarget) {
473     int32_t i=bytesLength-jumpTarget;
474     U_ASSERT(i>=0);
475     if(i<=BytesTrie::kMaxOneByteDelta) {
476         return write(i);
477     }
478     char intBytes[5];
479     int32_t length;
480     if(i<=BytesTrie::kMaxTwoByteDelta) {
481         intBytes[0]=(char)(BytesTrie::kMinTwoByteDeltaLead+(i>>8));
482         length=1;
483     } else {
484         if(i<=BytesTrie::kMaxThreeByteDelta) {
485             intBytes[0]=(char)(BytesTrie::kMinThreeByteDeltaLead+(i>>16));
486             length=2;
487         } else {
488             if(i<=0xffffff) {
489                 intBytes[0]=(char)BytesTrie::kFourByteDeltaLead;
490                 length=3;
491             } else {
492                 intBytes[0]=(char)BytesTrie::kFiveByteDeltaLead;
493                 intBytes[1]=(char)(i>>24);
494                 length=4;
495             }
496             intBytes[1]=(char)(i>>16);
497         }
498         intBytes[1]=(char)(i>>8);
499     }
500     intBytes[length++]=(char)i;
501     return write(intBytes, length);
502 }
503 
504 U_NAMESPACE_END
505