Check in the pristine copy of ICU 4.6...

icu46/source/common/utrie.c

+/*
+******************************************************************************
+*
+*   Copyright (C) 2001-2009, International Business Machines
+*   Corporation and others.  All Rights Reserved.
+*
+******************************************************************************
+*   file name:  utrie.c
+*   encoding:   US-ASCII
+*   tab size:   8 (not used)
+*   indentation:4
+*
+*   created on: 2001oct20
+*   created by: Markus W. Scherer
+*
+*   This is a common implementation of a "folded" trie.
+*   It is a kind of compressed, serializable table of 16- or 32-bit values associated with
+*   Unicode code points (0..0x10ffff).
+*/
+
+#ifdef UTRIE_DEBUG
+#   include <stdio.h>
+#endif
+
+#include "unicode/utypes.h"
+#include "cmemory.h"
+#include "utrie.h"
+
+/* miscellaneous ------------------------------------------------------------ */
+
+#undef ABS
+#define ABS(x) ((x)>=0 ? (x) : -(x))
+
+static U_INLINE UBool
+equal_uint32(const uint32_t *s, const uint32_t *t, int32_t length) {
+    while(length>0 && *s==*t) {
+        ++s;
+        ++t;
+        --length;
+    }
+    return (UBool)(length==0);
+}
+
+/* Building a trie ----------------------------------------------------------*/
+
+U_CAPI UNewTrie * U_EXPORT2
+utrie_open(UNewTrie *fillIn,
+           uint32_t *aliasData, int32_t maxDataLength,
+           uint32_t initialValue, uint32_t leadUnitValue,
+           UBool latin1Linear) {
+    UNewTrie *trie;
+    int32_t i, j;
+
+    if( maxDataLength<UTRIE_DATA_BLOCK_LENGTH ||
+        (latin1Linear && maxDataLength<1024)
+    ) {
+        return NULL;
+    }
+
+    if(fillIn!=NULL) {
+        trie=fillIn;
+    } else {
+        trie=(UNewTrie *)uprv_malloc(sizeof(UNewTrie));
+        if(trie==NULL) {
+            return NULL;
+        }
+    }
+    uprv_memset(trie, 0, sizeof(UNewTrie));
+    trie->isAllocated= (UBool)(fillIn==NULL);
+
+    if(aliasData!=NULL) {
+        trie->data=aliasData;
+        trie->isDataAllocated=FALSE;
+    } else {
+        trie->data=(uint32_t *)uprv_malloc(maxDataLength*4);
+        if(trie->data==NULL) {
+            uprv_free(trie);
+            return NULL;
+        }
+        trie->isDataAllocated=TRUE;
+    }
+
+    /* preallocate and reset the first data block (block index 0) */
+    j=UTRIE_DATA_BLOCK_LENGTH;
+
+    if(latin1Linear) {
+        /* preallocate and reset the first block (number 0) and Latin-1 (U+0000..U+00ff) after that */
+        /* made sure above that maxDataLength>=1024 */
+
+        /* set indexes to point to consecutive data blocks */
+        i=0;
+        do {
+            /* do this at least for trie->index[0] even if that block is only partly used for Latin-1 */
+            trie->index[i++]=j;
+            j+=UTRIE_DATA_BLOCK_LENGTH;
+        } while(i<(256>>UTRIE_SHIFT));
+    }
+
+    /* reset the initially allocated blocks to the initial value */
+    trie->dataLength=j;
+    while(j>0) {
+        trie->data[--j]=initialValue;
+    }
+
+    trie->leadUnitValue=leadUnitValue;
+    trie->indexLength=UTRIE_MAX_INDEX_LENGTH;
+    trie->dataCapacity=maxDataLength;
+    trie->isLatin1Linear=latin1Linear;
+    trie->isCompacted=FALSE;
+    return trie;
+}
+
+U_CAPI UNewTrie * U_EXPORT2
+utrie_clone(UNewTrie *fillIn, const UNewTrie *other, uint32_t *aliasData, int32_t aliasDataCapacity) {
+    UNewTrie *trie;
+    UBool isDataAllocated;
+
+    /* do not clone if other is not valid or already compacted */
+    if(other==NULL || other->data==NULL || other->isCompacted) {
+        return NULL;
+    }
+
+    /* clone data */
+    if(aliasData!=NULL && aliasDataCapacity>=other->dataCapacity) {
+        isDataAllocated=FALSE;
+    } else {
+        aliasDataCapacity=other->dataCapacity;
+        aliasData=(uint32_t *)uprv_malloc(other->dataCapacity*4);
+        if(aliasData==NULL) {
+            return NULL;
+        }
+        isDataAllocated=TRUE;
+    }
+
+    trie=utrie_open(fillIn, aliasData, aliasDataCapacity,
+                    other->data[0], other->leadUnitValue,
+                    other->isLatin1Linear);
+    if(trie==NULL) {
+        uprv_free(aliasData);
+    } else {
+        uprv_memcpy(trie->index, other->index, sizeof(trie->index));
+        uprv_memcpy(trie->data, other->data, other->dataLength*4);
+        trie->dataLength=other->dataLength;
+        trie->isDataAllocated=isDataAllocated;
+    }
+
+    return trie;
+}
+
+U_CAPI void U_EXPORT2
+utrie_close(UNewTrie *trie) {
+    if(trie!=NULL) {
+        if(trie->isDataAllocated) {
+            uprv_free(trie->data);
+            trie->data=NULL;
+        }
+        if(trie->isAllocated) {
+            uprv_free(trie);
+        }
+    }
+}
+
+U_CAPI uint32_t * U_EXPORT2
+utrie_getData(UNewTrie *trie, int32_t *pLength) {
+    if(trie==NULL || pLength==NULL) {
+        return NULL;
+    }
+
+    *pLength=trie->dataLength;
+    return trie->data;
+}
+
+static int32_t
+utrie_allocDataBlock(UNewTrie *trie) {
+    int32_t newBlock, newTop;
+
+    newBlock=trie->dataLength;
+    newTop=newBlock+UTRIE_DATA_BLOCK_LENGTH;
+    if(newTop>trie->dataCapacity) {
+        /* out of memory in the data array */
+        return -1;
+    }
+    trie->dataLength=newTop;
+    return newBlock;
+}
+
+/**
+ * No error checking for illegal arguments.
+ *
+ * @return -1 if no new data block available (out of memory in data array)
+ * @internal
+ */
+static int32_t
+utrie_getDataBlock(UNewTrie *trie, UChar32 c) {
+    int32_t indexValue, newBlock;
+
+    c>>=UTRIE_SHIFT;
+    indexValue=trie->index[c];
+    if(indexValue>0) {
+        return indexValue;
+    }
+
+    /* allocate a new data block */
+    newBlock=utrie_allocDataBlock(trie);
+    if(newBlock<0) {
+        /* out of memory in the data array */
+        return -1;
+    }
+    trie->index[c]=newBlock;
+
+    /* copy-on-write for a block from a setRange() */
+    uprv_memcpy(trie->data+newBlock, trie->data-indexValue, 4*UTRIE_DATA_BLOCK_LENGTH);
+    return newBlock;
+}
+
+/**
+ * @return TRUE if the value was successfully set
+ */
+U_CAPI UBool U_EXPORT2
+utrie_set32(UNewTrie *trie, UChar32 c, uint32_t value) {
+    int32_t block;
+
+    /* valid, uncompacted trie and valid c? */
+    if(trie==NULL || trie->isCompacted || (uint32_t)c>0x10ffff) {
+        return FALSE;
+    }
+
+    block=utrie_getDataBlock(trie, c);
+    if(block<0) {
+        return FALSE;
+    }
+
+    trie->data[block+(c&UTRIE_MASK)]=value;
+    return TRUE;
+}
+
+U_CAPI uint32_t U_EXPORT2
+utrie_get32(UNewTrie *trie, UChar32 c, UBool *pInBlockZero) {
+    int32_t block;
+
+    /* valid, uncompacted trie and valid c? */
+    if(trie==NULL || trie->isCompacted || (uint32_t)c>0x10ffff) {
+        if(pInBlockZero!=NULL) {
+            *pInBlockZero=TRUE;
+        }
+        return 0;
+    }
+
+    block=trie->index[c>>UTRIE_SHIFT];
+    if(pInBlockZero!=NULL) {
+        *pInBlockZero= (UBool)(block==0);
+    }
+
+    return trie->data[ABS(block)+(c&UTRIE_MASK)];
+}
+
+/**
+ * @internal
+ */
+static void
+utrie_fillBlock(uint32_t *block, UChar32 start, UChar32 limit,
+                uint32_t value, uint32_t initialValue, UBool overwrite) {
+    uint32_t *pLimit;
+
+    pLimit=block+limit;
+    block+=start;
+    if(overwrite) {
+        while(block<pLimit) {
+            *block++=value;
+        }
+    } else {
+        while(block<pLimit) {
+            if(*block==initialValue) {
+                *block=value;
+            }
+            ++block;
+        }
+    }
+}
+
+U_CAPI UBool U_EXPORT2
+utrie_setRange32(UNewTrie *trie, UChar32 start, UChar32 limit, uint32_t value, UBool overwrite) {
+    /*
+     * repeat value in [start..limit[
+     * mark index values for repeat-data blocks by setting bit 31 of the index values
+     * fill around existing values if any, if(overwrite)
+     */
+    uint32_t initialValue;
+    int32_t block, rest, repeatBlock;
+
+    /* valid, uncompacted trie and valid indexes? */
+    if( trie==NULL || trie->isCompacted ||
+        (uint32_t)start>0x10ffff || (uint32_t)limit>0x110000 || start>limit
+    ) {
+        return FALSE;
+    }
+    if(start==limit) {
+        return TRUE; /* nothing to do */
+    }
+
+    initialValue=trie->data[0];
+    if(start&UTRIE_MASK) {
+        UChar32 nextStart;
+
+        /* set partial block at [start..following block boundary[ */
+        block=utrie_getDataBlock(trie, start);
+        if(block<0) {
+            return FALSE;
+        }
+
+        nextStart=(start+UTRIE_DATA_BLOCK_LENGTH)&~UTRIE_MASK;
+        if(nextStart<=limit) {
+            utrie_fillBlock(trie->data+block, start&UTRIE_MASK, UTRIE_DATA_BLOCK_LENGTH,
+                            value, initialValue, overwrite);
+            start=nextStart;
+        } else {
+            utrie_fillBlock(trie->data+block, start&UTRIE_MASK, limit&UTRIE_MASK,
+                            value, initialValue, overwrite);
+            return TRUE;
+        }
+    }
+
+    /* number of positions in the last, partial block */
+    rest=limit&UTRIE_MASK;
+
+    /* round down limit to a block boundary */
+    limit&=~UTRIE_MASK;
+
+    /* iterate over all-value blocks */
+    if(value==initialValue) {
+        repeatBlock=0;
+    } else {
+        repeatBlock=-1;
+    }
+    while(start<limit) {
+        /* get index value */
+        block=trie->index[start>>UTRIE_SHIFT];
+        if(block>0) {
+            /* already allocated, fill in value */
+            utrie_fillBlock(trie->data+block, 0, UTRIE_DATA_BLOCK_LENGTH, value, initialValue, overwrite);
+        } else if(trie->data[-block]!=value && (block==0 || overwrite)) {
+            /* set the repeatBlock instead of the current block 0 or range block */
+            if(repeatBlock>=0) {
+                trie->index[start>>UTRIE_SHIFT]=-repeatBlock;
+            } else {
+                /* create and set and fill the repeatBlock */
+                repeatBlock=utrie_getDataBlock(trie, start);
+                if(repeatBlock<0) {
+                    return FALSE;
+                }
+
+                /* set the negative block number to indicate that it is a repeat block */
+                trie->index[start>>UTRIE_SHIFT]=-repeatBlock;
+                utrie_fillBlock(trie->data+repeatBlock, 0, UTRIE_DATA_BLOCK_LENGTH, value, initialValue, TRUE);
+            }
+        }
+
+        start+=UTRIE_DATA_BLOCK_LENGTH;
+    }
+
+    if(rest>0) {
+        /* set partial block at [last block boundary..limit[ */
+        block=utrie_getDataBlock(trie, start);
+        if(block<0) {
+            return FALSE;
+        }
+
+        utrie_fillBlock(trie->data+block, 0, rest, value, initialValue, overwrite);
+    }
+
+    return TRUE;
+}
+
+static int32_t
+_findSameIndexBlock(const int32_t *idx, int32_t indexLength,
+                    int32_t otherBlock) {
+    int32_t block, i;
+
+    for(block=UTRIE_BMP_INDEX_LENGTH; block<indexLength; block+=UTRIE_SURROGATE_BLOCK_COUNT) {
+        for(i=0; i<UTRIE_SURROGATE_BLOCK_COUNT; ++i) {
+            if(idx[block+i]!=idx[otherBlock+i]) {
+                break;
+            }
+        }
+        if(i==UTRIE_SURROGATE_BLOCK_COUNT) {
+            return block;
+        }
+    }
+    return indexLength;
+}
+
+/*
+ * Fold the normalization data for supplementary code points into
+ * a compact area on top of the BMP-part of the trie index,
+ * with the lead surrogates indexing this compact area.
+ *
+ * Duplicate the index values for lead surrogates:
+ * From inside the BMP area, where some may be overridden with folded values,
+ * to just after the BMP area, where they can be retrieved for
+ * code point lookups.
+ */
+static void
+utrie_fold(UNewTrie *trie, UNewTrieGetFoldedValue *getFoldedValue, UErrorCode *pErrorCode) {
+    int32_t leadIndexes[UTRIE_SURROGATE_BLOCK_COUNT];
+    int32_t *idx;
+    uint32_t value;
+    UChar32 c;
+    int32_t indexLength, block;
+#ifdef UTRIE_DEBUG
+    int countLeadCUWithData=0;
+#endif
+
+    idx=trie->index;
+
+    /* copy the lead surrogate indexes into a temporary array */
+    uprv_memcpy(leadIndexes, idx+(0xd800>>UTRIE_SHIFT), 4*UTRIE_SURROGATE_BLOCK_COUNT);
+
+    /*
+     * set all values for lead surrogate code *units* to leadUnitValue
+     * so that, by default, runtime lookups will find no data for associated
+     * supplementary code points, unless there is data for such code points
+     * which will result in a non-zero folding value below that is set for
+     * the respective lead units
+     *
+     * the above saved the indexes for surrogate code *points*
+     * fill the indexes with simplified code from utrie_setRange32()
+     */
+    if(trie->leadUnitValue==trie->data[0]) {
+        block=0; /* leadUnitValue==initialValue, use all-initial-value block */
+    } else {
+        /* create and fill the repeatBlock */
+        block=utrie_allocDataBlock(trie);
+        if(block<0) {
+            /* data table overflow */
+            *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
+            return;
+        }
+        utrie_fillBlock(trie->data+block, 0, UTRIE_DATA_BLOCK_LENGTH, trie->leadUnitValue, trie->data[0], TRUE);
+        block=-block; /* negative block number to indicate that it is a repeat block */
+    }
+    for(c=(0xd800>>UTRIE_SHIFT); c<(0xdc00>>UTRIE_SHIFT); ++c) {
+        trie->index[c]=block;
+    }
+
+    /*
+     * Fold significant index values into the area just after the BMP indexes.
+     * In case the first lead surrogate has significant data,
+     * its index block must be used first (in which case the folding is a no-op).
+     * Later all folded index blocks are moved up one to insert the copied
+     * lead surrogate indexes.
+     */
+    indexLength=UTRIE_BMP_INDEX_LENGTH;
+
+    /* search for any index (stage 1) entries for supplementary code points */
+    for(c=0x10000; c<0x110000;) {
+        if(idx[c>>UTRIE_SHIFT]!=0) {
+            /* there is data, treat the full block for a lead surrogate */
+            c&=~0x3ff;
+
+#ifdef UTRIE_DEBUG
+            ++countLeadCUWithData;
+            /* printf("supplementary data for lead surrogate U+%04lx\n", (long)(0xd7c0+(c>>10))); */
+#endif
+
+            /* is there an identical index block? */
+            block=_findSameIndexBlock(idx, indexLength, c>>UTRIE_SHIFT);
+
+            /*
+             * get a folded value for [c..c+0x400[ and,
+             * if different from the value for the lead surrogate code point,
+             * set it for the lead surrogate code unit
+             */
+            value=getFoldedValue(trie, c, block+UTRIE_SURROGATE_BLOCK_COUNT);
+            if(value!=utrie_get32(trie, U16_LEAD(c), NULL)) {
+                if(!utrie_set32(trie, U16_LEAD(c), value)) {
+                    /* data table overflow */
+                    *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
+                    return;
+                }
+
+                /* if we did not find an identical index block... */
+                if(block==indexLength) {
+                    /* move the actual index (stage 1) entries from the supplementary position to the new one */
+                    uprv_memmove(idx+indexLength,
+                                 idx+(c>>UTRIE_SHIFT),
+                                 4*UTRIE_SURROGATE_BLOCK_COUNT);
+                    indexLength+=UTRIE_SURROGATE_BLOCK_COUNT;
+                }
+            }
+            c+=0x400;
+        } else {
+            c+=UTRIE_DATA_BLOCK_LENGTH;
+        }
+    }
+#ifdef UTRIE_DEBUG
+    if(countLeadCUWithData>0) {
+        printf("supplementary data for %d lead surrogates\n", countLeadCUWithData);
+    }
+#endif
+
+    /*
+     * index array overflow?
+     * This is to guarantee that a folding offset is of the form
+     * UTRIE_BMP_INDEX_LENGTH+n*UTRIE_SURROGATE_BLOCK_COUNT with n=0..1023.
+     * If the index is too large, then n>=1024 and more than 10 bits are necessary.
+     *
+     * In fact, it can only ever become n==1024 with completely unfoldable data and
+     * the additional block of duplicated values for lead surrogates.
+     */
+    if(indexLength>=UTRIE_MAX_INDEX_LENGTH) {
+        *pErrorCode=U_INDEX_OUTOFBOUNDS_ERROR;
+        return;
+    }
+
+    /*
+     * make space for the lead surrogate index block and
+     * insert it between the BMP indexes and the folded ones
+     */
+    uprv_memmove(idx+UTRIE_BMP_INDEX_LENGTH+UTRIE_SURROGATE_BLOCK_COUNT,
+                 idx+UTRIE_BMP_INDEX_LENGTH,
+                 4*(indexLength-UTRIE_BMP_INDEX_LENGTH));
+    uprv_memcpy(idx+UTRIE_BMP_INDEX_LENGTH,
+                leadIndexes,
+                4*UTRIE_SURROGATE_BLOCK_COUNT);
+    indexLength+=UTRIE_SURROGATE_BLOCK_COUNT;
+
+#ifdef UTRIE_DEBUG
+    printf("trie index count: BMP %ld  all Unicode %ld  folded %ld\n",
+           UTRIE_BMP_INDEX_LENGTH, (long)UTRIE_MAX_INDEX_LENGTH, indexLength);
+#endif
+
+    trie->indexLength=indexLength;
+}
+
+/*
+ * Set a value in the trie index map to indicate which data block
+ * is referenced and which one is not.
+ * utrie_compact() will remove data blocks that are not used at all.
+ * Set
+ * - 0 if it is used
+ * - -1 if it is not used
+ */
+static void
+_findUnusedBlocks(UNewTrie *trie) {
+    int32_t i;
+
+    /* fill the entire map with "not used" */
+    uprv_memset(trie->map, 0xff, (UTRIE_MAX_BUILD_TIME_DATA_LENGTH>>UTRIE_SHIFT)*4);
+
+    /* mark each block that _is_ used with 0 */
+    for(i=0; i<trie->indexLength; ++i) {
+        trie->map[ABS(trie->index[i])>>UTRIE_SHIFT]=0;
+    }
+
+    /* never move the all-initial-value block 0 */
+    trie->map[0]=0;
+}
+
+static int32_t
+_findSameDataBlock(const uint32_t *data, int32_t dataLength,
+                   int32_t otherBlock, int32_t step) {
+    int32_t block;
+
+    /* ensure that we do not even partially get past dataLength */
+    dataLength-=UTRIE_DATA_BLOCK_LENGTH;
+
+    for(block=0; block<=dataLength; block+=step) {
+        if(equal_uint32(data+block, data+otherBlock, UTRIE_DATA_BLOCK_LENGTH)) {
+            return block;
+        }
+    }
+    return -1;
+}
+
+/*
+ * Compact a folded build-time trie.
+ *
+ * The compaction
+ * - removes blocks that are identical with earlier ones
+ * - overlaps adjacent blocks as much as possible (if overlap==TRUE)
+ * - moves blocks in steps of the data granularity
+ * - moves and overlaps blocks that overlap with multiple values in the overlap region
+ *
+ * It does not
+ * - try to move and overlap blocks that are not already adjacent
+ */
+static void
+utrie_compact(UNewTrie *trie, UBool overlap, UErrorCode *pErrorCode) {
+    int32_t i, start, newStart, overlapStart;
+
+    if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
+        return;
+    }
+
+    /* valid, uncompacted trie? */
+    if(trie==NULL) {
+        *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
+        return;
+    }
+    if(trie->isCompacted) {
+        return; /* nothing left to do */
+    }
+
+    /* compaction */
+
+    /* initialize the index map with "block is used/unused" flags */
+    _findUnusedBlocks(trie);
+
+    /* if Latin-1 is preallocated and linear, then do not compact Latin-1 data */
+    if(trie->isLatin1Linear && UTRIE_SHIFT<=8) {
+        overlapStart=UTRIE_DATA_BLOCK_LENGTH+256;
+    } else {
+        overlapStart=UTRIE_DATA_BLOCK_LENGTH;
+    }
+
+    newStart=UTRIE_DATA_BLOCK_LENGTH;
+    for(start=newStart; start<trie->dataLength;) {
+        /*
+         * start: index of first entry of current block
+         * newStart: index where the current block is to be moved
+         *           (right after current end of already-compacted data)
+         */
+
+        /* skip blocks that are not used */
+        if(trie->map[start>>UTRIE_SHIFT]<0) {
+            /* advance start to the next block */
+            start+=UTRIE_DATA_BLOCK_LENGTH;
+
+            /* leave newStart with the previous block! */
+            continue;
+        }
+
+        /* search for an identical block */
+        if( start>=overlapStart &&
+            (i=_findSameDataBlock(trie->data, newStart, start,
+                            overlap ? UTRIE_DATA_GRANULARITY : UTRIE_DATA_BLOCK_LENGTH))
+             >=0
+        ) {
+            /* found an identical block, set the other block's index value for the current block */
+            trie->map[start>>UTRIE_SHIFT]=i;
+
+            /* advance start to the next block */
+            start+=UTRIE_DATA_BLOCK_LENGTH;
+
+            /* leave newStart with the previous block! */
+            continue;
+        }
+
+        /* see if the beginning of this block can be overlapped with the end of the previous block */
+        if(overlap && start>=overlapStart) {
+            /* look for maximum overlap (modulo granularity) with the previous, adjacent block */
+            for(i=UTRIE_DATA_BLOCK_LENGTH-UTRIE_DATA_GRANULARITY;
+                i>0 && !equal_uint32(trie->data+(newStart-i), trie->data+start, i);
+                i-=UTRIE_DATA_GRANULARITY) {}
+        } else {
+            i=0;
+        }
+
+        if(i>0) {
+            /* some overlap */
+            trie->map[start>>UTRIE_SHIFT]=newStart-i;
+
+            /* move the non-overlapping indexes to their new positions */
+            start+=i;
+            for(i=UTRIE_DATA_BLOCK_LENGTH-i; i>0; --i) {
+                trie->data[newStart++]=trie->data[start++];
+            }
+        } else if(newStart<start) {
+            /* no overlap, just move the indexes to their new positions */
+            trie->map[start>>UTRIE_SHIFT]=newStart;
+            for(i=UTRIE_DATA_BLOCK_LENGTH; i>0; --i) {
+                trie->data[newStart++]=trie->data[start++];
+            }
+        } else /* no overlap && newStart==start */ {
+            trie->map[start>>UTRIE_SHIFT]=start;
+            newStart+=UTRIE_DATA_BLOCK_LENGTH;
+            start=newStart;
+        }
+    }
+
+    /* now adjust the index (stage 1) table */
+    for(i=0; i<trie->indexLength; ++i) {
+        trie->index[i]=trie->map[ABS(trie->index[i])>>UTRIE_SHIFT];
+    }
+
+#ifdef UTRIE_DEBUG
+    /* we saved some space */
+    printf("compacting trie: count of 32-bit words %lu->%lu\n",
+            (long)trie->dataLength, (long)newStart);
+#endif
+
+    trie->dataLength=newStart;
+}
+
+/* serialization ------------------------------------------------------------ */
+
+/*
+ * Default function for the folding value:
+ * Just store the offset (16 bits) if there is any non-initial-value entry.
+ *
+ * The offset parameter is never 0.
+ * Returning the offset itself is safe for UTRIE_SHIFT>=5 because
+ * for UTRIE_SHIFT==5 the maximum index length is UTRIE_MAX_INDEX_LENGTH==0x8800
+ * which fits into 16-bit trie values;
+ * for higher UTRIE_SHIFT, UTRIE_MAX_INDEX_LENGTH decreases.
+ *
+ * Theoretically, it would be safer for all possible UTRIE_SHIFT including
+ * those of 4 and lower to return offset>>UTRIE_SURROGATE_BLOCK_BITS
+ * which would always result in a value of 0x40..0x43f
+ * (start/end 1k blocks of supplementary Unicode code points).
+ * However, this would be uglier, and would not work for some existing
+ * binary data file formats.
+ *
+ * Also, we do not plan to change UTRIE_SHIFT because it would change binary
+ * data file formats, and we would probably not make it smaller because of
+ * the then even larger BMP index length even for empty tries.
+ */
+static uint32_t U_CALLCONV
+defaultGetFoldedValue(UNewTrie *trie, UChar32 start, int32_t offset) {
+    uint32_t value, initialValue;
+    UChar32 limit;
+    UBool inBlockZero;
+
+    initialValue=trie->data[0];
+    limit=start+0x400;
+    while(start<limit) {
+        value=utrie_get32(trie, start, &inBlockZero);
+        if(inBlockZero) {
+            start+=UTRIE_DATA_BLOCK_LENGTH;
+        } else if(value!=initialValue) {
+            return (uint32_t)offset;
+        } else {
+            ++start;
+        }
+    }
+    return 0;
+}
+
+U_CAPI int32_t U_EXPORT2
+utrie_serialize(UNewTrie *trie, void *dt, int32_t capacity,
+                UNewTrieGetFoldedValue *getFoldedValue,
+                UBool reduceTo16Bits,
+                UErrorCode *pErrorCode) {
+    UTrieHeader *header;
+    uint32_t *p;
+    uint16_t *dest16;
+    int32_t i, length;
+    uint8_t* data = NULL;
+
+    /* argument check */
+    if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
+        return 0;
+    }
+
+    if(trie==NULL || capacity<0 || (capacity>0 && dt==NULL)) {
+        *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
+        return 0;
+    }
+    if(getFoldedValue==NULL) {
+        getFoldedValue=defaultGetFoldedValue;
+    }
+
+    data = (uint8_t*)dt;
+    /* fold and compact if necessary, also checks that indexLength is within limits */
+    if(!trie->isCompacted) {
+        /* compact once without overlap to improve folding */
+        utrie_compact(trie, FALSE, pErrorCode);
+
+        /* fold the supplementary part of the index array */
+        utrie_fold(trie, getFoldedValue, pErrorCode);
+
+        /* compact again with overlap for minimum data array length */
+        utrie_compact(trie, TRUE, pErrorCode);
+
+        trie->isCompacted=TRUE;
+        if(U_FAILURE(*pErrorCode)) {
+            return 0;
+        }
+    }
+
+    /* is dataLength within limits? */
+    if( (reduceTo16Bits ? (trie->dataLength+trie->indexLength) : trie->dataLength) >= UTRIE_MAX_DATA_LENGTH) {
+        *pErrorCode=U_INDEX_OUTOFBOUNDS_ERROR;
+    }
+
+    length=sizeof(UTrieHeader)+2*trie->indexLength;
+    if(reduceTo16Bits) {
+        length+=2*trie->dataLength;
+    } else {
+        length+=4*trie->dataLength;
+    }
+
+    if(length>capacity) {
+        return length; /* preflighting */
+    }
+
+#ifdef UTRIE_DEBUG
+    printf("**UTrieLengths(serialize)** index:%6ld  data:%6ld  serialized:%6ld\n",
+           (long)trie->indexLength, (long)trie->dataLength, (long)length);
+#endif
+
+    /* set the header fields */
+    header=(UTrieHeader *)data;
+    data+=sizeof(UTrieHeader);
+
+    header->signature=0x54726965; /* "Trie" */
+    header->options=UTRIE_SHIFT | (UTRIE_INDEX_SHIFT<<UTRIE_OPTIONS_INDEX_SHIFT);
+
+    if(!reduceTo16Bits) {
+        header->options|=UTRIE_OPTIONS_DATA_IS_32_BIT;
+    }
+    if(trie->isLatin1Linear) {
+        header->options|=UTRIE_OPTIONS_LATIN1_IS_LINEAR;
+    }
+
+    header->indexLength=trie->indexLength;
+    header->dataLength=trie->dataLength;
+
+    /* write the index (stage 1) array and the 16/32-bit data (stage 2) array */
+    if(reduceTo16Bits) {
+        /* write 16-bit index values shifted right by UTRIE_INDEX_SHIFT, after adding indexLength */
+        p=(uint32_t *)trie->index;
+        dest16=(uint16_t *)data;
+        for(i=trie->indexLength; i>0; --i) {
+            *dest16++=(uint16_t)((*p++ + trie->indexLength)>>UTRIE_INDEX_SHIFT);
+        }
+
+        /* write 16-bit data values */
+        p=trie->data;
+        for(i=trie->dataLength; i>0; --i) {
+            *dest16++=(uint16_t)*p++;
+        }
+    } else {
+        /* write 16-bit index values shifted right by UTRIE_INDEX_SHIFT */
+        p=(uint32_t *)trie->index;
+        dest16=(uint16_t *)data;
+        for(i=trie->indexLength; i>0; --i) {
+            *dest16++=(uint16_t)(*p++ >> UTRIE_INDEX_SHIFT);
+        }
+
+        /* write 32-bit data values */
+        uprv_memcpy(dest16, trie->data, 4*trie->dataLength);
+    }
+
+    return length;
+}
+
+/* inverse to defaultGetFoldedValue() */
+U_CAPI int32_t U_EXPORT2
+utrie_defaultGetFoldingOffset(uint32_t data) {
+    return (int32_t)data;
+}
+
+U_CAPI int32_t U_EXPORT2
+utrie_unserialize(UTrie *trie, const void *data, int32_t length, UErrorCode *pErrorCode) {
+    const UTrieHeader *header;
+    const uint16_t *p16;
+    uint32_t options;
+
+    if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
+        return -1;
+    }
+
+    /* enough data for a trie header? */
+    if(length<sizeof(UTrieHeader)) {
+        *pErrorCode=U_INVALID_FORMAT_ERROR;
+        return -1;
+    }
+
+    /* check the signature */
+    header=(const UTrieHeader *)data;
+    if(header->signature!=0x54726965) {
+        *pErrorCode=U_INVALID_FORMAT_ERROR;
+        return -1;
+    }
+
+    /* get the options and check the shift values */
+    options=header->options;
+    if( (options&UTRIE_OPTIONS_SHIFT_MASK)!=UTRIE_SHIFT ||
+        ((options>>UTRIE_OPTIONS_INDEX_SHIFT)&UTRIE_OPTIONS_SHIFT_MASK)!=UTRIE_INDEX_SHIFT
+    ) {
+        *pErrorCode=U_INVALID_FORMAT_ERROR;
+        return -1;
+    }
+    trie->isLatin1Linear= (UBool)((options&UTRIE_OPTIONS_LATIN1_IS_LINEAR)!=0);
+
+    /* get the length values */
+    trie->indexLength=header->indexLength;
+    trie->dataLength=header->dataLength;
+
+    length-=(int32_t)sizeof(UTrieHeader);
+
+    /* enough data for the index? */
+    if(length<2*trie->indexLength) {
+        *pErrorCode=U_INVALID_FORMAT_ERROR;
+        return -1;
+    }
+    p16=(const uint16_t *)(header+1);
+    trie->index=p16;
+    p16+=trie->indexLength;
+    length-=2*trie->indexLength;
+
+    /* get the data */
+    if(options&UTRIE_OPTIONS_DATA_IS_32_BIT) {
+        if(length<4*trie->dataLength) {
+            *pErrorCode=U_INVALID_FORMAT_ERROR;
+            return -1;
+        }
+        trie->data32=(const uint32_t *)p16;
+        trie->initialValue=trie->data32[0];
+        length=(int32_t)sizeof(UTrieHeader)+2*trie->indexLength+4*trie->dataLength;
+    } else {
+        if(length<2*trie->dataLength) {
+            *pErrorCode=U_INVALID_FORMAT_ERROR;
+            return -1;
+        }
+
+        /* the "data16" data is used via the index pointer */
+        trie->data32=NULL;
+        trie->initialValue=trie->index[trie->indexLength];
+        length=(int32_t)sizeof(UTrieHeader)+2*trie->indexLength+2*trie->dataLength;
+    }
+
+    trie->getFoldingOffset=utrie_defaultGetFoldingOffset;
+
+    return length;
+}
+
+U_CAPI int32_t U_EXPORT2
+utrie_unserializeDummy(UTrie *trie,
+                       void *data, int32_t length,
+                       uint32_t initialValue, uint32_t leadUnitValue,
+                       UBool make16BitTrie,
+                       UErrorCode *pErrorCode) {
+    uint16_t *p16;
+    int32_t actualLength, latin1Length, i, limit;
+    uint16_t block;
+
+    if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
+        return -1;
+    }
+
+    /* calculate the actual size of the dummy trie data */
+
+    /* max(Latin-1, block 0) */
+    latin1Length= UTRIE_SHIFT<=8 ? 256 : UTRIE_DATA_BLOCK_LENGTH;
+
+    trie->indexLength=UTRIE_BMP_INDEX_LENGTH+UTRIE_SURROGATE_BLOCK_COUNT;
+    trie->dataLength=latin1Length;
+    if(leadUnitValue!=initialValue) {
+        trie->dataLength+=UTRIE_DATA_BLOCK_LENGTH;
+    }
+
+    actualLength=trie->indexLength*2;
+    if(make16BitTrie) {
+        actualLength+=trie->dataLength*2;
+    } else {
+        actualLength+=trie->dataLength*4;
+    }
+
+    /* enough space for the dummy trie? */
+    if(length<actualLength) {
+        *pErrorCode=U_BUFFER_OVERFLOW_ERROR;
+        return actualLength;
+    }
+
+    trie->isLatin1Linear=TRUE;
+    trie->initialValue=initialValue;
+
+    /* fill the index and data arrays */
+    p16=(uint16_t *)data;
+    trie->index=p16;
+
+    if(make16BitTrie) {
+        /* indexes to block 0 */
+        block=(uint16_t)(trie->indexLength>>UTRIE_INDEX_SHIFT);
+        limit=trie->indexLength;
+        for(i=0; i<limit; ++i) {
+            p16[i]=block;
+        }
+
+        if(leadUnitValue!=initialValue) {
+            /* indexes for lead surrogate code units to the block after Latin-1 */
+            block+=(uint16_t)(latin1Length>>UTRIE_INDEX_SHIFT);
+            i=0xd800>>UTRIE_SHIFT;
+            limit=0xdc00>>UTRIE_SHIFT;
+            for(; i<limit; ++i) {
+                p16[i]=block;
+            }
+        }
+
+        trie->data32=NULL;
+
+        /* Latin-1 data */
+        p16+=trie->indexLength;
+        for(i=0; i<latin1Length; ++i) {
+            p16[i]=(uint16_t)initialValue;
+        }
+
+        /* data for lead surrogate code units */
+        if(leadUnitValue!=initialValue) {
+            limit=latin1Length+UTRIE_DATA_BLOCK_LENGTH;
+            for(/* i=latin1Length */; i<limit; ++i) {
+                p16[i]=(uint16_t)leadUnitValue;
+            }
+        }
+    } else {
+        uint32_t *p32;
+
+        /* indexes to block 0 */
+        uprv_memset(p16, 0, trie->indexLength*2);
+
+        if(leadUnitValue!=initialValue) {
+            /* indexes for lead surrogate code units to the block after Latin-1 */
+            block=(uint16_t)(latin1Length>>UTRIE_INDEX_SHIFT);
+            i=0xd800>>UTRIE_SHIFT;
+            limit=0xdc00>>UTRIE_SHIFT;
+            for(; i<limit; ++i) {
+                p16[i]=block;
+            }
+        }
+
+        trie->data32=p32=(uint32_t *)(p16+trie->indexLength);
+
+        /* Latin-1 data */
+        for(i=0; i<latin1Length; ++i) {
+            p32[i]=initialValue;
+        }
+
+        /* data for lead surrogate code units */
+        if(leadUnitValue!=initialValue) {
+            limit=latin1Length+UTRIE_DATA_BLOCK_LENGTH;
+            for(/* i=latin1Length */; i<limit; ++i) {
+                p32[i]=leadUnitValue;
+            }
+        }
+    }
+
+    trie->getFoldingOffset=utrie_defaultGetFoldingOffset;
+
+    return actualLength;
+}
+
+/* enumeration -------------------------------------------------------------- */
+
+/* default UTrieEnumValue() returns the input value itself */
+static uint32_t U_CALLCONV
+enumSameValue(const void *context, uint32_t value) {
+    return value;
+}
+
+/**
+ * Enumerate all ranges of code points with the same relevant values.
+ * The values are transformed from the raw trie entries by the enumValue function.
+ */
+U_CAPI void U_EXPORT2
+utrie_enum(const UTrie *trie,
+           UTrieEnumValue *enumValue, UTrieEnumRange *enumRange, const void *context) {
+    const uint32_t *data32;
+    const uint16_t *idx;
+
+    uint32_t value, prevValue, initialValue;
+    UChar32 c, prev;
+    int32_t l, i, j, block, prevBlock, nullBlock, offset;
+
+    /* check arguments */
+    if(trie==NULL || trie->index==NULL || enumRange==NULL) {
+        return;
+    }
+    if(enumValue==NULL) {
+        enumValue=enumSameValue;
+    }
+
+    idx=trie->index;
+    data32=trie->data32;
+
+    /* get the enumeration value that corresponds to an initial-value trie data entry */
+    initialValue=enumValue(context, trie->initialValue);
+
+    if(data32==NULL) {
+        nullBlock=trie->indexLength;
+    } else {
+        nullBlock=0;
+    }
+
+    /* set variables for previous range */
+    prevBlock=nullBlock;
+    prev=0;
+    prevValue=initialValue;
+
+    /* enumerate BMP - the main loop enumerates data blocks */
+    for(i=0, c=0; c<=0xffff; ++i) {
+        if(c==0xd800) {
+            /* skip lead surrogate code _units_, go to lead surr. code _points_ */
+            i=UTRIE_BMP_INDEX_LENGTH;
+        } else if(c==0xdc00) {
+            /* go back to regular BMP code points */
+            i=c>>UTRIE_SHIFT;
+        }
+
+        block=idx[i]<<UTRIE_INDEX_SHIFT;
+        if(block==prevBlock) {
+            /* the block is the same as the previous one, and filled with value */
+            c+=UTRIE_DATA_BLOCK_LENGTH;
+        } else if(block==nullBlock) {
+            /* this is the all-initial-value block */
+            if(prevValue!=initialValue) {
+                if(prev<c) {
+                    if(!enumRange(context, prev, c, prevValue)) {
+                        return;
+                    }
+                }
+                prevBlock=nullBlock;
+                prev=c;
+                prevValue=initialValue;
+            }
+            c+=UTRIE_DATA_BLOCK_LENGTH;
+        } else {
+            prevBlock=block;
+            for(j=0; j<UTRIE_DATA_BLOCK_LENGTH; ++j) {
+                value=enumValue(context, data32!=NULL ? data32[block+j] : idx[block+j]);
+                if(value!=prevValue) {
+                    if(prev<c) {
+                        if(!enumRange(context, prev, c, prevValue)) {
+                            return;
+                        }
+                    }
+                    if(j>0) {
+                        /* the block is not filled with all the same value */
+                        prevBlock=-1;
+                    }
+                    prev=c;
+                    prevValue=value;
+                }
+                ++c;
+            }
+        }
+    }
+
+    /* enumerate supplementary code points */
+    for(l=0xd800; l<0xdc00;) {
+        /* lead surrogate access */
+        offset=idx[l>>UTRIE_SHIFT]<<UTRIE_INDEX_SHIFT;
+        if(offset==nullBlock) {
+            /* no entries for a whole block of lead surrogates */
+            if(prevValue!=initialValue) {
+                if(prev<c) {
+                    if(!enumRange(context, prev, c, prevValue)) {
+                        return;
+                    }
+                }
+                prevBlock=nullBlock;
+                prev=c;
+                prevValue=initialValue;
+            }
+
+            l+=UTRIE_DATA_BLOCK_LENGTH;
+            c+=UTRIE_DATA_BLOCK_LENGTH<<10;
+            continue;
+        }
+
+        value= data32!=NULL ? data32[offset+(l&UTRIE_MASK)] : idx[offset+(l&UTRIE_MASK)];
+
+        /* enumerate trail surrogates for this lead surrogate */
+        offset=trie->getFoldingOffset(value);
+        if(offset<=0) {
+            /* no data for this lead surrogate */
+            if(prevValue!=initialValue) {
+                if(prev<c) {
+                    if(!enumRange(context, prev, c, prevValue)) {
+                        return;
+                    }
+                }
+                prevBlock=nullBlock;
+                prev=c;
+                prevValue=initialValue;
+            }
+
+            /* nothing else to do for the supplementary code points for this lead surrogate */
+            c+=0x400;
+        } else {
+            /* enumerate code points for this lead surrogate */
+            i=offset;
+            offset+=UTRIE_SURROGATE_BLOCK_COUNT;
+            do {
+                /* copy of most of the body of the BMP loop */
+                block=idx[i]<<UTRIE_INDEX_SHIFT;
+                if(block==prevBlock) {
+                    /* the block is the same as the previous one, and filled with value */
+                    c+=UTRIE_DATA_BLOCK_LENGTH;
+                } else if(block==nullBlock) {
+                    /* this is the all-initial-value block */
+                    if(prevValue!=initialValue) {
+                        if(prev<c) {
+                            if(!enumRange(context, prev, c, prevValue)) {
+                                return;
+                            }
+                        }
+                        prevBlock=nullBlock;
+                        prev=c;
+                        prevValue=initialValue;
+                    }
+                    c+=UTRIE_DATA_BLOCK_LENGTH;
+                } else {
+                    prevBlock=block;
+                    for(j=0; j<UTRIE_DATA_BLOCK_LENGTH; ++j) {
+                        value=enumValue(context, data32!=NULL ? data32[block+j] : idx[block+j]);
+                        if(value!=prevValue) {
+                            if(prev<c) {
+                                if(!enumRange(context, prev, c, prevValue)) {
+                                    return;
+                                }
+                            }
+                            if(j>0) {
+                                /* the block is not filled with all the same value */
+                                prevBlock=-1;
+                            }
+                            prev=c;
+                            prevValue=value;
+                        }
+                        ++c;
+                    }
+                }
+            } while(++i<offset);
+        }
+
+        ++l;
+    }
+
+    /* deliver last range */
+    enumRange(context, prev, c, prevValue);
+}