icuSources/common/utrie.cpp

   1 /*
   2 ******************************************************************************
   3 *
   4 *   Copyright (C) 2001-2012, International Business Machines
   5 *   Corporation and others.  All Rights Reserved.
   6 *
   7 ******************************************************************************
   8 *   file name:  utrie.cpp
   9 *   encoding:   US-ASCII
  10 *   tab size:   8 (not used)
  11 *   indentation:4
  12 *
  13 *   created on: 2001oct20
  14 *   created by: Markus W. Scherer
  15 *
  16 *   This is a common implementation of a "folded" trie.
  17 *   It is a kind of compressed, serializable table of 16- or 32-bit values associated with
  18 *   Unicode code points (0..0x10ffff).
  19 */
  20
  21 #ifdef UTRIE_DEBUG
  22 #   include <stdio.h>
  23 #endif
  24
  25 #include "unicode/utypes.h"
  26 #include "cmemory.h"
  27 #include "utrie.h"
  28
  29 /* miscellaneous ------------------------------------------------------------ */
  30
  31 #undef ABS
  32 #define ABS(x) ((x)>=0 ? (x) : -(x))
  33
  34 static inline UBool
  35 equal_uint32(const uint32_t *s, const uint32_t *t, int32_t length) {
  36     while(length>0 && *s==*t) {
  37         ++s;
  38         ++t;
  39         --length;
  40     }
  41     return (UBool)(length==0);
  42 }
  43
  44 /* Building a trie ----------------------------------------------------------*/
  45
  46 U_CAPI UNewTrie * U_EXPORT2
  47 utrie_open(UNewTrie *fillIn,
  48            uint32_t *aliasData, int32_t maxDataLength,
  49            uint32_t initialValue, uint32_t leadUnitValue,
  50            UBool latin1Linear) {
  51     UNewTrie *trie;
  52     int32_t i, j;
  53
  54     if( maxDataLength<UTRIE_DATA_BLOCK_LENGTH ||
  55         (latin1Linear && maxDataLength<1024)
  56     ) {
  57         return NULL;
  58     }
  59
  60     if(fillIn!=NULL) {
  61         trie=fillIn;
  62     } else {
  63         trie=(UNewTrie *)uprv_malloc(sizeof(UNewTrie));
  64         if(trie==NULL) {
  65             return NULL;
  66         }
  67     }
  68     uprv_memset(trie, 0, sizeof(UNewTrie));
  69     trie->isAllocated= (UBool)(fillIn==NULL);
  70
  71     if(aliasData!=NULL) {
  72         trie->data=aliasData;
  73         trie->isDataAllocated=FALSE;
  74     } else {
  75         trie->data=(uint32_t *)uprv_malloc(maxDataLength*4);
  76         if(trie->data==NULL) {
  77             uprv_free(trie);
  78             return NULL;
  79         }
  80         trie->isDataAllocated=TRUE;
  81     }
  82
  83     /* preallocate and reset the first data block (block index 0) */
  84     j=UTRIE_DATA_BLOCK_LENGTH;
  85
  86     if(latin1Linear) {
  87         /* preallocate and reset the first block (number 0) and Latin-1 (U+0000..U+00ff) after that */
  88         /* made sure above that maxDataLength>=1024 */
  89
  90         /* set indexes to point to consecutive data blocks */
  91         i=0;
  92         do {
  93             /* do this at least for trie->index[0] even if that block is only partly used for Latin-1 */
  94             trie->index[i++]=j;
  95             j+=UTRIE_DATA_BLOCK_LENGTH;
  96         } while(i<(256>>UTRIE_SHIFT));
  97     }
  98
  99     /* reset the initially allocated blocks to the initial value */
 100     trie->dataLength=j;
 101     while(j>0) {
 102         trie->data[--j]=initialValue;
 103     }
 104
 105     trie->leadUnitValue=leadUnitValue;
 106     trie->indexLength=UTRIE_MAX_INDEX_LENGTH;
 107     trie->dataCapacity=maxDataLength;
 108     trie->isLatin1Linear=latin1Linear;
 109     trie->isCompacted=FALSE;
 110     return trie;
 111 }
 112
 113 U_CAPI UNewTrie * U_EXPORT2
 114 utrie_clone(UNewTrie *fillIn, const UNewTrie *other, uint32_t *aliasData, int32_t aliasDataCapacity) {
 115     UNewTrie *trie;
 116     UBool isDataAllocated;
 117
 118     /* do not clone if other is not valid or already compacted */
 119     if(other==NULL || other->data==NULL || other->isCompacted) {
 120         return NULL;
 121     }
 122
 123     /* clone data */
 124     if(aliasData!=NULL && aliasDataCapacity>=other->dataCapacity) {
 125         isDataAllocated=FALSE;
 126     } else {
 127         aliasDataCapacity=other->dataCapacity;
 128         aliasData=(uint32_t *)uprv_malloc(other->dataCapacity*4);
 129         if(aliasData==NULL) {
 130             return NULL;
 131         }
 132         isDataAllocated=TRUE;
 133     }
 134
 135     trie=utrie_open(fillIn, aliasData, aliasDataCapacity,
 136                     other->data[0], other->leadUnitValue,
 137                     other->isLatin1Linear);
 138     if(trie==NULL) {
 139         uprv_free(aliasData);
 140     } else {
 141         uprv_memcpy(trie->index, other->index, sizeof(trie->index));
 142         uprv_memcpy(trie->data, other->data, other->dataLength*4);
 143         trie->dataLength=other->dataLength;
 144         trie->isDataAllocated=isDataAllocated;
 145     }
 146
 147     return trie;
 148 }
 149
 150 U_CAPI void U_EXPORT2
 151 utrie_close(UNewTrie *trie) {
 152     if(trie!=NULL) {
 153         if(trie->isDataAllocated) {
 154             uprv_free(trie->data);
 155             trie->data=NULL;
 156         }
 157         if(trie->isAllocated) {
 158             uprv_free(trie);
 159         }
 160     }
 161 }
 162
 163 U_CAPI uint32_t * U_EXPORT2
 164 utrie_getData(UNewTrie *trie, int32_t *pLength) {
 165     if(trie==NULL || pLength==NULL) {
 166         return NULL;
 167     }
 168
 169     *pLength=trie->dataLength;
 170     return trie->data;
 171 }
 172
 173 static int32_t
 174 utrie_allocDataBlock(UNewTrie *trie) {
 175     int32_t newBlock, newTop;
 176
 177     newBlock=trie->dataLength;
 178     newTop=newBlock+UTRIE_DATA_BLOCK_LENGTH;
 179     if(newTop>trie->dataCapacity) {
 180         /* out of memory in the data array */
 181         return -1;
 182     }
 183     trie->dataLength=newTop;
 184     return newBlock;
 185 }
 186
 187 /**
 188  * No error checking for illegal arguments.
 189  *
 190  * @return -1 if no new data block available (out of memory in data array)
 191  * @internal
 192  */
 193 static int32_t
 194 utrie_getDataBlock(UNewTrie *trie, UChar32 c) {
 195     int32_t indexValue, newBlock;
 196
 197     c>>=UTRIE_SHIFT;
 198     indexValue=trie->index[c];
 199     if(indexValue>0) {
 200         return indexValue;
 201     }
 202
 203     /* allocate a new data block */
 204     newBlock=utrie_allocDataBlock(trie);
 205     if(newBlock<0) {
 206         /* out of memory in the data array */
 207         return -1;
 208     }
 209     trie->index[c]=newBlock;
 210
 211     /* copy-on-write for a block from a setRange() */
 212     uprv_memcpy(trie->data+newBlock, trie->data-indexValue, 4*UTRIE_DATA_BLOCK_LENGTH);
 213     return newBlock;
 214 }
 215
 216 /**
 217  * @return TRUE if the value was successfully set
 218  */
 219 U_CAPI UBool U_EXPORT2
 220 utrie_set32(UNewTrie *trie, UChar32 c, uint32_t value) {
 221     int32_t block;
 222
 223     /* valid, uncompacted trie and valid c? */
 224     if(trie==NULL || trie->isCompacted || (uint32_t)c>0x10ffff) {
 225         return FALSE;
 226     }
 227
 228     block=utrie_getDataBlock(trie, c);
 229     if(block<0) {
 230         return FALSE;
 231     }
 232
 233     trie->data[block+(c&UTRIE_MASK)]=value;
 234     return TRUE;
 235 }
 236
 237 U_CAPI uint32_t U_EXPORT2
 238 utrie_get32(UNewTrie *trie, UChar32 c, UBool *pInBlockZero) {
 239     int32_t block;
 240
 241     /* valid, uncompacted trie and valid c? */
 242     if(trie==NULL || trie->isCompacted || (uint32_t)c>0x10ffff) {
 243         if(pInBlockZero!=NULL) {
 244             *pInBlockZero=TRUE;
 245         }
 246         return 0;
 247     }
 248
 249     block=trie->index[c>>UTRIE_SHIFT];
 250     if(pInBlockZero!=NULL) {
 251         *pInBlockZero= (UBool)(block==0);
 252     }
 253
 254     return trie->data[ABS(block)+(c&UTRIE_MASK)];
 255 }
 256
 257 /**
 258  * @internal
 259  */
 260 static void
 261 utrie_fillBlock(uint32_t *block, UChar32 start, UChar32 limit,
 262                 uint32_t value, uint32_t initialValue, UBool overwrite) {
 263     uint32_t *pLimit;
 264
 265     pLimit=block+limit;
 266     block+=start;
 267     if(overwrite) {
 268         while(block<pLimit) {
 269             *block++=value;
 270         }
 271     } else {
 272         while(block<pLimit) {
 273             if(*block==initialValue) {
 274                 *block=value;
 275             }
 276             ++block;
 277         }
 278     }
 279 }
 280
 281 U_CAPI UBool U_EXPORT2
 282 utrie_setRange32(UNewTrie *trie, UChar32 start, UChar32 limit, uint32_t value, UBool overwrite) {
 283     /*
 284      * repeat value in [start..limit[
 285      * mark index values for repeat-data blocks by setting bit 31 of the index values
 286      * fill around existing values if any, if(overwrite)
 287      */
 288     uint32_t initialValue;
 289     int32_t block, rest, repeatBlock;
 290
 291     /* valid, uncompacted trie and valid indexes? */
 292     if( trie==NULL || trie->isCompacted ||
 293         (uint32_t)start>0x10ffff || (uint32_t)limit>0x110000 || start>limit
 294     ) {
 295         return FALSE;
 296     }
 297     if(start==limit) {
 298         return TRUE; /* nothing to do */
 299     }
 300
 301     initialValue=trie->data[0];
 302     if(start&UTRIE_MASK) {
 303         UChar32 nextStart;
 304
 305         /* set partial block at [start..following block boundary[ */
 306         block=utrie_getDataBlock(trie, start);
 307         if(block<0) {
 308             return FALSE;
 309         }
 310
 311         nextStart=(start+UTRIE_DATA_BLOCK_LENGTH)&~UTRIE_MASK;
 312         if(nextStart<=limit) {
 313             utrie_fillBlock(trie->data+block, start&UTRIE_MASK, UTRIE_DATA_BLOCK_LENGTH,
 314                             value, initialValue, overwrite);
 315             start=nextStart;
 316         } else {
 317             utrie_fillBlock(trie->data+block, start&UTRIE_MASK, limit&UTRIE_MASK,
 318                             value, initialValue, overwrite);
 319             return TRUE;
 320         }
 321     }
 322
 323     /* number of positions in the last, partial block */
 324     rest=limit&UTRIE_MASK;
 325
 326     /* round down limit to a block boundary */
 327     limit&=~UTRIE_MASK;
 328
 329     /* iterate over all-value blocks */
 330     if(value==initialValue) {
 331         repeatBlock=0;
 332     } else {
 333         repeatBlock=-1;
 334     }
 335     while(start<limit) {
 336         /* get index value */
 337         block=trie->index[start>>UTRIE_SHIFT];
 338         if(block>0) {
 339             /* already allocated, fill in value */
 340             utrie_fillBlock(trie->data+block, 0, UTRIE_DATA_BLOCK_LENGTH, value, initialValue, overwrite);
 341         } else if(trie->data[-block]!=value && (block==0 || overwrite)) {
 342             /* set the repeatBlock instead of the current block 0 or range block */
 343             if(repeatBlock>=0) {
 344                 trie->index[start>>UTRIE_SHIFT]=-repeatBlock;
 345             } else {
 346                 /* create and set and fill the repeatBlock */
 347                 repeatBlock=utrie_getDataBlock(trie, start);
 348                 if(repeatBlock<0) {
 349                     return FALSE;
 350                 }
 351
 352                 /* set the negative block number to indicate that it is a repeat block */
 353                 trie->index[start>>UTRIE_SHIFT]=-repeatBlock;
 354                 utrie_fillBlock(trie->data+repeatBlock, 0, UTRIE_DATA_BLOCK_LENGTH, value, initialValue, TRUE);
 355             }
 356         }
 357
 358         start+=UTRIE_DATA_BLOCK_LENGTH;
 359     }
 360
 361     if(rest>0) {
 362         /* set partial block at [last block boundary..limit[ */
 363         block=utrie_getDataBlock(trie, start);
 364         if(block<0) {
 365             return FALSE;
 366         }
 367
 368         utrie_fillBlock(trie->data+block, 0, rest, value, initialValue, overwrite);
 369     }
 370
 371     return TRUE;
 372 }
 373
 374 static int32_t
 375 _findSameIndexBlock(const int32_t *idx, int32_t indexLength,
 376                     int32_t otherBlock) {
 377     int32_t block, i;
 378
 379     for(block=UTRIE_BMP_INDEX_LENGTH; block<indexLength; block+=UTRIE_SURROGATE_BLOCK_COUNT) {
 380         for(i=0; i<UTRIE_SURROGATE_BLOCK_COUNT; ++i) {
 381             if(idx[block+i]!=idx[otherBlock+i]) {
 382                 break;
 383             }
 384         }
 385         if(i==UTRIE_SURROGATE_BLOCK_COUNT) {
 386             return block;
 387         }
 388     }
 389     return indexLength;
 390 }
 391
 392 /*
 393  * Fold the normalization data for supplementary code points into
 394  * a compact area on top of the BMP-part of the trie index,
 395  * with the lead surrogates indexing this compact area.
 396  *
 397  * Duplicate the index values for lead surrogates:
 398  * From inside the BMP area, where some may be overridden with folded values,
 399  * to just after the BMP area, where they can be retrieved for
 400  * code point lookups.
 401  */
 402 static void
 403 utrie_fold(UNewTrie *trie, UNewTrieGetFoldedValue *getFoldedValue, UErrorCode *pErrorCode) {
 404     int32_t leadIndexes[UTRIE_SURROGATE_BLOCK_COUNT];
 405     int32_t *idx;
 406     uint32_t value;
 407     UChar32 c;
 408     int32_t indexLength, block;
 409 #ifdef UTRIE_DEBUG
 410     int countLeadCUWithData=0;
 411 #endif
 412
 413     idx=trie->index;
 414
 415     /* copy the lead surrogate indexes into a temporary array */
 416     uprv_memcpy(leadIndexes, idx+(0xd800>>UTRIE_SHIFT), 4*UTRIE_SURROGATE_BLOCK_COUNT);
 417
 418     /*
 419      * set all values for lead surrogate code *units* to leadUnitValue
 420      * so that, by default, runtime lookups will find no data for associated
 421      * supplementary code points, unless there is data for such code points
 422      * which will result in a non-zero folding value below that is set for
 423      * the respective lead units
 424      *
 425      * the above saved the indexes for surrogate code *points*
 426      * fill the indexes with simplified code from utrie_setRange32()
 427      */
 428     if(trie->leadUnitValue==trie->data[0]) {
 429         block=0; /* leadUnitValue==initialValue, use all-initial-value block */
 430     } else {
 431         /* create and fill the repeatBlock */
 432         block=utrie_allocDataBlock(trie);
 433         if(block<0) {
 434             /* data table overflow */
 435             *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
 436             return;
 437         }
 438         utrie_fillBlock(trie->data+block, 0, UTRIE_DATA_BLOCK_LENGTH, trie->leadUnitValue, trie->data[0], TRUE);
 439         block=-block; /* negative block number to indicate that it is a repeat block */
 440     }
 441     for(c=(0xd800>>UTRIE_SHIFT); c<(0xdc00>>UTRIE_SHIFT); ++c) {
 442         trie->index[c]=block;
 443     }
 444
 445     /*
 446      * Fold significant index values into the area just after the BMP indexes.
 447      * In case the first lead surrogate has significant data,
 448      * its index block must be used first (in which case the folding is a no-op).
 449      * Later all folded index blocks are moved up one to insert the copied
 450      * lead surrogate indexes.
 451      */
 452     indexLength=UTRIE_BMP_INDEX_LENGTH;
 453
 454     /* search for any index (stage 1) entries for supplementary code points */
 455     for(c=0x10000; c<0x110000;) {
 456         if(idx[c>>UTRIE_SHIFT]!=0) {
 457             /* there is data, treat the full block for a lead surrogate */
 458             c&=~0x3ff;
 459
 460 #ifdef UTRIE_DEBUG
 461             ++countLeadCUWithData;
 462             /* printf("supplementary data for lead surrogate U+%04lx\n", (long)(0xd7c0+(c>>10))); */
 463 #endif
 464
 465             /* is there an identical index block? */
 466             block=_findSameIndexBlock(idx, indexLength, c>>UTRIE_SHIFT);
 467
 468             /*
 469              * get a folded value for [c..c+0x400[ and,
 470              * if different from the value for the lead surrogate code point,
 471              * set it for the lead surrogate code unit
 472              */
 473             value=getFoldedValue(trie, c, block+UTRIE_SURROGATE_BLOCK_COUNT);
 474             if(value!=utrie_get32(trie, U16_LEAD(c), NULL)) {
 475                 if(!utrie_set32(trie, U16_LEAD(c), value)) {
 476                     /* data table overflow */
 477                     *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
 478                     return;
 479                 }
 480
 481                 /* if we did not find an identical index block... */
 482                 if(block==indexLength) {
 483                     /* move the actual index (stage 1) entries from the supplementary position to the new one */
 484                     uprv_memmove(idx+indexLength,
 485                                  idx+(c>>UTRIE_SHIFT),
 486                                  4*UTRIE_SURROGATE_BLOCK_COUNT);
 487                     indexLength+=UTRIE_SURROGATE_BLOCK_COUNT;
 488                 }
 489             }
 490             c+=0x400;
 491         } else {
 492             c+=UTRIE_DATA_BLOCK_LENGTH;
 493         }
 494     }
 495 #ifdef UTRIE_DEBUG
 496     if(countLeadCUWithData>0) {
 497         printf("supplementary data for %d lead surrogates\n", countLeadCUWithData);
 498     }
 499 #endif
 500
 501     /*
 502      * index array overflow?
 503      * This is to guarantee that a folding offset is of the form
 504      * UTRIE_BMP_INDEX_LENGTH+n*UTRIE_SURROGATE_BLOCK_COUNT with n=0..1023.
 505      * If the index is too large, then n>=1024 and more than 10 bits are necessary.
 506      *
 507      * In fact, it can only ever become n==1024 with completely unfoldable data and
 508      * the additional block of duplicated values for lead surrogates.
 509      */
 510     if(indexLength>=UTRIE_MAX_INDEX_LENGTH) {
 511         *pErrorCode=U_INDEX_OUTOFBOUNDS_ERROR;
 512         return;
 513     }
 514
 515     /*
 516      * make space for the lead surrogate index block and
 517      * insert it between the BMP indexes and the folded ones
 518      */
 519     uprv_memmove(idx+UTRIE_BMP_INDEX_LENGTH+UTRIE_SURROGATE_BLOCK_COUNT,
 520                  idx+UTRIE_BMP_INDEX_LENGTH,
 521                  4*(indexLength-UTRIE_BMP_INDEX_LENGTH));
 522     uprv_memcpy(idx+UTRIE_BMP_INDEX_LENGTH,
 523                 leadIndexes,
 524                 4*UTRIE_SURROGATE_BLOCK_COUNT);
 525     indexLength+=UTRIE_SURROGATE_BLOCK_COUNT;
 526
 527 #ifdef UTRIE_DEBUG
 528     printf("trie index count: BMP %ld  all Unicode %ld  folded %ld\n",
 529            UTRIE_BMP_INDEX_LENGTH, (long)UTRIE_MAX_INDEX_LENGTH, indexLength);
 530 #endif
 531
 532     trie->indexLength=indexLength;
 533 }
 534
 535 /*
 536  * Set a value in the trie index map to indicate which data block
 537  * is referenced and which one is not.
 538  * utrie_compact() will remove data blocks that are not used at all.
 539  * Set
 540  * - 0 if it is used
 541  * - -1 if it is not used
 542  */
 543 static void
 544 _findUnusedBlocks(UNewTrie *trie) {
 545     int32_t i;
 546
 547     /* fill the entire map with "not used" */
 548     uprv_memset(trie->map, 0xff, (UTRIE_MAX_BUILD_TIME_DATA_LENGTH>>UTRIE_SHIFT)*4);
 549
 550     /* mark each block that _is_ used with 0 */
 551     for(i=0; i<trie->indexLength; ++i) {
 552         trie->map[ABS(trie->index[i])>>UTRIE_SHIFT]=0;
 553     }
 554
 555     /* never move the all-initial-value block 0 */
 556     trie->map[0]=0;
 557 }
 558
 559 static int32_t
 560 _findSameDataBlock(const uint32_t *data, int32_t dataLength,
 561                    int32_t otherBlock, int32_t step) {
 562     int32_t block;
 563
 564     /* ensure that we do not even partially get past dataLength */
 565     dataLength-=UTRIE_DATA_BLOCK_LENGTH;
 566
 567     for(block=0; block<=dataLength; block+=step) {
 568         if(equal_uint32(data+block, data+otherBlock, UTRIE_DATA_BLOCK_LENGTH)) {
 569             return block;
 570         }
 571     }
 572     return -1;
 573 }
 574
 575 /*
 576  * Compact a folded build-time trie.
 577  *
 578  * The compaction
 579  * - removes blocks that are identical with earlier ones
 580  * - overlaps adjacent blocks as much as possible (if overlap==TRUE)
 581  * - moves blocks in steps of the data granularity
 582  * - moves and overlaps blocks that overlap with multiple values in the overlap region
 583  *
 584  * It does not
 585  * - try to move and overlap blocks that are not already adjacent
 586  */
 587 static void
 588 utrie_compact(UNewTrie *trie, UBool overlap, UErrorCode *pErrorCode) {
 589     int32_t i, start, newStart, overlapStart;
 590
 591     if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
 592         return;
 593     }
 594
 595     /* valid, uncompacted trie? */
 596     if(trie==NULL) {
 597         *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
 598         return;
 599     }
 600     if(trie->isCompacted) {
 601         return; /* nothing left to do */
 602     }
 603
 604     /* compaction */
 605
 606     /* initialize the index map with "block is used/unused" flags */
 607     _findUnusedBlocks(trie);
 608
 609     /* if Latin-1 is preallocated and linear, then do not compact Latin-1 data */
 610     if(trie->isLatin1Linear && UTRIE_SHIFT<=8) {
 611         overlapStart=UTRIE_DATA_BLOCK_LENGTH+256;
 612     } else {
 613         overlapStart=UTRIE_DATA_BLOCK_LENGTH;
 614     }
 615
 616     newStart=UTRIE_DATA_BLOCK_LENGTH;
 617     for(start=newStart; start<trie->dataLength;) {
 618         /*
 619          * start: index of first entry of current block
 620          * newStart: index where the current block is to be moved
 621          *           (right after current end of already-compacted data)
 622          */
 623
 624         /* skip blocks that are not used */
 625         if(trie->map[start>>UTRIE_SHIFT]<0) {
 626             /* advance start to the next block */
 627             start+=UTRIE_DATA_BLOCK_LENGTH;
 628
 629             /* leave newStart with the previous block! */
 630             continue;
 631         }
 632
 633         /* search for an identical block */
 634         if( start>=overlapStart &&
 635             (i=_findSameDataBlock(trie->data, newStart, start,
 636                             overlap ? UTRIE_DATA_GRANULARITY : UTRIE_DATA_BLOCK_LENGTH))
 637              >=0
 638         ) {
 639             /* found an identical block, set the other block's index value for the current block */
 640             trie->map[start>>UTRIE_SHIFT]=i;
 641
 642             /* advance start to the next block */
 643             start+=UTRIE_DATA_BLOCK_LENGTH;
 644
 645             /* leave newStart with the previous block! */
 646             continue;
 647         }
 648
 649         /* see if the beginning of this block can be overlapped with the end of the previous block */
 650         if(overlap && start>=overlapStart) {
 651             /* look for maximum overlap (modulo granularity) with the previous, adjacent block */
 652             for(i=UTRIE_DATA_BLOCK_LENGTH-UTRIE_DATA_GRANULARITY;
 653                 i>0 && !equal_uint32(trie->data+(newStart-i), trie->data+start, i);
 654                 i-=UTRIE_DATA_GRANULARITY) {}
 655         } else {
 656             i=0;
 657         }
 658
 659         if(i>0) {
 660             /* some overlap */
 661             trie->map[start>>UTRIE_SHIFT]=newStart-i;
 662
 663             /* move the non-overlapping indexes to their new positions */
 664             start+=i;
 665             for(i=UTRIE_DATA_BLOCK_LENGTH-i; i>0; --i) {
 666                 trie->data[newStart++]=trie->data[start++];
 667             }
 668         } else if(newStart<start) {
 669             /* no overlap, just move the indexes to their new positions */
 670             trie->map[start>>UTRIE_SHIFT]=newStart;
 671             for(i=UTRIE_DATA_BLOCK_LENGTH; i>0; --i) {
 672                 trie->data[newStart++]=trie->data[start++];
 673             }
 674         } else /* no overlap && newStart==start */ {
 675             trie->map[start>>UTRIE_SHIFT]=start;
 676             newStart+=UTRIE_DATA_BLOCK_LENGTH;
 677             start=newStart;
 678         }
 679     }
 680
 681     /* now adjust the index (stage 1) table */
 682     for(i=0; i<trie->indexLength; ++i) {
 683         trie->index[i]=trie->map[ABS(trie->index[i])>>UTRIE_SHIFT];
 684     }
 685
 686 #ifdef UTRIE_DEBUG
 687     /* we saved some space */
 688     printf("compacting trie: count of 32-bit words %lu->%lu\n",
 689             (long)trie->dataLength, (long)newStart);
 690 #endif
 691
 692     trie->dataLength=newStart;
 693 }
 694
 695 /* serialization ------------------------------------------------------------ */
 696
 697 /*
 698  * Default function for the folding value:
 699  * Just store the offset (16 bits) if there is any non-initial-value entry.
 700  *
 701  * The offset parameter is never 0.
 702  * Returning the offset itself is safe for UTRIE_SHIFT>=5 because
 703  * for UTRIE_SHIFT==5 the maximum index length is UTRIE_MAX_INDEX_LENGTH==0x8800
 704  * which fits into 16-bit trie values;
 705  * for higher UTRIE_SHIFT, UTRIE_MAX_INDEX_LENGTH decreases.
 706  *
 707  * Theoretically, it would be safer for all possible UTRIE_SHIFT including
 708  * those of 4 and lower to return offset>>UTRIE_SURROGATE_BLOCK_BITS
 709  * which would always result in a value of 0x40..0x43f
 710  * (start/end 1k blocks of supplementary Unicode code points).
 711  * However, this would be uglier, and would not work for some existing
 712  * binary data file formats.
 713  *
 714  * Also, we do not plan to change UTRIE_SHIFT because it would change binary
 715  * data file formats, and we would probably not make it smaller because of
 716  * the then even larger BMP index length even for empty tries.
 717  */
 718 static uint32_t U_CALLCONV
 719 defaultGetFoldedValue(UNewTrie *trie, UChar32 start, int32_t offset) {
 720     uint32_t value, initialValue;
 721     UChar32 limit;
 722     UBool inBlockZero;
 723
 724     initialValue=trie->data[0];
 725     limit=start+0x400;
 726     while(start<limit) {
 727         value=utrie_get32(trie, start, &inBlockZero);
 728         if(inBlockZero) {
 729             start+=UTRIE_DATA_BLOCK_LENGTH;
 730         } else if(value!=initialValue) {
 731             return (uint32_t)offset;
 732         } else {
 733             ++start;
 734         }
 735     }
 736     return 0;
 737 }
 738
 739 U_CAPI int32_t U_EXPORT2
 740 utrie_serialize(UNewTrie *trie, void *dt, int32_t capacity,
 741                 UNewTrieGetFoldedValue *getFoldedValue,
 742                 UBool reduceTo16Bits,
 743                 UErrorCode *pErrorCode) {
 744     UTrieHeader *header;
 745     uint32_t *p;
 746     uint16_t *dest16;
 747     int32_t i, length;
 748     uint8_t* data = NULL;
 749
 750     /* argument check */
 751     if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
 752         return 0;
 753     }
 754
 755     if(trie==NULL || capacity<0 || (capacity>0 && dt==NULL)) {
 756         *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
 757         return 0;
 758     }
 759     if(getFoldedValue==NULL) {
 760         getFoldedValue=defaultGetFoldedValue;
 761     }
 762
 763     data = (uint8_t*)dt;
 764     /* fold and compact if necessary, also checks that indexLength is within limits */
 765     if(!trie->isCompacted) {
 766         /* compact once without overlap to improve folding */
 767         utrie_compact(trie, FALSE, pErrorCode);
 768
 769         /* fold the supplementary part of the index array */
 770         utrie_fold(trie, getFoldedValue, pErrorCode);
 771
 772         /* compact again with overlap for minimum data array length */
 773         utrie_compact(trie, TRUE, pErrorCode);
 774
 775         trie->isCompacted=TRUE;
 776         if(U_FAILURE(*pErrorCode)) {
 777             return 0;
 778         }
 779     }
 780
 781     /* is dataLength within limits? */
 782     if( (reduceTo16Bits ? (trie->dataLength+trie->indexLength) : trie->dataLength) >= UTRIE_MAX_DATA_LENGTH) {
 783         *pErrorCode=U_INDEX_OUTOFBOUNDS_ERROR;
 784     }
 785
 786     length=sizeof(UTrieHeader)+2*trie->indexLength;
 787     if(reduceTo16Bits) {
 788         length+=2*trie->dataLength;
 789     } else {
 790         length+=4*trie->dataLength;
 791     }
 792
 793     if(length>capacity) {
 794         return length; /* preflighting */
 795     }
 796
 797 #ifdef UTRIE_DEBUG
 798     printf("**UTrieLengths(serialize)** index:%6ld  data:%6ld  serialized:%6ld\n",
 799            (long)trie->indexLength, (long)trie->dataLength, (long)length);
 800 #endif
 801
 802     /* set the header fields */
 803     header=(UTrieHeader *)data;
 804     data+=sizeof(UTrieHeader);
 805
 806     header->signature=0x54726965; /* "Trie" */
 807     header->options=UTRIE_SHIFT | (UTRIE_INDEX_SHIFT<<UTRIE_OPTIONS_INDEX_SHIFT);
 808
 809     if(!reduceTo16Bits) {
 810         header->options|=UTRIE_OPTIONS_DATA_IS_32_BIT;
 811     }
 812     if(trie->isLatin1Linear) {
 813         header->options|=UTRIE_OPTIONS_LATIN1_IS_LINEAR;
 814     }
 815
 816     header->indexLength=trie->indexLength;
 817     header->dataLength=trie->dataLength;
 818
 819     /* write the index (stage 1) array and the 16/32-bit data (stage 2) array */
 820     if(reduceTo16Bits) {
 821         /* write 16-bit index values shifted right by UTRIE_INDEX_SHIFT, after adding indexLength */
 822         p=(uint32_t *)trie->index;
 823         dest16=(uint16_t *)data;
 824         for(i=trie->indexLength; i>0; --i) {
 825             *dest16++=(uint16_t)((*p++ + trie->indexLength)>>UTRIE_INDEX_SHIFT);
 826         }
 827
 828         /* write 16-bit data values */
 829         p=trie->data;
 830         for(i=trie->dataLength; i>0; --i) {
 831             *dest16++=(uint16_t)*p++;
 832         }
 833     } else {
 834         /* write 16-bit index values shifted right by UTRIE_INDEX_SHIFT */
 835         p=(uint32_t *)trie->index;
 836         dest16=(uint16_t *)data;
 837         for(i=trie->indexLength; i>0; --i) {
 838             *dest16++=(uint16_t)(*p++ >> UTRIE_INDEX_SHIFT);
 839         }
 840
 841         /* write 32-bit data values */
 842         uprv_memcpy(dest16, trie->data, 4*trie->dataLength);
 843     }
 844
 845     return length;
 846 }
 847
 848 /* inverse to defaultGetFoldedValue() */
 849 U_CAPI int32_t U_EXPORT2
 850 utrie_defaultGetFoldingOffset(uint32_t data) {
 851     return (int32_t)data;
 852 }
 853
 854 U_CAPI int32_t U_EXPORT2
 855 utrie_unserialize(UTrie *trie, const void *data, int32_t length, UErrorCode *pErrorCode) {
 856     const UTrieHeader *header;
 857     const uint16_t *p16;
 858     uint32_t options;
 859
 860     if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
 861         return -1;
 862     }
 863
 864     /* enough data for a trie header? */
 865     if(length<(int32_t)sizeof(UTrieHeader)) {
 866         *pErrorCode=U_INVALID_FORMAT_ERROR;
 867         return -1;
 868     }
 869
 870     /* check the signature */
 871     header=(const UTrieHeader *)data;
 872     if(header->signature!=0x54726965) {
 873         *pErrorCode=U_INVALID_FORMAT_ERROR;
 874         return -1;
 875     }
 876
 877     /* get the options and check the shift values */
 878     options=header->options;
 879     if( (options&UTRIE_OPTIONS_SHIFT_MASK)!=UTRIE_SHIFT ||
 880         ((options>>UTRIE_OPTIONS_INDEX_SHIFT)&UTRIE_OPTIONS_SHIFT_MASK)!=UTRIE_INDEX_SHIFT
 881     ) {
 882         *pErrorCode=U_INVALID_FORMAT_ERROR;
 883         return -1;
 884     }
 885     trie->isLatin1Linear= (UBool)((options&UTRIE_OPTIONS_LATIN1_IS_LINEAR)!=0);
 886
 887     /* get the length values */
 888     trie->indexLength=header->indexLength;
 889     trie->dataLength=header->dataLength;
 890
 891     length-=(int32_t)sizeof(UTrieHeader);
 892
 893     /* enough data for the index? */
 894     if(length<2*trie->indexLength) {
 895         *pErrorCode=U_INVALID_FORMAT_ERROR;
 896         return -1;
 897     }
 898     p16=(const uint16_t *)(header+1);
 899     trie->index=p16;
 900     p16+=trie->indexLength;
 901     length-=2*trie->indexLength;
 902
 903     /* get the data */
 904     if(options&UTRIE_OPTIONS_DATA_IS_32_BIT) {
 905         if(length<4*trie->dataLength) {
 906             *pErrorCode=U_INVALID_FORMAT_ERROR;
 907             return -1;
 908         }
 909         trie->data32=(const uint32_t *)p16;
 910         trie->initialValue=trie->data32[0];
 911         length=(int32_t)sizeof(UTrieHeader)+2*trie->indexLength+4*trie->dataLength;
 912     } else {
 913         if(length<2*trie->dataLength) {
 914             *pErrorCode=U_INVALID_FORMAT_ERROR;
 915             return -1;
 916         }
 917
 918         /* the "data16" data is used via the index pointer */
 919         trie->data32=NULL;
 920         trie->initialValue=trie->index[trie->indexLength];
 921         length=(int32_t)sizeof(UTrieHeader)+2*trie->indexLength+2*trie->dataLength;
 922     }
 923
 924     trie->getFoldingOffset=utrie_defaultGetFoldingOffset;
 925
 926     return length;
 927 }
 928
 929 U_CAPI int32_t U_EXPORT2
 930 utrie_unserializeDummy(UTrie *trie,
 931                        void *data, int32_t length,
 932                        uint32_t initialValue, uint32_t leadUnitValue,
 933                        UBool make16BitTrie,
 934                        UErrorCode *pErrorCode) {
 935     uint16_t *p16;
 936     int32_t actualLength, latin1Length, i, limit;
 937     uint16_t block;
 938
 939     if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
 940         return -1;
 941     }
 942
 943     /* calculate the actual size of the dummy trie data */
 944
 945     /* max(Latin-1, block 0) */
 946     latin1Length= 256; /*UTRIE_SHIFT<=8 ? 256 : UTRIE_DATA_BLOCK_LENGTH;*/
 947
 948     trie->indexLength=UTRIE_BMP_INDEX_LENGTH+UTRIE_SURROGATE_BLOCK_COUNT;
 949     trie->dataLength=latin1Length;
 950     if(leadUnitValue!=initialValue) {
 951         trie->dataLength+=UTRIE_DATA_BLOCK_LENGTH;
 952     }
 953
 954     actualLength=trie->indexLength*2;
 955     if(make16BitTrie) {
 956         actualLength+=trie->dataLength*2;
 957     } else {
 958         actualLength+=trie->dataLength*4;
 959     }
 960
 961     /* enough space for the dummy trie? */
 962     if(length<actualLength) {
 963         *pErrorCode=U_BUFFER_OVERFLOW_ERROR;
 964         return actualLength;
 965     }
 966
 967     trie->isLatin1Linear=TRUE;
 968     trie->initialValue=initialValue;
 969
 970     /* fill the index and data arrays */
 971     p16=(uint16_t *)data;
 972     trie->index=p16;
 973
 974     if(make16BitTrie) {
 975         /* indexes to block 0 */
 976         block=(uint16_t)(trie->indexLength>>UTRIE_INDEX_SHIFT);
 977         limit=trie->indexLength;
 978         for(i=0; i<limit; ++i) {
 979             p16[i]=block;
 980         }
 981
 982         if(leadUnitValue!=initialValue) {
 983             /* indexes for lead surrogate code units to the block after Latin-1 */
 984             block+=(uint16_t)(latin1Length>>UTRIE_INDEX_SHIFT);
 985             i=0xd800>>UTRIE_SHIFT;
 986             limit=0xdc00>>UTRIE_SHIFT;
 987             for(; i<limit; ++i) {
 988                 p16[i]=block;
 989             }
 990         }
 991
 992         trie->data32=NULL;
 993
 994         /* Latin-1 data */
 995         p16+=trie->indexLength;
 996         for(i=0; i<latin1Length; ++i) {
 997             p16[i]=(uint16_t)initialValue;
 998         }
 999
1000         /* data for lead surrogate code units */
1001         if(leadUnitValue!=initialValue) {
1002             limit=latin1Length+UTRIE_DATA_BLOCK_LENGTH;
1003             for(/* i=latin1Length */; i<limit; ++i) {
1004                 p16[i]=(uint16_t)leadUnitValue;
1005             }
1006         }
1007     } else {
1008         uint32_t *p32;
1009
1010         /* indexes to block 0 */
1011         uprv_memset(p16, 0, trie->indexLength*2);
1012
1013         if(leadUnitValue!=initialValue) {
1014             /* indexes for lead surrogate code units to the block after Latin-1 */
1015             block=(uint16_t)(latin1Length>>UTRIE_INDEX_SHIFT);
1016             i=0xd800>>UTRIE_SHIFT;
1017             limit=0xdc00>>UTRIE_SHIFT;
1018             for(; i<limit; ++i) {
1019                 p16[i]=block;
1020             }
1021         }
1022
1023         trie->data32=p32=(uint32_t *)(p16+trie->indexLength);
1024
1025         /* Latin-1 data */
1026         for(i=0; i<latin1Length; ++i) {
1027             p32[i]=initialValue;
1028         }
1029
1030         /* data for lead surrogate code units */
1031         if(leadUnitValue!=initialValue) {
1032             limit=latin1Length+UTRIE_DATA_BLOCK_LENGTH;
1033             for(/* i=latin1Length */; i<limit; ++i) {
1034                 p32[i]=leadUnitValue;
1035             }
1036         }
1037     }
1038
1039     trie->getFoldingOffset=utrie_defaultGetFoldingOffset;
1040
1041     return actualLength;
1042 }
1043
1044 /* enumeration -------------------------------------------------------------- */
1045
1046 /* default UTrieEnumValue() returns the input value itself */
1047 static uint32_t U_CALLCONV
1048 enumSameValue(const void * /*context*/, uint32_t value) {
1049     return value;
1050 }
1051
1052 /**
1053  * Enumerate all ranges of code points with the same relevant values.
1054  * The values are transformed from the raw trie entries by the enumValue function.
1055  */
1056 U_CAPI void U_EXPORT2
1057 utrie_enum(const UTrie *trie,
1058            UTrieEnumValue *enumValue, UTrieEnumRange *enumRange, const void *context) {
1059     const uint32_t *data32;
1060     const uint16_t *idx;
1061
1062     uint32_t value, prevValue, initialValue;
1063     UChar32 c, prev;
1064     int32_t l, i, j, block, prevBlock, nullBlock, offset;
1065
1066     /* check arguments */
1067     if(trie==NULL || trie->index==NULL || enumRange==NULL) {
1068         return;
1069     }
1070     if(enumValue==NULL) {
1071         enumValue=enumSameValue;
1072     }
1073
1074     idx=trie->index;
1075     data32=trie->data32;
1076
1077     /* get the enumeration value that corresponds to an initial-value trie data entry */
1078     initialValue=enumValue(context, trie->initialValue);
1079
1080     if(data32==NULL) {
1081         nullBlock=trie->indexLength;
1082     } else {
1083         nullBlock=0;
1084     }
1085
1086     /* set variables for previous range */
1087     prevBlock=nullBlock;
1088     prev=0;
1089     prevValue=initialValue;
1090
1091     /* enumerate BMP - the main loop enumerates data blocks */
1092     for(i=0, c=0; c<=0xffff; ++i) {
1093         if(c==0xd800) {
1094             /* skip lead surrogate code _units_, go to lead surr. code _points_ */
1095             i=UTRIE_BMP_INDEX_LENGTH;
1096         } else if(c==0xdc00) {
1097             /* go back to regular BMP code points */
1098             i=c>>UTRIE_SHIFT;
1099         }
1100
1101         block=idx[i]<<UTRIE_INDEX_SHIFT;
1102         if(block==prevBlock) {
1103             /* the block is the same as the previous one, and filled with value */
1104             c+=UTRIE_DATA_BLOCK_LENGTH;
1105         } else if(block==nullBlock) {
1106             /* this is the all-initial-value block */
1107             if(prevValue!=initialValue) {
1108                 if(prev<c) {
1109                     if(!enumRange(context, prev, c, prevValue)) {
1110                         return;
1111                     }
1112                 }
1113                 prevBlock=nullBlock;
1114                 prev=c;
1115                 prevValue=initialValue;
1116             }
1117             c+=UTRIE_DATA_BLOCK_LENGTH;
1118         } else {
1119             prevBlock=block;
1120             for(j=0; j<UTRIE_DATA_BLOCK_LENGTH; ++j) {
1121                 value=enumValue(context, data32!=NULL ? data32[block+j] : idx[block+j]);
1122                 if(value!=prevValue) {
1123                     if(prev<c) {
1124                         if(!enumRange(context, prev, c, prevValue)) {
1125                             return;
1126                         }
1127                     }
1128                     if(j>0) {
1129                         /* the block is not filled with all the same value */
1130                         prevBlock=-1;
1131                     }
1132                     prev=c;
1133                     prevValue=value;
1134                 }
1135                 ++c;
1136             }
1137         }
1138     }
1139
1140     /* enumerate supplementary code points */
1141     for(l=0xd800; l<0xdc00;) {
1142         /* lead surrogate access */
1143         offset=idx[l>>UTRIE_SHIFT]<<UTRIE_INDEX_SHIFT;
1144         if(offset==nullBlock) {
1145             /* no entries for a whole block of lead surrogates */
1146             if(prevValue!=initialValue) {
1147                 if(prev<c) {
1148                     if(!enumRange(context, prev, c, prevValue)) {
1149                         return;
1150                     }
1151                 }
1152                 prevBlock=nullBlock;
1153                 prev=c;
1154                 prevValue=initialValue;
1155             }
1156
1157             l+=UTRIE_DATA_BLOCK_LENGTH;
1158             c+=UTRIE_DATA_BLOCK_LENGTH<<10;
1159             continue;
1160         }
1161
1162         value= data32!=NULL ? data32[offset+(l&UTRIE_MASK)] : idx[offset+(l&UTRIE_MASK)];
1163
1164         /* enumerate trail surrogates for this lead surrogate */
1165         offset=trie->getFoldingOffset(value);
1166         if(offset<=0) {
1167             /* no data for this lead surrogate */
1168             if(prevValue!=initialValue) {
1169                 if(prev<c) {
1170                     if(!enumRange(context, prev, c, prevValue)) {
1171                         return;
1172                     }
1173                 }
1174                 prevBlock=nullBlock;
1175                 prev=c;
1176                 prevValue=initialValue;
1177             }
1178
1179             /* nothing else to do for the supplementary code points for this lead surrogate */
1180             c+=0x400;
1181         } else {
1182             /* enumerate code points for this lead surrogate */
1183             i=offset;
1184             offset+=UTRIE_SURROGATE_BLOCK_COUNT;
1185             do {
1186                 /* copy of most of the body of the BMP loop */
1187                 block=idx[i]<<UTRIE_INDEX_SHIFT;
1188                 if(block==prevBlock) {
1189                     /* the block is the same as the previous one, and filled with value */
1190                     c+=UTRIE_DATA_BLOCK_LENGTH;
1191                 } else if(block==nullBlock) {
1192                     /* this is the all-initial-value block */
1193                     if(prevValue!=initialValue) {
1194                         if(prev<c) {
1195                             if(!enumRange(context, prev, c, prevValue)) {
1196                                 return;
1197                             }
1198                         }
1199                         prevBlock=nullBlock;
1200                         prev=c;
1201                         prevValue=initialValue;
1202                     }
1203                     c+=UTRIE_DATA_BLOCK_LENGTH;
1204                 } else {
1205                     prevBlock=block;
1206                     for(j=0; j<UTRIE_DATA_BLOCK_LENGTH; ++j) {
1207                         value=enumValue(context, data32!=NULL ? data32[block+j] : idx[block+j]);
1208                         if(value!=prevValue) {
1209                             if(prev<c) {
1210                                 if(!enumRange(context, prev, c, prevValue)) {
1211                                     return;
1212                                 }
1213                             }
1214                             if(j>0) {
1215                                 /* the block is not filled with all the same value */
1216                                 prevBlock=-1;
1217                             }
1218                             prev=c;
1219                             prevValue=value;
1220                         }
1221                         ++c;
1222                     }
1223                 }
1224             } while(++i<offset);
1225         }
1226
1227         ++l;
1228     }
1229
1230     /* deliver last range */
1231     enumRange(context, prev, c, prevValue);
1232 }