Home | History | Annotate | Download | only in common
      1 /*
      2 ******************************************************************************
      3 *
      4 *   Copyright (C) 2001-2014, International Business Machines
      5 *   Corporation and others.  All Rights Reserved.
      6 *
      7 ******************************************************************************
      8 *   file name:  utrie2.h
      9 *   encoding:   US-ASCII
     10 *   tab size:   8 (not used)
     11 *   indentation:4
     12 *
     13 *   created on: 2008aug16 (starting from a copy of utrie.h)
     14 *   created by: Markus W. Scherer
     15 */
     16 
     17 #ifndef __UTRIE2_H__
     18 #define __UTRIE2_H__
     19 
     20 #include "unicode/utypes.h"
     21 #include "putilimp.h"
     22 #include "udataswp.h"
     23 
     24 U_CDECL_BEGIN
     25 
     26 struct UTrie;  /* forward declaration */
     27 #ifndef __UTRIE_H__
     28 typedef struct UTrie UTrie;
     29 #endif
     30 
     31 /**
     32  * \file
     33  *
     34  * This is a common implementation of a Unicode trie.
     35  * It is a kind of compressed, serializable table of 16- or 32-bit values associated with
     36  * Unicode code points (0..0x10ffff). (A map from code points to integers.)
     37  *
     38  * This is the second common version of a Unicode trie (hence the name UTrie2).
     39  * Compared with UTrie version 1:
     40  * - Still splitting BMP code points 11:5 bits for index and data table lookups.
     41  * - Still separate data for lead surrogate code _units_ vs. code _points_,
     42  *   but the lead surrogate code unit values are not required any more
     43  *   for data lookup for supplementary code points.
     44  * - The "folding" mechanism is removed. In UTrie version 1, this somewhat
     45  *   hard-to-explain mechanism was meant to be used for optimized UTF-16
     46  *   processing, with application-specific encoding of indexing bits
     47  *   in the lead surrogate data for the associated supplementary code points.
     48  * - For the last single-value code point range (ending with U+10ffff),
     49  *   the starting code point ("highStart") and the value are stored.
     50  * - For supplementary code points U+10000..highStart-1 a three-table lookup
     51  *   (two index tables and one data table) is used. The first index
     52  *   is truncated, omitting both the BMP portion and the high range.
     53  * - There is a special small index for 2-byte UTF-8, and the initial data
     54  *   entries are designed for fast 1/2-byte UTF-8 lookup.
     55  */
     56 
     57 /**
     58  * Trie structure.
     59  * Use only with public API macros and functions.
     60  */
     61 struct UTrie2;
     62 typedef struct UTrie2 UTrie2;
     63 
     64 /* Public UTrie2 API functions: read-only access ---------------------------- */
     65 
     66 /**
     67  * Selectors for the width of a UTrie2 data value.
     68  */
     69 enum UTrie2ValueBits {
     70     /** 16 bits per UTrie2 data value. */
     71     UTRIE2_16_VALUE_BITS,
     72     /** 32 bits per UTrie2 data value. */
     73     UTRIE2_32_VALUE_BITS,
     74     /** Number of selectors for the width of UTrie2 data values. */
     75     UTRIE2_COUNT_VALUE_BITS
     76 };
     77 typedef enum UTrie2ValueBits UTrie2ValueBits;
     78 
     79 /**
     80  * Open a frozen trie from its serialized from, stored in 32-bit-aligned memory.
     81  * Inverse of utrie2_serialize().
     82  * The memory must remain valid and unchanged as long as the trie is used.
     83  * You must utrie2_close() the trie once you are done using it.
     84  *
     85  * @param valueBits selects the data entry size; results in an
     86  *                  U_INVALID_FORMAT_ERROR if it does not match the serialized form
     87  * @param data a pointer to 32-bit-aligned memory containing the serialized form of a UTrie2
     88  * @param length the number of bytes available at data;
     89  *               can be more than necessary
     90  * @param pActualLength receives the actual number of bytes at data taken up by the trie data;
     91  *                      can be NULL
     92  * @param pErrorCode an in/out ICU UErrorCode
     93  * @return the unserialized trie
     94  *
     95  * @see utrie2_open
     96  * @see utrie2_serialize
     97  */
     98 U_CAPI UTrie2 * U_EXPORT2
     99 utrie2_openFromSerialized(UTrie2ValueBits valueBits,
    100                           const void *data, int32_t length, int32_t *pActualLength,
    101                           UErrorCode *pErrorCode);
    102 
    103 /**
    104  * Open a frozen, empty "dummy" trie.
    105  * A dummy trie is an empty trie, used when a real data trie cannot
    106  * be loaded. Equivalent to calling utrie2_open() and utrie2_freeze(),
    107  * but without internally creating and compacting/serializing the
    108  * builder data structure.
    109  *
    110  * The trie always returns the initialValue,
    111  * or the errorValue for out-of-range code points and illegal UTF-8.
    112  *
    113  * You must utrie2_close() the trie once you are done using it.
    114  *
    115  * @param valueBits selects the data entry size
    116  * @param initialValue the initial value that is set for all code points
    117  * @param errorValue the value for out-of-range code points and illegal UTF-8
    118  * @param pErrorCode an in/out ICU UErrorCode
    119  * @return the dummy trie
    120  *
    121  * @see utrie2_openFromSerialized
    122  * @see utrie2_open
    123  */
    124 U_CAPI UTrie2 * U_EXPORT2
    125 utrie2_openDummy(UTrie2ValueBits valueBits,
    126                  uint32_t initialValue, uint32_t errorValue,
    127                  UErrorCode *pErrorCode);
    128 
    129 /**
    130  * Get a value from a code point as stored in the trie.
    131  * Easier to use than UTRIE2_GET16() and UTRIE2_GET32() but slower.
    132  * Easier to use because, unlike the macros, this function works on all UTrie2
    133  * objects, frozen or not, holding 16-bit or 32-bit data values.
    134  *
    135  * @param trie the trie
    136  * @param c the code point
    137  * @return the value
    138  */
    139 U_CAPI uint32_t U_EXPORT2
    140 utrie2_get32(const UTrie2 *trie, UChar32 c);
    141 
    142 /* enumeration callback types */
    143 
    144 /**
    145  * Callback from utrie2_enum(), extracts a uint32_t value from a
    146  * trie value. This value will be passed on to the UTrie2EnumRange function.
    147  *
    148  * @param context an opaque pointer, as passed into utrie2_enum()
    149  * @param value a value from the trie
    150  * @return the value that is to be passed on to the UTrie2EnumRange function
    151  */
    152 typedef uint32_t U_CALLCONV
    153 UTrie2EnumValue(const void *context, uint32_t value);
    154 
    155 /**
    156  * Callback from utrie2_enum(), is called for each contiguous range
    157  * of code points with the same value as retrieved from the trie and
    158  * transformed by the UTrie2EnumValue function.
    159  *
    160  * The callback function can stop the enumeration by returning FALSE.
    161  *
    162  * @param context an opaque pointer, as passed into utrie2_enum()
    163  * @param start the first code point in a contiguous range with value
    164  * @param end the last code point in a contiguous range with value (inclusive)
    165  * @param value the value that is set for all code points in [start..end]
    166  * @return FALSE to stop the enumeration
    167  */
    168 typedef UBool U_CALLCONV
    169 UTrie2EnumRange(const void *context, UChar32 start, UChar32 end, uint32_t value);
    170 
    171 /**
    172  * Enumerate efficiently all values in a trie.
    173  * Do not modify the trie during the enumeration.
    174  *
    175  * For each entry in the trie, the value to be delivered is passed through
    176  * the UTrie2EnumValue function.
    177  * The value is unchanged if that function pointer is NULL.
    178  *
    179  * For each contiguous range of code points with a given (transformed) value,
    180  * the UTrie2EnumRange function is called.
    181  *
    182  * @param trie a pointer to the trie
    183  * @param enumValue a pointer to a function that may transform the trie entry value,
    184  *                  or NULL if the values from the trie are to be used directly
    185  * @param enumRange a pointer to a function that is called for each contiguous range
    186  *                  of code points with the same (transformed) value
    187  * @param context an opaque pointer that is passed on to the callback functions
    188  */
    189 U_CAPI void U_EXPORT2
    190 utrie2_enum(const UTrie2 *trie,
    191             UTrie2EnumValue *enumValue, UTrie2EnumRange *enumRange, const void *context);
    192 
    193 /* Building a trie ---------------------------------------------------------- */
    194 
    195 /**
    196  * Open an empty, writable trie. At build time, 32-bit data values are used.
    197  * utrie2_freeze() takes a valueBits parameter
    198  * which determines the data value width in the serialized and frozen forms.
    199  * You must utrie2_close() the trie once you are done using it.
    200  *
    201  * @param initialValue the initial value that is set for all code points
    202  * @param errorValue the value for out-of-range code points and illegal UTF-8
    203  * @param pErrorCode an in/out ICU UErrorCode
    204  * @return a pointer to the allocated and initialized new trie
    205  */
    206 U_CAPI UTrie2 * U_EXPORT2
    207 utrie2_open(uint32_t initialValue, uint32_t errorValue, UErrorCode *pErrorCode);
    208 
    209 /**
    210  * Clone a trie.
    211  * You must utrie2_close() the clone once you are done using it.
    212  *
    213  * @param other the trie to clone
    214  * @param pErrorCode an in/out ICU UErrorCode
    215  * @return a pointer to the new trie clone
    216  */
    217 U_CAPI UTrie2 * U_EXPORT2
    218 utrie2_clone(const UTrie2 *other, UErrorCode *pErrorCode);
    219 
    220 /**
    221  * Clone a trie. The clone will be mutable/writable even if the other trie
    222  * is frozen. (See utrie2_freeze().)
    223  * You must utrie2_close() the clone once you are done using it.
    224  *
    225  * @param other the trie to clone
    226  * @param pErrorCode an in/out ICU UErrorCode
    227  * @return a pointer to the new trie clone
    228  */
    229 U_CAPI UTrie2 * U_EXPORT2
    230 utrie2_cloneAsThawed(const UTrie2 *other, UErrorCode *pErrorCode);
    231 
    232 /**
    233  * Close a trie and release associated memory.
    234  *
    235  * @param trie the trie
    236  */
    237 U_CAPI void U_EXPORT2
    238 utrie2_close(UTrie2 *trie);
    239 
    240 /**
    241  * Set a value for a code point.
    242  *
    243  * @param trie the unfrozen trie
    244  * @param c the code point
    245  * @param value the value
    246  * @param pErrorCode an in/out ICU UErrorCode; among other possible error codes:
    247  * - U_NO_WRITE_PERMISSION if the trie is frozen
    248  */
    249 U_CAPI void U_EXPORT2
    250 utrie2_set32(UTrie2 *trie, UChar32 c, uint32_t value, UErrorCode *pErrorCode);
    251 
    252 /**
    253  * Set a value in a range of code points [start..end].
    254  * All code points c with start<=c<=end will get the value if
    255  * overwrite is TRUE or if the old value is the initial value.
    256  *
    257  * @param trie the unfrozen trie
    258  * @param start the first code point to get the value
    259  * @param end the last code point to get the value (inclusive)
    260  * @param value the value
    261  * @param overwrite flag for whether old non-initial values are to be overwritten
    262  * @param pErrorCode an in/out ICU UErrorCode; among other possible error codes:
    263  * - U_NO_WRITE_PERMISSION if the trie is frozen
    264  */
    265 U_CAPI void U_EXPORT2
    266 utrie2_setRange32(UTrie2 *trie,
    267                   UChar32 start, UChar32 end,
    268                   uint32_t value, UBool overwrite,
    269                   UErrorCode *pErrorCode);
    270 
    271 /**
    272  * Freeze a trie. Make it immutable (read-only) and compact it,
    273  * ready for serialization and for use with fast macros.
    274  * Functions to set values will fail after serializing.
    275  *
    276  * A trie can be frozen only once. If this function is called again with different
    277  * valueBits then it will set a U_ILLEGAL_ARGUMENT_ERROR.
    278  *
    279  * @param trie the trie
    280  * @param valueBits selects the data entry size; if smaller than 32 bits, then
    281  *                  the values stored in the trie will be truncated
    282  * @param pErrorCode an in/out ICU UErrorCode; among other possible error codes:
    283  * - U_INDEX_OUTOFBOUNDS_ERROR if the compacted index or data arrays are too long
    284  *                             for serialization
    285  *                             (the trie will be immutable and usable,
    286  *                             but not frozen and not usable with the fast macros)
    287  *
    288  * @see utrie2_cloneAsThawed
    289  */
    290 U_CAPI void U_EXPORT2
    291 utrie2_freeze(UTrie2 *trie, UTrie2ValueBits valueBits, UErrorCode *pErrorCode);
    292 
    293 /**
    294  * Test if the trie is frozen. (See utrie2_freeze().)
    295  *
    296  * @param trie the trie
    297  * @return TRUE if the trie is frozen, that is, immutable, ready for serialization
    298  *         and for use with fast macros
    299  */
    300 U_CAPI UBool U_EXPORT2
    301 utrie2_isFrozen(const UTrie2 *trie);
    302 
    303 /**
    304  * Serialize a frozen trie into 32-bit aligned memory.
    305  * If the trie is not frozen, then the function returns with a U_ILLEGAL_ARGUMENT_ERROR.
    306  * A trie can be serialized multiple times.
    307  *
    308  * @param trie the frozen trie
    309  * @param data a pointer to 32-bit-aligned memory to be filled with the trie data,
    310  *             can be NULL if capacity==0
    311  * @param capacity the number of bytes available at data,
    312  *                 or 0 for preflighting
    313  * @param pErrorCode an in/out ICU UErrorCode; among other possible error codes:
    314  * - U_BUFFER_OVERFLOW_ERROR if the data storage block is too small for serialization
    315  * - U_ILLEGAL_ARGUMENT_ERROR if the trie is not frozen or the data and capacity
    316  *                            parameters are bad
    317  * @return the number of bytes written or needed for the trie
    318  *
    319  * @see utrie2_openFromSerialized()
    320  */
    321 U_CAPI int32_t U_EXPORT2
    322 utrie2_serialize(const UTrie2 *trie,
    323                  void *data, int32_t capacity,
    324                  UErrorCode *pErrorCode);
    325 
    326 /* Public UTrie2 API: miscellaneous functions ------------------------------- */
    327 
    328 /**
    329  * Get the UTrie version from 32-bit-aligned memory containing the serialized form
    330  * of either a UTrie (version 1) or a UTrie2 (version 2).
    331  *
    332  * @param data a pointer to 32-bit-aligned memory containing the serialized form
    333  *             of a UTrie, version 1 or 2
    334  * @param length the number of bytes available at data;
    335  *               can be more than necessary (see return value)
    336  * @param anyEndianOk If FALSE, only platform-endian serialized forms are recognized.
    337  *                    If TRUE, opposite-endian serialized forms are recognized as well.
    338  * @return the UTrie version of the serialized form, or 0 if it is not
    339  *         recognized as a serialized UTrie
    340  */
    341 U_CAPI int32_t U_EXPORT2
    342 utrie2_getVersion(const void *data, int32_t length, UBool anyEndianOk);
    343 
    344 /**
    345  * Swap a serialized UTrie2.
    346  * @internal
    347  */
    348 U_CAPI int32_t U_EXPORT2
    349 utrie2_swap(const UDataSwapper *ds,
    350             const void *inData, int32_t length, void *outData,
    351             UErrorCode *pErrorCode);
    352 
    353 /**
    354  * Swap a serialized UTrie or UTrie2.
    355  * @internal
    356  */
    357 U_CAPI int32_t U_EXPORT2
    358 utrie2_swapAnyVersion(const UDataSwapper *ds,
    359                       const void *inData, int32_t length, void *outData,
    360                       UErrorCode *pErrorCode);
    361 
    362 /**
    363  * Build a UTrie2 (version 2) from a UTrie (version 1).
    364  * Enumerates all values in the UTrie and builds a UTrie2 with the same values.
    365  * The resulting UTrie2 will be frozen.
    366  *
    367  * @param trie1 the runtime UTrie structure to be enumerated
    368  * @param errorValue the value for out-of-range code points and illegal UTF-8
    369  * @param pErrorCode an in/out ICU UErrorCode
    370  * @return The frozen UTrie2 with the same values as the UTrie.
    371  */
    372 U_CAPI UTrie2 * U_EXPORT2
    373 utrie2_fromUTrie(const UTrie *trie1, uint32_t errorValue, UErrorCode *pErrorCode);
    374 
    375 /* Public UTrie2 API macros ------------------------------------------------- */
    376 
    377 /*
    378  * These macros provide fast data lookup from a frozen trie.
    379  * They will crash when used on an unfrozen trie.
    380  */
    381 
    382 /**
    383  * Return a 16-bit trie value from a code point, with range checking.
    384  * Returns trie->errorValue if c is not in the range 0..U+10ffff.
    385  *
    386  * @param trie (const UTrie2 *, in) a frozen trie
    387  * @param c (UChar32, in) the input code point
    388  * @return (uint16_t) The code point's trie value.
    389  */
    390 #define UTRIE2_GET16(trie, c) _UTRIE2_GET((trie), index, (trie)->indexLength, (c))
    391 
    392 /**
    393  * Return a 32-bit trie value from a code point, with range checking.
    394  * Returns trie->errorValue if c is not in the range 0..U+10ffff.
    395  *
    396  * @param trie (const UTrie2 *, in) a frozen trie
    397  * @param c (UChar32, in) the input code point
    398  * @return (uint32_t) The code point's trie value.
    399  */
    400 #define UTRIE2_GET32(trie, c) _UTRIE2_GET((trie), data32, 0, (c))
    401 
    402 /**
    403  * UTF-16: Get the next code point (UChar32 c, out), post-increment src,
    404  * and get a 16-bit value from the trie.
    405  *
    406  * @param trie (const UTrie2 *, in) a frozen trie
    407  * @param src (const UChar *, in/out) the source text pointer
    408  * @param limit (const UChar *, in) the limit pointer for the text, or NULL if NUL-terminated
    409  * @param c (UChar32, out) variable for the code point
    410  * @param result (uint16_t, out) uint16_t variable for the trie lookup result
    411  */
    412 #define UTRIE2_U16_NEXT16(trie, src, limit, c, result) _UTRIE2_U16_NEXT(trie, index, src, limit, c, result)
    413 
    414 /**
    415  * UTF-16: Get the next code point (UChar32 c, out), post-increment src,
    416  * and get a 32-bit value from the trie.
    417  *
    418  * @param trie (const UTrie2 *, in) a frozen trie
    419  * @param src (const UChar *, in/out) the source text pointer
    420  * @param limit (const UChar *, in) the limit pointer for the text, or NULL if NUL-terminated
    421  * @param c (UChar32, out) variable for the code point
    422  * @param result (uint32_t, out) uint32_t variable for the trie lookup result
    423  */
    424 #define UTRIE2_U16_NEXT32(trie, src, limit, c, result) _UTRIE2_U16_NEXT(trie, data32, src, limit, c, result)
    425 
    426 /**
    427  * UTF-16: Get the previous code point (UChar32 c, out), pre-decrement src,
    428  * and get a 16-bit value from the trie.
    429  *
    430  * @param trie (const UTrie2 *, in) a frozen trie
    431  * @param start (const UChar *, in) the start pointer for the text
    432  * @param src (const UChar *, in/out) the source text pointer
    433  * @param c (UChar32, out) variable for the code point
    434  * @param result (uint16_t, out) uint16_t variable for the trie lookup result
    435  */
    436 #define UTRIE2_U16_PREV16(trie, start, src, c, result) _UTRIE2_U16_PREV(trie, index, start, src, c, result)
    437 
    438 /**
    439  * UTF-16: Get the previous code point (UChar32 c, out), pre-decrement src,
    440  * and get a 32-bit value from the trie.
    441  *
    442  * @param trie (const UTrie2 *, in) a frozen trie
    443  * @param start (const UChar *, in) the start pointer for the text
    444  * @param src (const UChar *, in/out) the source text pointer
    445  * @param c (UChar32, out) variable for the code point
    446  * @param result (uint32_t, out) uint32_t variable for the trie lookup result
    447  */
    448 #define UTRIE2_U16_PREV32(trie, start, src, c, result) _UTRIE2_U16_PREV(trie, data32, start, src, c, result)
    449 
    450 /**
    451  * UTF-8: Post-increment src and get a 16-bit value from the trie.
    452  *
    453  * @param trie (const UTrie2 *, in) a frozen trie
    454  * @param src (const char *, in/out) the source text pointer
    455  * @param limit (const char *, in) the limit pointer for the text (must not be NULL)
    456  * @param result (uint16_t, out) uint16_t variable for the trie lookup result
    457  */
    458 #define UTRIE2_U8_NEXT16(trie, src, limit, result)\
    459     _UTRIE2_U8_NEXT(trie, data16, index, src, limit, result)
    460 
    461 /**
    462  * UTF-8: Post-increment src and get a 32-bit value from the trie.
    463  *
    464  * @param trie (const UTrie2 *, in) a frozen trie
    465  * @param src (const char *, in/out) the source text pointer
    466  * @param limit (const char *, in) the limit pointer for the text (must not be NULL)
    467  * @param result (uint16_t, out) uint32_t variable for the trie lookup result
    468  */
    469 #define UTRIE2_U8_NEXT32(trie, src, limit, result) \
    470     _UTRIE2_U8_NEXT(trie, data32, data32, src, limit, result)
    471 
    472 /**
    473  * UTF-8: Pre-decrement src and get a 16-bit value from the trie.
    474  *
    475  * @param trie (const UTrie2 *, in) a frozen trie
    476  * @param start (const char *, in) the start pointer for the text
    477  * @param src (const char *, in/out) the source text pointer
    478  * @param result (uint16_t, out) uint16_t variable for the trie lookup result
    479  */
    480 #define UTRIE2_U8_PREV16(trie, start, src, result) \
    481     _UTRIE2_U8_PREV(trie, data16, index, start, src, result)
    482 
    483 /**
    484  * UTF-8: Pre-decrement src and get a 32-bit value from the trie.
    485  *
    486  * @param trie (const UTrie2 *, in) a frozen trie
    487  * @param start (const char *, in) the start pointer for the text
    488  * @param src (const char *, in/out) the source text pointer
    489  * @param result (uint16_t, out) uint32_t variable for the trie lookup result
    490  */
    491 #define UTRIE2_U8_PREV32(trie, start, src, result) \
    492     _UTRIE2_U8_PREV(trie, data32, data32, start, src, result)
    493 
    494 /* Public UTrie2 API: optimized UTF-16 access ------------------------------- */
    495 
    496 /*
    497  * The following functions and macros are used for highly optimized UTF-16
    498  * text processing. The UTRIE2_U16_NEXTxy() macros do not depend on these.
    499  *
    500  * A UTrie2 stores separate values for lead surrogate code _units_ vs. code _points_.
    501  * UTF-16 text processing can be optimized by detecting surrogate pairs and
    502  * assembling supplementary code points only when there is non-trivial data
    503  * available.
    504  *
    505  * At build-time, use utrie2_enumForLeadSurrogate() to see if there
    506  * is non-trivial (non-initialValue) data for any of the supplementary
    507  * code points associated with a lead surrogate.
    508  * If so, then set a special (application-specific) value for the
    509  * lead surrogate code _unit_, with utrie2_set32ForLeadSurrogateCodeUnit().
    510  *
    511  * At runtime, use UTRIE2_GET16_FROM_U16_SINGLE_LEAD() or
    512  * UTRIE2_GET32_FROM_U16_SINGLE_LEAD() per code unit. If there is non-trivial
    513  * data and the code unit is a lead surrogate, then check if a trail surrogate
    514  * follows. If so, assemble the supplementary code point with
    515  * U16_GET_SUPPLEMENTARY() and look up its value with UTRIE2_GET16_FROM_SUPP()
    516  * or UTRIE2_GET32_FROM_SUPP(); otherwise reset the lead
    517  * surrogate's value or do a code point lookup for it.
    518  *
    519  * If there is only trivial data for lead and trail surrogates, then processing
    520  * can often skip them. For example, in normalization or case mapping
    521  * all characters that do not have any mappings are simply copied as is.
    522  */
    523 
    524 /**
    525  * Get a value from a lead surrogate code unit as stored in the trie.
    526  *
    527  * @param trie the trie
    528  * @param c the code unit (U+D800..U+DBFF)
    529  * @return the value
    530  */
    531 U_CAPI uint32_t U_EXPORT2
    532 utrie2_get32FromLeadSurrogateCodeUnit(const UTrie2 *trie, UChar32 c);
    533 
    534 /**
    535  * Enumerate the trie values for the 1024=0x400 code points
    536  * corresponding to a given lead surrogate.
    537  * For example, for the lead surrogate U+D87E it will enumerate the values
    538  * for [U+2F800..U+2FC00[.
    539  * Used by data builder code that sets special lead surrogate code unit values
    540  * for optimized UTF-16 string processing.
    541  *
    542  * Do not modify the trie during the enumeration.
    543  *
    544  * Except for the limited code point range, this functions just like utrie2_enum():
    545  * For each entry in the trie, the value to be delivered is passed through
    546  * the UTrie2EnumValue function.
    547  * The value is unchanged if that function pointer is NULL.
    548  *
    549  * For each contiguous range of code points with a given (transformed) value,
    550  * the UTrie2EnumRange function is called.
    551  *
    552  * @param trie a pointer to the trie
    553  * @param enumValue a pointer to a function that may transform the trie entry value,
    554  *                  or NULL if the values from the trie are to be used directly
    555  * @param enumRange a pointer to a function that is called for each contiguous range
    556  *                  of code points with the same (transformed) value
    557  * @param context an opaque pointer that is passed on to the callback functions
    558  */
    559 U_CAPI void U_EXPORT2
    560 utrie2_enumForLeadSurrogate(const UTrie2 *trie, UChar32 lead,
    561                             UTrie2EnumValue *enumValue, UTrie2EnumRange *enumRange,
    562                             const void *context);
    563 
    564 /**
    565  * Set a value for a lead surrogate code unit.
    566  *
    567  * @param trie the unfrozen trie
    568  * @param lead the lead surrogate code unit (U+D800..U+DBFF)
    569  * @param value the value
    570  * @param pErrorCode an in/out ICU UErrorCode; among other possible error codes:
    571  * - U_NO_WRITE_PERMISSION if the trie is frozen
    572  */
    573 U_CAPI void U_EXPORT2
    574 utrie2_set32ForLeadSurrogateCodeUnit(UTrie2 *trie,
    575                                      UChar32 lead, uint32_t value,
    576                                      UErrorCode *pErrorCode);
    577 
    578 /**
    579  * Return a 16-bit trie value from a UTF-16 single/lead code unit (<=U+ffff).
    580  * Same as UTRIE2_GET16() if c is a BMP code point except for lead surrogates,
    581  * but smaller and faster.
    582  *
    583  * @param trie (const UTrie2 *, in) a frozen trie
    584  * @param c (UChar32, in) the input code unit, must be 0<=c<=U+ffff
    585  * @return (uint16_t) The code unit's trie value.
    586  */
    587 #define UTRIE2_GET16_FROM_U16_SINGLE_LEAD(trie, c) _UTRIE2_GET_FROM_U16_SINGLE_LEAD((trie), index, c)
    588 
    589 /**
    590  * Return a 32-bit trie value from a UTF-16 single/lead code unit (<=U+ffff).
    591  * Same as UTRIE2_GET32() if c is a BMP code point except for lead surrogates,
    592  * but smaller and faster.
    593  *
    594  * @param trie (const UTrie2 *, in) a frozen trie
    595  * @param c (UChar32, in) the input code unit, must be 0<=c<=U+ffff
    596  * @return (uint32_t) The code unit's trie value.
    597  */
    598 #define UTRIE2_GET32_FROM_U16_SINGLE_LEAD(trie, c) _UTRIE2_GET_FROM_U16_SINGLE_LEAD((trie), data32, c)
    599 
    600 /**
    601  * Return a 16-bit trie value from a supplementary code point (U+10000..U+10ffff).
    602  *
    603  * @param trie (const UTrie2 *, in) a frozen trie
    604  * @param c (UChar32, in) the input code point, must be U+10000<=c<=U+10ffff
    605  * @return (uint16_t) The code point's trie value.
    606  */
    607 #define UTRIE2_GET16_FROM_SUPP(trie, c) _UTRIE2_GET_FROM_SUPP((trie), index, c)
    608 
    609 /**
    610  * Return a 32-bit trie value from a supplementary code point (U+10000..U+10ffff).
    611  *
    612  * @param trie (const UTrie2 *, in) a frozen trie
    613  * @param c (UChar32, in) the input code point, must be U+10000<=c<=U+10ffff
    614  * @return (uint32_t) The code point's trie value.
    615  */
    616 #define UTRIE2_GET32_FROM_SUPP(trie, c) _UTRIE2_GET_FROM_SUPP((trie), data32, c)
    617 
    618 U_CDECL_END
    619 
    620 /* C++ convenience wrappers ------------------------------------------------- */
    621 
    622 #ifdef __cplusplus
    623 
    624 #include "unicode/utf.h"
    625 #include "mutex.h"
    626 
    627 U_NAMESPACE_BEGIN
    628 
    629 // Use the Forward/Backward subclasses below.
    630 class UTrie2StringIterator : public UMemory {
    631 public:
    632     UTrie2StringIterator(const UTrie2 *t, const UChar *p) :
    633         trie(t), codePointStart(p), codePointLimit(p), codePoint(U_SENTINEL) {}
    634 
    635     const UTrie2 *trie;
    636     const UChar *codePointStart, *codePointLimit;
    637     UChar32 codePoint;
    638 };
    639 
    640 class BackwardUTrie2StringIterator : public UTrie2StringIterator {
    641 public:
    642     BackwardUTrie2StringIterator(const UTrie2 *t, const UChar *s, const UChar *p) :
    643         UTrie2StringIterator(t, p), start(s) {}
    644 
    645     uint16_t previous16();
    646 
    647     const UChar *start;
    648 };
    649 
    650 class ForwardUTrie2StringIterator : public UTrie2StringIterator {
    651 public:
    652     // Iteration limit l can be NULL.
    653     // In that case, the caller must detect c==0 and stop.
    654     ForwardUTrie2StringIterator(const UTrie2 *t, const UChar *p, const UChar *l) :
    655         UTrie2StringIterator(t, p), limit(l) {}
    656 
    657     uint16_t next16();
    658 
    659     const UChar *limit;
    660 };
    661 
    662 U_NAMESPACE_END
    663 
    664 #endif
    665 
    666 /* Internal definitions ----------------------------------------------------- */
    667 
    668 U_CDECL_BEGIN
    669 
    670 /** Build-time trie structure. */
    671 struct UNewTrie2;
    672 typedef struct UNewTrie2 UNewTrie2;
    673 
    674 /*
    675  * Trie structure definition.
    676  *
    677  * Either the data table is 16 bits wide and accessed via the index
    678  * pointer, with each index item increased by indexLength;
    679  * in this case, data32==NULL, and data16 is used for direct ASCII access.
    680  *
    681  * Or the data table is 32 bits wide and accessed via the data32 pointer.
    682  */
    683 struct UTrie2 {
    684     /* protected: used by macros and functions for reading values */
    685     const uint16_t *index;
    686     const uint16_t *data16;     /* for fast UTF-8 ASCII access, if 16b data */
    687     const uint32_t *data32;     /* NULL if 16b data is used via index */
    688 
    689     int32_t indexLength, dataLength;
    690     uint16_t index2NullOffset;  /* 0xffff if there is no dedicated index-2 null block */
    691     uint16_t dataNullOffset;
    692     uint32_t initialValue;
    693     /** Value returned for out-of-range code points and illegal UTF-8. */
    694     uint32_t errorValue;
    695 
    696     /* Start of the last range which ends at U+10ffff, and its value. */
    697     UChar32 highStart;
    698     int32_t highValueIndex;
    699 
    700     /* private: used by builder and unserialization functions */
    701     void *memory;           /* serialized bytes; NULL if not frozen yet */
    702     int32_t length;         /* number of serialized bytes at memory; 0 if not frozen yet */
    703     UBool isMemoryOwned;    /* TRUE if the trie owns the memory */
    704     UBool padding1;
    705     int16_t padding2;
    706     UNewTrie2 *newTrie;     /* builder object; NULL when frozen */
    707 };
    708 
    709 /**
    710  * Trie constants, defining shift widths, index array lengths, etc.
    711  *
    712  * These are needed for the runtime macros but users can treat these as
    713  * implementation details and skip to the actual public API further below.
    714  */
    715 enum {
    716     /** Shift size for getting the index-1 table offset. */
    717     UTRIE2_SHIFT_1=6+5,
    718 
    719     /** Shift size for getting the index-2 table offset. */
    720     UTRIE2_SHIFT_2=5,
    721 
    722     /**
    723      * Difference between the two shift sizes,
    724      * for getting an index-1 offset from an index-2 offset. 6=11-5
    725      */
    726     UTRIE2_SHIFT_1_2=UTRIE2_SHIFT_1-UTRIE2_SHIFT_2,
    727 
    728     /**
    729      * Number of index-1 entries for the BMP. 32=0x20
    730      * This part of the index-1 table is omitted from the serialized form.
    731      */
    732     UTRIE2_OMITTED_BMP_INDEX_1_LENGTH=0x10000>>UTRIE2_SHIFT_1,
    733 
    734     /** Number of code points per index-1 table entry. 2048=0x800 */
    735     UTRIE2_CP_PER_INDEX_1_ENTRY=1<<UTRIE2_SHIFT_1,
    736 
    737     /** Number of entries in an index-2 block. 64=0x40 */
    738     UTRIE2_INDEX_2_BLOCK_LENGTH=1<<UTRIE2_SHIFT_1_2,
    739 
    740     /** Mask for getting the lower bits for the in-index-2-block offset. */
    741     UTRIE2_INDEX_2_MASK=UTRIE2_INDEX_2_BLOCK_LENGTH-1,
    742 
    743     /** Number of entries in a data block. 32=0x20 */
    744     UTRIE2_DATA_BLOCK_LENGTH=1<<UTRIE2_SHIFT_2,
    745 
    746     /** Mask for getting the lower bits for the in-data-block offset. */
    747     UTRIE2_DATA_MASK=UTRIE2_DATA_BLOCK_LENGTH-1,
    748 
    749     /**
    750      * Shift size for shifting left the index array values.
    751      * Increases possible data size with 16-bit index values at the cost
    752      * of compactability.
    753      * This requires data blocks to be aligned by UTRIE2_DATA_GRANULARITY.
    754      */
    755     UTRIE2_INDEX_SHIFT=2,
    756 
    757     /** The alignment size of a data block. Also the granularity for compaction. */
    758     UTRIE2_DATA_GRANULARITY=1<<UTRIE2_INDEX_SHIFT,
    759 
    760     /* Fixed layout of the first part of the index array. ------------------- */
    761 
    762     /**
    763      * The BMP part of the index-2 table is fixed and linear and starts at offset 0.
    764      * Length=2048=0x800=0x10000>>UTRIE2_SHIFT_2.
    765      */
    766     UTRIE2_INDEX_2_OFFSET=0,
    767 
    768     /**
    769      * The part of the index-2 table for U+D800..U+DBFF stores values for
    770      * lead surrogate code _units_ not code _points_.
    771      * Values for lead surrogate code _points_ are indexed with this portion of the table.
    772      * Length=32=0x20=0x400>>UTRIE2_SHIFT_2. (There are 1024=0x400 lead surrogates.)
    773      */
    774     UTRIE2_LSCP_INDEX_2_OFFSET=0x10000>>UTRIE2_SHIFT_2,
    775     UTRIE2_LSCP_INDEX_2_LENGTH=0x400>>UTRIE2_SHIFT_2,
    776 
    777     /** Count the lengths of both BMP pieces. 2080=0x820 */
    778     UTRIE2_INDEX_2_BMP_LENGTH=UTRIE2_LSCP_INDEX_2_OFFSET+UTRIE2_LSCP_INDEX_2_LENGTH,
    779 
    780     /**
    781      * The 2-byte UTF-8 version of the index-2 table follows at offset 2080=0x820.
    782      * Length 32=0x20 for lead bytes C0..DF, regardless of UTRIE2_SHIFT_2.
    783      */
    784     UTRIE2_UTF8_2B_INDEX_2_OFFSET=UTRIE2_INDEX_2_BMP_LENGTH,
    785     UTRIE2_UTF8_2B_INDEX_2_LENGTH=0x800>>6,  /* U+0800 is the first code point after 2-byte UTF-8 */
    786 
    787     /**
    788      * The index-1 table, only used for supplementary code points, at offset 2112=0x840.
    789      * Variable length, for code points up to highStart, where the last single-value range starts.
    790      * Maximum length 512=0x200=0x100000>>UTRIE2_SHIFT_1.
    791      * (For 0x100000 supplementary code points U+10000..U+10ffff.)
    792      *
    793      * The part of the index-2 table for supplementary code points starts
    794      * after this index-1 table.
    795      *
    796      * Both the index-1 table and the following part of the index-2 table
    797      * are omitted completely if there is only BMP data.
    798      */
    799     UTRIE2_INDEX_1_OFFSET=UTRIE2_UTF8_2B_INDEX_2_OFFSET+UTRIE2_UTF8_2B_INDEX_2_LENGTH,
    800     UTRIE2_MAX_INDEX_1_LENGTH=0x100000>>UTRIE2_SHIFT_1,
    801 
    802     /*
    803      * Fixed layout of the first part of the data array. -----------------------
    804      * Starts with 4 blocks (128=0x80 entries) for ASCII.
    805      */
    806 
    807     /**
    808      * The illegal-UTF-8 data block follows the ASCII block, at offset 128=0x80.
    809      * Used with linear access for single bytes 0..0xbf for simple error handling.
    810      * Length 64=0x40, not UTRIE2_DATA_BLOCK_LENGTH.
    811      */
    812     UTRIE2_BAD_UTF8_DATA_OFFSET=0x80,
    813 
    814     /** The start of non-linear-ASCII data blocks, at offset 192=0xc0. */
    815     UTRIE2_DATA_START_OFFSET=0xc0
    816 };
    817 
    818 /* Internal functions and macros -------------------------------------------- */
    819 
    820 /**
    821  * Internal function for part of the UTRIE2_U8_NEXTxx() macro implementations.
    822  * Do not call directly.
    823  * @internal
    824  */
    825 U_INTERNAL int32_t U_EXPORT2
    826 utrie2_internalU8NextIndex(const UTrie2 *trie, UChar32 c,
    827                            const uint8_t *src, const uint8_t *limit);
    828 
    829 /**
    830  * Internal function for part of the UTRIE2_U8_PREVxx() macro implementations.
    831  * Do not call directly.
    832  * @internal
    833  */
    834 U_INTERNAL int32_t U_EXPORT2
    835 utrie2_internalU8PrevIndex(const UTrie2 *trie, UChar32 c,
    836                            const uint8_t *start, const uint8_t *src);
    837 
    838 
    839 /** Internal low-level trie getter. Returns a data index. */
    840 #define _UTRIE2_INDEX_RAW(offset, trieIndex, c) \
    841     (((int32_t)((trieIndex)[(offset)+((c)>>UTRIE2_SHIFT_2)]) \
    842     <<UTRIE2_INDEX_SHIFT)+ \
    843     ((c)&UTRIE2_DATA_MASK))
    844 
    845 /** Internal trie getter from a UTF-16 single/lead code unit. Returns the data index. */
    846 #define _UTRIE2_INDEX_FROM_U16_SINGLE_LEAD(trieIndex, c) _UTRIE2_INDEX_RAW(0, trieIndex, c)
    847 
    848 /** Internal trie getter from a lead surrogate code point (D800..DBFF). Returns the data index. */
    849 #define _UTRIE2_INDEX_FROM_LSCP(trieIndex, c) \
    850     _UTRIE2_INDEX_RAW(UTRIE2_LSCP_INDEX_2_OFFSET-(0xd800>>UTRIE2_SHIFT_2), trieIndex, c)
    851 
    852 /** Internal trie getter from a BMP code point. Returns the data index. */
    853 #define _UTRIE2_INDEX_FROM_BMP(trieIndex, c) \
    854     _UTRIE2_INDEX_RAW(U_IS_LEAD(c) ? UTRIE2_LSCP_INDEX_2_OFFSET-(0xd800>>UTRIE2_SHIFT_2) : 0, \
    855                       trieIndex, c)
    856 
    857 /** Internal trie getter from a supplementary code point below highStart. Returns the data index. */
    858 #define _UTRIE2_INDEX_FROM_SUPP(trieIndex, c) \
    859     (((int32_t)((trieIndex)[ \
    860         (trieIndex)[(UTRIE2_INDEX_1_OFFSET-UTRIE2_OMITTED_BMP_INDEX_1_LENGTH)+ \
    861                       ((c)>>UTRIE2_SHIFT_1)]+ \
    862         (((c)>>UTRIE2_SHIFT_2)&UTRIE2_INDEX_2_MASK)]) \
    863     <<UTRIE2_INDEX_SHIFT)+ \
    864     ((c)&UTRIE2_DATA_MASK))
    865 
    866 /**
    867  * Internal trie getter from a code point, with checking that c is in 0..10FFFF.
    868  * Returns the data index.
    869  */
    870 #define _UTRIE2_INDEX_FROM_CP(trie, asciiOffset, c) \
    871     ((uint32_t)(c)<0xd800 ? \
    872         _UTRIE2_INDEX_RAW(0, (trie)->index, c) : \
    873         (uint32_t)(c)<=0xffff ? \
    874             _UTRIE2_INDEX_RAW( \
    875                 (c)<=0xdbff ? UTRIE2_LSCP_INDEX_2_OFFSET-(0xd800>>UTRIE2_SHIFT_2) : 0, \
    876                 (trie)->index, c) : \
    877             (uint32_t)(c)>0x10ffff ? \
    878                 (asciiOffset)+UTRIE2_BAD_UTF8_DATA_OFFSET : \
    879                 (c)>=(trie)->highStart ? \
    880                     (trie)->highValueIndex : \
    881                     _UTRIE2_INDEX_FROM_SUPP((trie)->index, c))
    882 
    883 /** Internal trie getter from a UTF-16 single/lead code unit. Returns the data. */
    884 #define _UTRIE2_GET_FROM_U16_SINGLE_LEAD(trie, data, c) \
    885     (trie)->data[_UTRIE2_INDEX_FROM_U16_SINGLE_LEAD((trie)->index, c)]
    886 
    887 /** Internal trie getter from a supplementary code point. Returns the data. */
    888 #define _UTRIE2_GET_FROM_SUPP(trie, data, c) \
    889     (trie)->data[(c)>=(trie)->highStart ? (trie)->highValueIndex : \
    890                  _UTRIE2_INDEX_FROM_SUPP((trie)->index, c)]
    891 
    892 /**
    893  * Internal trie getter from a code point, with checking that c is in 0..10FFFF.
    894  * Returns the data.
    895  */
    896 #define _UTRIE2_GET(trie, data, asciiOffset, c) \
    897     (trie)->data[_UTRIE2_INDEX_FROM_CP(trie, asciiOffset, c)]
    898 
    899 /** Internal next-post-increment: get the next code point (c) and its data. */
    900 #define _UTRIE2_U16_NEXT(trie, data, src, limit, c, result) { \
    901     { \
    902         uint16_t __c2; \
    903         (c)=*(src)++; \
    904         if(!U16_IS_LEAD(c)) { \
    905             (result)=_UTRIE2_GET_FROM_U16_SINGLE_LEAD(trie, data, c); \
    906         } else if((src)==(limit) || !U16_IS_TRAIL(__c2=*(src))) { \
    907             (result)=(trie)->data[_UTRIE2_INDEX_FROM_LSCP((trie)->index, c)]; \
    908         } else { \
    909             ++(src); \
    910             (c)=U16_GET_SUPPLEMENTARY((c), __c2); \
    911             (result)=_UTRIE2_GET_FROM_SUPP((trie), data, (c)); \
    912         } \
    913     } \
    914 }
    915 
    916 /** Internal pre-decrement-previous: get the previous code point (c) and its data */
    917 #define _UTRIE2_U16_PREV(trie, data, start, src, c, result) { \
    918     { \
    919         uint16_t __c2; \
    920         (c)=*--(src); \
    921         if(!U16_IS_TRAIL(c) || (src)==(start) || !U16_IS_LEAD(__c2=*((src)-1))) { \
    922             (result)=(trie)->data[_UTRIE2_INDEX_FROM_BMP((trie)->index, c)]; \
    923         } else { \
    924             --(src); \
    925             (c)=U16_GET_SUPPLEMENTARY(__c2, (c)); \
    926             (result)=_UTRIE2_GET_FROM_SUPP((trie), data, (c)); \
    927         } \
    928     } \
    929 }
    930 
    931 /** Internal UTF-8 next-post-increment: get the next code point's data. */
    932 #define _UTRIE2_U8_NEXT(trie, ascii, data, src, limit, result) { \
    933     uint8_t __lead=(uint8_t)*(src)++; \
    934     if(__lead<0xc0) { \
    935         (result)=(trie)->ascii[__lead]; \
    936     } else { \
    937         uint8_t __t1, __t2; \
    938         if( /* handle U+0000..U+07FF inline */ \
    939             __lead<0xe0 && (src)<(limit) && \
    940             (__t1=(uint8_t)(*(src)-0x80))<=0x3f \
    941         ) { \
    942             ++(src); \
    943             (result)=(trie)->data[ \
    944                 (trie)->index[(UTRIE2_UTF8_2B_INDEX_2_OFFSET-0xc0)+__lead]+ \
    945                 __t1]; \
    946         } else if( /* handle U+0000..U+CFFF inline */ \
    947             __lead<0xed && ((src)+1)<(limit) && \
    948             (__t1=(uint8_t)(*(src)-0x80))<=0x3f && (__lead>0xe0 || __t1>=0x20) && \
    949             (__t2=(uint8_t)(*((src)+1)-0x80))<= 0x3f \
    950         ) { \
    951             (src)+=2; \
    952             (result)=(trie)->data[ \
    953                 ((int32_t)((trie)->index[((__lead-0xe0)<<(12-UTRIE2_SHIFT_2))+ \
    954                                          (__t1<<(6-UTRIE2_SHIFT_2))+(__t2>>UTRIE2_SHIFT_2)]) \
    955                 <<UTRIE2_INDEX_SHIFT)+ \
    956                 (__t2&UTRIE2_DATA_MASK)]; \
    957         } else { \
    958             int32_t __index=utrie2_internalU8NextIndex((trie), __lead, (const uint8_t *)(src), \
    959                                                                        (const uint8_t *)(limit)); \
    960             (src)+=__index&7; \
    961             (result)=(trie)->data[__index>>3]; \
    962         } \
    963     } \
    964 }
    965 
    966 /** Internal UTF-8 pre-decrement-previous: get the previous code point's data. */
    967 #define _UTRIE2_U8_PREV(trie, ascii, data, start, src, result) { \
    968     uint8_t __b=(uint8_t)*--(src); \
    969     if(__b<0x80) { \
    970         (result)=(trie)->ascii[__b]; \
    971     } else { \
    972         int32_t __index=utrie2_internalU8PrevIndex((trie), __b, (const uint8_t *)(start), \
    973                                                                 (const uint8_t *)(src)); \
    974         (src)-=__index&7; \
    975         (result)=(trie)->data[__index>>3]; \
    976     } \
    977 }
    978 
    979 U_CDECL_END
    980 
    981 /**
    982  * Work around MSVC 2003 optimization bugs.
    983  */
    984 #if defined (U_HAVE_MSVC_2003_OR_EARLIER)
    985 #pragma optimize("", off)
    986 #endif
    987 
    988 #endif
    989