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