Lines Matching refs:trie
36 // Enough data for a trie header?
99 // Allocate the trie.
100 UCPTrie *trie = (UCPTrie *)uprv_malloc(sizeof(UCPTrie));
101 if (trie == nullptr) {
105 uprv_memcpy(trie, &tempTrie, sizeof(tempTrie));
107 trie->name = "fromSerialized";
112 trie->index = p16;
113 p16 += trie->indexLength;
116 int32_t nullValueOffset = trie->dataNullOffset;
117 if (nullValueOffset >= trie->dataLength) {
118 nullValueOffset = trie->dataLength - UCPTRIE_HIGH_VALUE_NEG_DATA_OFFSET;
122 trie->data.ptr16 = p16;
123 trie->nullValue = trie->data.ptr16[nullValueOffset];
126 trie->data.ptr32 = (const uint32_t *)p16;
127 trie->nullValue = trie->data.ptr32[nullValueOffset];
130 trie->data.ptr8 = (const uint8_t *)p16;
131 trie->nullValue = trie->data.ptr8[nullValueOffset];
142 return trie;
146 ucptrie_close(UCPTrie *trie) {
147 uprv_free(trie);
151 ucptrie_getType(const UCPTrie *trie) {
152 return (UCPTrieType)trie->type;
156 ucptrie_getValueWidth(const UCPTrie *trie) {
157 return (UCPTrieValueWidth)trie->valueWidth;
161 ucptrie_internalSmallIndex(const UCPTrie *trie, UChar32 c) {
163 if (trie->type == UCPTRIE_TYPE_FAST) {
164 U_ASSERT(0xffff < c && c < trie->highStart);
167 U_ASSERT((uint32_t)c < (uint32_t)trie->highStart && trie->highStart > UCPTRIE_SMALL_LIMIT);
170 int32_t i3Block = trie->index[
171 (int32_t)trie->index[i1] + ((c >> UCPTRIE_SHIFT_2) & UCPTRIE_INDEX_2_MASK)];
176 dataBlock = trie->index[i3Block + i3];
181 dataBlock = ((int32_t)trie->index[i3Block++] << (2 + (2 * i3))) & 0x30000;
182 dataBlock |= trie->index[i3Block + i3];
188 ucptrie_internalSmallU8Index(const UCPTrie *trie, int32_t lt1, uint8_t t2, uint8_t t3) {
190 if (c >= trie->highStart) {
192 return trie->dataLength - UCPTRIE_HIGH_VALUE_NEG_DATA_OFFSET;
194 return ucptrie_internalSmallIndex(trie, c);
198 ucptrie_internalU8PrevIndex(const UCPTrie *trie, UChar32 c,
210 int32_t idx = _UCPTRIE_CP_INDEX(trie, 0xffff, c);
225 // Unreachable if the trie is properly initialized.
233 ucptrie_get(const UCPTrie *trie, UChar32 c) {
239 UChar32 fastMax = trie->type == UCPTRIE_TYPE_FAST ? 0xffff : UCPTRIE_SMALL_MAX;
240 dataIndex = _UCPTRIE_CP_INDEX(trie, fastMax, c);
242 return getValue(trie->data, (UCPTrieValueWidth)trie->valueWidth, dataIndex);
264 const UCPTrie *trie = reinterpret_cast<const UCPTrie *>(t);
265 UCPTrieValueWidth valueWidth = (UCPTrieValueWidth)trie->valueWidth;
266 if (start >= trie->highStart) {
268 int32_t di = trie->dataLength - UCPTRIE_HIGH_VALUE_NEG_DATA_OFFSET;
269 uint32_t value = getValue(trie->data, valueWidth, di);
276 uint32_t nullValue = trie->nullValue;
278 const uint16_t *index = trie->index;
290 if (c <= 0xffff && (trie->type == UCPTRIE_TYPE_FAST || c <= UCPTRIE_SMALL_MAX)) {
293 i3BlockLength = trie->type == UCPTRIE_TYPE_FAST ?
299 if (trie->type == UCPTRIE_TYPE_FAST) {
300 U_ASSERT(0xffff < c && c < trie->highStart);
303 U_ASSERT(c < trie->highStart && trie->highStart > UCPTRIE_SMALL_LIMIT);
306 i3Block = trie->index[
307 (int32_t)trie->index[i1] + ((c >> UCPTRIE_SHIFT_2) & UCPTRIE_INDEX_2_MASK)];
315 if (i3Block == trie->index3NullOffset) {
322 trieValue = trie->nullValue;
327 prevBlock = trie->dataNullOffset;
354 if (block == trie->dataNullOffset) {
361 trieValue = trie->nullValue;
369 uint32_t trieValue2 = getValue(trie->data, valueWidth, di);
373 maybeFilterValue(trieValue2, trie->nullValue, nullValue,
381 value = maybeFilterValue(trieValue2, trie->nullValue, nullValue,
387 trieValue2 = getValue(trie->data, valueWidth, ++di);
390 maybeFilterValue(trieValue2, trie->nullValue, nullValue,
400 } while (c < trie->highStart);
402 int32_t di = trie->dataLength - UCPTRIE_HIGH_VALUE_NEG_DATA_OFFSET;
403 uint32_t highValue = getValue(trie->data, valueWidth, di);
404 if (maybeFilterValue(highValue, trie->nullValue, nullValue,
416 const void *trie, UChar32 start,
420 return getRange(trie, start, filter, context, pValue);
428 UChar32 end = getRange(trie, start, filter, context, pValue);
453 UChar32 end2 = getRange(trie, surrEnd + 1, filter, context, &value2);
461 ucptrie_getRange(const UCPTrie *trie, UChar32 start,
464 return ucptrie_internalGetRange(getRange, trie, start,
470 ucptrie_toBinary(const UCPTrie *trie,
477 UCPTrieType type = (UCPTrieType)trie->type;
478 UCPTrieValueWidth valueWidth = (UCPTrieValueWidth)trie->valueWidth;
487 int32_t length = (int32_t)sizeof(UCPTrieHeader) + trie->indexLength * 2;
490 length += trie->dataLength * 2;
493 length += trie->dataLength * 4;
496 length += trie->dataLength;
511 ((trie->dataLength & 0xf0000) >> 4) |
512 ((trie->dataNullOffset & 0xf0000) >> 8) |
513 (trie->type << 6) |
515 header->indexLength = (uint16_t)trie->indexLength;
516 header->dataLength = (uint16_t)trie->dataLength;
517 header->index3NullOffset = trie->index3NullOffset;
518 header->dataNullOffset = (uint16_t)trie->dataNullOffset;
519 header->shiftedHighStart = trie->highStart >> UCPTRIE_SHIFT_2;
522 uprv_memcpy(bytes, trie->index, trie->indexLength * 2);
523 bytes += trie->indexLength * 2;
527 uprv_memcpy(bytes, trie->data.ptr16, trie->dataLength * 2);
530 uprv_memcpy(bytes, trie->data.ptr32, trie->dataLength * 4);
533 uprv_memcpy(bytes, trie->data.ptr8, trie->dataLength);
545 long countNull(const UCPTrie *trie) {
546 uint32_t nullValue=trie->nullValue;
547 int32_t length=trie->dataLength;
549 switch (trie->valueWidth) {
552 if(trie->data.ptr16[i]==nullValue) { ++count; }
557 if(trie->data.ptr32[i]==nullValue) { ++count; }
562 if(trie->data.ptr8[i]==nullValue) { ++count; }
573 ucptrie_printLengths(const UCPTrie *trie, const char *which) {
574 long indexLength=trie->indexLength;
575 long dataLength=(long)trie->dataLength;
577 dataLength*(trie->valueWidth==UCPTRIE_VALUE_BITS_16 ? 2 :
578 trie->valueWidth==UCPTRIE_VALUE_BITS_32 ? 4 : 1);
580 which, trie->name, indexLength, dataLength, countNull(trie), totalLength);