Lines Matching refs:trie
18 * This is a common implementation of a "folded" trie.
46 /* Building a trie ----------------------------------------------------------*/
53 UNewTrie *trie;
63 trie=fillIn;
65 trie=(UNewTrie *)uprv_malloc(sizeof(UNewTrie));
66 if(trie==NULL) {
70 uprv_memset(trie, 0, sizeof(UNewTrie));
71 trie->isAllocated= (UBool)(fillIn==NULL);
74 trie->data=aliasData;
75 trie->isDataAllocated=FALSE;
77 trie->data=(uint32_t *)uprv_malloc(maxDataLength*4);
78 if(trie->data==NULL) {
79 uprv_free(trie);
82 trie->isDataAllocated=TRUE;
95 /* do this at least for trie->index[0] even if that block is only partly used for Latin-1 */
96 trie->index[i++]=j;
102 trie->dataLength=j;
104 trie->data[--j]=initialValue;
107 trie->leadUnitValue=leadUnitValue;
108 trie->indexLength=UTRIE_MAX_INDEX_LENGTH;
109 trie->dataCapacity=maxDataLength;
110 trie->isLatin1Linear=latin1Linear;
111 trie->isCompacted=FALSE;
112 return trie;
117 UNewTrie *trie;
137 trie=utrie_open(fillIn, aliasData, aliasDataCapacity,
140 if(trie==NULL) {
143 uprv_memcpy(trie->index, other->index, sizeof(trie->index));
144 uprv_memcpy(trie->data, other->data, (size_t)other->dataLength*4);
145 trie->dataLength=other->dataLength;
146 trie->isDataAllocated=isDataAllocated;
149 return trie;
153 utrie_close(UNewTrie *trie) {
154 if(trie!=NULL) {
155 if(trie->isDataAllocated) {
156 uprv_free(trie->data);
157 trie->data=NULL;
159 if(trie->isAllocated) {
160 uprv_free(trie);
166 utrie_getData(UNewTrie *trie, int32_t *pLength) {
167 if(trie==NULL || pLength==NULL) {
171 *pLength=trie->dataLength;
172 return trie->data;
176 utrie_allocDataBlock(UNewTrie *trie) {
179 newBlock=trie->dataLength;
181 if(newTop>trie->dataCapacity) {
185 trie->dataLength=newTop;
196 utrie_getDataBlock(UNewTrie *trie, UChar32 c) {
200 indexValue=trie->index[c];
206 newBlock=utrie_allocDataBlock(trie);
211 trie->index[c]=newBlock;
214 uprv_memcpy(trie->data+newBlock, trie->data-indexValue, 4*UTRIE_DATA_BLOCK_LENGTH);
222 utrie_set32(UNewTrie *trie, UChar32 c, uint32_t value) {
225 /* valid, uncompacted trie and valid c? */
226 if(trie==NULL || trie->isCompacted || (uint32_t)c>0x10ffff) {
230 block=utrie_getDataBlock(trie, c);
235 trie->data[block+(c&UTRIE_MASK)]=value;
240 utrie_get32(UNewTrie *trie, UChar32 c, UBool *pInBlockZero) {
243 /* valid, uncompacted trie and valid c? */
244 if(trie==NULL || trie->isCompacted || (uint32_t)c>0x10ffff) {
251 block=trie->index[c>>UTRIE_SHIFT];
256 return trie->data[ABS(block)+(c&UTRIE_MASK)];
284 utrie_setRange32(UNewTrie *trie, UChar32 start, UChar32 limit, uint32_t value, UBool overwrite) {
293 /* valid, uncompacted trie and valid indexes? */
294 if( trie==NULL || trie->isCompacted ||
303 initialValue=trie->data[0];
308 block=utrie_getDataBlock(trie, start);
315 utrie_fillBlock(trie->data+block, start&UTRIE_MASK, UTRIE_DATA_BLOCK_LENGTH,
319 utrie_fillBlock(trie->data+block, start&UTRIE_MASK, limit&UTRIE_MASK,
339 block=trie->index[start>>UTRIE_SHIFT];
342 utrie_fillBlock(trie->data+block, 0, UTRIE_DATA_BLOCK_LENGTH, value, initialValue, overwrite);
343 } else if(trie->data[-block]!=value && (block==0 || overwrite)) {
346 trie->index[start>>UTRIE_SHIFT]=-repeatBlock;
349 repeatBlock=utrie_getDataBlock(trie, start);
355 trie->index[start>>UTRIE_SHIFT]=-repeatBlock;
356 utrie_fillBlock(trie->data+repeatBlock, 0, UTRIE_DATA_BLOCK_LENGTH, value, initialValue, TRUE);
365 block=utrie_getDataBlock(trie, start);
370 utrie_fillBlock(trie->data+block, 0, rest, value, initialValue, overwrite);
396 * a compact area on top of the BMP-part of the trie index,
405 utrie_fold(UNewTrie *trie, UNewTrieGetFoldedValue *getFoldedValue, UErrorCode *pErrorCode) {
415 idx=trie->index;
430 if(trie->leadUnitValue==trie->data[0]) {
434 block=utrie_allocDataBlock(trie);
440 utrie_fillBlock(trie->data+block, 0, UTRIE_DATA_BLOCK_LENGTH, trie->leadUnitValue, trie->data[0], TRUE);
444 trie->index[c]=block;
475 value=getFoldedValue(trie, c, block+UTRIE_SURROGATE_BLOCK_COUNT);
476 if(value!=utrie_get32(trie, U16_LEAD(c), NULL)) {
477 if(!utrie_set32(trie, U16_LEAD(c), value)) {
530 printf("trie index count: BMP %ld all Unicode %ld folded %ld\n",
534 trie
538 * Set a value in the trie index map to indicate which data block
546 _findUnusedBlocks(UNewTrie *trie) {
550 uprv_memset(trie->map, 0xff, (UTRIE_MAX_BUILD_TIME_DATA_LENGTH>>UTRIE_SHIFT)*4);
553 for(i=0; i<trie->indexLength; ++i) {
554 trie->map[ABS(trie->index[i])>>UTRIE_SHIFT]=0;
558 trie->map[0]=0;
578 * Compact a folded build-time trie.
590 utrie_compact(UNewTrie *trie, UBool overlap, UErrorCode *pErrorCode) {
597 /* valid, uncompacted trie? */
598 if(trie==NULL) {
602 if(trie->isCompacted) {
609 _findUnusedBlocks(trie);
612 if(trie->isLatin1Linear && UTRIE_SHIFT<=8) {
619 for(start=newStart; start<trie->dataLength;) {
627 if(trie->map[start>>UTRIE_SHIFT]<0) {
637 (i=_findSameDataBlock(trie->data, newStart, start,
642 trie->map[start>>UTRIE_SHIFT]=i;
655 i>0 && !equal_uint32(trie->data+(newStart-i), trie->data+start, i);
663 trie->map[start>>UTRIE_SHIFT]=newStart-i;
668 trie->data[newStart++]=trie->data[start++];
672 trie->map[start>>UTRIE_SHIFT]=newStart;
674 trie->data[newStart++]=trie->data[start++];
677 trie->map[start>>UTRIE_SHIFT]=start;
684 for(i=0; i<trie->indexLength; ++i) {
685 trie->index[i]=trie->map[ABS(trie->index[i])>>UTRIE_SHIFT];
690 printf("compacting trie: count of 32-bit words %lu->%lu\n",
691 (long)trie->dataLength, (long)newStart);
694 trie->dataLength=newStart;
706 * which fits into 16-bit trie values;
721 defaultGetFoldedValue(UNewTrie *trie, UChar32 start, int32_t offset) {
726 initialValue=trie->data[0];
729 value=utrie_get32(trie, start, &inBlockZero);
742 utrie_serialize(UNewTrie *trie, void *dt, int32_t capacity,
757 if(trie==NULL || capacity<0 || (capacity>0 && dt==NULL)) {
767 if(!trie->isCompacted) {
769 utrie_compact(trie, FALSE, pErrorCode);
772 utrie_fold(trie, getFoldedValue, pErrorCode);
775 utrie_compact(trie, TRUE, pErrorCode);
777 trie->isCompacted=TRUE;
784 if( (reduceTo16Bits ? (trie->dataLength+trie->indexLength) : trie->dataLength) >= UTRIE_MAX_DATA_LENGTH) {
788 length=sizeof(UTrieHeader)+2*trie->indexLength;
790 length+=2*trie->dataLength;
792 length+=4*trie->dataLength;
801 (long)trie->indexLength, (long)trie->dataLength, (long)length);
808 header->signature=0x54726965; /* "Trie" */
814 if(trie->isLatin1Linear) {
818 header->indexLength=trie->indexLength;
819 header->dataLength=trie->dataLength;
824 p=(uint32_t *)trie->index;
826 for(i=trie->indexLength; i>0; --i) {
827 *dest16++=(uint16_t)((*p++ + trie->indexLength)>>UTRIE_INDEX_SHIFT);
831 p=trie->data;
832 for(i=trie->dataLength; i>0; --i) {
837 p=(uint32_t *)trie->index;
839 for(i=trie->indexLength; i>0; --i) {
844 uprv_memcpy(dest16, trie->data, 4*(size_t)trie->dataLength);
857 utrie_unserialize(UTrie *trie, const void *data, int32_t length, UErrorCode *pErrorCode) {
866 /* enough data for a trie header? */
887 trie->isLatin1Linear= (UBool)((options&UTRIE_OPTIONS_LATIN1_IS_LINEAR)!=0);
890 trie->indexLength=header->indexLength;
891 trie->dataLength=header->dataLength;
896 if(length<2*trie->indexLength) {
901 trie->index=p16;
902 p16+=trie->indexLength;
903 length-=2*trie->indexLength;
907 if(length<4*trie->dataLength) {
911 trie->data32=(const uint32_t *)p16;
912 trie->initialValue=trie->data32[0];
913 length=(int32_t)sizeof(UTrieHeader)+2*trie->indexLength+4*trie->dataLength;
915 if(length<2*trie->dataLength) {
921 trie->data32=NULL;
922 trie->initialValue=trie->index[trie->indexLength];
923 length=(int32_t)sizeof(UTrieHeader)+2*trie->indexLength+2*trie->dataLength;
926 trie->getFoldingOffset=utrie_defaultGetFoldingOffset;
932 utrie_unserializeDummy(UTrie *trie,
945 /* calculate the actual size of the dummy trie data */
950 trie->indexLength=UTRIE_BMP_INDEX_LENGTH+UTRIE_SURROGATE_BLOCK_COUNT;
951 trie->dataLength=latin1Length;
953 trie->dataLength+=UTRIE_DATA_BLOCK_LENGTH;
956 actualLength=trie->indexLength*2;
958 actualLength+=trie->dataLength*2;
960 actualLength+=trie->dataLength*4;
963 /* enough space for the dummy trie? */
969 trie->isLatin1Linear=TRUE;
970 trie->initialValue=initialValue;
974 trie->index=p16;
978 block=(uint16_t)(trie->indexLength>>UTRIE_INDEX_SHIFT);
979 limit=trie->indexLength;
994 trie->data32=NULL;
997 p16+=trie->indexLength;
1013 uprv_memset(p16, 0, trie->indexLength*2);
1025 trie->data32=p32=(uint32_t *)(p16+trie->indexLength);
1041 trie->getFoldingOffset=utrie_defaultGetFoldingOffset;
1056 * The values are transformed from the raw trie entries by the enumValue function.
1059 utrie_enum(const UTrie *trie,
1069 if(trie==NULL || trie->index==NULL || enumRange==NULL) {
1076 idx=trie->index;
1077 data32=trie->data32;
1079 /* get the enumeration value that corresponds to an initial-value trie data entry */
1080 initialValue=enumValue(context, trie->initialValue);
1083 nullBlock=trie->indexLength;
1167 offset=trie->getFoldingOffset(value);
