1/*
2******************************************************************************
3*
4*   Copyright (C) 2001-2014, International Business Machines
5*   Corporation and others.  All Rights Reserved.
6*
7******************************************************************************
8*   file name:  utrie2.cpp
9*   encoding:   US-ASCII
10*   tab size:   8 (not used)
11*   indentation:4
12*
13*   created on: 2008aug16 (starting from a copy of utrie.c)
14*   created by: Markus W. Scherer
15*
16*   This is a common implementation of a Unicode trie.
17*   It is a kind of compressed, serializable table of 16- or 32-bit values associated with
18*   Unicode code points (0..0x10ffff).
19*   This is the second common version of a Unicode trie (hence the name UTrie2).
20*   See utrie2.h for a comparison.
21*
22*   This file contains only the runtime and enumeration code, for read-only access.
23*   See utrie2_builder.c for the builder code.
24*/
25#ifdef UTRIE2_DEBUG
26#   include <stdio.h>
27#endif
28
29#include "unicode/utypes.h"
30#include "unicode/utf.h"
31#include "unicode/utf8.h"
32#include "unicode/utf16.h"
33#include "cmemory.h"
34#include "utrie2.h"
35#include "utrie2_impl.h"
36#include "uassert.h"
37
38/* Public UTrie2 API implementation ----------------------------------------- */
39
40static uint32_t
41get32(const UNewTrie2 *trie, UChar32 c, UBool fromLSCP) {
42    int32_t i2, block;
43
44    if(c>=trie->highStart && (!U_IS_LEAD(c) || fromLSCP)) {
45        return trie->data[trie->dataLength-UTRIE2_DATA_GRANULARITY];
46    }
47
48    if(U_IS_LEAD(c) && fromLSCP) {
49        i2=(UTRIE2_LSCP_INDEX_2_OFFSET-(0xd800>>UTRIE2_SHIFT_2))+
50            (c>>UTRIE2_SHIFT_2);
51    } else {
52        i2=trie->index1[c>>UTRIE2_SHIFT_1]+
53            ((c>>UTRIE2_SHIFT_2)&UTRIE2_INDEX_2_MASK);
54    }
55    block=trie->index2[i2];
56    return trie->data[block+(c&UTRIE2_DATA_MASK)];
57}
58
59U_CAPI uint32_t U_EXPORT2
60utrie2_get32(const UTrie2 *trie, UChar32 c) {
61    if(trie->data16!=NULL) {
62        return UTRIE2_GET16(trie, c);
63    } else if(trie->data32!=NULL) {
64        return UTRIE2_GET32(trie, c);
65    } else if((uint32_t)c>0x10ffff) {
66        return trie->errorValue;
67    } else {
68        return get32(trie->newTrie, c, TRUE);
69    }
70}
71
72U_CAPI uint32_t U_EXPORT2
73utrie2_get32FromLeadSurrogateCodeUnit(const UTrie2 *trie, UChar32 c) {
74    if(!U_IS_LEAD(c)) {
75        return trie->errorValue;
76    }
77    if(trie->data16!=NULL) {
78        return UTRIE2_GET16_FROM_U16_SINGLE_LEAD(trie, c);
79    } else if(trie->data32!=NULL) {
80        return UTRIE2_GET32_FROM_U16_SINGLE_LEAD(trie, c);
81    } else {
82        return get32(trie->newTrie, c, FALSE);
83    }
84}
85
86static inline int32_t
87u8Index(const UTrie2 *trie, UChar32 c, int32_t i) {
88    int32_t idx=
89        _UTRIE2_INDEX_FROM_CP(
90            trie,
91            trie->data32==NULL ? trie->indexLength : 0,
92            c);
93    return (idx<<3)|i;
94}
95
96U_CAPI int32_t U_EXPORT2
97utrie2_internalU8NextIndex(const UTrie2 *trie, UChar32 c,
98                           const uint8_t *src, const uint8_t *limit) {
99    int32_t i, length;
100    i=0;
101    /* support 64-bit pointers by avoiding cast of arbitrary difference */
102    if((limit-src)<=7) {
103        length=(int32_t)(limit-src);
104    } else {
105        length=7;
106    }
107    c=utf8_nextCharSafeBody(src, &i, length, c, -1);
108    return u8Index(trie, c, i);
109}
110
111U_CAPI int32_t U_EXPORT2
112utrie2_internalU8PrevIndex(const UTrie2 *trie, UChar32 c,
113                           const uint8_t *start, const uint8_t *src) {
114    int32_t i, length;
115    /* support 64-bit pointers by avoiding cast of arbitrary difference */
116    if((src-start)<=7) {
117        i=length=(int32_t)(src-start);
118    } else {
119        i=length=7;
120        start=src-7;
121    }
122    c=utf8_prevCharSafeBody(start, 0, &i, c, -1);
123    i=length-i;  /* number of bytes read backward from src */
124    return u8Index(trie, c, i);
125}
126
127U_CAPI UTrie2 * U_EXPORT2
128utrie2_openFromSerialized(UTrie2ValueBits valueBits,
129                          const void *data, int32_t length, int32_t *pActualLength,
130                          UErrorCode *pErrorCode) {
131    const UTrie2Header *header;
132    const uint16_t *p16;
133    int32_t actualLength;
134
135    UTrie2 tempTrie;
136    UTrie2 *trie;
137
138    if(U_FAILURE(*pErrorCode)) {
139        return 0;
140    }
141
142    if( length<=0 || (U_POINTER_MASK_LSB(data, 3)!=0) ||
143        valueBits<0 || UTRIE2_COUNT_VALUE_BITS<=valueBits
144    ) {
145        *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
146        return 0;
147    }
148
149    /* enough data for a trie header? */
150    if(length<(int32_t)sizeof(UTrie2Header)) {
151        *pErrorCode=U_INVALID_FORMAT_ERROR;
152        return 0;
153    }
154
155    /* check the signature */
156    header=(const UTrie2Header *)data;
157    if(header->signature!=UTRIE2_SIG) {
158        *pErrorCode=U_INVALID_FORMAT_ERROR;
159        return 0;
160    }
161
162    /* get the options */
163    if(valueBits!=(UTrie2ValueBits)(header->options&UTRIE2_OPTIONS_VALUE_BITS_MASK)) {
164        *pErrorCode=U_INVALID_FORMAT_ERROR;
165        return 0;
166    }
167
168    /* get the length values and offsets */
169    uprv_memset(&tempTrie, 0, sizeof(tempTrie));
170    tempTrie.indexLength=header->indexLength;
171    tempTrie.dataLength=header->shiftedDataLength<<UTRIE2_INDEX_SHIFT;
172    tempTrie.index2NullOffset=header->index2NullOffset;
173    tempTrie.dataNullOffset=header->dataNullOffset;
174
175    tempTrie.highStart=header->shiftedHighStart<<UTRIE2_SHIFT_1;
176    tempTrie.highValueIndex=tempTrie.dataLength-UTRIE2_DATA_GRANULARITY;
177    if(valueBits==UTRIE2_16_VALUE_BITS) {
178        tempTrie.highValueIndex+=tempTrie.indexLength;
179    }
180
181    /* calculate the actual length */
182    actualLength=(int32_t)sizeof(UTrie2Header)+tempTrie.indexLength*2;
183    if(valueBits==UTRIE2_16_VALUE_BITS) {
184        actualLength+=tempTrie.dataLength*2;
185    } else {
186        actualLength+=tempTrie.dataLength*4;
187    }
188    if(length<actualLength) {
189        *pErrorCode=U_INVALID_FORMAT_ERROR;  /* not enough bytes */
190        return 0;
191    }
192
193    /* allocate the trie */
194    trie=(UTrie2 *)uprv_malloc(sizeof(UTrie2));
195    if(trie==NULL) {
196        *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
197        return 0;
198    }
199    uprv_memcpy(trie, &tempTrie, sizeof(tempTrie));
200    trie->memory=(uint32_t *)data;
201    trie->length=actualLength;
202    trie->isMemoryOwned=FALSE;
203
204    /* set the pointers to its index and data arrays */
205    p16=(const uint16_t *)(header+1);
206    trie->index=p16;
207    p16+=trie->indexLength;
208
209    /* get the data */
210    switch(valueBits) {
211    case UTRIE2_16_VALUE_BITS:
212        trie->data16=p16;
213        trie->data32=NULL;
214        trie->initialValue=trie->index[trie->dataNullOffset];
215        trie->errorValue=trie->data16[UTRIE2_BAD_UTF8_DATA_OFFSET];
216        break;
217    case UTRIE2_32_VALUE_BITS:
218        trie->data16=NULL;
219        trie->data32=(const uint32_t *)p16;
220        trie->initialValue=trie->data32[trie->dataNullOffset];
221        trie->errorValue=trie->data32[UTRIE2_BAD_UTF8_DATA_OFFSET];
222        break;
223    default:
224        *pErrorCode=U_INVALID_FORMAT_ERROR;
225        return 0;
226    }
227
228    if(pActualLength!=NULL) {
229        *pActualLength=actualLength;
230    }
231    return trie;
232}
233
234U_CAPI UTrie2 * U_EXPORT2
235utrie2_openDummy(UTrie2ValueBits valueBits,
236                 uint32_t initialValue, uint32_t errorValue,
237                 UErrorCode *pErrorCode) {
238    UTrie2 *trie;
239    UTrie2Header *header;
240    uint32_t *p;
241    uint16_t *dest16;
242    int32_t indexLength, dataLength, length, i;
243    int32_t dataMove;  /* >0 if the data is moved to the end of the index array */
244
245    if(U_FAILURE(*pErrorCode)) {
246        return 0;
247    }
248
249    if(valueBits<0 || UTRIE2_COUNT_VALUE_BITS<=valueBits) {
250        *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
251        return 0;
252    }
253
254    /* calculate the total length of the dummy trie data */
255    indexLength=UTRIE2_INDEX_1_OFFSET;
256    dataLength=UTRIE2_DATA_START_OFFSET+UTRIE2_DATA_GRANULARITY;
257    length=(int32_t)sizeof(UTrie2Header)+indexLength*2;
258    if(valueBits==UTRIE2_16_VALUE_BITS) {
259        length+=dataLength*2;
260    } else {
261        length+=dataLength*4;
262    }
263
264    /* allocate the trie */
265    trie=(UTrie2 *)uprv_malloc(sizeof(UTrie2));
266    if(trie==NULL) {
267        *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
268        return 0;
269    }
270    uprv_memset(trie, 0, sizeof(UTrie2));
271    trie->memory=uprv_malloc(length);
272    if(trie->memory==NULL) {
273        uprv_free(trie);
274        *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
275        return 0;
276    }
277    trie->length=length;
278    trie->isMemoryOwned=TRUE;
279
280    /* set the UTrie2 fields */
281    if(valueBits==UTRIE2_16_VALUE_BITS) {
282        dataMove=indexLength;
283    } else {
284        dataMove=0;
285    }
286
287    trie->indexLength=indexLength;
288    trie->dataLength=dataLength;
289    trie->index2NullOffset=UTRIE2_INDEX_2_OFFSET;
290    trie->dataNullOffset=(uint16_t)dataMove;
291    trie->initialValue=initialValue;
292    trie->errorValue=errorValue;
293    trie->highStart=0;
294    trie->highValueIndex=dataMove+UTRIE2_DATA_START_OFFSET;
295
296    /* set the header fields */
297    header=(UTrie2Header *)trie->memory;
298
299    header->signature=UTRIE2_SIG; /* "Tri2" */
300    header->options=(uint16_t)valueBits;
301
302    header->indexLength=(uint16_t)indexLength;
303    header->shiftedDataLength=(uint16_t)(dataLength>>UTRIE2_INDEX_SHIFT);
304    header->index2NullOffset=(uint16_t)UTRIE2_INDEX_2_OFFSET;
305    header->dataNullOffset=(uint16_t)dataMove;
306    header->shiftedHighStart=0;
307
308    /* fill the index and data arrays */
309    dest16=(uint16_t *)(header+1);
310    trie->index=dest16;
311
312    /* write the index-2 array values shifted right by UTRIE2_INDEX_SHIFT */
313    for(i=0; i<UTRIE2_INDEX_2_BMP_LENGTH; ++i) {
314        *dest16++=(uint16_t)(dataMove>>UTRIE2_INDEX_SHIFT);  /* null data block */
315    }
316
317    /* write UTF-8 2-byte index-2 values, not right-shifted */
318    for(i=0; i<(0xc2-0xc0); ++i) {                                  /* C0..C1 */
319        *dest16++=(uint16_t)(dataMove+UTRIE2_BAD_UTF8_DATA_OFFSET);
320    }
321    for(; i<(0xe0-0xc0); ++i) {                                     /* C2..DF */
322        *dest16++=(uint16_t)dataMove;
323    }
324
325    /* write the 16/32-bit data array */
326    switch(valueBits) {
327    case UTRIE2_16_VALUE_BITS:
328        /* write 16-bit data values */
329        trie->data16=dest16;
330        trie->data32=NULL;
331        for(i=0; i<0x80; ++i) {
332            *dest16++=(uint16_t)initialValue;
333        }
334        for(; i<0xc0; ++i) {
335            *dest16++=(uint16_t)errorValue;
336        }
337        /* highValue and reserved values */
338        for(i=0; i<UTRIE2_DATA_GRANULARITY; ++i) {
339            *dest16++=(uint16_t)initialValue;
340        }
341        break;
342    case UTRIE2_32_VALUE_BITS:
343        /* write 32-bit data values */
344        p=(uint32_t *)dest16;
345        trie->data16=NULL;
346        trie->data32=p;
347        for(i=0; i<0x80; ++i) {
348            *p++=initialValue;
349        }
350        for(; i<0xc0; ++i) {
351            *p++=errorValue;
352        }
353        /* highValue and reserved values */
354        for(i=0; i<UTRIE2_DATA_GRANULARITY; ++i) {
355            *p++=initialValue;
356        }
357        break;
358    default:
359        *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
360        return 0;
361    }
362
363    return trie;
364}
365
366U_CAPI void U_EXPORT2
367utrie2_close(UTrie2 *trie) {
368    if(trie!=NULL) {
369        if(trie->isMemoryOwned) {
370            uprv_free(trie->memory);
371        }
372        if(trie->newTrie!=NULL) {
373            uprv_free(trie->newTrie->data);
374            uprv_free(trie->newTrie);
375        }
376        uprv_free(trie);
377    }
378}
379
380U_CAPI int32_t U_EXPORT2
381utrie2_getVersion(const void *data, int32_t length, UBool anyEndianOk) {
382    uint32_t signature;
383    if(length<16 || data==NULL || (U_POINTER_MASK_LSB(data, 3)!=0)) {
384        return 0;
385    }
386    signature=*(const uint32_t *)data;
387    if(signature==UTRIE2_SIG) {
388        return 2;
389    }
390    if(anyEndianOk && signature==UTRIE2_OE_SIG) {
391        return 2;
392    }
393    if(signature==UTRIE_SIG) {
394        return 1;
395    }
396    if(anyEndianOk && signature==UTRIE_OE_SIG) {
397        return 1;
398    }
399    return 0;
400}
401
402U_CAPI UBool U_EXPORT2
403utrie2_isFrozen(const UTrie2 *trie) {
404    return (UBool)(trie->newTrie==NULL);
405}
406
407U_CAPI int32_t U_EXPORT2
408utrie2_serialize(const UTrie2 *trie,
409                 void *data, int32_t capacity,
410                 UErrorCode *pErrorCode) {
411    /* argument check */
412    if(U_FAILURE(*pErrorCode)) {
413        return 0;
414    }
415
416    if( trie==NULL || trie->memory==NULL || trie->newTrie!=NULL ||
417        capacity<0 || (capacity>0 && (data==NULL || (U_POINTER_MASK_LSB(data, 3)!=0)))
418    ) {
419        *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
420        return 0;
421    }
422
423    if(capacity>=trie->length) {
424        uprv_memcpy(data, trie->memory, trie->length);
425    } else {
426        *pErrorCode=U_BUFFER_OVERFLOW_ERROR;
427    }
428    return trie->length;
429}
430
431U_CAPI int32_t U_EXPORT2
432utrie2_swap(const UDataSwapper *ds,
433            const void *inData, int32_t length, void *outData,
434            UErrorCode *pErrorCode) {
435    const UTrie2Header *inTrie;
436    UTrie2Header trie;
437    int32_t dataLength, size;
438    UTrie2ValueBits valueBits;
439
440    if(U_FAILURE(*pErrorCode)) {
441        return 0;
442    }
443    if(ds==NULL || inData==NULL || (length>=0 && outData==NULL)) {
444        *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
445        return 0;
446    }
447
448    /* setup and swapping */
449    if(length>=0 && length<(int32_t)sizeof(UTrie2Header)) {
450        *pErrorCode=U_INDEX_OUTOFBOUNDS_ERROR;
451        return 0;
452    }
453
454    inTrie=(const UTrie2Header *)inData;
455    trie.signature=ds->readUInt32(inTrie->signature);
456    trie.options=ds->readUInt16(inTrie->options);
457    trie.indexLength=ds->readUInt16(inTrie->indexLength);
458    trie.shiftedDataLength=ds->readUInt16(inTrie->shiftedDataLength);
459
460    valueBits=(UTrie2ValueBits)(trie.options&UTRIE2_OPTIONS_VALUE_BITS_MASK);
461    dataLength=(int32_t)trie.shiftedDataLength<<UTRIE2_INDEX_SHIFT;
462
463    if( trie.signature!=UTRIE2_SIG ||
464        valueBits<0 || UTRIE2_COUNT_VALUE_BITS<=valueBits ||
465        trie.indexLength<UTRIE2_INDEX_1_OFFSET ||
466        dataLength<UTRIE2_DATA_START_OFFSET
467    ) {
468        *pErrorCode=U_INVALID_FORMAT_ERROR; /* not a UTrie */
469        return 0;
470    }
471
472    size=sizeof(UTrie2Header)+trie.indexLength*2;
473    switch(valueBits) {
474    case UTRIE2_16_VALUE_BITS:
475        size+=dataLength*2;
476        break;
477    case UTRIE2_32_VALUE_BITS:
478        size+=dataLength*4;
479        break;
480    default:
481        *pErrorCode=U_INVALID_FORMAT_ERROR;
482        return 0;
483    }
484
485    if(length>=0) {
486        UTrie2Header *outTrie;
487
488        if(length<size) {
489            *pErrorCode=U_INDEX_OUTOFBOUNDS_ERROR;
490            return 0;
491        }
492
493        outTrie=(UTrie2Header *)outData;
494
495        /* swap the header */
496        ds->swapArray32(ds, &inTrie->signature, 4, &outTrie->signature, pErrorCode);
497        ds->swapArray16(ds, &inTrie->options, 12, &outTrie->options, pErrorCode);
498
499        /* swap the index and the data */
500        switch(valueBits) {
501        case UTRIE2_16_VALUE_BITS:
502            ds->swapArray16(ds, inTrie+1, (trie.indexLength+dataLength)*2, outTrie+1, pErrorCode);
503            break;
504        case UTRIE2_32_VALUE_BITS:
505            ds->swapArray16(ds, inTrie+1, trie.indexLength*2, outTrie+1, pErrorCode);
506            ds->swapArray32(ds, (const uint16_t *)(inTrie+1)+trie.indexLength, dataLength*4,
507                                     (uint16_t *)(outTrie+1)+trie.indexLength, pErrorCode);
508            break;
509        default:
510            *pErrorCode=U_INVALID_FORMAT_ERROR;
511            return 0;
512        }
513    }
514
515    return size;
516}
517
518// utrie2_swapAnyVersion() should be defined here but lives in utrie2_builder.c
519// to avoid a dependency from utrie2.cpp on utrie.c.
520
521/* enumeration -------------------------------------------------------------- */
522
523#define MIN_VALUE(a, b) ((a)<(b) ? (a) : (b))
524
525/* default UTrie2EnumValue() returns the input value itself */
526static uint32_t U_CALLCONV
527enumSameValue(const void * /*context*/, uint32_t value) {
528    return value;
529}
530
531/**
532 * Enumerate all ranges of code points with the same relevant values.
533 * The values are transformed from the raw trie entries by the enumValue function.
534 *
535 * Currently requires start<limit and both start and limit must be multiples
536 * of UTRIE2_DATA_BLOCK_LENGTH.
537 *
538 * Optimizations:
539 * - Skip a whole block if we know that it is filled with a single value,
540 *   and it is the same as we visited just before.
541 * - Handle the null block specially because we know a priori that it is filled
542 *   with a single value.
543 */
544static void
545enumEitherTrie(const UTrie2 *trie,
546               UChar32 start, UChar32 limit,
547               UTrie2EnumValue *enumValue, UTrie2EnumRange *enumRange, const void *context) {
548    const uint32_t *data32;
549    const uint16_t *idx;
550
551    uint32_t value, prevValue, initialValue;
552    UChar32 c, prev, highStart;
553    int32_t j, i2Block, prevI2Block, index2NullOffset, block, prevBlock, nullBlock;
554
555    if(enumRange==NULL) {
556        return;
557    }
558    if(enumValue==NULL) {
559        enumValue=enumSameValue;
560    }
561
562    if(trie->newTrie==NULL) {
563        /* frozen trie */
564        idx=trie->index;
565        U_ASSERT(idx!=NULL); /* the following code assumes trie->newTrie is not NULL when idx is NULL */
566        data32=trie->data32;
567
568        index2NullOffset=trie->index2NullOffset;
569        nullBlock=trie->dataNullOffset;
570    } else {
571        /* unfrozen, mutable trie */
572        idx=NULL;
573        data32=trie->newTrie->data;
574        U_ASSERT(data32!=NULL); /* the following code assumes idx is not NULL when data32 is NULL */
575
576        index2NullOffset=trie->newTrie->index2NullOffset;
577        nullBlock=trie->newTrie->dataNullOffset;
578    }
579
580    highStart=trie->highStart;
581
582    /* get the enumeration value that corresponds to an initial-value trie data entry */
583    initialValue=enumValue(context, trie->initialValue);
584
585    /* set variables for previous range */
586    prevI2Block=-1;
587    prevBlock=-1;
588    prev=start;
589    prevValue=0;
590
591    /* enumerate index-2 blocks */
592    for(c=start; c<limit && c<highStart;) {
593        /* Code point limit for iterating inside this i2Block. */
594        UChar32 tempLimit=c+UTRIE2_CP_PER_INDEX_1_ENTRY;
595        if(limit<tempLimit) {
596            tempLimit=limit;
597        }
598        if(c<=0xffff) {
599            if(!U_IS_SURROGATE(c)) {
600                i2Block=c>>UTRIE2_SHIFT_2;
601            } else if(U_IS_SURROGATE_LEAD(c)) {
602                /*
603                 * Enumerate values for lead surrogate code points, not code units:
604                 * This special block has half the normal length.
605                 */
606                i2Block=UTRIE2_LSCP_INDEX_2_OFFSET;
607                tempLimit=MIN_VALUE(0xdc00, limit);
608            } else {
609                /*
610                 * Switch back to the normal part of the index-2 table.
611                 * Enumerate the second half of the surrogates block.
612                 */
613                i2Block=0xd800>>UTRIE2_SHIFT_2;
614                tempLimit=MIN_VALUE(0xe000, limit);
615            }
616        } else {
617            /* supplementary code points */
618            if(idx!=NULL) {
619                i2Block=idx[(UTRIE2_INDEX_1_OFFSET-UTRIE2_OMITTED_BMP_INDEX_1_LENGTH)+
620                              (c>>UTRIE2_SHIFT_1)];
621            } else {
622                i2Block=trie->newTrie->index1[c>>UTRIE2_SHIFT_1];
623            }
624            if(i2Block==prevI2Block && (c-prev)>=UTRIE2_CP_PER_INDEX_1_ENTRY) {
625                /*
626                 * The index-2 block is the same as the previous one, and filled with prevValue.
627                 * Only possible for supplementary code points because the linear-BMP index-2
628                 * table creates unique i2Block values.
629                 */
630                c+=UTRIE2_CP_PER_INDEX_1_ENTRY;
631                continue;
632            }
633        }
634        prevI2Block=i2Block;
635        if(i2Block==index2NullOffset) {
636            /* this is the null index-2 block */
637            if(prevValue!=initialValue) {
638                if(prev<c && !enumRange(context, prev, c-1, prevValue)) {
639                    return;
640                }
641                prevBlock=nullBlock;
642                prev=c;
643                prevValue=initialValue;
644            }
645            c+=UTRIE2_CP_PER_INDEX_1_ENTRY;
646        } else {
647            /* enumerate data blocks for one index-2 block */
648            int32_t i2, i2Limit;
649            i2=(c>>UTRIE2_SHIFT_2)&UTRIE2_INDEX_2_MASK;
650            if((c>>UTRIE2_SHIFT_1)==(tempLimit>>UTRIE2_SHIFT_1)) {
651                i2Limit=(tempLimit>>UTRIE2_SHIFT_2)&UTRIE2_INDEX_2_MASK;
652            } else {
653                i2Limit=UTRIE2_INDEX_2_BLOCK_LENGTH;
654            }
655            for(; i2<i2Limit; ++i2) {
656                if(idx!=NULL) {
657                    block=(int32_t)idx[i2Block+i2]<<UTRIE2_INDEX_SHIFT;
658                } else {
659                    block=trie->newTrie->index2[i2Block+i2];
660                }
661                if(block==prevBlock && (c-prev)>=UTRIE2_DATA_BLOCK_LENGTH) {
662                    /* the block is the same as the previous one, and filled with prevValue */
663                    c+=UTRIE2_DATA_BLOCK_LENGTH;
664                    continue;
665                }
666                prevBlock=block;
667                if(block==nullBlock) {
668                    /* this is the null data block */
669                    if(prevValue!=initialValue) {
670                        if(prev<c && !enumRange(context, prev, c-1, prevValue)) {
671                            return;
672                        }
673                        prev=c;
674                        prevValue=initialValue;
675                    }
676                    c+=UTRIE2_DATA_BLOCK_LENGTH;
677                } else {
678                    for(j=0; j<UTRIE2_DATA_BLOCK_LENGTH; ++j) {
679                        value=enumValue(context, data32!=NULL ? data32[block+j] : idx[block+j]);
680                        if(value!=prevValue) {
681                            if(prev<c && !enumRange(context, prev, c-1, prevValue)) {
682                                return;
683                            }
684                            prev=c;
685                            prevValue=value;
686                        }
687                        ++c;
688                    }
689                }
690            }
691        }
692    }
693
694    if(c>limit) {
695        c=limit;  /* could be higher if in the index2NullOffset */
696    } else if(c<limit) {
697        /* c==highStart<limit */
698        uint32_t highValue;
699        if(idx!=NULL) {
700            highValue=
701                data32!=NULL ?
702                    data32[trie->highValueIndex] :
703                    idx[trie->highValueIndex];
704        } else {
705            highValue=trie->newTrie->data[trie->newTrie->dataLength-UTRIE2_DATA_GRANULARITY];
706        }
707        value=enumValue(context, highValue);
708        if(value!=prevValue) {
709            if(prev<c && !enumRange(context, prev, c-1, prevValue)) {
710                return;
711            }
712            prev=c;
713            prevValue=value;
714        }
715        c=limit;
716    }
717
718    /* deliver last range */
719    enumRange(context, prev, c-1, prevValue);
720}
721
722U_CAPI void U_EXPORT2
723utrie2_enum(const UTrie2 *trie,
724            UTrie2EnumValue *enumValue, UTrie2EnumRange *enumRange, const void *context) {
725    enumEitherTrie(trie, 0, 0x110000, enumValue, enumRange, context);
726}
727
728U_CAPI void U_EXPORT2
729utrie2_enumForLeadSurrogate(const UTrie2 *trie, UChar32 lead,
730                            UTrie2EnumValue *enumValue, UTrie2EnumRange *enumRange,
731                            const void *context) {
732    if(!U16_IS_LEAD(lead)) {
733        return;
734    }
735    lead=(lead-0xd7c0)<<10;   /* start code point */
736    enumEitherTrie(trie, lead, lead+0x400, enumValue, enumRange, context);
737}
738
739/* C++ convenience wrappers ------------------------------------------------- */
740
741U_NAMESPACE_BEGIN
742
743uint16_t BackwardUTrie2StringIterator::previous16() {
744    codePointLimit=codePointStart;
745    if(start>=codePointStart) {
746        codePoint=U_SENTINEL;
747        return 0;
748    }
749    uint16_t result;
750    UTRIE2_U16_PREV16(trie, start, codePointStart, codePoint, result);
751    return result;
752}
753
754uint16_t ForwardUTrie2StringIterator::next16() {
755    codePointStart=codePointLimit;
756    if(codePointLimit==limit) {
757        codePoint=U_SENTINEL;
758        return 0;
759    }
760    uint16_t result;
761    UTRIE2_U16_NEXT16(trie, codePointLimit, limit, codePoint, result);
762    return result;
763}
764
765U_NAMESPACE_END
766