icuSources/common/ucharstrie.cpp

   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-2011, International Business Machines
   6 *   Corporation and others.  All Rights Reserved.
   7 *******************************************************************************
   8 *   file name:  ucharstrie.h
   9 *   encoding:   UTF-8
  10 *   tab size:   8 (not used)
  11 *   indentation:4
  12 *
  13 *   created on: 2010nov14
  14 *   created by: Markus W. Scherer
  15 */
  16
  17 #include "unicode/utypes.h"
  18 #include "unicode/appendable.h"
  19 #include "unicode/ucharstrie.h"
  20 #include "unicode/uobject.h"
  21 #include "unicode/utf16.h"
  22 #include "cmemory.h"
  23 #include "uassert.h"
  24
  25 U_NAMESPACE_BEGIN
  26
  27 UCharsTrie::~UCharsTrie() {
  28     uprv_free(ownedArray_);
  29 }
  30
  31 UStringTrieResult
  32 UCharsTrie::current() const {
  33     const UChar *pos=pos_;
  34     if(pos==NULL) {
  35         return USTRINGTRIE_NO_MATCH;
  36     } else {
  37         int32_t node;
  38         return (remainingMatchLength_<0 && (node=*pos)>=kMinValueLead) ?
  39                 valueResult(node) : USTRINGTRIE_NO_VALUE;
  40     }
  41 }
  42
  43 UStringTrieResult
  44 UCharsTrie::firstForCodePoint(UChar32 cp) {
  45     return cp<=0xffff ?
  46         first(cp) :
  47         (USTRINGTRIE_HAS_NEXT(first(U16_LEAD(cp))) ?
  48             next(U16_TRAIL(cp)) :
  49             USTRINGTRIE_NO_MATCH);
  50 }
  51
  52 UStringTrieResult
  53 UCharsTrie::nextForCodePoint(UChar32 cp) {
  54     return cp<=0xffff ?
  55         next(cp) :
  56         (USTRINGTRIE_HAS_NEXT(next(U16_LEAD(cp))) ?
  57             next(U16_TRAIL(cp)) :
  58             USTRINGTRIE_NO_MATCH);
  59 }
  60
  61 UStringTrieResult
  62 UCharsTrie::branchNext(const UChar *pos, int32_t length, int32_t uchar) {
  63     // Branch according to the current unit.
  64     if(length==0) {
  65         length=*pos++;
  66     }
  67     ++length;
  68     // The length of the branch is the number of units to select from.
  69     // The data structure encodes a binary search.
  70     while(length>kMaxBranchLinearSubNodeLength) {
  71         if(uchar<*pos++) {
  72             length>>=1;
  73             pos=jumpByDelta(pos);
  74         } else {
  75             length=length-(length>>1);
  76             pos=skipDelta(pos);
  77         }
  78     }
  79     // Drop down to linear search for the last few units.
  80     // length>=2 because the loop body above sees length>kMaxBranchLinearSubNodeLength>=3
  81     // and divides length by 2.
  82     do {
  83         if(uchar==*pos++) {
  84             UStringTrieResult result;
  85             int32_t node=*pos;
  86             if(node&kValueIsFinal) {
  87                 // Leave the final value for getValue() to read.
  88                 result=USTRINGTRIE_FINAL_VALUE;
  89             } else {
  90                 // Use the non-final value as the jump delta.
  91                 ++pos;
  92                 // int32_t delta=readValue(pos, node);
  93                 int32_t delta;
  94                 if(node<kMinTwoUnitValueLead) {
  95                     delta=node;
  96                 } else if(node<kThreeUnitValueLead) {
  97                     delta=((node-kMinTwoUnitValueLead)<<16)|*pos++;
  98                 } else {
  99                     delta=(pos[0]<<16)|pos[1];
 100                     pos+=2;
 101                 }
 102                 // end readValue()
 103                 pos+=delta;
 104                 node=*pos;
 105                 result= node>=kMinValueLead ? valueResult(node) : USTRINGTRIE_NO_VALUE;
 106             }
 107             pos_=pos;
 108             return result;
 109         }
 110         --length;
 111         pos=skipValue(pos);
 112     } while(length>1);
 113     if(uchar==*pos++) {
 114         pos_=pos;
 115         int32_t node=*pos;
 116         return node>=kMinValueLead ? valueResult(node) : USTRINGTRIE_NO_VALUE;
 117     } else {
 118         stop();
 119         return USTRINGTRIE_NO_MATCH;
 120     }
 121 }
 122
 123 UStringTrieResult
 124 UCharsTrie::nextImpl(const UChar *pos, int32_t uchar) {
 125     int32_t node=*pos++;
 126     for(;;) {
 127         if(node<kMinLinearMatch) {
 128             return branchNext(pos, node, uchar);
 129         } else if(node<kMinValueLead) {
 130             // Match the first of length+1 units.
 131             int32_t length=node-kMinLinearMatch;  // Actual match length minus 1.
 132             if(uchar==*pos++) {
 133                 remainingMatchLength_=--length;
 134                 pos_=pos;
 135                 return (length<0 && (node=*pos)>=kMinValueLead) ?
 136                         valueResult(node) : USTRINGTRIE_NO_VALUE;
 137             } else {
 138                 // No match.
 139                 break;
 140             }
 141         } else if(node&kValueIsFinal) {
 142             // No further matching units.
 143             break;
 144         } else {
 145             // Skip intermediate value.
 146             pos=skipNodeValue(pos, node);
 147             node&=kNodeTypeMask;
 148         }
 149     }
 150     stop();
 151     return USTRINGTRIE_NO_MATCH;
 152 }
 153
 154 UStringTrieResult
 155 UCharsTrie::next(int32_t uchar) {
 156     const UChar *pos=pos_;
 157     if(pos==NULL) {
 158         return USTRINGTRIE_NO_MATCH;
 159     }
 160     int32_t length=remainingMatchLength_;  // Actual remaining match length minus 1.
 161     if(length>=0) {
 162         // Remaining part of a linear-match node.
 163         if(uchar==*pos++) {
 164             remainingMatchLength_=--length;
 165             pos_=pos;
 166             int32_t node;
 167             return (length<0 && (node=*pos)>=kMinValueLead) ?
 168                     valueResult(node) : USTRINGTRIE_NO_VALUE;
 169         } else {
 170             stop();
 171             return USTRINGTRIE_NO_MATCH;
 172         }
 173     }
 174     return nextImpl(pos, uchar);
 175 }
 176
 177 UStringTrieResult
 178 UCharsTrie::next(ConstChar16Ptr ptr, int32_t sLength) {
 179     const UChar *s=ptr;
 180     if(sLength<0 ? *s==0 : sLength==0) {
 181         // Empty input.
 182         return current();
 183     }
 184     const UChar *pos=pos_;
 185     if(pos==NULL) {
 186         return USTRINGTRIE_NO_MATCH;
 187     }
 188     int32_t length=remainingMatchLength_;  // Actual remaining match length minus 1.
 189     for(;;) {
 190         // Fetch the next input unit, if there is one.
 191         // Continue a linear-match node without rechecking sLength<0.
 192         int32_t uchar;
 193         if(sLength<0) {
 194             for(;;) {
 195                 if((uchar=*s++)==0) {
 196                     remainingMatchLength_=length;
 197                     pos_=pos;
 198                     int32_t node;
 199                     return (length<0 && (node=*pos)>=kMinValueLead) ?
 200                             valueResult(node) : USTRINGTRIE_NO_VALUE;
 201                 }
 202                 if(length<0) {
 203                     remainingMatchLength_=length;
 204                     break;
 205                 }
 206                 if(uchar!=*pos) {
 207                     stop();
 208                     return USTRINGTRIE_NO_MATCH;
 209                 }
 210                 ++pos;
 211                 --length;
 212             }
 213         } else {
 214             for(;;) {
 215                 if(sLength==0) {
 216                     remainingMatchLength_=length;
 217                     pos_=pos;
 218                     int32_t node;
 219                     return (length<0 && (node=*pos)>=kMinValueLead) ?
 220                             valueResult(node) : USTRINGTRIE_NO_VALUE;
 221                 }
 222                 uchar=*s++;
 223                 --sLength;
 224                 if(length<0) {
 225                     remainingMatchLength_=length;
 226                     break;
 227                 }
 228                 if(uchar!=*pos) {
 229                     stop();
 230                     return USTRINGTRIE_NO_MATCH;
 231                 }
 232                 ++pos;
 233                 --length;
 234             }
 235         }
 236         int32_t node=*pos++;
 237         for(;;) {
 238             if(node<kMinLinearMatch) {
 239                 UStringTrieResult result=branchNext(pos, node, uchar);
 240                 if(result==USTRINGTRIE_NO_MATCH) {
 241                     return USTRINGTRIE_NO_MATCH;
 242                 }
 243                 // Fetch the next input unit, if there is one.
 244                 if(sLength<0) {
 245                     if((uchar=*s++)==0) {
 246                         return result;
 247                     }
 248                 } else {
 249                     if(sLength==0) {
 250                         return result;
 251                     }
 252                     uchar=*s++;
 253                     --sLength;
 254                 }
 255                 if(result==USTRINGTRIE_FINAL_VALUE) {
 256                     // No further matching units.
 257                     stop();
 258                     return USTRINGTRIE_NO_MATCH;
 259                 }
 260                 pos=pos_;  // branchNext() advanced pos and wrote it to pos_ .
 261                 node=*pos++;
 262             } else if(node<kMinValueLead) {
 263                 // Match length+1 units.
 264                 length=node-kMinLinearMatch;  // Actual match length minus 1.
 265                 if(uchar!=*pos) {
 266                     stop();
 267                     return USTRINGTRIE_NO_MATCH;
 268                 }
 269                 ++pos;
 270                 --length;
 271                 break;
 272             } else if(node&kValueIsFinal) {
 273                 // No further matching units.
 274                 stop();
 275                 return USTRINGTRIE_NO_MATCH;
 276             } else {
 277                 // Skip intermediate value.
 278                 pos=skipNodeValue(pos, node);
 279                 node&=kNodeTypeMask;
 280             }
 281         }
 282     }
 283 }
 284
 285 const UChar *
 286 UCharsTrie::findUniqueValueFromBranch(const UChar *pos, int32_t length,
 287                                       UBool haveUniqueValue, int32_t &uniqueValue) {
 288     while(length>kMaxBranchLinearSubNodeLength) {
 289         ++pos;  // ignore the comparison unit
 290         if(NULL==findUniqueValueFromBranch(jumpByDelta(pos), length>>1, haveUniqueValue, uniqueValue)) {
 291             return NULL;
 292         }
 293         length=length-(length>>1);
 294         pos=skipDelta(pos);
 295     }
 296     do {
 297         ++pos;  // ignore a comparison unit
 298         // handle its value
 299         int32_t node=*pos++;
 300         UBool isFinal=(UBool)(node>>15);
 301         node&=0x7fff;
 302         int32_t value=readValue(pos, node);
 303         pos=skipValue(pos, node);
 304         if(isFinal) {
 305             if(haveUniqueValue) {
 306                 if(value!=uniqueValue) {
 307                     return NULL;
 308                 }
 309             } else {
 310                 uniqueValue=value;
 311                 haveUniqueValue=TRUE;
 312             }
 313         } else {
 314             if(!findUniqueValue(pos+value, haveUniqueValue, uniqueValue)) {
 315                 return NULL;
 316             }
 317             haveUniqueValue=TRUE;
 318         }
 319     } while(--length>1);
 320     return pos+1;  // ignore the last comparison unit
 321 }
 322
 323 UBool
 324 UCharsTrie::findUniqueValue(const UChar *pos, UBool haveUniqueValue, int32_t &uniqueValue) {
 325     int32_t node=*pos++;
 326     for(;;) {
 327         if(node<kMinLinearMatch) {
 328             if(node==0) {
 329                 node=*pos++;
 330             }
 331             pos=findUniqueValueFromBranch(pos, node+1, haveUniqueValue, uniqueValue);
 332             if(pos==NULL) {
 333                 return FALSE;
 334             }
 335             haveUniqueValue=TRUE;
 336             node=*pos++;
 337         } else if(node<kMinValueLead) {
 338             // linear-match node
 339             pos+=node-kMinLinearMatch+1;  // Ignore the match units.
 340             node=*pos++;
 341         } else {
 342             UBool isFinal=(UBool)(node>>15);
 343             int32_t value;
 344             if(isFinal) {
 345                 value=readValue(pos, node&0x7fff);
 346             } else {
 347                 value=readNodeValue(pos, node);
 348             }
 349             if(haveUniqueValue) {
 350                 if(value!=uniqueValue) {
 351                     return FALSE;
 352                 }
 353             } else {
 354                 uniqueValue=value;
 355                 haveUniqueValue=TRUE;
 356             }
 357             if(isFinal) {
 358                 return TRUE;
 359             }
 360             pos=skipNodeValue(pos, node);
 361             node&=kNodeTypeMask;
 362         }
 363     }
 364 }
 365
 366 int32_t
 367 UCharsTrie::getNextUChars(Appendable &out) const {
 368     const UChar *pos=pos_;
 369     if(pos==NULL) {
 370         return 0;
 371     }
 372     if(remainingMatchLength_>=0) {
 373         out.appendCodeUnit(*pos);  // Next unit of a pending linear-match node.
 374         return 1;
 375     }
 376     int32_t node=*pos++;
 377     if(node>=kMinValueLead) {
 378         if(node&kValueIsFinal) {
 379             return 0;
 380         } else {
 381             pos=skipNodeValue(pos, node);
 382             node&=kNodeTypeMask;
 383         }
 384     }
 385     if(node<kMinLinearMatch) {
 386         if(node==0) {
 387             node=*pos++;
 388         }
 389         out.reserveAppendCapacity(++node);
 390         getNextBranchUChars(pos, node, out);
 391         return node;
 392     } else {
 393         // First unit of the linear-match node.
 394         out.appendCodeUnit(*pos);
 395         return 1;
 396     }
 397 }
 398
 399 void
 400 UCharsTrie::getNextBranchUChars(const UChar *pos, int32_t length, Appendable &out) {
 401     while(length>kMaxBranchLinearSubNodeLength) {
 402         ++pos;  // ignore the comparison unit
 403         getNextBranchUChars(jumpByDelta(pos), length>>1, out);
 404         length=length-(length>>1);
 405         pos=skipDelta(pos);
 406     }
 407     do {
 408         out.appendCodeUnit(*pos++);
 409         pos=skipValue(pos);
 410     } while(--length>1);
 411     out.appendCodeUnit(*pos);
 412 }
 413
 414 U_NAMESPACE_END