1 /* 2 ******************************************************************************* 3 * Copyright (C) 2010-2014, International Business Machines 4 * Corporation and others. All Rights Reserved. 5 ******************************************************************************* 6 * file name: bytetrietest.cpp 7 * encoding: US-ASCII 8 * tab size: 8 (not used) 9 * indentation:4 10 * 11 * created on: 2010nov16 12 * created by: Markus W. Scherer 13 */ 14 15 #include <string.h> 16 17 #include "unicode/utypes.h" 18 #include "unicode/bytestrie.h" 19 #include "unicode/bytestriebuilder.h" 20 #include "unicode/localpointer.h" 21 #include "unicode/stringpiece.h" 22 #include "intltest.h" 23 #include "cmemory.h" 24 25 struct StringAndValue { 26 const char *s; 27 int32_t value; 28 }; 29 30 class BytesTrieTest : public IntlTest { 31 public: 32 BytesTrieTest(); 33 virtual ~BytesTrieTest(); 34 35 void runIndexedTest(int32_t index, UBool exec, const char *&name, char *par=NULL); 36 void TestBuilder(); 37 void TestEmpty(); 38 void Test_a(); 39 void Test_a_ab(); 40 void TestShortestBranch(); 41 void TestBranches(); 42 void TestLongSequence(); 43 void TestLongBranch(); 44 void TestValuesForState(); 45 void TestCompact(); 46 47 BytesTrie *buildMonthsTrie(UStringTrieBuildOption buildOption); 48 void TestHasUniqueValue(); 49 void TestGetNextBytes(); 50 void TestIteratorFromBranch(); 51 void TestIteratorFromLinearMatch(); 52 void TestTruncatingIteratorFromRoot(); 53 void TestTruncatingIteratorFromLinearMatchShort(); 54 void TestTruncatingIteratorFromLinearMatchLong(); 55 void TestIteratorFromBytes(); 56 57 void checkData(const StringAndValue data[], int32_t dataLength); 58 void checkData(const StringAndValue data[], int32_t dataLength, UStringTrieBuildOption buildOption); 59 BytesTrie *buildTrie(const StringAndValue data[], int32_t dataLength, 60 UStringTrieBuildOption buildOption); 61 void checkFirst(BytesTrie &trie, const StringAndValue data[], int32_t dataLength); 62 void checkNext(BytesTrie &trie, const StringAndValue data[], int32_t dataLength); 63 void checkNextWithState(BytesTrie &trie, const StringAndValue data[], int32_t dataLength); 64 void checkNextString(BytesTrie &trie, const StringAndValue data[], int32_t dataLength); 65 void checkIterator(const BytesTrie &trie, const StringAndValue data[], int32_t dataLength); 66 void checkIterator(BytesTrie::Iterator &iter, const StringAndValue data[], int32_t dataLength); 67 68 private: 69 BytesTrieBuilder *builder_; 70 }; 71 72 extern IntlTest *createBytesTrieTest() { 73 return new BytesTrieTest(); 74 } 75 76 BytesTrieTest::BytesTrieTest() : builder_(NULL) { 77 IcuTestErrorCode errorCode(*this, "BytesTrieTest()"); 78 builder_=new BytesTrieBuilder(errorCode); 79 } 80 81 BytesTrieTest::~BytesTrieTest() { 82 delete builder_; 83 } 84 85 void BytesTrieTest::runIndexedTest(int32_t index, UBool exec, const char *&name, char * /*par*/) { 86 if(exec) { 87 logln("TestSuite BytesTrieTest: "); 88 } 89 TESTCASE_AUTO_BEGIN; 90 TESTCASE_AUTO(TestBuilder); 91 TESTCASE_AUTO(TestEmpty); 92 TESTCASE_AUTO(Test_a); 93 TESTCASE_AUTO(Test_a_ab); 94 TESTCASE_AUTO(TestShortestBranch); 95 TESTCASE_AUTO(TestBranches); 96 TESTCASE_AUTO(TestLongSequence); 97 TESTCASE_AUTO(TestLongBranch); 98 TESTCASE_AUTO(TestValuesForState); 99 TESTCASE_AUTO(TestCompact); 100 TESTCASE_AUTO(TestHasUniqueValue); 101 TESTCASE_AUTO(TestGetNextBytes); 102 TESTCASE_AUTO(TestIteratorFromBranch); 103 TESTCASE_AUTO(TestIteratorFromLinearMatch); 104 TESTCASE_AUTO(TestTruncatingIteratorFromRoot); 105 TESTCASE_AUTO(TestTruncatingIteratorFromLinearMatchShort); 106 TESTCASE_AUTO(TestTruncatingIteratorFromLinearMatchLong); 107 TESTCASE_AUTO(TestIteratorFromBytes); 108 TESTCASE_AUTO_END; 109 } 110 111 void BytesTrieTest::TestBuilder() { 112 IcuTestErrorCode errorCode(*this, "TestBuilder()"); 113 builder_->clear(); 114 delete builder_->build(USTRINGTRIE_BUILD_FAST, errorCode); 115 if(errorCode.reset()!=U_INDEX_OUTOFBOUNDS_ERROR) { 116 errln("BytesTrieBuilder().build() did not set U_INDEX_OUTOFBOUNDS_ERROR"); 117 return; 118 } 119 // TODO: remove .build(...) once add() checks for duplicates. 120 builder_->add("=", 0, errorCode).add("=", 1, errorCode).build(USTRINGTRIE_BUILD_FAST, errorCode); 121 if(errorCode.reset()!=U_ILLEGAL_ARGUMENT_ERROR) { 122 errln("BytesTrieBuilder.add() did not detect duplicates"); 123 return; 124 } 125 } 126 127 void BytesTrieTest::TestEmpty() { 128 static const StringAndValue data[]={ 129 { "", 0 } 130 }; 131 checkData(data, UPRV_LENGTHOF(data)); 132 } 133 134 void BytesTrieTest::Test_a() { 135 static const StringAndValue data[]={ 136 { "a", 1 } 137 }; 138 checkData(data, UPRV_LENGTHOF(data)); 139 } 140 141 void BytesTrieTest::Test_a_ab() { 142 static const StringAndValue data[]={ 143 { "a", 1 }, 144 { "ab", 100 } 145 }; 146 checkData(data, UPRV_LENGTHOF(data)); 147 } 148 149 void BytesTrieTest::TestShortestBranch() { 150 static const StringAndValue data[]={ 151 { "a", 1000 }, 152 { "b", 2000 } 153 }; 154 checkData(data, UPRV_LENGTHOF(data)); 155 } 156 157 void BytesTrieTest::TestBranches() { 158 static const StringAndValue data[]={ 159 { "a", 0x10 }, 160 { "cc", 0x40 }, 161 { "e", 0x100 }, 162 { "ggg", 0x400 }, 163 { "i", 0x1000 }, 164 { "kkkk", 0x4000 }, 165 { "n", 0x10000 }, 166 { "ppppp", 0x40000 }, 167 { "r", 0x100000 }, 168 { "sss", 0x200000 }, 169 { "t", 0x400000 }, 170 { "uu", 0x800000 }, 171 { "vv", 0x7fffffff }, 172 { "zz", (int32_t)0x80000000 } 173 }; 174 for(int32_t length=2; length<=UPRV_LENGTHOF(data); ++length) { 175 logln("TestBranches length=%d", (int)length); 176 checkData(data, length); 177 } 178 } 179 180 void BytesTrieTest::TestLongSequence() { 181 static const StringAndValue data[]={ 182 { "a", -1 }, 183 // sequence of linear-match nodes 184 { "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ", -2 }, 185 // more than 256 bytes 186 { "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" 187 "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" 188 "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" 189 "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" 190 "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" 191 "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ", -3 } 192 }; 193 checkData(data, UPRV_LENGTHOF(data)); 194 } 195 196 void BytesTrieTest::TestLongBranch() { 197 // Split-branch and interesting compact-integer values. 198 static const StringAndValue data[]={ 199 { "a", -2 }, 200 { "b", -1 }, 201 { "c", 0 }, 202 { "d2", 1 }, 203 { "f", 0x3f }, 204 { "g", 0x40 }, 205 { "h", 0x41 }, 206 { "j23", 0x1900 }, 207 { "j24", 0x19ff }, 208 { "j25", 0x1a00 }, 209 { "k2", 0x1a80 }, 210 { "k3", 0x1aff }, 211 { "l234567890", 0x1b00 }, 212 { "l234567890123", 0x1b01 }, 213 { "nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn", 0x10ffff }, 214 { "oooooooooooooooooooooooooooooooooooooooooooooooooooooo", 0x110000 }, 215 { "pppppppppppppppppppppppppppppppppppppppppppppppppppppp", 0x120000 }, 216 { "r", 0x333333 }, 217 { "s2345", 0x4444444 }, 218 { "t234567890", 0x77777777 }, 219 { "z", (int32_t)0x80000001 } 220 }; 221 checkData(data, UPRV_LENGTHOF(data)); 222 } 223 224 void BytesTrieTest::TestValuesForState() { 225 // Check that saveState() and resetToState() interact properly 226 // with next() and current(). 227 static const StringAndValue data[]={ 228 { "a", -1 }, 229 { "ab", -2 }, 230 { "abc", -3 }, 231 { "abcd", -4 }, 232 { "abcde", -5 }, 233 { "abcdef", -6 } 234 }; 235 checkData(data, UPRV_LENGTHOF(data)); 236 } 237 238 void BytesTrieTest::TestCompact() { 239 // Duplicate trailing strings and values provide opportunities for compacting. 240 static const StringAndValue data[]={ 241 { "+", 0 }, 242 { "+august", 8 }, 243 { "+december", 12 }, 244 { "+july", 7 }, 245 { "+june", 6 }, 246 { "+november", 11 }, 247 { "+october", 10 }, 248 { "+september", 9 }, 249 { "-", 0 }, 250 { "-august", 8 }, 251 { "-december", 12 }, 252 { "-july", 7 }, 253 { "-june", 6 }, 254 { "-november", 11 }, 255 { "-october", 10 }, 256 { "-september", 9 }, 257 // The l+n branch (with its sub-nodes) is a duplicate but will be written 258 // both times because each time it follows a different linear-match node. 259 { "xjuly", 7 }, 260 { "xjune", 6 } 261 }; 262 checkData(data, UPRV_LENGTHOF(data)); 263 } 264 265 BytesTrie *BytesTrieTest::buildMonthsTrie(UStringTrieBuildOption buildOption) { 266 // All types of nodes leading to the same value, 267 // for code coverage of recursive functions. 268 // In particular, we need a lot of branches on some single level 269 // to exercise a split-branch node. 270 static const StringAndValue data[]={ 271 { "august", 8 }, 272 { "jan", 1 }, 273 { "jan.", 1 }, 274 { "jana", 1 }, 275 { "janbb", 1 }, 276 { "janc", 1 }, 277 { "janddd", 1 }, 278 { "janee", 1 }, 279 { "janef", 1 }, 280 { "janf", 1 }, 281 { "jangg", 1 }, 282 { "janh", 1 }, 283 { "janiiii", 1 }, 284 { "janj", 1 }, 285 { "jankk", 1 }, 286 { "jankl", 1 }, 287 { "jankmm", 1 }, 288 { "janl", 1 }, 289 { "janm", 1 }, 290 { "jannnnnnnnnnnnnnnnnnnnnnnnnnnnn", 1 }, 291 { "jano", 1 }, 292 { "janpp", 1 }, 293 { "janqqq", 1 }, 294 { "janr", 1 }, 295 { "januar", 1 }, 296 { "january", 1 }, 297 { "july", 7 }, 298 { "jun", 6 }, 299 { "jun.", 6 }, 300 { "june", 6 } 301 }; 302 return buildTrie(data, UPRV_LENGTHOF(data), buildOption); 303 } 304 305 void BytesTrieTest::TestHasUniqueValue() { 306 LocalPointer<BytesTrie> trie(buildMonthsTrie(USTRINGTRIE_BUILD_FAST)); 307 if(trie.isNull()) { 308 return; // buildTrie() reported an error 309 } 310 int32_t uniqueValue; 311 if(trie->hasUniqueValue(uniqueValue)) { 312 errln("unique value at root"); 313 } 314 trie->next('j'); 315 trie->next('a'); 316 trie->next('n'); 317 // hasUniqueValue() directly after next() 318 if(!trie->hasUniqueValue(uniqueValue) || uniqueValue!=1) { 319 errln("not unique value 1 after \"jan\""); 320 } 321 trie->first('j'); 322 trie->next('u'); 323 if(trie->hasUniqueValue(uniqueValue)) { 324 errln("unique value after \"ju\""); 325 } 326 if(trie->next('n')!=USTRINGTRIE_INTERMEDIATE_VALUE || 6!=trie->getValue()) { 327 errln("not normal value 6 after \"jun\""); 328 } 329 // hasUniqueValue() after getValue() 330 if(!trie->hasUniqueValue(uniqueValue) || uniqueValue!=6) { 331 errln("not unique value 6 after \"jun\""); 332 } 333 // hasUniqueValue() from within a linear-match node 334 trie->first('a'); 335 trie->next('u'); 336 if(!trie->hasUniqueValue(uniqueValue) || uniqueValue!=8) { 337 errln("not unique value 8 after \"au\""); 338 } 339 } 340 341 void BytesTrieTest::TestGetNextBytes() { 342 LocalPointer<BytesTrie> trie(buildMonthsTrie(USTRINGTRIE_BUILD_SMALL)); 343 if(trie.isNull()) { 344 return; // buildTrie() reported an error 345 } 346 char buffer[40]; 347 CheckedArrayByteSink sink(buffer, UPRV_LENGTHOF(buffer)); 348 int32_t count=trie->getNextBytes(sink); 349 if(count!=2 || sink.NumberOfBytesAppended()!=2 || buffer[0]!='a' || buffer[1]!='j') { 350 errln("months getNextBytes()!=[aj] at root"); 351 } 352 trie->next('j'); 353 trie->next('a'); 354 trie->next('n'); 355 // getNextBytes() directly after next() 356 count=trie->getNextBytes(sink.Reset()); 357 buffer[count]=0; 358 if(count!=20 || sink.NumberOfBytesAppended()!=20 || 0!=strcmp(buffer, ".abcdefghijklmnopqru")) { 359 errln("months getNextBytes()!=[.abcdefghijklmnopqru] after \"jan\""); 360 } 361 // getNextBytes() after getValue() 362 trie->getValue(); // next() had returned USTRINGTRIE_INTERMEDIATE_VALUE. 363 memset(buffer, 0, sizeof(buffer)); 364 count=trie->getNextBytes(sink.Reset()); 365 if(count!=20 || sink.NumberOfBytesAppended()!=20 || 0!=strcmp(buffer, ".abcdefghijklmnopqru")) { 366 errln("months getNextBytes()!=[.abcdefghijklmnopqru] after \"jan\"+getValue()"); 367 } 368 // getNextBytes() from a linear-match node 369 trie->next('u'); 370 memset(buffer, 0, sizeof(buffer)); 371 count=trie->getNextBytes(sink.Reset()); 372 if(count!=1 || sink.NumberOfBytesAppended()!=1 || buffer[0]!='a') { 373 errln("months getNextBytes()!=[a] after \"janu\""); 374 } 375 trie->next('a'); 376 memset(buffer, 0, sizeof(buffer)); 377 count=trie->getNextBytes(sink.Reset()); 378 if(count!=1 || sink.NumberOfBytesAppended()!=1 || buffer[0]!='r') { 379 errln("months getNextBytes()!=[r] after \"janua\""); 380 } 381 trie->next('r'); 382 trie->next('y'); 383 // getNextBytes() after a final match 384 count=trie->getNextBytes(sink.Reset()); 385 if(count!=0 || sink.NumberOfBytesAppended()!=0) { 386 errln("months getNextBytes()!=[] after \"january\""); 387 } 388 } 389 390 void BytesTrieTest::TestIteratorFromBranch() { 391 LocalPointer<BytesTrie> trie(buildMonthsTrie(USTRINGTRIE_BUILD_FAST)); 392 if(trie.isNull()) { 393 return; // buildTrie() reported an error 394 } 395 // Go to a branch node. 396 trie->next('j'); 397 trie->next('a'); 398 trie->next('n'); 399 IcuTestErrorCode errorCode(*this, "TestIteratorFromBranch()"); 400 BytesTrie::Iterator iter(*trie, 0, errorCode); 401 if(errorCode.logIfFailureAndReset("BytesTrie::Iterator(trie) constructor")) { 402 return; 403 } 404 // Expected data: Same as in buildMonthsTrie(), except only the suffixes 405 // following "jan". 406 static const StringAndValue data[]={ 407 { "", 1 }, 408 { ".", 1 }, 409 { "a", 1 }, 410 { "bb", 1 }, 411 { "c", 1 }, 412 { "ddd", 1 }, 413 { "ee", 1 }, 414 { "ef", 1 }, 415 { "f", 1 }, 416 { "gg", 1 }, 417 { "h", 1 }, 418 { "iiii", 1 }, 419 { "j", 1 }, 420 { "kk", 1 }, 421 { "kl", 1 }, 422 { "kmm", 1 }, 423 { "l", 1 }, 424 { "m", 1 }, 425 { "nnnnnnnnnnnnnnnnnnnnnnnnnnnn", 1 }, 426 { "o", 1 }, 427 { "pp", 1 }, 428 { "qqq", 1 }, 429 { "r", 1 }, 430 { "uar", 1 }, 431 { "uary", 1 } 432 }; 433 checkIterator(iter, data, UPRV_LENGTHOF(data)); 434 // Reset, and we should get the same result. 435 logln("after iter.reset()"); 436 checkIterator(iter.reset(), data, UPRV_LENGTHOF(data)); 437 } 438 439 void BytesTrieTest::TestIteratorFromLinearMatch() { 440 LocalPointer<BytesTrie> trie(buildMonthsTrie(USTRINGTRIE_BUILD_SMALL)); 441 if(trie.isNull()) { 442 return; // buildTrie() reported an error 443 } 444 // Go into a linear-match node. 445 trie->next('j'); 446 trie->next('a'); 447 trie->next('n'); 448 trie->next('u'); 449 trie->next('a'); 450 IcuTestErrorCode errorCode(*this, "TestIteratorFromLinearMatch()"); 451 BytesTrie::Iterator iter(*trie, 0, errorCode); 452 if(errorCode.logIfFailureAndReset("BytesTrie::Iterator(trie) constructor")) { 453 return; 454 } 455 // Expected data: Same as in buildMonthsTrie(), except only the suffixes 456 // following "janua". 457 static const StringAndValue data[]={ 458 { "r", 1 }, 459 { "ry", 1 } 460 }; 461 checkIterator(iter, data, UPRV_LENGTHOF(data)); 462 // Reset, and we should get the same result. 463 logln("after iter.reset()"); 464 checkIterator(iter.reset(), data, UPRV_LENGTHOF(data)); 465 } 466 467 void BytesTrieTest::TestTruncatingIteratorFromRoot() { 468 LocalPointer<BytesTrie> trie(buildMonthsTrie(USTRINGTRIE_BUILD_FAST)); 469 if(trie.isNull()) { 470 return; // buildTrie() reported an error 471 } 472 IcuTestErrorCode errorCode(*this, "TestTruncatingIteratorFromRoot()"); 473 BytesTrie::Iterator iter(*trie, 4, errorCode); 474 if(errorCode.logIfFailureAndReset("BytesTrie::Iterator(trie) constructor")) { 475 return; 476 } 477 // Expected data: Same as in buildMonthsTrie(), except only the first 4 characters 478 // of each string, and no string duplicates from the truncation. 479 static const StringAndValue data[]={ 480 { "augu", -1 }, 481 { "jan", 1 }, 482 { "jan.", 1 }, 483 { "jana", 1 }, 484 { "janb", -1 }, 485 { "janc", 1 }, 486 { "jand", -1 }, 487 { "jane", -1 }, 488 { "janf", 1 }, 489 { "jang", -1 }, 490 { "janh", 1 }, 491 { "jani", -1 }, 492 { "janj", 1 }, 493 { "jank", -1 }, 494 { "janl", 1 }, 495 { "janm", 1 }, 496 { "jann", -1 }, 497 { "jano", 1 }, 498 { "janp", -1 }, 499 { "janq", -1 }, 500 { "janr", 1 }, 501 { "janu", -1 }, 502 { "july", 7 }, 503 { "jun", 6 }, 504 { "jun.", 6 }, 505 { "june", 6 } 506 }; 507 checkIterator(iter, data, UPRV_LENGTHOF(data)); 508 // Reset, and we should get the same result. 509 logln("after iter.reset()"); 510 checkIterator(iter.reset(), data, UPRV_LENGTHOF(data)); 511 } 512 513 void BytesTrieTest::TestTruncatingIteratorFromLinearMatchShort() { 514 static const StringAndValue data[]={ 515 { "abcdef", 10 }, 516 { "abcdepq", 200 }, 517 { "abcdeyz", 3000 } 518 }; 519 LocalPointer<BytesTrie> trie(buildTrie(data, UPRV_LENGTHOF(data), USTRINGTRIE_BUILD_FAST)); 520 if(trie.isNull()) { 521 return; // buildTrie() reported an error 522 } 523 // Go into a linear-match node. 524 trie->next('a'); 525 trie->next('b'); 526 IcuTestErrorCode errorCode(*this, "TestTruncatingIteratorFromLinearMatchShort()"); 527 // Truncate within the linear-match node. 528 BytesTrie::Iterator iter(*trie, 2, errorCode); 529 if(errorCode.logIfFailureAndReset("BytesTrie::Iterator(trie) constructor")) { 530 return; 531 } 532 static const StringAndValue expected[]={ 533 { "cd", -1 } 534 }; 535 checkIterator(iter, expected, UPRV_LENGTHOF(expected)); 536 // Reset, and we should get the same result. 537 logln("after iter.reset()"); 538 checkIterator(iter.reset(), expected, UPRV_LENGTHOF(expected)); 539 } 540 541 void BytesTrieTest::TestTruncatingIteratorFromLinearMatchLong() { 542 static const StringAndValue data[]={ 543 { "abcdef", 10 }, 544 { "abcdepq", 200 }, 545 { "abcdeyz", 3000 } 546 }; 547 LocalPointer<BytesTrie> trie(buildTrie(data, UPRV_LENGTHOF(data), USTRINGTRIE_BUILD_FAST)); 548 if(trie.isNull()) { 549 return; // buildTrie() reported an error 550 } 551 // Go into a linear-match node. 552 trie->next('a'); 553 trie->next('b'); 554 trie->next('c'); 555 IcuTestErrorCode errorCode(*this, "TestTruncatingIteratorFromLinearMatchLong()"); 556 // Truncate after the linear-match node. 557 BytesTrie::Iterator iter(*trie, 3, errorCode); 558 if(errorCode.logIfFailureAndReset("BytesTrie::Iterator(trie) constructor")) { 559 return; 560 } 561 static const StringAndValue expected[]={ 562 { "def", 10 }, 563 { "dep", -1 }, 564 { "dey", -1 } 565 }; 566 checkIterator(iter, expected, UPRV_LENGTHOF(expected)); 567 // Reset, and we should get the same result. 568 logln("after iter.reset()"); 569 checkIterator(iter.reset(), expected, UPRV_LENGTHOF(expected)); 570 } 571 572 void BytesTrieTest::TestIteratorFromBytes() { 573 static const StringAndValue data[]={ 574 { "mm", 3 }, 575 { "mmm", 33 }, 576 { "mmnop", 333 } 577 }; 578 builder_->clear(); 579 IcuTestErrorCode errorCode(*this, "TestIteratorFromBytes()"); 580 for(int32_t i=0; i<UPRV_LENGTHOF(data); ++i) { 581 builder_->add(data[i].s, data[i].value, errorCode); 582 } 583 StringPiece trieBytes=builder_->buildStringPiece(USTRINGTRIE_BUILD_FAST, errorCode); 584 BytesTrie::Iterator iter(trieBytes.data(), 0, errorCode); 585 checkIterator(iter, data, UPRV_LENGTHOF(data)); 586 } 587 588 void BytesTrieTest::checkData(const StringAndValue data[], int32_t dataLength) { 589 logln("checkData(dataLength=%d, fast)", (int)dataLength); 590 checkData(data, dataLength, USTRINGTRIE_BUILD_FAST); 591 logln("checkData(dataLength=%d, small)", (int)dataLength); 592 checkData(data, dataLength, USTRINGTRIE_BUILD_SMALL); 593 } 594 595 void BytesTrieTest::checkData(const StringAndValue data[], int32_t dataLength, UStringTrieBuildOption buildOption) { 596 LocalPointer<BytesTrie> trie(buildTrie(data, dataLength, buildOption)); 597 if(trie.isNull()) { 598 return; // buildTrie() reported an error 599 } 600 checkFirst(*trie, data, dataLength); 601 checkNext(*trie, data, dataLength); 602 checkNextWithState(*trie, data, dataLength); 603 checkNextString(*trie, data, dataLength); 604 checkIterator(*trie, data, dataLength); 605 } 606 607 BytesTrie *BytesTrieTest::buildTrie(const StringAndValue data[], int32_t dataLength, 608 UStringTrieBuildOption buildOption) { 609 IcuTestErrorCode errorCode(*this, "buildTrie()"); 610 // Add the items to the trie builder in an interesting (not trivial, not random) order. 611 int32_t index, step; 612 if(dataLength&1) { 613 // Odd number of items. 614 index=dataLength/2; 615 step=2; 616 } else if((dataLength%3)!=0) { 617 // Not a multiple of 3. 618 index=dataLength/5; 619 step=3; 620 } else { 621 index=dataLength-1; 622 step=-1; 623 } 624 builder_->clear(); 625 for(int32_t i=0; i<dataLength; ++i) { 626 builder_->add(data[index].s, data[index].value, errorCode); 627 index=(index+step)%dataLength; 628 } 629 StringPiece sp=builder_->buildStringPiece(buildOption, errorCode); 630 LocalPointer<BytesTrie> trie(builder_->build(buildOption, errorCode)); 631 if(!errorCode.logIfFailureAndReset("add()/build()")) { 632 builder_->add("zzz", 999, errorCode); 633 if(errorCode.reset()!=U_NO_WRITE_PERMISSION) { 634 errln("builder.build().add(zzz) did not set U_NO_WRITE_PERMISSION"); 635 } 636 } 637 logln("serialized trie size: %ld bytes\n", (long)sp.length()); 638 StringPiece sp2=builder_->buildStringPiece(buildOption, errorCode); 639 if(sp.data()==sp2.data()) { 640 errln("builder.buildStringPiece() before & after build() returned same array"); 641 } 642 if(errorCode.isFailure()) { 643 return NULL; 644 } 645 // Tries from either build() method should be identical but 646 // BytesTrie does not implement equals(). 647 // We just return either one. 648 if((dataLength&1)!=0) { 649 return trie.orphan(); 650 } else { 651 return new BytesTrie(sp2.data()); 652 } 653 } 654 655 void BytesTrieTest::checkFirst(BytesTrie &trie, 656 const StringAndValue data[], int32_t dataLength) { 657 for(int32_t i=0; i<dataLength; ++i) { 658 int c=*data[i].s; 659 if(c==0) { 660 continue; // skip empty string 661 } 662 UStringTrieResult firstResult=trie.first(c); 663 int32_t firstValue=USTRINGTRIE_HAS_VALUE(firstResult) ? trie.getValue() : -1; 664 UStringTrieResult nextResult=trie.next(data[i].s[1]); 665 if(firstResult!=trie.reset().next(c) || 666 firstResult!=trie.current() || 667 firstValue!=(USTRINGTRIE_HAS_VALUE(firstResult) ? trie.getValue() : -1) || 668 nextResult!=trie.next(data[i].s[1]) 669 ) { 670 errln("trie.first(%c)!=trie.reset().next(same) for %s", 671 c, data[i].s); 672 } 673 } 674 trie.reset(); 675 } 676 677 void BytesTrieTest::checkNext(BytesTrie &trie, 678 const StringAndValue data[], int32_t dataLength) { 679 BytesTrie::State state; 680 for(int32_t i=0; i<dataLength; ++i) { 681 int32_t stringLength= (i&1) ? -1 : strlen(data[i].s); 682 UStringTrieResult result; 683 if( !USTRINGTRIE_HAS_VALUE(result=trie.next(data[i].s, stringLength)) || 684 result!=trie.current() 685 ) { 686 errln("trie does not seem to contain %s", data[i].s); 687 } else if(trie.getValue()!=data[i].value) { 688 errln("trie value for %s is %ld=0x%lx instead of expected %ld=0x%lx", 689 data[i].s, 690 (long)trie.getValue(), (long)trie.getValue(), 691 (long)data[i].value, (long)data[i].value); 692 } else if(result!=trie.current() || trie.getValue()!=data[i].value) { 693 errln("trie value for %s changes when repeating current()/getValue()", data[i].s); 694 } 695 trie.reset(); 696 stringLength=strlen(data[i].s); 697 result=trie.current(); 698 for(int32_t j=0; j<stringLength; ++j) { 699 if(!USTRINGTRIE_HAS_NEXT(result)) { 700 errln("trie.current()!=hasNext before end of %s (at index %d)", data[i].s, j); 701 break; 702 } 703 if(result==USTRINGTRIE_INTERMEDIATE_VALUE) { 704 trie.getValue(); 705 if(trie.current()!=USTRINGTRIE_INTERMEDIATE_VALUE) { 706 errln("trie.getValue().current()!=USTRINGTRIE_INTERMEDIATE_VALUE before end of %s (at index %d)", data[i].s, j); 707 break; 708 } 709 } 710 result=trie.next(data[i].s[j]); 711 if(!USTRINGTRIE_MATCHES(result)) { 712 errln("trie.next()=USTRINGTRIE_NO_MATCH before end of %s (at index %d)", data[i].s, j); 713 break; 714 } 715 if(result!=trie.current()) { 716 errln("trie.next()!=following current() before end of %s (at index %d)", data[i].s, j); 717 break; 718 } 719 } 720 if(!USTRINGTRIE_HAS_VALUE(result)) { 721 errln("trie.next()!=hasValue at the end of %s", data[i].s); 722 continue; 723 } 724 trie.getValue(); 725 if(result!=trie.current()) { 726 errln("trie.current() != current()+getValue()+current() after end of %s", 727 data[i].s); 728 } 729 // Compare the final current() with whether next() can actually continue. 730 trie.saveState(state); 731 UBool nextContinues=FALSE; 732 // Try all graphic characters; we only use those in test strings in this file. 733 #if U_CHARSET_FAMILY==U_ASCII_FAMILY 734 const int32_t minChar=0x20; 735 const int32_t maxChar=0x7e; 736 #elif U_CHARSET_FAMILY==U_EBCDIC_FAMILY 737 const int32_t minChar=0x40; 738 const int32_t maxChar=0xfe; 739 #else 740 const int32_t minChar=0; 741 const int32_t maxChar=0xff; 742 #endif 743 for(int32_t c=minChar; c<=maxChar; ++c) { 744 if(trie.resetToState(state).next(c)) { 745 nextContinues=TRUE; 746 break; 747 } 748 } 749 if((result==USTRINGTRIE_INTERMEDIATE_VALUE)!=nextContinues) { 750 errln("(trie.current()==USTRINGTRIE_INTERMEDIATE_VALUE) contradicts " 751 "(trie.next(some byte)!=USTRINGTRIE_NO_MATCH) after end of %s", data[i].s); 752 } 753 trie.reset(); 754 } 755 } 756 757 void BytesTrieTest::checkNextWithState(BytesTrie &trie, 758 const StringAndValue data[], int32_t dataLength) { 759 BytesTrie::State noState, state; 760 for(int32_t i=0; i<dataLength; ++i) { 761 if((i&1)==0) { 762 // This should have no effect. 763 trie.resetToState(noState); 764 } 765 const char *expectedString=data[i].s; 766 int32_t stringLength=strlen(expectedString); 767 int32_t partialLength=stringLength/3; 768 for(int32_t j=0; j<partialLength; ++j) { 769 if(!USTRINGTRIE_MATCHES(trie.next(expectedString[j]))) { 770 errln("trie.next()=USTRINGTRIE_NO_MATCH for a prefix of %s", data[i].s); 771 return; 772 } 773 } 774 trie.saveState(state); 775 UStringTrieResult resultAtState=trie.current(); 776 UStringTrieResult result; 777 int32_t valueAtState=-99; 778 if(USTRINGTRIE_HAS_VALUE(resultAtState)) { 779 valueAtState=trie.getValue(); 780 } 781 result=trie.next(0); // mismatch 782 if(result!=USTRINGTRIE_NO_MATCH || result!=trie.current()) { 783 errln("trie.next(0) matched after part of %s", data[i].s); 784 } 785 if( resultAtState!=trie.resetToState(state).current() || 786 (USTRINGTRIE_HAS_VALUE(resultAtState) && valueAtState!=trie.getValue()) 787 ) { 788 errln("trie.next(part of %s) changes current()/getValue() after " 789 "saveState/next(0)/resetToState", 790 data[i].s); 791 } else if(!USTRINGTRIE_HAS_VALUE( 792 result=trie.next(expectedString+partialLength, 793 stringLength-partialLength)) || 794 result!=trie.current()) { 795 errln("trie.next(rest of %s) does not seem to contain %s after " 796 "saveState/next(0)/resetToState", 797 data[i].s, data[i].s); 798 } else if(!USTRINGTRIE_HAS_VALUE( 799 result=trie.resetToState(state). 800 next(expectedString+partialLength, 801 stringLength-partialLength)) || 802 result!=trie.current()) { 803 errln("trie does not seem to contain %s after saveState/next(rest)/resetToState", 804 data[i].s); 805 } else if(trie.getValue()!=data[i].value) { 806 errln("trie value for %s is %ld=0x%lx instead of expected %ld=0x%lx", 807 data[i].s, 808 (long)trie.getValue(), (long)trie.getValue(), 809 (long)data[i].value, (long)data[i].value); 810 } 811 trie.reset(); 812 } 813 } 814 815 // next(string) is also tested in other functions, 816 // but here we try to go partway through the string, and then beyond it. 817 void BytesTrieTest::checkNextString(BytesTrie &trie, 818 const StringAndValue data[], int32_t dataLength) { 819 for(int32_t i=0; i<dataLength; ++i) { 820 const char *expectedString=data[i].s; 821 int32_t stringLength=strlen(expectedString); 822 if(!trie.next(expectedString, stringLength/2)) { 823 errln("trie.next(up to middle of string)=USTRINGTRIE_NO_MATCH for %s", data[i].s); 824 continue; 825 } 826 // Test that we stop properly at the end of the string. 827 if(trie.next(expectedString+stringLength/2, stringLength+1-stringLength/2)) { 828 errln("trie.next(string+NUL)!=USTRINGTRIE_NO_MATCH for %s", data[i].s); 829 } 830 trie.reset(); 831 } 832 } 833 834 void BytesTrieTest::checkIterator(const BytesTrie &trie, 835 const StringAndValue data[], int32_t dataLength) { 836 IcuTestErrorCode errorCode(*this, "checkIterator()"); 837 BytesTrie::Iterator iter(trie, 0, errorCode); 838 if(errorCode.logIfFailureAndReset("BytesTrie::Iterator(trie) constructor")) { 839 return; 840 } 841 checkIterator(iter, data, dataLength); 842 } 843 844 void BytesTrieTest::checkIterator(BytesTrie::Iterator &iter, 845 const StringAndValue data[], int32_t dataLength) { 846 IcuTestErrorCode errorCode(*this, "checkIterator()"); 847 for(int32_t i=0; i<dataLength; ++i) { 848 if(!iter.hasNext()) { 849 errln("trie iterator hasNext()=FALSE for item %d: %s", (int)i, data[i].s); 850 break; 851 } 852 UBool hasNext=iter.next(errorCode); 853 if(errorCode.logIfFailureAndReset("trie iterator next() for item %d: %s", (int)i, data[i].s)) { 854 break; 855 } 856 if(!hasNext) { 857 errln("trie iterator next()=FALSE for item %d: %s", (int)i, data[i].s); 858 break; 859 } 860 if(iter.getString()!=StringPiece(data[i].s)) { 861 errln("trie iterator next().getString()=%s but expected %s for item %d", 862 iter.getString().data(), data[i].s, (int)i); 863 } 864 if(iter.getValue()!=data[i].value) { 865 errln("trie iterator next().getValue()=%ld=0x%lx but expected %ld=0x%lx for item %d: %s", 866 (long)iter.getValue(), (long)iter.getValue(), 867 (long)data[i].value, (long)data[i].value, 868 (int)i, data[i].s); 869 } 870 } 871 if(iter.hasNext()) { 872 errln("trie iterator hasNext()=TRUE after all items"); 873 } 874 UBool hasNext=iter.next(errorCode); 875 errorCode.logIfFailureAndReset("trie iterator next() after all items"); 876 if(hasNext) { 877 errln("trie iterator next()=TRUE after all items"); 878 } 879 } 880
