icuSources/common/utrie2.h

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