source/common/bytestriebuilder.cpp

   1 // Copyright (C) 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:   US-ASCII
  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
  42     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     }
  54     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
  64     char charAt(int32_t index, const CharString &strings) const { return data(strings)[index]; }
  65
  66     int32_t getValue() const { return value; }
  67
  68     int32_t compareStringTo(const BytesTrieElement &o, const CharString &strings) const;
  69
  70 private:
  71     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
  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
 114 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
 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
 141 BytesTrieBuilder::~BytesTrieBuilder() {
 142     delete strings;
 143     delete[] elements;
 144     uprv_free(bytes);
 145 }
 146
 147 BytesTrieBuilder &
 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
 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 *
 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
 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
 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 &
 273 BytesTrieBuilder::clear() {
 274     strings->clear();
 275     elementsLength=0;
 276     bytesLength=0;
 277     return *this;
 278 }
 279
 280 int32_t
 281 BytesTrieBuilder::getElementStringLength(int32_t i) const {
 282     return elements[i].getStringLength(*strings);
 283 }
 284
 285 UChar
 286 BytesTrieBuilder::getElementUnit(int32_t i, int32_t byteIndex) const {
 287     return (uint8_t)elements[i].charAt(byteIndex, *strings);
 288 }
 289
 290 int32_t
 291 BytesTrieBuilder::getElementValue(int32_t i) const {
 292     return elements[i].getValue();
 293 }
 294
 295 int32_t
 296 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
 307 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
 321 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
 332 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
 340 BytesTrieBuilder::BTLinearMatchNode::BTLinearMatchNode(const char *bytes, int32_t len, Node *nextNode)
 341         : LinearMatchNode(len, nextNode), s(bytes) {
 342     hash=hash*37+ustr_hashCharsN(bytes, len);
 343 }
 344
 345 UBool
 346 BytesTrieBuilder::BTLinearMatchNode::operator==(const Node &other) const {
 347     if(this==&other) {
 348         return TRUE;
 349     }
 350     if(!LinearMatchNode::operator==(other)) {
 351         return FALSE;
 352     }
 353     const BTLinearMatchNode &o=(const BTLinearMatchNode &)other;
 354     return 0==uprv_memcmp(s, o.s, length);
 355 }
 356
 357 void
 358 BytesTrieBuilder::BTLinearMatchNode::write(StringTrieBuilder &builder) {
 359     BytesTrieBuilder &b=(BytesTrieBuilder &)builder;
 360     next->write(builder);
 361     b.write(s, length);
 362     offset=b.write(b.getMinLinearMatch()+length-1);
 363 }
 364
 365 StringTrieBuilder::Node *
 366 BytesTrieBuilder::createLinearMatchNode(int32_t i, int32_t byteIndex, int32_t length,
 367                                         Node *nextNode) const {
 368     return new BTLinearMatchNode(
 369             elements[i].getString(*strings).data()+byteIndex,
 370             length,
 371             nextNode);
 372 }
 373
 374 UBool
 375 BytesTrieBuilder::ensureCapacity(int32_t length) {
 376     if(bytes==NULL) {
 377         return FALSE;  // previous memory allocation had failed
 378     }
 379     if(length>bytesCapacity) {
 380         int32_t newCapacity=bytesCapacity;
 381         do {
 382             newCapacity*=2;
 383         } while(newCapacity<=length);
 384         char *newBytes=static_cast<char *>(uprv_malloc(newCapacity));
 385         if(newBytes==NULL) {
 386             // unable to allocate memory
 387             uprv_free(bytes);
 388             bytes=NULL;
 389             bytesCapacity=0;
 390             return FALSE;
 391         }
 392         uprv_memcpy(newBytes+(newCapacity-bytesLength),
 393                     bytes+(bytesCapacity-bytesLength), bytesLength);
 394         uprv_free(bytes);
 395         bytes=newBytes;
 396         bytesCapacity=newCapacity;
 397     }
 398     return TRUE;
 399 }
 400
 401 int32_t
 402 BytesTrieBuilder::write(int32_t byte) {
 403     int32_t newLength=bytesLength+1;
 404     if(ensureCapacity(newLength)) {
 405         bytesLength=newLength;
 406         bytes[bytesCapacity-bytesLength]=(char)byte;
 407     }
 408     return bytesLength;
 409 }
 410
 411 int32_t
 412 BytesTrieBuilder::write(const char *b, int32_t length) {
 413     int32_t newLength=bytesLength+length;
 414     if(ensureCapacity(newLength)) {
 415         bytesLength=newLength;
 416         uprv_memcpy(bytes+(bytesCapacity-bytesLength), b, length);
 417     }
 418     return bytesLength;
 419 }
 420
 421 int32_t
 422 BytesTrieBuilder::writeElementUnits(int32_t i, int32_t byteIndex, int32_t length) {
 423     return write(elements[i].getString(*strings).data()+byteIndex, length);
 424 }
 425
 426 int32_t
 427 BytesTrieBuilder::writeValueAndFinal(int32_t i, UBool isFinal) {
 428     if(0<=i && i<=BytesTrie::kMaxOneByteValue) {
 429         return write(((BytesTrie::kMinOneByteValueLead+i)<<1)|isFinal);
 430     }
 431     char intBytes[5];
 432     int32_t length=1;
 433     if(i<0 || i>0xffffff) {
 434         intBytes[0]=(char)BytesTrie::kFiveByteValueLead;
 435         intBytes[1]=(char)((uint32_t)i>>24);
 436         intBytes[2]=(char)((uint32_t)i>>16);
 437         intBytes[3]=(char)((uint32_t)i>>8);
 438         intBytes[4]=(char)i;
 439         length=5;
 440     // } else if(i<=BytesTrie::kMaxOneByteValue) {
 441     //     intBytes[0]=(char)(BytesTrie::kMinOneByteValueLead+i);
 442     } else {
 443         if(i<=BytesTrie::kMaxTwoByteValue) {
 444             intBytes[0]=(char)(BytesTrie::kMinTwoByteValueLead+(i>>8));
 445         } else {
 446             if(i<=BytesTrie::kMaxThreeByteValue) {
 447                 intBytes[0]=(char)(BytesTrie::kMinThreeByteValueLead+(i>>16));
 448             } else {
 449                 intBytes[0]=(char)BytesTrie::kFourByteValueLead;
 450                 intBytes[1]=(char)(i>>16);
 451                 length=2;
 452             }
 453             intBytes[length++]=(char)(i>>8);
 454         }
 455         intBytes[length++]=(char)i;
 456     }
 457     intBytes[0]=(char)((intBytes[0]<<1)|isFinal);
 458     return write(intBytes, length);
 459 }
 460
 461 int32_t
 462 BytesTrieBuilder::writeValueAndType(UBool hasValue, int32_t value, int32_t node) {
 463     int32_t offset=write(node);
 464     if(hasValue) {
 465         offset=writeValueAndFinal(value, FALSE);
 466     }
 467     return offset;
 468 }
 469
 470 int32_t
 471 BytesTrieBuilder::writeDeltaTo(int32_t jumpTarget) {
 472     int32_t i=bytesLength-jumpTarget;
 473     U_ASSERT(i>=0);
 474     if(i<=BytesTrie::kMaxOneByteDelta) {
 475         return write(i);
 476     }
 477     char intBytes[5];
 478     int32_t length;
 479     if(i<=BytesTrie::kMaxTwoByteDelta) {
 480         intBytes[0]=(char)(BytesTrie::kMinTwoByteDeltaLead+(i>>8));
 481         length=1;
 482     } else {
 483         if(i<=BytesTrie::kMaxThreeByteDelta) {
 484             intBytes[0]=(char)(BytesTrie::kMinThreeByteDeltaLead+(i>>16));
 485             length=2;
 486         } else {
 487             if(i<=0xffffff) {
 488                 intBytes[0]=(char)BytesTrie::kFourByteDeltaLead;
 489                 length=3;
 490             } else {
 491                 intBytes[0]=(char)BytesTrie::kFiveByteDeltaLead;
 492                 intBytes[1]=(char)(i>>24);
 493                 length=4;
 494             }
 495             intBytes[1]=(char)(i>>16);
 496         }
 497         intBytes[1]=(char)(i>>8);
 498     }
 499     intBytes[length++]=(char)i;
 500     return write(intBytes, length);
 501 }
 502
 503 U_NAMESPACE_END