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