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