src/third_party/icu/source/common/utrie2.h

   1 /*
   2 ******************************************************************************
   3 *
   4 *   Copyright (C) 2001-2013, 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(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