Lines Matching full:trie
16 * This is a common implementation of a Unicode trie.
19 * This is the second common version of a Unicode trie (hence the name UTrie2).
42 * have been chosen to minimize trie sizes overall.
71 /* Building a trie ----------------------------------------------------------*/
106 allocIndex2Block(UNewTrie2 *trie);
110 UTrie2 *trie;
119 trie=(UTrie2 *)uprv_malloc(sizeof(UTrie2));
122 if(trie==NULL || newTrie==NULL || data==NULL) {
123 uprv_free(trie);
130 uprv_memset(trie, 0, sizeof(UTrie2));
131 trie->initialValue=initialValue;
132 trie->errorValue=errorValue;
133 trie->highStart=0x110000;
134 trie->newTrie=newTrie;
229 utrie2_set32(trie, i, initialValue, pErrorCode);
232 return trie;
237 UNewTrie2 *trie;
239 trie=(UNewTrie2 *)uprv_malloc(sizeof(UNewTrie2));
240 if(trie==NULL) {
244 trie->data=(uint32_t *)uprv_malloc(other->dataCapacity*4);
245 if(trie->data==NULL) {
246 uprv_free(trie);
249 trie->dataCapacity=other->dataCapacity;
252 uprv_memcpy(trie->index1, other->index1, sizeof(trie->index1));
253 uprv_memcpy(trie->index2, other->index2, other->index2Length*4);
254 trie->index2NullOffset=other->index2NullOffset;
255 trie->index2Length=other->index2Length;
257 uprv_memcpy(trie->data, other->data, other->dataLength*4);
258 trie->dataNullOffset=other->dataNullOffset;
259 trie->dataLength=other->dataLength;
263 trie->firstFreeBlock=0;
265 uprv_memcpy(trie->map, other->map, (other->dataLength>>UTRIE2_SHIFT_2)*4);
266 trie->firstFreeBlock=other->firstFreeBlock;
269 trie->initialValue=other->initialValue;
270 trie->errorValue=other->errorValue;
271 trie->highStart=other->highStart;
272 trie->isCompacted=other->isCompacted;
274 return trie;
279 UTrie2 *trie;
289 trie=(UTrie2 *)uprv_malloc(sizeof(UTrie2));
290 if(trie==NULL) {
293 uprv_memcpy(trie, other, sizeof(UTrie2));
296 trie->memory=uprv_malloc(other->length);
297 if(trie->memory!=NULL) {
298 trie->isMemoryOwned=TRUE;
299 uprv_memcpy(trie->memory, other->memory, other->length);
302 trie->index=(uint16_t *)trie->memory+(other->index-(uint16_t *)other->memory);
304 trie->data16=(uint16_t *)trie->memory+(other->data16-(uint16_t *)other->memory);
307 trie->data32=(uint32_t *)trie->memory+(other->data32-(uint32_t *)other->memory);
311 trie->newTrie=cloneBuilder(other->newTrie);
314 if(trie->memory==NULL && trie->newTrie==NULL) {
315 uprv_free(trie);
316 trie=NULL;
318 return trie;
322 UTrie2 *trie;
330 if(value!=nt->trie->initialValue) {
335 utrie2_set32(nt->trie, start, value, &nt->errorCode);
337 utrie2_setRange32(nt->trie, start, end, value, TRUE, &nt->errorCode);
347 utrie_printLengths(const UTrie *trie) {
348 long indexLength=trie->indexLength;
349 long dataLength=(long)trie->dataLength;
350 long totalLength=(long)sizeof(UTrieHeader)+indexLength*2+dataLength*(trie->data32!=NULL ? 4 : 2);
356 utrie2_printLengths(const UTrie2 *trie, const char *which) {
357 long indexLength=trie->indexLength;
358 long dataLength=(long)trie->dataLength;
359 long totalLength=(long)sizeof(UTrie2Header)+indexLength*2+dataLength*(trie->data32!=NULL ? 4 : 2);
378 return utrie2_clone(other, pErrorCode); /* clone an unfrozen trie */
381 /* Clone the frozen trie by enumerating it and building a new one. */
382 context.trie=utrie2_open(other->initialValue, other->errorValue, pErrorCode);
398 utrie2_set32ForLeadSurrogateCodeUnit(context.trie, lead, value, pErrorCode);
402 utrie2_close(context.trie);
403 context.trie=NULL;
405 return context.trie;
421 context.trie=utrie2_open(trie1->initialValue, errorValue, pErrorCode);
437 utrie2_set32ForLeadSurrogateCodeUnit(context.trie, lead, value, pErrorCode);
441 utrie2_freeze(context.trie,
448 utrie2_printLengths(context.trie, "fromUTrie");
452 utrie2_close(context.trie);
453 context.trie=NULL;
455 return context.trie;
459 isInNullBlock(UNewTrie2 *trie, UChar32 c, UBool forLSCP) {
466 i2=trie->index1[c>>UTRIE2_SHIFT_1]+
469 block=trie->index2[i2];
470 return (UBool)(block==trie->dataNullOffset);
474 allocIndex2Block(UNewTrie2 *trie) {
477 newBlock=trie->index2Length;
479 if(newTop>LENGTHOF(trie->index2)) {
487 trie->index2Length=newTop;
488 uprv_memcpy(trie->index2+newBlock, trie->index2+trie->index2NullOffset, UTRIE2_INDEX_2_BLOCK_LENGTH*4);
493 getIndex2Block(UNewTrie2 *trie, UChar32 c, UBool forLSCP) {
501 i2=trie->index1[i1];
502 if(i2==trie->index2NullOffset) {
503 i2=allocIndex2Block(trie);
507 trie->index1[i1]=i2;
513 allocDataBlock(UNewTrie2 *trie, int32_t copyBlock) {
516 if(trie->firstFreeBlock!=0) {
518 newBlock=trie->firstFreeBlock;
519 trie->firstFreeBlock=-trie->map[newBlock>>UTRIE2_SHIFT_2];
522 newBlock=trie->dataLength;
524 if(newTop>trie->dataCapacity) {
529 if(trie->dataCapacity<UNEWTRIE2_MEDIUM_DATA_LENGTH) {
531 } else if(trie->dataCapacity<UNEWTRIE2_MAX_DATA_LENGTH) {
545 uprv_memcpy(data, trie->data, trie->dataLength*4);
546 uprv_free(trie->data);
547 trie->data=data;
548 trie->dataCapacity=capacity;
550 trie->dataLength=newTop;
552 uprv_memcpy(trie->data+newBlock, trie->data+copyBlock, UTRIE2_DATA_BLOCK_LENGTH*4);
553 trie->map[newBlock>>UTRIE2_SHIFT_2]=0;
559 releaseDataBlock(UNewTrie2 *trie, int32_t block) {
561 trie->map[block>>UTRIE2_SHIFT_2]=-trie->firstFreeBlock;
562 trie->firstFreeBlock=block;
566 isWritableBlock(UNewTrie2 *trie, int32_t block) {
567 return (UBool)(block!=trie->dataNullOffset && 1==trie->map[block>>UTRIE2_SHIFT_2]);
571 setIndex2Entry(UNewTrie2 *trie, int32_t i2, int32_t block) {
573 ++trie->map[block>>UTRIE2_SHIFT_2]; /* increment first, in case block==oldBlock! */
574 oldBlock=trie->index2[i2];
575 if(0 == --trie->map[oldBlock>>UTRIE2_SHIFT_2]) {
576 releaseDataBlock(trie, oldBlock);
578 trie->index2[i2]=block;
588 getDataBlock(UNewTrie2 *trie, UChar32 c, UBool forLSCP) {
591 i2=getIndex2Block(trie, c, forLSCP);
597 oldBlock=trie->index2[i2];
598 if(isWritableBlock(trie, oldBlock)) {
603 newBlock=allocDataBlock(trie, oldBlock);
608 setIndex2Entry(trie, i2, newBlock);
616 set32(UNewTrie2 *trie,
621 if(trie==NULL || trie->isCompacted) {
626 block=getDataBlock(trie, c, forLSCP);
632 trie->data[block+(c&UTRIE2_DATA_MASK)]=value;
636 utrie2_set32(UTrie2 *trie, UChar32 c, uint32_t value, UErrorCode *pErrorCode) {
644 set32(trie->newTrie, c, TRUE, value, pErrorCode);
648 utrie2_set32ForLeadSurrogateCodeUnit(UTrie2 *trie,
658 set32(trie->newTrie, c, FALSE, value, pErrorCode);
695 utrie2_setRange32(UTrie2 *trie,
715 newTrie=trie->newTrie;
895 * Find the start of the last range in the trie by enumerating backward.
899 findHighStart(UNewTrie2 *trie, uint32_t highValue) {
906 data32=trie->data;
907 initialValue=trie->initialValue;
909 index2NullOffset=trie->index2NullOffset;
910 nullBlock=trie->dataNullOffset;
926 i2Block=trie->index1[--i1];
942 block=trie->index2[i2Block+ --i2];
973 * Compact a build-time trie.
985 compactData(UNewTrie2 *trie) {
993 trie->map[i]=start;
1002 for(start=newStart; start<trie->dataLength;) {
1014 if(trie->map[start>>UTRIE2_SHIFT_2]<=0) {
1023 if( (movedStart=findSameDataBlock(trie->data, newStart, start, blockLength))
1028 trie->map[mapIndex++]=movedStart;
1042 overlap>0 && !equal_uint32(trie->data+(newStart-overlap), trie->data+start, overlap);
1049 trie->map[mapIndex++]=movedStart;
1056 trie->data[newStart++]=trie->data[start++];
1060 trie->map[mapIndex++]=start;
1068 for(i=0; i<trie->index2Length; ++i) {
1073 trie->index2[i]=trie->map[trie->index2[i]>>UTRIE2_SHIFT_2];
1075 trie->dataNullOffset=trie->map[trie->dataNullOffset>>UTRIE2_SHIFT_2];
1079 trie->data[newStart++]=trie->initialValue;
1085 (long)trie->dataLength, (long)newStart);
1088 trie->dataLength=newStart;
1092 compactIndex2(UNewTrie2 *trie) {
1098 trie->map[i]=start;
1102 newStart+=UTRIE2_UTF8_2B_INDEX_2_LENGTH+((trie->highStart-0x10000)>>UTRIE2_SHIFT_1);
1104 for(start=UNEWTRIE2_INDEX_2_NULL_OFFSET; start<trie->index2Length;) {
1112 if( (movedStart=findSameIndex2Block(trie->index2, newStart, start))
1116 trie->map[start>>UTRIE2_SHIFT_1_2]=movedStart;
1128 overlap>0 && !equal_int32(trie->index2+(newStart-overlap), trie->index2+start, overlap);
1133 trie->map[start>>UTRIE2_SHIFT_1_2]=newStart-overlap;
1138 trie->index2[newStart++]=trie->index2[start++];
1141 trie->map[start>>UTRIE2_SHIFT_1_2]=start;
1149 trie->index1[i]=trie->map[trie->index1[i]>>UTRIE2_SHIFT_1_2];
1151 trie->index2NullOffset=trie->map[trie->index2NullOffset>>UTRIE2_SHIFT_1_2];
1155 * Needs to be granularity-aligned for 16-bit trie
1161 trie->index2[newStart++]=(int32_t)0xffff<<UTRIE2_INDEX_SHIFT;
1167 (long)trie->index2Length, (long)newStart);
1170 trie->index2Length=newStart;
1174 compactTrie(UTrie2 *trie, UErrorCode *pErrorCode) {
1179 newTrie=trie->newTrie;
1182 highValue=utrie2_get32(trie, 0x10ffff);
1186 highValue=trie->errorValue;
1190 * Set trie->highStart only after utrie2_get32(trie, highStart).
1191 * Otherwise utrie2_get32(trie, highStart) would try to read the highValue.
1193 trie->highStart=newTrie->highStart=highStart;
1197 (long)highStart, (long)highValue, (long)trie->initialValue);
1203 utrie2_setRange32(trie, suppHighStart, 0x10ffff, trie->initialValue, TRUE, pErrorCode);
1215 (long)highStart, (long)trie->newTrie->index2Length, (long)UTRIE2_INDEX_1_OFFSET);
1226 newTrie->data[newTrie->dataLength++]=trie->initialValue;
1249 /* Compact and internally serialize the trie. */
1251 utrie2_freeze(UTrie2 *trie, UTrie2ValueBits valueBits, UErrorCode *pErrorCode) {
1265 if( trie==NULL ||
1271 newTrie=trie->newTrie;
1275 trie->data16!=NULL ? UTRIE2_16_VALUE_BITS : UTRIE2_32_VALUE_BITS;
1284 compactTrie(trie, pErrorCode);
1289 highStart=trie->highStart;
1324 trie->memory=uprv_malloc(length);
1325 if(trie->memory==NULL) {
1329 trie->length=length;
1330 trie->isMemoryOwned=TRUE;
1332 trie->indexLength=allIndexesLength;
1333 trie->dataLength=newTrie->dataLength;
1335 trie->index2NullOffset=0xffff;
1337 trie->index2NullOffset=UTRIE2_INDEX_2_OFFSET+newTrie->index2NullOffset;
1339 trie->dataNullOffset=(uint16_t)(dataMove+newTrie->dataNullOffset);
1340 trie->highValueIndex=dataMove+trie->dataLength-UTRIE2_DATA_GRANULARITY;
1343 header=(UTrie2Header *)trie->memory;
1348 header->indexLength=(uint16_t)trie->indexLength;
1349 header->shiftedDataLength=(uint16_t)(trie->dataLength>>UTRIE2_INDEX_SHIFT);
1350 header->index2NullOffset=trie->index2NullOffset;
1351 header->dataNullOffset=trie->dataNullOffset;
1356 trie->index=dest16;
1396 trie->data16=dest16;
1397 trie->data32=NULL;
1405 trie->data16=NULL;
1406 trie->data32=(uint32_t *)dest16;
1417 trie->newTrie=NULL;
1421 utrie2_isFrozen(const UTrie2 *trie) {
1422 return (UBool)(trie->newTrie==NULL);
1426 utrie2_serialize(UTrie2 *trie,
1434 if( trie==NULL || trie->memory==NULL || trie->newTrie!=NULL ||
1441 if(capacity>=trie->length) {
1442 uprv_memcpy(data, trie->memory, trie->length);
1446 return trie->length;
