• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // © 2016 and later: Unicode, Inc. and others.
2 // License & terms of use: http://www.unicode.org/copyright.html
3 /*
4 ******************************************************************************
5 *
6 *   Copyright (C) 2001-2014, International Business Machines
7 *   Corporation and others.  All Rights Reserved.
8 *
9 ******************************************************************************
10 *   file name:  utrie2_builder.cpp
11 *   encoding:   UTF-8
12 *   tab size:   8 (not used)
13 *   indentation:4
14 *
15 *   created on: 2008sep26 (split off from utrie2.c)
16 *   created by: Markus W. Scherer
17 *
18 *   This is a common implementation of a Unicode trie.
19 *   It is a kind of compressed, serializable table of 16- or 32-bit values associated with
20 *   Unicode code points (0..0x10ffff).
21 *   This is the second common version of a Unicode trie (hence the name UTrie2).
22 *   See utrie2.h for a comparison.
23 *
24 *   This file contains only the builder code.
25 *   See utrie2.c for the runtime and enumeration code.
26 */
27 // #define UTRIE2_DEBUG
28 #ifdef UTRIE2_DEBUG
29 #   include <stdio.h>
30 #endif
31 // #define UCPTRIE_DEBUG
32 
33 #include "unicode/utypes.h"
34 #ifdef UCPTRIE_DEBUG
35 #include "unicode/ucptrie.h"
36 #include "unicode/umutablecptrie.h"
37 #include "ucptrie_impl.h"
38 #endif
39 #include "cmemory.h"
40 #include "utrie2.h"
41 #include "utrie2_impl.h"
42 
43 #include "utrie.h"  // for utrie2_fromUTrie()
44 
45 /* Implementation notes ----------------------------------------------------- */
46 
47 /*
48  * The UTRIE2_SHIFT_1, UTRIE2_SHIFT_2, UTRIE2_INDEX_SHIFT and other values
49  * have been chosen to minimize trie sizes overall.
50  * Most of the code is flexible enough to work with a range of values,
51  * within certain limits.
52  *
53  * Exception: Support for separate values for lead surrogate code _units_
54  * vs. code _points_ was added after the constants were fixed,
55  * and has not been tested nor particularly designed for different constant values.
56  * (Especially the utrie2_enum() code that jumps to the special LSCP index-2
57  * part and back.)
58  *
59  * Requires UTRIE2_SHIFT_2<=6. Otherwise 0xc0 which is the top of the ASCII-linear data
60  * including the bad-UTF-8-data block is not a multiple of UTRIE2_DATA_BLOCK_LENGTH
61  * and map[block>>UTRIE2_SHIFT_2] (used in reference counting and compaction
62  * remapping) stops working.
63  *
64  * Requires UTRIE2_SHIFT_1>=10 because utrie2_enumForLeadSurrogate()
65  * assumes that a single index-2 block is used for 0x400 code points
66  * corresponding to one lead surrogate.
67  *
68  * Requires UTRIE2_SHIFT_1<=16. Otherwise one single index-2 block contains
69  * more than one Unicode plane, and the split of the index-2 table into a BMP
70  * part and a supplementary part, with a gap in between, would not work.
71  *
72  * Requires UTRIE2_INDEX_SHIFT>=1 not because of the code but because
73  * there is data with more than 64k distinct values,
74  * for example for Unihan collation with a separate collation weight per
75  * Han character.
76  */
77 
78 /* Building a trie ----------------------------------------------------------*/
79 
80 enum {
81     /** The null index-2 block, following the gap in the index-2 table. */
82     UNEWTRIE2_INDEX_2_NULL_OFFSET=UNEWTRIE2_INDEX_GAP_OFFSET+UNEWTRIE2_INDEX_GAP_LENGTH,
83 
84     /** The start of allocated index-2 blocks. */
85     UNEWTRIE2_INDEX_2_START_OFFSET=UNEWTRIE2_INDEX_2_NULL_OFFSET+UTRIE2_INDEX_2_BLOCK_LENGTH,
86 
87     /**
88      * The null data block.
89      * Length 64=0x40 even if UTRIE2_DATA_BLOCK_LENGTH is smaller,
90      * to work with 6-bit trail bytes from 2-byte UTF-8.
91      */
92     UNEWTRIE2_DATA_NULL_OFFSET=UTRIE2_DATA_START_OFFSET,
93 
94     /** The start of allocated data blocks. */
95     UNEWTRIE2_DATA_START_OFFSET=UNEWTRIE2_DATA_NULL_OFFSET+0x40,
96 
97     /**
98      * The start of data blocks for U+0800 and above.
99      * Below, compaction uses a block length of 64 for 2-byte UTF-8.
100      * From here on, compaction uses UTRIE2_DATA_BLOCK_LENGTH.
101      * Data values for 0x780 code points beyond ASCII.
102      */
103     UNEWTRIE2_DATA_0800_OFFSET=UNEWTRIE2_DATA_START_OFFSET+0x780
104 };
105 
106 /* Start with allocation of 16k data entries. */
107 #define UNEWTRIE2_INITIAL_DATA_LENGTH ((int32_t)1<<14)
108 
109 /* Grow about 8x each time. */
110 #define UNEWTRIE2_MEDIUM_DATA_LENGTH ((int32_t)1<<17)
111 
112 static int32_t
113 allocIndex2Block(UNewTrie2 *trie);
114 
115 U_CAPI UTrie2 * U_EXPORT2
utrie2_open(uint32_t initialValue,uint32_t errorValue,UErrorCode * pErrorCode)116 utrie2_open(uint32_t initialValue, uint32_t errorValue, UErrorCode *pErrorCode) {
117     UTrie2 *trie;
118     UNewTrie2 *newTrie;
119     uint32_t *data;
120     int32_t i, j;
121 
122     if(U_FAILURE(*pErrorCode)) {
123         return NULL;
124     }
125 
126     trie=(UTrie2 *)uprv_malloc(sizeof(UTrie2));
127     newTrie=(UNewTrie2 *)uprv_malloc(sizeof(UNewTrie2));
128     data=(uint32_t *)uprv_malloc(UNEWTRIE2_INITIAL_DATA_LENGTH*4);
129     if(trie==NULL || newTrie==NULL || data==NULL) {
130         uprv_free(trie);
131         uprv_free(newTrie);
132         uprv_free(data);
133         *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
134         return 0;
135     }
136 
137     uprv_memset(trie, 0, sizeof(UTrie2));
138     trie->initialValue=initialValue;
139     trie->errorValue=errorValue;
140     trie->highStart=0x110000;
141     trie->newTrie=newTrie;
142 #ifdef UTRIE2_DEBUG
143     trie->name="open";
144 #endif
145 
146     newTrie->data=data;
147 #ifdef UCPTRIE_DEBUG
148     newTrie->t3=umutablecptrie_open(initialValue, errorValue, pErrorCode);
149 #endif
150     newTrie->dataCapacity=UNEWTRIE2_INITIAL_DATA_LENGTH;
151     newTrie->initialValue=initialValue;
152     newTrie->errorValue=errorValue;
153     newTrie->highStart=0x110000;
154     newTrie->firstFreeBlock=0;  /* no free block in the list */
155     newTrie->isCompacted=FALSE;
156 
157     /*
158      * preallocate and reset
159      * - ASCII
160      * - the bad-UTF-8-data block
161      * - the null data block
162      */
163     for(i=0; i<0x80; ++i) {
164         newTrie->data[i]=initialValue;
165     }
166     for(; i<0xc0; ++i) {
167         newTrie->data[i]=errorValue;
168     }
169     for(i=UNEWTRIE2_DATA_NULL_OFFSET; i<UNEWTRIE2_DATA_START_OFFSET; ++i) {
170         newTrie->data[i]=initialValue;
171     }
172     newTrie->dataNullOffset=UNEWTRIE2_DATA_NULL_OFFSET;
173     newTrie->dataLength=UNEWTRIE2_DATA_START_OFFSET;
174 
175     /* set the index-2 indexes for the 2=0x80>>UTRIE2_SHIFT_2 ASCII data blocks */
176     for(i=0, j=0; j<0x80; ++i, j+=UTRIE2_DATA_BLOCK_LENGTH) {
177         newTrie->index2[i]=j;
178         newTrie->map[i]=1;
179     }
180     /* reference counts for the bad-UTF-8-data block */
181     for(; j<0xc0; ++i, j+=UTRIE2_DATA_BLOCK_LENGTH) {
182         newTrie->map[i]=0;
183     }
184     /*
185      * Reference counts for the null data block: all blocks except for the ASCII blocks.
186      * Plus 1 so that we don't drop this block during compaction.
187      * Plus as many as needed for lead surrogate code points.
188      */
189     /* i==newTrie->dataNullOffset */
190     newTrie->map[i++]=
191         (0x110000>>UTRIE2_SHIFT_2)-
192         (0x80>>UTRIE2_SHIFT_2)+
193         1+
194         UTRIE2_LSCP_INDEX_2_LENGTH;
195     j+=UTRIE2_DATA_BLOCK_LENGTH;
196     for(; j<UNEWTRIE2_DATA_START_OFFSET; ++i, j+=UTRIE2_DATA_BLOCK_LENGTH) {
197         newTrie->map[i]=0;
198     }
199 
200     /*
201      * set the remaining indexes in the BMP index-2 block
202      * to the null data block
203      */
204     for(i=0x80>>UTRIE2_SHIFT_2; i<UTRIE2_INDEX_2_BMP_LENGTH; ++i) {
205         newTrie->index2[i]=UNEWTRIE2_DATA_NULL_OFFSET;
206     }
207 
208     /*
209      * Fill the index gap with impossible values so that compaction
210      * does not overlap other index-2 blocks with the gap.
211      */
212     for(i=0; i<UNEWTRIE2_INDEX_GAP_LENGTH; ++i) {
213         newTrie->index2[UNEWTRIE2_INDEX_GAP_OFFSET+i]=-1;
214     }
215 
216     /* set the indexes in the null index-2 block */
217     for(i=0; i<UTRIE2_INDEX_2_BLOCK_LENGTH; ++i) {
218         newTrie->index2[UNEWTRIE2_INDEX_2_NULL_OFFSET+i]=UNEWTRIE2_DATA_NULL_OFFSET;
219     }
220     newTrie->index2NullOffset=UNEWTRIE2_INDEX_2_NULL_OFFSET;
221     newTrie->index2Length=UNEWTRIE2_INDEX_2_START_OFFSET;
222 
223     /* set the index-1 indexes for the linear index-2 block */
224     for(i=0, j=0;
225         i<UTRIE2_OMITTED_BMP_INDEX_1_LENGTH;
226         ++i, j+=UTRIE2_INDEX_2_BLOCK_LENGTH
227     ) {
228         newTrie->index1[i]=j;
229     }
230 
231     /* set the remaining index-1 indexes to the null index-2 block */
232     for(; i<UNEWTRIE2_INDEX_1_LENGTH; ++i) {
233         newTrie->index1[i]=UNEWTRIE2_INDEX_2_NULL_OFFSET;
234     }
235 
236     /*
237      * Preallocate and reset data for U+0080..U+07ff,
238      * for 2-byte UTF-8 which will be compacted in 64-blocks
239      * even if UTRIE2_DATA_BLOCK_LENGTH is smaller.
240      */
241     for(i=0x80; i<0x800; i+=UTRIE2_DATA_BLOCK_LENGTH) {
242         utrie2_set32(trie, i, initialValue, pErrorCode);
243     }
244 
245     return trie;
246 }
247 
248 static UNewTrie2 *
cloneBuilder(const UNewTrie2 * other)249 cloneBuilder(const UNewTrie2 *other) {
250     UNewTrie2 *trie;
251 
252     trie=(UNewTrie2 *)uprv_malloc(sizeof(UNewTrie2));
253     if(trie==NULL) {
254         return NULL;
255     }
256 
257     trie->data=(uint32_t *)uprv_malloc(other->dataCapacity*4);
258     if(trie->data==NULL) {
259         uprv_free(trie);
260         return NULL;
261     }
262 #ifdef UCPTRIE_DEBUG
263     if(other->t3==nullptr) {
264         trie->t3=nullptr;
265     } else {
266         UErrorCode errorCode=U_ZERO_ERROR;
267         trie->t3=umutablecptrie_clone(other->t3, &errorCode);
268     }
269 #endif
270     trie->dataCapacity=other->dataCapacity;
271 
272     /* clone data */
273     uprv_memcpy(trie->index1, other->index1, sizeof(trie->index1));
274     uprv_memcpy(trie->index2, other->index2, (size_t)other->index2Length*4);
275     trie->index2NullOffset=other->index2NullOffset;
276     trie->index2Length=other->index2Length;
277 
278     uprv_memcpy(trie->data, other->data, (size_t)other->dataLength*4);
279     trie->dataNullOffset=other->dataNullOffset;
280     trie->dataLength=other->dataLength;
281 
282     /* reference counters */
283     if(other->isCompacted) {
284         trie->firstFreeBlock=0;
285     } else {
286         uprv_memcpy(trie->map, other->map, ((size_t)other->dataLength>>UTRIE2_SHIFT_2)*4);
287         trie->firstFreeBlock=other->firstFreeBlock;
288     }
289 
290     trie->initialValue=other->initialValue;
291     trie->errorValue=other->errorValue;
292     trie->highStart=other->highStart;
293     trie->isCompacted=other->isCompacted;
294 
295     return trie;
296 }
297 
298 U_CAPI UTrie2 * U_EXPORT2
utrie2_clone(const UTrie2 * other,UErrorCode * pErrorCode)299 utrie2_clone(const UTrie2 *other, UErrorCode *pErrorCode) {
300     UTrie2 *trie;
301 
302     if(U_FAILURE(*pErrorCode)) {
303         return NULL;
304     }
305     if(other==NULL || (other->memory==NULL && other->newTrie==NULL)) {
306         *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
307         return NULL;
308     }
309 
310     trie=(UTrie2 *)uprv_malloc(sizeof(UTrie2));
311     if(trie==NULL) {
312         return NULL;
313     }
314     uprv_memcpy(trie, other, sizeof(UTrie2));
315 
316     if(other->memory!=NULL) {
317         trie->memory=uprv_malloc(other->length);
318         if(trie->memory!=NULL) {
319             trie->isMemoryOwned=TRUE;
320             uprv_memcpy(trie->memory, other->memory, other->length);
321 
322             /* make the clone's pointers point to its own memory */
323             trie->index=(uint16_t *)trie->memory+(other->index-(uint16_t *)other->memory);
324             if(other->data16!=NULL) {
325                 trie->data16=(uint16_t *)trie->memory+(other->data16-(uint16_t *)other->memory);
326             }
327             if(other->data32!=NULL) {
328                 trie->data32=(uint32_t *)trie->memory+(other->data32-(uint32_t *)other->memory);
329             }
330         }
331     } else /* other->newTrie!=NULL */ {
332         trie->newTrie=cloneBuilder(other->newTrie);
333     }
334 
335     if(trie->memory==NULL && trie->newTrie==NULL) {
336         uprv_free(trie);
337         trie=NULL;
338     }
339     return trie;
340 }
341 
342 typedef struct NewTrieAndStatus {
343     UTrie2 *trie;
344     UErrorCode errorCode;
345     UBool exclusiveLimit;  /* rather than inclusive range end */
346 } NewTrieAndStatus;
347 
348 static UBool U_CALLCONV
copyEnumRange(const void * context,UChar32 start,UChar32 end,uint32_t value)349 copyEnumRange(const void *context, UChar32 start, UChar32 end, uint32_t value) {
350     NewTrieAndStatus *nt=(NewTrieAndStatus *)context;
351     if(value!=nt->trie->initialValue) {
352         if(nt->exclusiveLimit) {
353             --end;
354         }
355         if(start==end) {
356             utrie2_set32(nt->trie, start, value, &nt->errorCode);
357         } else {
358             utrie2_setRange32(nt->trie, start, end, value, TRUE, &nt->errorCode);
359         }
360         return U_SUCCESS(nt->errorCode);
361     } else {
362         return TRUE;
363     }
364 }
365 
366 #ifdef UTRIE2_DEBUG
countInitial(const UTrie2 * trie)367 static long countInitial(const UTrie2 *trie) {
368     uint32_t initialValue=trie->initialValue;
369     int32_t length=trie->dataLength;
370     long count=0;
371     if(trie->data16!=nullptr) {
372         for(int32_t i=0; i<length; ++i) {
373             if(trie->data16[i]==initialValue) { ++count; }
374         }
375     } else {
376         for(int32_t i=0; i<length; ++i) {
377             if(trie->data32[i]==initialValue) { ++count; }
378         }
379     }
380     return count;
381 }
382 
383 static void
utrie_printLengths(const UTrie * trie)384 utrie_printLengths(const UTrie *trie) {
385     long indexLength=trie->indexLength;
386     long dataLength=(long)trie->dataLength;
387     long totalLength=(long)sizeof(UTrieHeader)+indexLength*2+dataLength*(trie->data32!=NULL ? 4 : 2);
388     printf("**UTrieLengths** index:%6ld  data:%6ld  serialized:%6ld\n",
389            indexLength, dataLength, totalLength);
390 }
391 
392 static void
utrie2_printLengths(const UTrie2 * trie,const char * which)393 utrie2_printLengths(const UTrie2 *trie, const char *which) {
394     long indexLength=trie->indexLength;
395     long dataLength=(long)trie->dataLength;
396     long totalLength=(long)sizeof(UTrie2Header)+indexLength*2+dataLength*(trie->data32!=NULL ? 4 : 2);
397     printf("**UTrie2Lengths(%s %s)** index:%6ld  data:%6ld  countInitial:%6ld  serialized:%6ld\n",
398            which, trie->name, indexLength, dataLength, countInitial(trie), totalLength);
399 }
400 #endif
401 
402 U_CAPI UTrie2 * U_EXPORT2
utrie2_cloneAsThawed(const UTrie2 * other,UErrorCode * pErrorCode)403 utrie2_cloneAsThawed(const UTrie2 *other, UErrorCode *pErrorCode) {
404     NewTrieAndStatus context;
405     UChar lead;
406 
407     if(U_FAILURE(*pErrorCode)) {
408         return NULL;
409     }
410     if(other==NULL || (other->memory==NULL && other->newTrie==NULL)) {
411         *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
412         return NULL;
413     }
414     if(other->newTrie!=NULL && !other->newTrie->isCompacted) {
415         return utrie2_clone(other, pErrorCode);  /* clone an unfrozen trie */
416     }
417 
418     /* Clone the frozen trie by enumerating it and building a new one. */
419     context.trie=utrie2_open(other->initialValue, other->errorValue, pErrorCode);
420     if(U_FAILURE(*pErrorCode)) {
421         return NULL;
422     }
423     context.exclusiveLimit=FALSE;
424     context.errorCode=*pErrorCode;
425     utrie2_enum(other, NULL, copyEnumRange, &context);
426     *pErrorCode=context.errorCode;
427     for(lead=0xd800; lead<0xdc00; ++lead) {
428         uint32_t value;
429         if(other->data32==NULL) {
430             value=UTRIE2_GET16_FROM_U16_SINGLE_LEAD(other, lead);
431         } else {
432             value=UTRIE2_GET32_FROM_U16_SINGLE_LEAD(other, lead);
433         }
434         if(value!=other->initialValue) {
435             utrie2_set32ForLeadSurrogateCodeUnit(context.trie, lead, value, pErrorCode);
436         }
437     }
438     if(U_FAILURE(*pErrorCode)) {
439         utrie2_close(context.trie);
440         context.trie=NULL;
441     }
442     return context.trie;
443 }
444 
445 /* Almost the same as utrie2_cloneAsThawed() but copies a UTrie and freezes the clone. */
446 U_CAPI UTrie2 * U_EXPORT2
utrie2_fromUTrie(const UTrie * trie1,uint32_t errorValue,UErrorCode * pErrorCode)447 utrie2_fromUTrie(const UTrie *trie1, uint32_t errorValue, UErrorCode *pErrorCode) {
448     NewTrieAndStatus context;
449     UChar lead;
450 
451     if(U_FAILURE(*pErrorCode)) {
452         return NULL;
453     }
454     if(trie1==NULL) {
455         *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
456         return NULL;
457     }
458     context.trie=utrie2_open(trie1->initialValue, errorValue, pErrorCode);
459     if(U_FAILURE(*pErrorCode)) {
460         return NULL;
461     }
462     context.exclusiveLimit=TRUE;
463     context.errorCode=*pErrorCode;
464     utrie_enum(trie1, NULL, copyEnumRange, &context);
465     *pErrorCode=context.errorCode;
466     for(lead=0xd800; lead<0xdc00; ++lead) {
467         uint32_t value;
468         if(trie1->data32==NULL) {
469             value=UTRIE_GET16_FROM_LEAD(trie1, lead);
470         } else {
471             value=UTRIE_GET32_FROM_LEAD(trie1, lead);
472         }
473         if(value!=trie1->initialValue) {
474             utrie2_set32ForLeadSurrogateCodeUnit(context.trie, lead, value, pErrorCode);
475         }
476     }
477     if(U_SUCCESS(*pErrorCode)) {
478         utrie2_freeze(context.trie,
479                       trie1->data32!=NULL ? UTRIE2_32_VALUE_BITS : UTRIE2_16_VALUE_BITS,
480                       pErrorCode);
481     }
482 #ifdef UTRIE2_DEBUG
483     if(U_SUCCESS(*pErrorCode)) {
484         utrie_printLengths(trie1);
485         utrie2_printLengths(context.trie, "fromUTrie");
486     }
487 #endif
488     if(U_FAILURE(*pErrorCode)) {
489         utrie2_close(context.trie);
490         context.trie=NULL;
491     }
492     return context.trie;
493 }
494 
495 static inline UBool
isInNullBlock(UNewTrie2 * trie,UChar32 c,UBool forLSCP)496 isInNullBlock(UNewTrie2 *trie, UChar32 c, UBool forLSCP) {
497     int32_t i2, block;
498 
499     if(U_IS_LEAD(c) && forLSCP) {
500         i2=(UTRIE2_LSCP_INDEX_2_OFFSET-(0xd800>>UTRIE2_SHIFT_2))+
501             (c>>UTRIE2_SHIFT_2);
502     } else {
503         i2=trie->index1[c>>UTRIE2_SHIFT_1]+
504             ((c>>UTRIE2_SHIFT_2)&UTRIE2_INDEX_2_MASK);
505     }
506     block=trie->index2[i2];
507     return (UBool)(block==trie->dataNullOffset);
508 }
509 
510 static int32_t
allocIndex2Block(UNewTrie2 * trie)511 allocIndex2Block(UNewTrie2 *trie) {
512     int32_t newBlock, newTop;
513 
514     newBlock=trie->index2Length;
515     newTop=newBlock+UTRIE2_INDEX_2_BLOCK_LENGTH;
516     if(newTop>UPRV_LENGTHOF(trie->index2)) {
517         /*
518          * Should never occur.
519          * Either UTRIE2_MAX_BUILD_TIME_INDEX_LENGTH is incorrect,
520          * or the code writes more values than should be possible.
521          */
522         return -1;
523     }
524     trie->index2Length=newTop;
525     uprv_memcpy(trie->index2+newBlock, trie->index2+trie->index2NullOffset, UTRIE2_INDEX_2_BLOCK_LENGTH*4);
526     return newBlock;
527 }
528 
529 static int32_t
getIndex2Block(UNewTrie2 * trie,UChar32 c,UBool forLSCP)530 getIndex2Block(UNewTrie2 *trie, UChar32 c, UBool forLSCP) {
531     int32_t i1, i2;
532 
533     if(U_IS_LEAD(c) && forLSCP) {
534         return UTRIE2_LSCP_INDEX_2_OFFSET;
535     }
536 
537     i1=c>>UTRIE2_SHIFT_1;
538     i2=trie->index1[i1];
539     if(i2==trie->index2NullOffset) {
540         i2=allocIndex2Block(trie);
541         if(i2<0) {
542             return -1;  /* program error */
543         }
544         trie->index1[i1]=i2;
545     }
546     return i2;
547 }
548 
549 static int32_t
allocDataBlock(UNewTrie2 * trie,int32_t copyBlock)550 allocDataBlock(UNewTrie2 *trie, int32_t copyBlock) {
551     int32_t newBlock, newTop;
552 
553     if(trie->firstFreeBlock!=0) {
554         /* get the first free block */
555         newBlock=trie->firstFreeBlock;
556         trie->firstFreeBlock=-trie->map[newBlock>>UTRIE2_SHIFT_2];
557     } else {
558         /* get a new block from the high end */
559         newBlock=trie->dataLength;
560         newTop=newBlock+UTRIE2_DATA_BLOCK_LENGTH;
561         if(newTop>trie->dataCapacity) {
562             /* out of memory in the data array */
563             int32_t capacity;
564             uint32_t *data;
565 
566             if(trie->dataCapacity<UNEWTRIE2_MEDIUM_DATA_LENGTH) {
567                 capacity=UNEWTRIE2_MEDIUM_DATA_LENGTH;
568             } else if(trie->dataCapacity<UNEWTRIE2_MAX_DATA_LENGTH) {
569                 capacity=UNEWTRIE2_MAX_DATA_LENGTH;
570             } else {
571                 /*
572                  * Should never occur.
573                  * Either UNEWTRIE2_MAX_DATA_LENGTH is incorrect,
574                  * or the code writes more values than should be possible.
575                  */
576                 return -1;
577             }
578             data=(uint32_t *)uprv_malloc(capacity*4);
579             if(data==NULL) {
580                 return -1;
581             }
582             uprv_memcpy(data, trie->data, (size_t)trie->dataLength*4);
583             uprv_free(trie->data);
584             trie->data=data;
585             trie->dataCapacity=capacity;
586         }
587         trie->dataLength=newTop;
588     }
589     uprv_memcpy(trie->data+newBlock, trie->data+copyBlock, UTRIE2_DATA_BLOCK_LENGTH*4);
590     trie->map[newBlock>>UTRIE2_SHIFT_2]=0;
591     return newBlock;
592 }
593 
594 /* call when the block's reference counter reaches 0 */
595 static void
releaseDataBlock(UNewTrie2 * trie,int32_t block)596 releaseDataBlock(UNewTrie2 *trie, int32_t block) {
597     /* put this block at the front of the free-block chain */
598     trie->map[block>>UTRIE2_SHIFT_2]=-trie->firstFreeBlock;
599     trie->firstFreeBlock=block;
600 }
601 
602 static inline UBool
isWritableBlock(UNewTrie2 * trie,int32_t block)603 isWritableBlock(UNewTrie2 *trie, int32_t block) {
604     return (UBool)(block!=trie->dataNullOffset && 1==trie->map[block>>UTRIE2_SHIFT_2]);
605 }
606 
607 static inline void
setIndex2Entry(UNewTrie2 * trie,int32_t i2,int32_t block)608 setIndex2Entry(UNewTrie2 *trie, int32_t i2, int32_t block) {
609     int32_t oldBlock;
610     ++trie->map[block>>UTRIE2_SHIFT_2];  /* increment first, in case block==oldBlock! */
611     oldBlock=trie->index2[i2];
612     if(0 == --trie->map[oldBlock>>UTRIE2_SHIFT_2]) {
613         releaseDataBlock(trie, oldBlock);
614     }
615     trie->index2[i2]=block;
616 }
617 
618 /**
619  * No error checking for illegal arguments.
620  *
621  * @return -1 if no new data block available (out of memory in data array)
622  * @internal
623  */
624 static int32_t
getDataBlock(UNewTrie2 * trie,UChar32 c,UBool forLSCP)625 getDataBlock(UNewTrie2 *trie, UChar32 c, UBool forLSCP) {
626     int32_t i2, oldBlock, newBlock;
627 
628     i2=getIndex2Block(trie, c, forLSCP);
629     if(i2<0) {
630         return -1;  /* program error */
631     }
632 
633     i2+=(c>>UTRIE2_SHIFT_2)&UTRIE2_INDEX_2_MASK;
634     oldBlock=trie->index2[i2];
635     if(isWritableBlock(trie, oldBlock)) {
636         return oldBlock;
637     }
638 
639     /* allocate a new data block */
640     newBlock=allocDataBlock(trie, oldBlock);
641     if(newBlock<0) {
642         /* out of memory in the data array */
643         return -1;
644     }
645     setIndex2Entry(trie, i2, newBlock);
646     return newBlock;
647 }
648 
649 /**
650  * @return TRUE if the value was successfully set
651  */
652 static void
set32(UNewTrie2 * trie,UChar32 c,UBool forLSCP,uint32_t value,UErrorCode * pErrorCode)653 set32(UNewTrie2 *trie,
654       UChar32 c, UBool forLSCP, uint32_t value,
655       UErrorCode *pErrorCode) {
656     int32_t block;
657 
658     if(trie==NULL || trie->isCompacted) {
659         *pErrorCode=U_NO_WRITE_PERMISSION;
660         return;
661     }
662 #ifdef UCPTRIE_DEBUG
663     umutablecptrie_set(trie->t3, c, value, pErrorCode);
664 #endif
665 
666     block=getDataBlock(trie, c, forLSCP);
667     if(block<0) {
668         *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
669         return;
670     }
671 
672     trie->data[block+(c&UTRIE2_DATA_MASK)]=value;
673 }
674 
675 U_CAPI void U_EXPORT2
utrie2_set32(UTrie2 * trie,UChar32 c,uint32_t value,UErrorCode * pErrorCode)676 utrie2_set32(UTrie2 *trie, UChar32 c, uint32_t value, UErrorCode *pErrorCode) {
677     if(U_FAILURE(*pErrorCode)) {
678         return;
679     }
680     if((uint32_t)c>0x10ffff) {
681         *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
682         return;
683     }
684     set32(trie->newTrie, c, TRUE, value, pErrorCode);
685 }
686 
687 U_CAPI void U_EXPORT2
utrie2_set32ForLeadSurrogateCodeUnit(UTrie2 * trie,UChar32 c,uint32_t value,UErrorCode * pErrorCode)688 utrie2_set32ForLeadSurrogateCodeUnit(UTrie2 *trie,
689                                      UChar32 c, uint32_t value,
690                                      UErrorCode *pErrorCode) {
691     if(U_FAILURE(*pErrorCode)) {
692         return;
693     }
694     if(!U_IS_LEAD(c)) {
695         *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
696         return;
697     }
698     set32(trie->newTrie, c, FALSE, value, pErrorCode);
699 }
700 
701 static void
writeBlock(uint32_t * block,uint32_t value)702 writeBlock(uint32_t *block, uint32_t value) {
703     uint32_t *limit=block+UTRIE2_DATA_BLOCK_LENGTH;
704     while(block<limit) {
705         *block++=value;
706     }
707 }
708 
709 /**
710  * initialValue is ignored if overwrite=TRUE
711  * @internal
712  */
713 static void
fillBlock(uint32_t * block,UChar32 start,UChar32 limit,uint32_t value,uint32_t initialValue,UBool overwrite)714 fillBlock(uint32_t *block, UChar32 start, UChar32 limit,
715           uint32_t value, uint32_t initialValue, UBool overwrite) {
716     uint32_t *pLimit;
717 
718     pLimit=block+limit;
719     block+=start;
720     if(overwrite) {
721         while(block<pLimit) {
722             *block++=value;
723         }
724     } else {
725         while(block<pLimit) {
726             if(*block==initialValue) {
727                 *block=value;
728             }
729             ++block;
730         }
731     }
732 }
733 
734 U_CAPI void U_EXPORT2
utrie2_setRange32(UTrie2 * trie,UChar32 start,UChar32 end,uint32_t value,UBool overwrite,UErrorCode * pErrorCode)735 utrie2_setRange32(UTrie2 *trie,
736                   UChar32 start, UChar32 end,
737                   uint32_t value, UBool overwrite,
738                   UErrorCode *pErrorCode) {
739     /*
740      * repeat value in [start..end]
741      * mark index values for repeat-data blocks by setting bit 31 of the index values
742      * fill around existing values if any, if(overwrite)
743      */
744     UNewTrie2 *newTrie;
745     int32_t block, rest, repeatBlock;
746     UChar32 limit;
747 
748     if(U_FAILURE(*pErrorCode)) {
749         return;
750     }
751     if((uint32_t)start>0x10ffff || (uint32_t)end>0x10ffff || start>end) {
752         *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
753         return;
754     }
755     newTrie=trie->newTrie;
756     if(newTrie==NULL || newTrie->isCompacted) {
757         *pErrorCode=U_NO_WRITE_PERMISSION;
758         return;
759     }
760 #ifdef UCPTRIE_DEBUG
761     umutablecptrie_setRange(newTrie->t3, start, end, value, pErrorCode);
762 #endif
763     if(!overwrite && value==newTrie->initialValue) {
764         return; /* nothing to do */
765     }
766 
767     limit=end+1;
768     if(start&UTRIE2_DATA_MASK) {
769         UChar32 nextStart;
770 
771         /* set partial block at [start..following block boundary[ */
772         block=getDataBlock(newTrie, start, TRUE);
773         if(block<0) {
774             *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
775             return;
776         }
777 
778         nextStart=(start+UTRIE2_DATA_MASK)&~UTRIE2_DATA_MASK;
779         if(nextStart<=limit) {
780             fillBlock(newTrie->data+block, start&UTRIE2_DATA_MASK, UTRIE2_DATA_BLOCK_LENGTH,
781                       value, newTrie->initialValue, overwrite);
782             start=nextStart;
783         } else {
784             fillBlock(newTrie->data+block, start&UTRIE2_DATA_MASK, limit&UTRIE2_DATA_MASK,
785                       value, newTrie->initialValue, overwrite);
786             return;
787         }
788     }
789 
790     /* number of positions in the last, partial block */
791     rest=limit&UTRIE2_DATA_MASK;
792 
793     /* round down limit to a block boundary */
794     limit&=~UTRIE2_DATA_MASK;
795 
796     /* iterate over all-value blocks */
797     if(value==newTrie->initialValue) {
798         repeatBlock=newTrie->dataNullOffset;
799     } else {
800         repeatBlock=-1;
801     }
802 
803     while(start<limit) {
804         int32_t i2;
805         UBool setRepeatBlock=FALSE;
806 
807         if(value==newTrie->initialValue && isInNullBlock(newTrie, start, TRUE)) {
808             start+=UTRIE2_DATA_BLOCK_LENGTH; /* nothing to do */
809             continue;
810         }
811 
812         /* get index value */
813         i2=getIndex2Block(newTrie, start, TRUE);
814         if(i2<0) {
815             *pErrorCode=U_INTERNAL_PROGRAM_ERROR;
816             return;
817         }
818         i2+=(start>>UTRIE2_SHIFT_2)&UTRIE2_INDEX_2_MASK;
819         block=newTrie->index2[i2];
820         if(isWritableBlock(newTrie, block)) {
821             /* already allocated */
822             if(overwrite && block>=UNEWTRIE2_DATA_0800_OFFSET) {
823                 /*
824                  * We overwrite all values, and it's not a
825                  * protected (ASCII-linear or 2-byte UTF-8) block:
826                  * replace with the repeatBlock.
827                  */
828                 setRepeatBlock=TRUE;
829             } else {
830                 /* !overwrite, or protected block: just write the values into this block */
831                 fillBlock(newTrie->data+block,
832                           0, UTRIE2_DATA_BLOCK_LENGTH,
833                           value, newTrie->initialValue, overwrite);
834             }
835         } else if(newTrie->data[block]!=value && (overwrite || block==newTrie->dataNullOffset)) {
836             /*
837              * Set the repeatBlock instead of the null block or previous repeat block:
838              *
839              * If !isWritableBlock() then all entries in the block have the same value
840              * because it's the null block or a range block (the repeatBlock from a previous
841              * call to utrie2_setRange32()).
842              * No other blocks are used multiple times before compacting.
843              *
844              * The null block is the only non-writable block with the initialValue because
845              * of the repeatBlock initialization above. (If value==initialValue, then
846              * the repeatBlock will be the null data block.)
847              *
848              * We set our repeatBlock if the desired value differs from the block's value,
849              * and if we overwrite any data or if the data is all initial values
850              * (which is the same as the block being the null block, see above).
851              */
852             setRepeatBlock=TRUE;
853         }
854         if(setRepeatBlock) {
855             if(repeatBlock>=0) {
856                 setIndex2Entry(newTrie, i2, repeatBlock);
857             } else {
858                 /* create and set and fill the repeatBlock */
859                 repeatBlock=getDataBlock(newTrie, start, TRUE);
860                 if(repeatBlock<0) {
861                     *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
862                     return;
863                 }
864                 writeBlock(newTrie->data+repeatBlock, value);
865             }
866         }
867 
868         start+=UTRIE2_DATA_BLOCK_LENGTH;
869     }
870 
871     if(rest>0) {
872         /* set partial block at [last block boundary..limit[ */
873         block=getDataBlock(newTrie, start, TRUE);
874         if(block<0) {
875             *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
876             return;
877         }
878 
879         fillBlock(newTrie->data+block, 0, rest, value, newTrie->initialValue, overwrite);
880     }
881 
882     return;
883 }
884 
885 /* compaction --------------------------------------------------------------- */
886 
887 static inline UBool
equal_int32(const int32_t * s,const int32_t * t,int32_t length)888 equal_int32(const int32_t *s, const int32_t *t, int32_t length) {
889     while(length>0 && *s==*t) {
890         ++s;
891         ++t;
892         --length;
893     }
894     return (UBool)(length==0);
895 }
896 
897 static inline UBool
equal_uint32(const uint32_t * s,const uint32_t * t,int32_t length)898 equal_uint32(const uint32_t *s, const uint32_t *t, int32_t length) {
899     while(length>0 && *s==*t) {
900         ++s;
901         ++t;
902         --length;
903     }
904     return (UBool)(length==0);
905 }
906 
907 static int32_t
findSameIndex2Block(const int32_t * idx,int32_t index2Length,int32_t otherBlock)908 findSameIndex2Block(const int32_t *idx, int32_t index2Length, int32_t otherBlock) {
909     int32_t block;
910 
911     /* ensure that we do not even partially get past index2Length */
912     index2Length-=UTRIE2_INDEX_2_BLOCK_LENGTH;
913 
914     for(block=0; block<=index2Length; ++block) {
915         if(equal_int32(idx+block, idx+otherBlock, UTRIE2_INDEX_2_BLOCK_LENGTH)) {
916             return block;
917         }
918     }
919     return -1;
920 }
921 
922 static int32_t
findSameDataBlock(const uint32_t * data,int32_t dataLength,int32_t otherBlock,int32_t blockLength)923 findSameDataBlock(const uint32_t *data, int32_t dataLength, int32_t otherBlock, int32_t blockLength) {
924     int32_t block;
925 
926     /* ensure that we do not even partially get past dataLength */
927     dataLength-=blockLength;
928 
929     for(block=0; block<=dataLength; block+=UTRIE2_DATA_GRANULARITY) {
930         if(equal_uint32(data+block, data+otherBlock, blockLength)) {
931             return block;
932         }
933     }
934     return -1;
935 }
936 
937 /*
938  * Find the start of the last range in the trie by enumerating backward.
939  * Indexes for supplementary code points higher than this will be omitted.
940  */
941 static UChar32
findHighStart(UNewTrie2 * trie,uint32_t highValue)942 findHighStart(UNewTrie2 *trie, uint32_t highValue) {
943     const uint32_t *data32;
944 
945     uint32_t value, initialValue;
946     UChar32 c, prev;
947     int32_t i1, i2, j, i2Block, prevI2Block, index2NullOffset, block, prevBlock, nullBlock;
948 
949     data32=trie->data;
950     initialValue=trie->initialValue;
951 
952     index2NullOffset=trie->index2NullOffset;
953     nullBlock=trie->dataNullOffset;
954 
955     /* set variables for previous range */
956     if(highValue==initialValue) {
957         prevI2Block=index2NullOffset;
958         prevBlock=nullBlock;
959     } else {
960         prevI2Block=-1;
961         prevBlock=-1;
962     }
963     prev=0x110000;
964 
965     /* enumerate index-2 blocks */
966     i1=UNEWTRIE2_INDEX_1_LENGTH;
967     c=prev;
968     while(c>0) {
969         i2Block=trie->index1[--i1];
970         if(i2Block==prevI2Block) {
971             /* the index-2 block is the same as the previous one, and filled with highValue */
972             c-=UTRIE2_CP_PER_INDEX_1_ENTRY;
973             continue;
974         }
975         prevI2Block=i2Block;
976         if(i2Block==index2NullOffset) {
977             /* this is the null index-2 block */
978             if(highValue!=initialValue) {
979                 return c;
980             }
981             c-=UTRIE2_CP_PER_INDEX_1_ENTRY;
982         } else {
983             /* enumerate data blocks for one index-2 block */
984             for(i2=UTRIE2_INDEX_2_BLOCK_LENGTH; i2>0;) {
985                 block=trie->index2[i2Block+ --i2];
986                 if(block==prevBlock) {
987                     /* the block is the same as the previous one, and filled with highValue */
988                     c-=UTRIE2_DATA_BLOCK_LENGTH;
989                     continue;
990                 }
991                 prevBlock=block;
992                 if(block==nullBlock) {
993                     /* this is the null data block */
994                     if(highValue!=initialValue) {
995                         return c;
996                     }
997                     c-=UTRIE2_DATA_BLOCK_LENGTH;
998                 } else {
999                     for(j=UTRIE2_DATA_BLOCK_LENGTH; j>0;) {
1000                         value=data32[block+ --j];
1001                         if(value!=highValue) {
1002                             return c;
1003                         }
1004                         --c;
1005                     }
1006                 }
1007             }
1008         }
1009     }
1010 
1011     /* deliver last range */
1012     return 0;
1013 }
1014 
1015 /*
1016  * Compact a build-time trie.
1017  *
1018  * The compaction
1019  * - removes blocks that are identical with earlier ones
1020  * - overlaps adjacent blocks as much as possible (if overlap==TRUE)
1021  * - moves blocks in steps of the data granularity
1022  * - moves and overlaps blocks that overlap with multiple values in the overlap region
1023  *
1024  * It does not
1025  * - try to move and overlap blocks that are not already adjacent
1026  */
1027 static void
compactData(UNewTrie2 * trie)1028 compactData(UNewTrie2 *trie) {
1029 #ifdef UTRIE2_DEBUG
1030     int32_t countSame=0, sumOverlaps=0;
1031 #endif
1032 
1033     int32_t start, newStart, movedStart;
1034     int32_t blockLength, overlap;
1035     int32_t i, mapIndex, blockCount;
1036 
1037     /* do not compact linear-ASCII data */
1038     newStart=UTRIE2_DATA_START_OFFSET;
1039     for(start=0, i=0; start<newStart; start+=UTRIE2_DATA_BLOCK_LENGTH, ++i) {
1040         trie->map[i]=start;
1041     }
1042 
1043     /*
1044      * Start with a block length of 64 for 2-byte UTF-8,
1045      * then switch to UTRIE2_DATA_BLOCK_LENGTH.
1046      */
1047     blockLength=64;
1048     blockCount=blockLength>>UTRIE2_SHIFT_2;
1049     for(start=newStart; start<trie->dataLength;) {
1050         /*
1051          * start: index of first entry of current block
1052          * newStart: index where the current block is to be moved
1053          *           (right after current end of already-compacted data)
1054          */
1055         if(start==UNEWTRIE2_DATA_0800_OFFSET) {
1056             blockLength=UTRIE2_DATA_BLOCK_LENGTH;
1057             blockCount=1;
1058         }
1059 
1060         /* skip blocks that are not used */
1061         if(trie->map[start>>UTRIE2_SHIFT_2]<=0) {
1062             /* advance start to the next block */
1063             start+=blockLength;
1064 
1065             /* leave newStart with the previous block! */
1066             continue;
1067         }
1068 
1069         /* search for an identical block */
1070         if( (movedStart=findSameDataBlock(trie->data, newStart, start, blockLength))
1071              >=0
1072         ) {
1073 #ifdef UTRIE2_DEBUG
1074             ++countSame;
1075 #endif
1076             /* found an identical block, set the other block's index value for the current block */
1077             for(i=blockCount, mapIndex=start>>UTRIE2_SHIFT_2; i>0; --i) {
1078                 trie->map[mapIndex++]=movedStart;
1079                 movedStart+=UTRIE2_DATA_BLOCK_LENGTH;
1080             }
1081 
1082             /* advance start to the next block */
1083             start+=blockLength;
1084 
1085             /* leave newStart with the previous block! */
1086             continue;
1087         }
1088 
1089         /* see if the beginning of this block can be overlapped with the end of the previous block */
1090         /* look for maximum overlap (modulo granularity) with the previous, adjacent block */
1091         for(overlap=blockLength-UTRIE2_DATA_GRANULARITY;
1092             overlap>0 && !equal_uint32(trie->data+(newStart-overlap), trie->data+start, overlap);
1093             overlap-=UTRIE2_DATA_GRANULARITY) {}
1094 
1095 #ifdef UTRIE2_DEBUG
1096             sumOverlaps+=overlap;
1097 #endif
1098         if(overlap>0 || newStart<start) {
1099             /* some overlap, or just move the whole block */
1100             movedStart=newStart-overlap;
1101             for(i=blockCount, mapIndex=start>>UTRIE2_SHIFT_2; i>0; --i) {
1102                 trie->map[mapIndex++]=movedStart;
1103                 movedStart+=UTRIE2_DATA_BLOCK_LENGTH;
1104             }
1105 
1106             /* move the non-overlapping indexes to their new positions */
1107             start+=overlap;
1108             for(i=blockLength-overlap; i>0; --i) {
1109                 trie->data[newStart++]=trie->data[start++];
1110             }
1111         } else /* no overlap && newStart==start */ {
1112             for(i=blockCount, mapIndex=start>>UTRIE2_SHIFT_2; i>0; --i) {
1113                 trie->map[mapIndex++]=start;
1114                 start+=UTRIE2_DATA_BLOCK_LENGTH;
1115             }
1116             newStart=start;
1117         }
1118     }
1119 
1120     /* now adjust the index-2 table */
1121     for(i=0; i<trie->index2Length; ++i) {
1122         if(i==UNEWTRIE2_INDEX_GAP_OFFSET) {
1123             /* Gap indexes are invalid (-1). Skip over the gap. */
1124             i+=UNEWTRIE2_INDEX_GAP_LENGTH;
1125         }
1126         trie->index2[i]=trie->map[trie->index2[i]>>UTRIE2_SHIFT_2];
1127     }
1128     trie->dataNullOffset=trie->map[trie->dataNullOffset>>UTRIE2_SHIFT_2];
1129 
1130     /* ensure dataLength alignment */
1131     while((newStart&(UTRIE2_DATA_GRANULARITY-1))!=0) {
1132         trie->data[newStart++]=trie->initialValue;
1133     }
1134 
1135 #ifdef UTRIE2_DEBUG
1136     /* we saved some space */
1137     printf("compacting UTrie2: count of 32-bit data words %lu->%lu  countSame=%ld  sumOverlaps=%ld\n",
1138             (long)trie->dataLength, (long)newStart, (long)countSame, (long)sumOverlaps);
1139 #endif
1140 
1141     trie->dataLength=newStart;
1142 }
1143 
1144 static void
compactIndex2(UNewTrie2 * trie)1145 compactIndex2(UNewTrie2 *trie) {
1146     int32_t i, start, newStart, movedStart, overlap;
1147 
1148     /* do not compact linear-BMP index-2 blocks */
1149     newStart=UTRIE2_INDEX_2_BMP_LENGTH;
1150     for(start=0, i=0; start<newStart; start+=UTRIE2_INDEX_2_BLOCK_LENGTH, ++i) {
1151         trie->map[i]=start;
1152     }
1153 
1154     /* Reduce the index table gap to what will be needed at runtime. */
1155     newStart+=UTRIE2_UTF8_2B_INDEX_2_LENGTH+((trie->highStart-0x10000)>>UTRIE2_SHIFT_1);
1156 
1157     for(start=UNEWTRIE2_INDEX_2_NULL_OFFSET; start<trie->index2Length;) {
1158         /*
1159          * start: index of first entry of current block
1160          * newStart: index where the current block is to be moved
1161          *           (right after current end of already-compacted data)
1162          */
1163 
1164         /* search for an identical block */
1165         if( (movedStart=findSameIndex2Block(trie->index2, newStart, start))
1166              >=0
1167         ) {
1168             /* found an identical block, set the other block's index value for the current block */
1169             trie->map[start>>UTRIE2_SHIFT_1_2]=movedStart;
1170 
1171             /* advance start to the next block */
1172             start+=UTRIE2_INDEX_2_BLOCK_LENGTH;
1173 
1174             /* leave newStart with the previous block! */
1175             continue;
1176         }
1177 
1178         /* see if the beginning of this block can be overlapped with the end of the previous block */
1179         /* look for maximum overlap with the previous, adjacent block */
1180         for(overlap=UTRIE2_INDEX_2_BLOCK_LENGTH-1;
1181             overlap>0 && !equal_int32(trie->index2+(newStart-overlap), trie->index2+start, overlap);
1182             --overlap) {}
1183 
1184         if(overlap>0 || newStart<start) {
1185             /* some overlap, or just move the whole block */
1186             trie->map[start>>UTRIE2_SHIFT_1_2]=newStart-overlap;
1187 
1188             /* move the non-overlapping indexes to their new positions */
1189             start+=overlap;
1190             for(i=UTRIE2_INDEX_2_BLOCK_LENGTH-overlap; i>0; --i) {
1191                 trie->index2[newStart++]=trie->index2[start++];
1192             }
1193         } else /* no overlap && newStart==start */ {
1194             trie->map[start>>UTRIE2_SHIFT_1_2]=start;
1195             start+=UTRIE2_INDEX_2_BLOCK_LENGTH;
1196             newStart=start;
1197         }
1198     }
1199 
1200     /* now adjust the index-1 table */
1201     for(i=0; i<UNEWTRIE2_INDEX_1_LENGTH; ++i) {
1202         trie->index1[i]=trie->map[trie->index1[i]>>UTRIE2_SHIFT_1_2];
1203     }
1204     trie->index2NullOffset=trie->map[trie->index2NullOffset>>UTRIE2_SHIFT_1_2];
1205 
1206     /*
1207      * Ensure data table alignment:
1208      * Needs to be granularity-aligned for 16-bit trie
1209      * (so that dataMove will be down-shiftable),
1210      * and 2-aligned for uint32_t data.
1211      */
1212     while((newStart&((UTRIE2_DATA_GRANULARITY-1)|1))!=0) {
1213         /* Arbitrary value: 0x3fffc not possible for real data. */
1214         trie->index2[newStart++]=(int32_t)0xffff<<UTRIE2_INDEX_SHIFT;
1215     }
1216 
1217 #ifdef UTRIE2_DEBUG
1218     /* we saved some space */
1219     printf("compacting UTrie2: count of 16-bit index words %lu->%lu\n",
1220             (long)trie->index2Length, (long)newStart);
1221 #endif
1222 
1223     trie->index2Length=newStart;
1224 }
1225 
1226 static void
compactTrie(UTrie2 * trie,UErrorCode * pErrorCode)1227 compactTrie(UTrie2 *trie, UErrorCode *pErrorCode) {
1228     UNewTrie2 *newTrie;
1229     UChar32 highStart, suppHighStart;
1230     uint32_t highValue;
1231 
1232     newTrie=trie->newTrie;
1233 
1234     /* find highStart and round it up */
1235     highValue=utrie2_get32(trie, 0x10ffff);
1236     highStart=findHighStart(newTrie, highValue);
1237     highStart=(highStart+(UTRIE2_CP_PER_INDEX_1_ENTRY-1))&~(UTRIE2_CP_PER_INDEX_1_ENTRY-1);
1238     if(highStart==0x110000) {
1239         highValue=trie->errorValue;
1240     }
1241 
1242     /*
1243      * Set trie->highStart only after utrie2_get32(trie, highStart).
1244      * Otherwise utrie2_get32(trie, highStart) would try to read the highValue.
1245      */
1246     trie->highStart=newTrie->highStart=highStart;
1247 
1248 #ifdef UTRIE2_DEBUG
1249     printf("UTrie2: highStart U+%06lx  highValue 0x%lx  initialValue 0x%lx\n",
1250             (long)highStart, (long)highValue, (long)trie->initialValue);
1251 #endif
1252 
1253     if(highStart<0x110000) {
1254         /* Blank out [highStart..10ffff] to release associated data blocks. */
1255         suppHighStart= highStart<=0x10000 ? 0x10000 : highStart;
1256         utrie2_setRange32(trie, suppHighStart, 0x10ffff, trie->initialValue, TRUE, pErrorCode);
1257         if(U_FAILURE(*pErrorCode)) {
1258             return;
1259         }
1260     }
1261 
1262     compactData(newTrie);
1263     if(highStart>0x10000) {
1264         compactIndex2(newTrie);
1265 #ifdef UTRIE2_DEBUG
1266     } else {
1267         printf("UTrie2: highStart U+%04lx  count of 16-bit index words %lu->%lu\n",
1268                 (long)highStart, (long)trie->newTrie->index2Length, (long)UTRIE2_INDEX_1_OFFSET);
1269 #endif
1270     }
1271 
1272     /*
1273      * Store the highValue in the data array and round up the dataLength.
1274      * Must be done after compactData() because that assumes that dataLength
1275      * is a multiple of UTRIE2_DATA_BLOCK_LENGTH.
1276      */
1277     newTrie->data[newTrie->dataLength++]=highValue;
1278     while((newTrie->dataLength&(UTRIE2_DATA_GRANULARITY-1))!=0) {
1279         newTrie->data[newTrie->dataLength++]=trie->initialValue;
1280     }
1281 
1282     newTrie->isCompacted=TRUE;
1283 }
1284 
1285 /* serialization ------------------------------------------------------------ */
1286 
1287 /**
1288  * Maximum length of the runtime index array.
1289  * Limited by its own 16-bit index values, and by uint16_t UTrie2Header.indexLength.
1290  * (The actual maximum length is lower,
1291  * (0x110000>>UTRIE2_SHIFT_2)+UTRIE2_UTF8_2B_INDEX_2_LENGTH+UTRIE2_MAX_INDEX_1_LENGTH.)
1292  */
1293 #define UTRIE2_MAX_INDEX_LENGTH 0xffff
1294 
1295 /**
1296  * Maximum length of the runtime data array.
1297  * Limited by 16-bit index values that are left-shifted by UTRIE2_INDEX_SHIFT,
1298  * and by uint16_t UTrie2Header.shiftedDataLength.
1299  */
1300 #define UTRIE2_MAX_DATA_LENGTH (0xffff<<UTRIE2_INDEX_SHIFT)
1301 
1302 /* Compact and internally serialize the trie. */
1303 U_CAPI void U_EXPORT2
utrie2_freeze(UTrie2 * trie,UTrie2ValueBits valueBits,UErrorCode * pErrorCode)1304 utrie2_freeze(UTrie2 *trie, UTrie2ValueBits valueBits, UErrorCode *pErrorCode) {
1305     UNewTrie2 *newTrie;
1306     UTrie2Header *header;
1307     uint32_t *p;
1308     uint16_t *dest16;
1309     int32_t i, length;
1310     int32_t allIndexesLength;
1311     int32_t dataMove;  /* >0 if the data is moved to the end of the index array */
1312     UChar32 highStart;
1313 
1314     /* argument check */
1315     if(U_FAILURE(*pErrorCode)) {
1316         return;
1317     }
1318     if( trie==NULL ||
1319         valueBits<0 || UTRIE2_COUNT_VALUE_BITS<=valueBits
1320     ) {
1321         *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
1322         return;
1323     }
1324     newTrie=trie->newTrie;
1325     if(newTrie==NULL) {
1326         /* already frozen */
1327         UTrie2ValueBits frozenValueBits=
1328             trie->data16!=NULL ? UTRIE2_16_VALUE_BITS : UTRIE2_32_VALUE_BITS;
1329         if(valueBits!=frozenValueBits) {
1330             *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
1331         }
1332         return;
1333     }
1334 
1335     /* compact if necessary */
1336     if(!newTrie->isCompacted) {
1337         compactTrie(trie, pErrorCode);
1338         if(U_FAILURE(*pErrorCode)) {
1339             return;
1340         }
1341     }
1342     highStart=trie->highStart;
1343 
1344     if(highStart<=0x10000) {
1345         allIndexesLength=UTRIE2_INDEX_1_OFFSET;
1346     } else {
1347         allIndexesLength=newTrie->index2Length;
1348     }
1349     if(valueBits==UTRIE2_16_VALUE_BITS) {
1350         dataMove=allIndexesLength;
1351     } else {
1352         dataMove=0;
1353     }
1354 
1355     /* are indexLength and dataLength within limits? */
1356     if( /* for unshifted indexLength */
1357         allIndexesLength>UTRIE2_MAX_INDEX_LENGTH ||
1358         /* for unshifted dataNullOffset */
1359         (dataMove+newTrie->dataNullOffset)>0xffff ||
1360         /* for unshifted 2-byte UTF-8 index-2 values */
1361         (dataMove+UNEWTRIE2_DATA_0800_OFFSET)>0xffff ||
1362         /* for shiftedDataLength */
1363         (dataMove+newTrie->dataLength)>UTRIE2_MAX_DATA_LENGTH
1364     ) {
1365         *pErrorCode=U_INDEX_OUTOFBOUNDS_ERROR;
1366         return;
1367     }
1368 
1369     /* calculate the total serialized length */
1370     length=sizeof(UTrie2Header)+allIndexesLength*2;
1371     if(valueBits==UTRIE2_16_VALUE_BITS) {
1372         length+=newTrie->dataLength*2;
1373     } else {
1374         length+=newTrie->dataLength*4;
1375     }
1376 
1377     trie->memory=uprv_malloc(length);
1378     if(trie->memory==NULL) {
1379         *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
1380         return;
1381     }
1382     trie->length=length;
1383     trie->isMemoryOwned=TRUE;
1384 
1385     trie->indexLength=allIndexesLength;
1386     trie->dataLength=newTrie->dataLength;
1387     if(highStart<=0x10000) {
1388         trie->index2NullOffset=0xffff;
1389     } else {
1390         trie->index2NullOffset=static_cast<uint16_t>(UTRIE2_INDEX_2_OFFSET+newTrie->index2NullOffset);
1391     }
1392     trie->dataNullOffset=(uint16_t)(dataMove+newTrie->dataNullOffset);
1393     trie->highValueIndex=dataMove+trie->dataLength-UTRIE2_DATA_GRANULARITY;
1394 
1395     /* set the header fields */
1396     header=(UTrie2Header *)trie->memory;
1397 
1398     header->signature=UTRIE2_SIG; /* "Tri2" */
1399     header->options=(uint16_t)valueBits;
1400 
1401     header->indexLength=(uint16_t)trie->indexLength;
1402     header->shiftedDataLength=(uint16_t)(trie->dataLength>>UTRIE2_INDEX_SHIFT);
1403     header->index2NullOffset=trie->index2NullOffset;
1404     header->dataNullOffset=trie->dataNullOffset;
1405     header->shiftedHighStart=(uint16_t)(highStart>>UTRIE2_SHIFT_1);
1406 
1407     /* fill the index and data arrays */
1408     dest16=(uint16_t *)(header+1);
1409     trie->index=dest16;
1410 
1411     /* write the index-2 array values shifted right by UTRIE2_INDEX_SHIFT, after adding dataMove */
1412     p=(uint32_t *)newTrie->index2;
1413     for(i=UTRIE2_INDEX_2_BMP_LENGTH; i>0; --i) {
1414         *dest16++=(uint16_t)((dataMove + *p++)>>UTRIE2_INDEX_SHIFT);
1415     }
1416 
1417     /* write UTF-8 2-byte index-2 values, not right-shifted */
1418     for(i=0; i<(0xc2-0xc0); ++i) {                                  /* C0..C1 */
1419         *dest16++=(uint16_t)(dataMove+UTRIE2_BAD_UTF8_DATA_OFFSET);
1420     }
1421     for(; i<(0xe0-0xc0); ++i) {                                     /* C2..DF */
1422         *dest16++=(uint16_t)(dataMove+newTrie->index2[i<<(6-UTRIE2_SHIFT_2)]);
1423     }
1424 
1425     if(highStart>0x10000) {
1426         int32_t index1Length=(highStart-0x10000)>>UTRIE2_SHIFT_1;
1427         int32_t index2Offset=UTRIE2_INDEX_2_BMP_LENGTH+UTRIE2_UTF8_2B_INDEX_2_LENGTH+index1Length;
1428 
1429         /* write 16-bit index-1 values for supplementary code points */
1430         p=(uint32_t *)newTrie->index1+UTRIE2_OMITTED_BMP_INDEX_1_LENGTH;
1431         for(i=index1Length; i>0; --i) {
1432             *dest16++=(uint16_t)(UTRIE2_INDEX_2_OFFSET + *p++);
1433         }
1434 
1435         /*
1436          * write the index-2 array values for supplementary code points,
1437          * shifted right by UTRIE2_INDEX_SHIFT, after adding dataMove
1438          */
1439         p=(uint32_t *)newTrie->index2+index2Offset;
1440         for(i=newTrie->index2Length-index2Offset; i>0; --i) {
1441             *dest16++=(uint16_t)((dataMove + *p++)>>UTRIE2_INDEX_SHIFT);
1442         }
1443     }
1444 
1445     /* write the 16/32-bit data array */
1446     switch(valueBits) {
1447     case UTRIE2_16_VALUE_BITS:
1448         /* write 16-bit data values */
1449         trie->data16=dest16;
1450         trie->data32=NULL;
1451         p=newTrie->data;
1452         for(i=newTrie->dataLength; i>0; --i) {
1453             *dest16++=(uint16_t)*p++;
1454         }
1455         break;
1456     case UTRIE2_32_VALUE_BITS:
1457         /* write 32-bit data values */
1458         trie->data16=NULL;
1459         trie->data32=(uint32_t *)dest16;
1460         uprv_memcpy(dest16, newTrie->data, (size_t)newTrie->dataLength*4);
1461         break;
1462     default:
1463         *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
1464         return;
1465     }
1466 
1467 #ifdef UTRIE2_DEBUG
1468     utrie2_printLengths(trie, "");
1469 #endif
1470 
1471 #ifdef UCPTRIE_DEBUG
1472     umutablecptrie_setName(newTrie->t3, trie->name);
1473     ucptrie_close(
1474         umutablecptrie_buildImmutable(
1475             newTrie->t3, UCPTRIE_TYPE_FAST, (UCPTrieValueWidth)valueBits, pErrorCode));
1476 #endif
1477     /* Delete the UNewTrie2. */
1478     uprv_free(newTrie->data);
1479     uprv_free(newTrie);
1480     trie->newTrie=NULL;
1481 }
1482