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: UTrie2StringIterator(const UTrie2 * t,const UChar * p)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: BackwardUTrie2StringIterator(const UTrie2 * t,const UChar * s,const UChar * p)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. ForwardUTrie2StringIterator(const UTrie2 * t,const UChar * p,const UChar * l)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 987