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