1 // © 2016 and later: Unicode, Inc. and others. 2 // License & terms of use: http://www.unicode.org/copyright.html 3 /* 4 ****************************************************************************** 5 * 6 * Copyright (C) 2001-2011, International Business Machines 7 * Corporation and others. All Rights Reserved. 8 * 9 ****************************************************************************** 10 * file name: utrie.h 11 * encoding: UTF-8 12 * tab size: 8 (not used) 13 * indentation:4 14 * 15 * created on: 2001nov08 16 * created by: Markus W. Scherer 17 */ 18 19 #ifndef __UTRIE_H__ 20 #define __UTRIE_H__ 21 22 #include "unicode/utypes.h" 23 #include "unicode/utf16.h" 24 25 U_CDECL_BEGIN 26 27 /** 28 * \file 29 * 30 * This is a common implementation of a "folded" trie. 31 * It is a kind of compressed, serializable table of 16- or 32-bit values associated with 32 * Unicode code points (0..0x10ffff). 33 * 34 * This implementation is optimized for getting values while walking forward 35 * through a UTF-16 string. 36 * Therefore, the simplest and fastest access macros are the 37 * _FROM_LEAD() and _FROM_OFFSET_TRAIL() macros. 38 * 39 * The _FROM_BMP() macros are a little more complicated; they get values 40 * even for lead surrogate code _points_, while the _FROM_LEAD() macros 41 * get special "folded" values for lead surrogate code _units_ if 42 * there is relevant data associated with them. 43 * From such a folded value, an offset needs to be extracted to supply 44 * to the _FROM_OFFSET_TRAIL() macros. 45 * 46 * Most of the more complex (and more convenient) functions/macros call a callback function 47 * to get that offset from the folded value for a lead surrogate unit. 48 */ 49 50 /** 51 * Trie constants, defining shift widths, index array lengths, etc. 52 */ 53 enum { 54 /** Shift size for shifting right the input index. 1..9 */ 55 UTRIE_SHIFT=5, 56 57 /** Number of data values in a stage 2 (data array) block. 2, 4, 8, .., 0x200 */ 58 UTRIE_DATA_BLOCK_LENGTH=1<<UTRIE_SHIFT, 59 60 /** Mask for getting the lower bits from the input index. */ 61 UTRIE_MASK=UTRIE_DATA_BLOCK_LENGTH-1, 62 63 /** 64 * Lead surrogate code points' index displacement in the index array. 65 * 0x10000-0xd800=0x2800 66 */ 67 UTRIE_LEAD_INDEX_DISP=0x2800>>UTRIE_SHIFT, 68 69 /** 70 * Shift size for shifting left the index array values. 71 * Increases possible data size with 16-bit index values at the cost 72 * of compactability. 73 * This requires blocks of stage 2 data to be aligned by UTRIE_DATA_GRANULARITY. 74 * 0..UTRIE_SHIFT 75 */ 76 UTRIE_INDEX_SHIFT=2, 77 78 /** The alignment size of a stage 2 data block. Also the granularity for compaction. */ 79 UTRIE_DATA_GRANULARITY=1<<UTRIE_INDEX_SHIFT, 80 81 /** Number of bits of a trail surrogate that are used in index table lookups. */ 82 UTRIE_SURROGATE_BLOCK_BITS=10-UTRIE_SHIFT, 83 84 /** 85 * Number of index (stage 1) entries per lead surrogate. 86 * Same as number of index entries for 1024 trail surrogates, 87 * ==0x400>>UTRIE_SHIFT 88 */ 89 UTRIE_SURROGATE_BLOCK_COUNT=(1<<UTRIE_SURROGATE_BLOCK_BITS), 90 91 /** Length of the BMP portion of the index (stage 1) array. */ 92 UTRIE_BMP_INDEX_LENGTH=0x10000>>UTRIE_SHIFT 93 }; 94 95 /** 96 * Length of the index (stage 1) array before folding. 97 * Maximum number of Unicode code points (0x110000) shifted right by UTRIE_SHIFT. 98 */ 99 #define UTRIE_MAX_INDEX_LENGTH (0x110000>>UTRIE_SHIFT) 100 101 /** 102 * Maximum length of the runtime data (stage 2) array. 103 * Limited by 16-bit index values that are left-shifted by UTRIE_INDEX_SHIFT. 104 */ 105 #define UTRIE_MAX_DATA_LENGTH (0x10000<<UTRIE_INDEX_SHIFT) 106 107 /** 108 * Maximum length of the build-time data (stage 2) array. 109 * The maximum length is 0x110000+UTRIE_DATA_BLOCK_LENGTH+0x400. 110 * (Number of Unicode code points + one all-initial-value block + 111 * possible duplicate entries for 1024 lead surrogates.) 112 */ 113 #define UTRIE_MAX_BUILD_TIME_DATA_LENGTH (0x110000+UTRIE_DATA_BLOCK_LENGTH+0x400) 114 115 /** 116 * Number of bytes for a dummy trie. 117 * A dummy trie is an empty runtime trie, used when a real data trie cannot 118 * be loaded. 119 * The number of bytes works for Latin-1-linear tries with 32-bit data 120 * (worst case). 121 * 122 * Calculation: 123 * BMP index + 1 index block for lead surrogate code points + 124 * Latin-1-linear array + 1 data block for lead surrogate code points 125 * 126 * Latin-1: if(UTRIE_SHIFT<=8) { 256 } else { included in first data block } 127 * 128 * @see utrie_unserializeDummy 129 */ 130 #define UTRIE_DUMMY_SIZE ((UTRIE_BMP_INDEX_LENGTH+UTRIE_SURROGATE_BLOCK_COUNT)*2+(UTRIE_SHIFT<=8?256:UTRIE_DATA_BLOCK_LENGTH)*4+UTRIE_DATA_BLOCK_LENGTH*4) 131 132 /** 133 * Runtime UTrie callback function. 134 * Extract from a lead surrogate's data the 135 * index array offset of the indexes for that lead surrogate. 136 * 137 * @param data data value for a surrogate from the trie, including the folding offset 138 * @return offset>=UTRIE_BMP_INDEX_LENGTH, or 0 if there is no data for the lead surrogate 139 */ 140 typedef int32_t U_CALLCONV 141 UTrieGetFoldingOffset(uint32_t data); 142 143 /** 144 * Run-time Trie structure. 145 * 146 * Either the data table is 16 bits wide and accessed via the index 147 * pointer, with each index item increased by indexLength; 148 * in this case, data32==NULL. 149 * 150 * Or the data table is 32 bits wide and accessed via the data32 pointer. 151 */ 152 struct UTrie { 153 const uint16_t *index; 154 const uint32_t *data32; /* NULL if 16b data is used via index */ 155 156 /** 157 * This function is not used in _FROM_LEAD, _FROM_BMP, and _FROM_OFFSET_TRAIL macros. 158 * If convenience macros like _GET16 or _NEXT32 are used, this function must be set. 159 * 160 * utrie_unserialize() sets a default function which simply returns 161 * the lead surrogate's value itself - which is the inverse of the default 162 * folding function used by utrie_serialize(). 163 * 164 * @see UTrieGetFoldingOffset 165 */ 166 UTrieGetFoldingOffset *getFoldingOffset; 167 168 int32_t indexLength, dataLength; 169 uint32_t initialValue; 170 UBool isLatin1Linear; 171 }; 172 173 #ifndef __UTRIE2_H__ 174 typedef struct UTrie UTrie; 175 #endif 176 177 /** Internal trie getter from an offset (0 if c16 is a BMP/lead units) and a 16-bit unit */ 178 #define _UTRIE_GET_RAW(trie, data, offset, c16) \ 179 (trie)->data[ \ 180 ((int32_t)((trie)->index[(offset)+((c16)>>UTRIE_SHIFT)])<<UTRIE_INDEX_SHIFT)+ \ 181 ((c16)&UTRIE_MASK) \ 182 ] 183 184 /** Internal trie getter from a pair of surrogates */ 185 #define _UTRIE_GET_FROM_PAIR(trie, data, c, c2, result, resultType) UPRV_BLOCK_MACRO_BEGIN { \ 186 int32_t __offset; \ 187 \ 188 /* get data for lead surrogate */ \ 189 (result)=_UTRIE_GET_RAW((trie), data, 0, (c)); \ 190 __offset=(trie)->getFoldingOffset(result); \ 191 \ 192 /* get the real data from the folded lead/trail units */ \ 193 if(__offset>0) { \ 194 (result)=_UTRIE_GET_RAW((trie), data, __offset, (c2)&0x3ff); \ 195 } else { \ 196 (result)=(resultType)((trie)->initialValue); \ 197 } \ 198 } UPRV_BLOCK_MACRO_END 199 200 /** Internal trie getter from a BMP code point, treating a lead surrogate as a normal code point */ 201 #define _UTRIE_GET_FROM_BMP(trie, data, c16) \ 202 _UTRIE_GET_RAW(trie, data, 0xd800<=(c16) && (c16)<=0xdbff ? UTRIE_LEAD_INDEX_DISP : 0, c16) 203 204 /** 205 * Internal trie getter from a code point. 206 * Could be faster(?) but longer with 207 * if((c32)<=0xd7ff) { (result)=_UTRIE_GET_RAW(trie, data, 0, c32); } 208 */ 209 #define _UTRIE_GET(trie, data, c32, result, resultType) UPRV_BLOCK_MACRO_BEGIN { \ 210 if((uint32_t)(c32)<=0xffff) { \ 211 /* BMP code points */ \ 212 (result)=_UTRIE_GET_FROM_BMP(trie, data, c32); \ 213 } else if((uint32_t)(c32)<=0x10ffff) { \ 214 /* supplementary code point */ \ 215 UChar __lead16=U16_LEAD(c32); \ 216 _UTRIE_GET_FROM_PAIR(trie, data, __lead16, c32, result, resultType); \ 217 } else { \ 218 /* out of range */ \ 219 (result)=(resultType)((trie)->initialValue); \ 220 } \ 221 } UPRV_BLOCK_MACRO_END 222 223 /** Internal next-post-increment: get the next code point (c, c2) and its data */ 224 #define _UTRIE_NEXT(trie, data, src, limit, c, c2, result, resultType) UPRV_BLOCK_MACRO_BEGIN { \ 225 (c)=*(src)++; \ 226 if(!U16_IS_LEAD(c)) { \ 227 (c2)=0; \ 228 (result)=_UTRIE_GET_RAW((trie), data, 0, (c)); \ 229 } else if((src)!=(limit) && U16_IS_TRAIL((c2)=*(src))) { \ 230 ++(src); \ 231 _UTRIE_GET_FROM_PAIR((trie), data, (c), (c2), (result), resultType); \ 232 } else { \ 233 /* unpaired lead surrogate code point */ \ 234 (c2)=0; \ 235 (result)=_UTRIE_GET_RAW((trie), data, UTRIE_LEAD_INDEX_DISP, (c)); \ 236 } \ 237 } UPRV_BLOCK_MACRO_END 238 239 /** Internal previous: get the previous code point (c, c2) and its data */ 240 #define _UTRIE_PREVIOUS(trie, data, start, src, c, c2, result, resultType) UPRV_BLOCK_MACRO_BEGIN { \ 241 (c)=*--(src); \ 242 if(!U16_IS_SURROGATE(c)) { \ 243 (c2)=0; \ 244 (result)=_UTRIE_GET_RAW((trie), data, 0, (c)); \ 245 } else if(!U16_IS_SURROGATE_LEAD(c)) { \ 246 /* trail surrogate */ \ 247 if((start)!=(src) && U16_IS_LEAD((c2)=*((src)-1))) { \ 248 --(src); \ 249 (result)=(c); (c)=(c2); (c2)=(UChar)(result); /* swap c, c2 */ \ 250 _UTRIE_GET_FROM_PAIR((trie), data, (c), (c2), (result), resultType); \ 251 } else { \ 252 /* unpaired trail surrogate code point */ \ 253 (c2)=0; \ 254 (result)=_UTRIE_GET_RAW((trie), data, 0, (c)); \ 255 } \ 256 } else { \ 257 /* unpaired lead surrogate code point */ \ 258 (c2)=0; \ 259 (result)=_UTRIE_GET_RAW((trie), data, UTRIE_LEAD_INDEX_DISP, (c)); \ 260 } \ 261 } UPRV_BLOCK_MACRO_END 262 263 /* Public UTrie API ---------------------------------------------------------*/ 264 265 /** 266 * Get a pointer to the contiguous part of the data array 267 * for the Latin-1 range (U+0000..U+00ff). 268 * Must be used only if the Latin-1 range is in fact linear 269 * (trie->isLatin1Linear). 270 * 271 * @param trie (const UTrie *, in) a pointer to the runtime trie structure 272 * @return (const uint16_t *) pointer to values for Latin-1 code points 273 */ 274 #define UTRIE_GET16_LATIN1(trie) ((trie)->index+(trie)->indexLength+UTRIE_DATA_BLOCK_LENGTH) 275 276 /** 277 * Get a pointer to the contiguous part of the data array 278 * for the Latin-1 range (U+0000..U+00ff). 279 * Must be used only if the Latin-1 range is in fact linear 280 * (trie->isLatin1Linear). 281 * 282 * @param trie (const UTrie *, in) a pointer to the runtime trie structure 283 * @return (const uint32_t *) pointer to values for Latin-1 code points 284 */ 285 #define UTRIE_GET32_LATIN1(trie) ((trie)->data32+UTRIE_DATA_BLOCK_LENGTH) 286 287 /** 288 * Get a 16-bit trie value from a BMP code point (UChar, <=U+ffff). 289 * c16 may be a lead surrogate, which may have a value including a folding offset. 290 * 291 * @param trie (const UTrie *, in) a pointer to the runtime trie structure 292 * @param c16 (UChar, in) the input BMP code point 293 * @return (uint16_t) trie lookup result 294 */ 295 #define UTRIE_GET16_FROM_LEAD(trie, c16) _UTRIE_GET_RAW(trie, index, 0, c16) 296 297 /** 298 * Get a 32-bit trie value from a BMP code point (UChar, <=U+ffff). 299 * c16 may be a lead surrogate, which may have a value including a folding offset. 300 * 301 * @param trie (const UTrie *, in) a pointer to the runtime trie structure 302 * @param c16 (UChar, in) the input BMP code point 303 * @return (uint32_t) trie lookup result 304 */ 305 #define UTRIE_GET32_FROM_LEAD(trie, c16) _UTRIE_GET_RAW(trie, data32, 0, c16) 306 307 /** 308 * Get a 16-bit trie value from a BMP code point (UChar, <=U+ffff). 309 * Even lead surrogate code points are treated as normal code points, 310 * with unfolded values that may differ from _FROM_LEAD() macro results for them. 311 * 312 * @param trie (const UTrie *, in) a pointer to the runtime trie structure 313 * @param c16 (UChar, in) the input BMP code point 314 * @return (uint16_t) trie lookup result 315 */ 316 #define UTRIE_GET16_FROM_BMP(trie, c16) _UTRIE_GET_FROM_BMP(trie, index, c16) 317 318 /** 319 * Get a 32-bit trie value from a BMP code point (UChar, <=U+ffff). 320 * Even lead surrogate code points are treated as normal code points, 321 * with unfolded values that may differ from _FROM_LEAD() macro results for them. 322 * 323 * @param trie (const UTrie *, in) a pointer to the runtime trie structure 324 * @param c16 (UChar, in) the input BMP code point 325 * @return (uint32_t) trie lookup result 326 */ 327 #define UTRIE_GET32_FROM_BMP(trie, c16) _UTRIE_GET_FROM_BMP(trie, data32, c16) 328 329 /** 330 * Get a 16-bit trie value from a code point. 331 * Even lead surrogate code points are treated as normal code points, 332 * with unfolded values that may differ from _FROM_LEAD() macro results for them. 333 * 334 * @param trie (const UTrie *, in) a pointer to the runtime trie structure 335 * @param c32 (UChar32, in) the input code point 336 * @param result (uint16_t, out) uint16_t variable for the trie lookup result 337 */ 338 #define UTRIE_GET16(trie, c32, result) _UTRIE_GET(trie, index, c32, result, uint16_t) 339 340 /** 341 * Get a 32-bit trie value from a code point. 342 * Even lead surrogate code points are treated as normal code points, 343 * with unfolded values that may differ from _FROM_LEAD() macro results for them. 344 * 345 * @param trie (const UTrie *, in) a pointer to the runtime trie structure 346 * @param c32 (UChar32, in) the input code point 347 * @param result (uint32_t, out) uint32_t variable for the trie lookup result 348 */ 349 #define UTRIE_GET32(trie, c32, result) _UTRIE_GET(trie, data32, c32, result, uint32_t) 350 351 /** 352 * Get the next code point (c, c2), post-increment src, 353 * and get a 16-bit value from the trie. 354 * 355 * @param trie (const UTrie *, in) a pointer to the runtime trie structure 356 * @param src (const UChar *, in/out) the source text pointer 357 * @param limit (const UChar *, in) the limit pointer for the text, or NULL 358 * @param c (UChar, out) variable for the BMP or lead code unit 359 * @param c2 (UChar, out) variable for 0 or the trail code unit 360 * @param result (uint16_t, out) uint16_t variable for the trie lookup result 361 */ 362 #define UTRIE_NEXT16(trie, src, limit, c, c2, result) _UTRIE_NEXT(trie, index, src, limit, c, c2, result, uint16_t) 363 364 /** 365 * Get the next code point (c, c2), post-increment src, 366 * and get a 32-bit value from the trie. 367 * 368 * @param trie (const UTrie *, in) a pointer to the runtime trie structure 369 * @param src (const UChar *, in/out) the source text pointer 370 * @param limit (const UChar *, in) the limit pointer for the text, or NULL 371 * @param c (UChar, out) variable for the BMP or lead code unit 372 * @param c2 (UChar, out) variable for 0 or the trail code unit 373 * @param result (uint32_t, out) uint32_t variable for the trie lookup result 374 */ 375 #define UTRIE_NEXT32(trie, src, limit, c, c2, result) _UTRIE_NEXT(trie, data32, src, limit, c, c2, result, uint32_t) 376 377 /** 378 * Get the previous code point (c, c2), pre-decrement src, 379 * and get a 16-bit value from the trie. 380 * 381 * @param trie (const UTrie *, in) a pointer to the runtime trie structure 382 * @param start (const UChar *, in) the start pointer for the text, or NULL 383 * @param src (const UChar *, in/out) the source text pointer 384 * @param c (UChar, out) variable for the BMP or lead code unit 385 * @param c2 (UChar, out) variable for 0 or the trail code unit 386 * @param result (uint16_t, out) uint16_t variable for the trie lookup result 387 */ 388 #define UTRIE_PREVIOUS16(trie, start, src, c, c2, result) _UTRIE_PREVIOUS(trie, index, start, src, c, c2, result, uint16_t) 389 390 /** 391 * Get the previous code point (c, c2), pre-decrement src, 392 * and get a 32-bit value from the trie. 393 * 394 * @param trie (const UTrie *, in) a pointer to the runtime trie structure 395 * @param start (const UChar *, in) the start pointer for the text, or NULL 396 * @param src (const UChar *, in/out) the source text pointer 397 * @param c (UChar, out) variable for the BMP or lead code unit 398 * @param c2 (UChar, out) variable for 0 or the trail code unit 399 * @param result (uint32_t, out) uint32_t variable for the trie lookup result 400 */ 401 #define UTRIE_PREVIOUS32(trie, start, src, c, c2, result) _UTRIE_PREVIOUS(trie, data32, start, src, c, c2, result, uint32_t) 402 403 /** 404 * Get a 16-bit trie value from a pair of surrogates. 405 * 406 * @param trie (const UTrie *, in) a pointer to the runtime trie structure 407 * @param c (UChar, in) a lead surrogate 408 * @param c2 (UChar, in) a trail surrogate 409 * @param result (uint16_t, out) uint16_t variable for the trie lookup result 410 */ 411 #define UTRIE_GET16_FROM_PAIR(trie, c, c2, result) _UTRIE_GET_FROM_PAIR(trie, index, c, c2, result, uint16_t) 412 413 /** 414 * Get a 32-bit trie value from a pair of surrogates. 415 * 416 * @param trie (const UTrie *, in) a pointer to the runtime trie structure 417 * @param c (UChar, in) a lead surrogate 418 * @param c2 (UChar, in) a trail surrogate 419 * @param result (uint32_t, out) uint32_t variable for the trie lookup result 420 */ 421 #define UTRIE_GET32_FROM_PAIR(trie, c, c2, result) _UTRIE_GET_FROM_PAIR(trie, data32, c, c2, result, uint32_t) 422 423 /** 424 * Get a 16-bit trie value from a folding offset (from the value of a lead surrogate) 425 * and a trail surrogate. 426 * 427 * @param trie (const UTrie *, in) a pointer to the runtime trie structure 428 * @param offset (int32_t, in) the folding offset from the value of a lead surrogate 429 * @param c2 (UChar, in) a trail surrogate (only the 10 low bits are significant) 430 * @return (uint16_t) trie lookup result 431 */ 432 #define UTRIE_GET16_FROM_OFFSET_TRAIL(trie, offset, c2) _UTRIE_GET_RAW(trie, index, offset, (c2)&0x3ff) 433 434 /** 435 * Get a 32-bit trie value from a folding offset (from the value of a lead surrogate) 436 * and a trail surrogate. 437 * 438 * @param trie (const UTrie *, in) a pointer to the runtime trie structure 439 * @param offset (int32_t, in) the folding offset from the value of a lead surrogate 440 * @param c2 (UChar, in) a trail surrogate (only the 10 low bits are significant) 441 * @return (uint32_t) trie lookup result 442 */ 443 #define UTRIE_GET32_FROM_OFFSET_TRAIL(trie, offset, c2) _UTRIE_GET_RAW(trie, data32, offset, (c2)&0x3ff) 444 445 /* enumeration callback types */ 446 447 /** 448 * Callback from utrie_enum(), extracts a uint32_t value from a 449 * trie value. This value will be passed on to the UTrieEnumRange function. 450 * 451 * @param context an opaque pointer, as passed into utrie_enum() 452 * @param value a value from the trie 453 * @return the value that is to be passed on to the UTrieEnumRange function 454 */ 455 typedef uint32_t U_CALLCONV 456 UTrieEnumValue(const void *context, uint32_t value); 457 458 /** 459 * Callback from utrie_enum(), is called for each contiguous range 460 * of code points with the same value as retrieved from the trie and 461 * transformed by the UTrieEnumValue function. 462 * 463 * The callback function can stop the enumeration by returning FALSE. 464 * 465 * @param context an opaque pointer, as passed into utrie_enum() 466 * @param start the first code point in a contiguous range with value 467 * @param limit one past the last code point in a contiguous range with value 468 * @param value the value that is set for all code points in [start..limit[ 469 * @return FALSE to stop the enumeration 470 */ 471 typedef UBool U_CALLCONV 472 UTrieEnumRange(const void *context, UChar32 start, UChar32 limit, uint32_t value); 473 474 /** 475 * Enumerate efficiently all values in a trie. 476 * For each entry in the trie, the value to be delivered is passed through 477 * the UTrieEnumValue function. 478 * The value is unchanged if that function pointer is NULL. 479 * 480 * For each contiguous range of code points with a given value, 481 * the UTrieEnumRange function is called. 482 * 483 * @param trie a pointer to the runtime trie structure 484 * @param enumValue a pointer to a function that may transform the trie entry value, 485 * or NULL if the values from the trie are to be used directly 486 * @param enumRange a pointer to a function that is called for each contiguous range 487 * of code points with the same value 488 * @param context an opaque pointer that is passed on to the callback functions 489 */ 490 U_CAPI void U_EXPORT2 491 utrie_enum(const UTrie *trie, 492 UTrieEnumValue *enumValue, UTrieEnumRange *enumRange, const void *context); 493 494 /** 495 * Unserialize a trie from 32-bit-aligned memory. 496 * Inverse of utrie_serialize(). 497 * Fills the UTrie runtime trie structure with the settings for the trie data. 498 * 499 * @param trie a pointer to the runtime trie structure 500 * @param data a pointer to 32-bit-aligned memory containing trie data 501 * @param length the number of bytes available at data 502 * @param pErrorCode an in/out ICU UErrorCode 503 * @return the number of bytes at data taken up by the trie data 504 */ 505 U_CAPI int32_t U_EXPORT2 506 utrie_unserialize(UTrie *trie, const void *data, int32_t length, UErrorCode *pErrorCode); 507 508 /** 509 * "Unserialize" a dummy trie. 510 * A dummy trie is an empty runtime trie, used when a real data trie cannot 511 * be loaded. 512 * 513 * The input memory is filled so that the trie always returns the initialValue, 514 * or the leadUnitValue for lead surrogate code points. 515 * The Latin-1 part is always set up to be linear. 516 * 517 * @param trie a pointer to the runtime trie structure 518 * @param data a pointer to 32-bit-aligned memory to be filled with the dummy trie data 519 * @param length the number of bytes available at data (recommended to use UTRIE_DUMMY_SIZE) 520 * @param initialValue the initial value that is set for all code points 521 * @param leadUnitValue the value for lead surrogate code _units_ that do not 522 * have associated supplementary data 523 * @param pErrorCode an in/out ICU UErrorCode 524 * 525 * @see UTRIE_DUMMY_SIZE 526 * @see utrie_open 527 */ 528 U_CAPI int32_t U_EXPORT2 529 utrie_unserializeDummy(UTrie *trie, 530 void *data, int32_t length, 531 uint32_t initialValue, uint32_t leadUnitValue, 532 UBool make16BitTrie, 533 UErrorCode *pErrorCode); 534 535 /** 536 * Default implementation for UTrie.getFoldingOffset, set automatically by 537 * utrie_unserialize(). 538 * Simply returns the lead surrogate's value itself - which is the inverse 539 * of the default folding function used by utrie_serialize(). 540 * Exported for static const UTrie structures. 541 * 542 * @see UTrieGetFoldingOffset 543 */ 544 U_CAPI int32_t U_EXPORT2 545 utrie_defaultGetFoldingOffset(uint32_t data); 546 547 /* Building a trie ----------------------------------------------------------*/ 548 549 /** 550 * Build-time trie structure. 551 * Opaque definition, here only to make fillIn parameters possible 552 * for utrie_open() and utrie_clone(). 553 */ 554 struct UNewTrie { 555 /** 556 * Index values at build-time are 32 bits wide for easier processing. 557 * Bit 31 is set if the data block is used by multiple index values (from utrie_setRange()). 558 */ 559 int32_t index[UTRIE_MAX_INDEX_LENGTH+UTRIE_SURROGATE_BLOCK_COUNT]; 560 uint32_t *data; 561 562 uint32_t leadUnitValue; 563 int32_t indexLength, dataCapacity, dataLength; 564 UBool isAllocated, isDataAllocated; 565 UBool isLatin1Linear, isCompacted; 566 567 /** 568 * Map of adjusted indexes, used in utrie_compact(). 569 * Maps from original indexes to new ones. 570 */ 571 int32_t map[UTRIE_MAX_BUILD_TIME_DATA_LENGTH>>UTRIE_SHIFT]; 572 }; 573 574 typedef struct UNewTrie UNewTrie; 575 576 /** 577 * Build-time trie callback function, used with utrie_serialize(). 578 * This function calculates a lead surrogate's value including a folding offset 579 * from the 1024 supplementary code points [start..start+1024[ . 580 * It is U+10000 <= start <= U+10fc00 and (start&0x3ff)==0. 581 * 582 * The folding offset is provided by the caller. 583 * It is offset=UTRIE_BMP_INDEX_LENGTH+n*UTRIE_SURROGATE_BLOCK_COUNT with n=0..1023. 584 * Instead of the offset itself, n can be stored in 10 bits - 585 * or fewer if it can be assumed that few lead surrogates have associated data. 586 * 587 * The returned value must be 588 * - not zero if and only if there is relevant data 589 * for the corresponding 1024 supplementary code points 590 * - such that UTrie.getFoldingOffset(UNewTrieGetFoldedValue(..., offset))==offset 591 * 592 * @return a folded value, or 0 if there is no relevant data for the lead surrogate. 593 */ 594 typedef uint32_t U_CALLCONV 595 UNewTrieGetFoldedValue(UNewTrie *trie, UChar32 start, int32_t offset); 596 597 /** 598 * Open a build-time trie structure. 599 * The size of the build-time data array is specified to avoid allocating a large 600 * array in all cases. The array itself can also be passed in. 601 * 602 * Although the trie is never fully expanded to a linear array, especially when 603 * utrie_setRange32() is used, the data array could be large during build time. 604 * The maximum length is 605 * UTRIE_MAX_BUILD_TIME_DATA_LENGTH=0x110000+UTRIE_DATA_BLOCK_LENGTH+0x400. 606 * (Number of Unicode code points + one all-initial-value block + 607 * possible duplicate entries for 1024 lead surrogates.) 608 * (UTRIE_DATA_BLOCK_LENGTH<=0x200 in all cases.) 609 * 610 * @param fillIn a pointer to a UNewTrie structure to be initialized (will not be released), or 611 * NULL if one is to be allocated 612 * @param aliasData a pointer to a data array to be used (will not be released), or 613 * NULL if one is to be allocated 614 * @param maxDataLength the capacity of aliasData (if not NULL) or 615 * the length of the data array to be allocated 616 * @param initialValue the initial value that is set for all code points 617 * @param leadUnitValue the value for lead surrogate code _units_ that do not 618 * have associated supplementary data 619 * @param latin1Linear a flag indicating whether the Latin-1 range is to be allocated and 620 * kept in a linear, contiguous part of the data array 621 * @return a pointer to the initialized fillIn or the allocated and initialized new UNewTrie 622 */ 623 U_CAPI UNewTrie * U_EXPORT2 624 utrie_open(UNewTrie *fillIn, 625 uint32_t *aliasData, int32_t maxDataLength, 626 uint32_t initialValue, uint32_t leadUnitValue, 627 UBool latin1Linear); 628 629 /** 630 * Clone a build-time trie structure with all entries. 631 * 632 * @param fillIn like in utrie_open() 633 * @param other the build-time trie structure to clone 634 * @param aliasData like in utrie_open(), 635 * used if aliasDataLength>=(capacity of other's data array) 636 * @param aliasDataLength the length of aliasData 637 * @return a pointer to the initialized fillIn or the allocated and initialized new UNewTrie 638 */ 639 U_CAPI UNewTrie * U_EXPORT2 640 utrie_clone(UNewTrie *fillIn, const UNewTrie *other, uint32_t *aliasData, int32_t aliasDataLength); 641 642 /** 643 * Close a build-time trie structure, and release memory 644 * that was allocated by utrie_open() or utrie_clone(). 645 * 646 * @param trie the build-time trie 647 */ 648 U_CAPI void U_EXPORT2 649 utrie_close(UNewTrie *trie); 650 651 /** 652 * Get the data array of a build-time trie. 653 * The data may be modified, but entries that are equal before 654 * must still be equal after modification. 655 * 656 * @param trie the build-time trie 657 * @param pLength (out) a pointer to a variable that receives the number 658 * of entries in the data array 659 * @return the data array 660 */ 661 U_CAPI uint32_t * U_EXPORT2 662 utrie_getData(UNewTrie *trie, int32_t *pLength); 663 664 /** 665 * Set a value for a code point. 666 * 667 * @param trie the build-time trie 668 * @param c the code point 669 * @param value the value 670 * @return FALSE if a failure occurred (illegal argument or data array overrun) 671 */ 672 U_CAPI UBool U_EXPORT2 673 utrie_set32(UNewTrie *trie, UChar32 c, uint32_t value); 674 675 /** 676 * Get a value from a code point as stored in the build-time trie. 677 * 678 * @param trie the build-time trie 679 * @param c the code point 680 * @param pInBlockZero if not NULL, then *pInBlockZero is set to TRUE 681 * iff the value is retrieved from block 0; 682 * block 0 is the all-initial-value initial block 683 * @return the value 684 */ 685 U_CAPI uint32_t U_EXPORT2 686 utrie_get32(UNewTrie *trie, UChar32 c, UBool *pInBlockZero); 687 688 /** 689 * Set a value in a range of code points [start..limit[. 690 * All code points c with start<=c<limit will get the value if 691 * overwrite is TRUE or if the old value is 0. 692 * 693 * @param trie the build-time trie 694 * @param start the first code point to get the value 695 * @param limit one past the last code point to get the value 696 * @param value the value 697 * @param overwrite flag for whether old non-initial values are to be overwritten 698 * @return FALSE if a failure occurred (illegal argument or data array overrun) 699 */ 700 U_CAPI UBool U_EXPORT2 701 utrie_setRange32(UNewTrie *trie, UChar32 start, UChar32 limit, uint32_t value, UBool overwrite); 702 703 /** 704 * Compact the build-time trie after all values are set, and then 705 * serialize it into 32-bit aligned memory. 706 * 707 * After this, the trie can only be serizalized again and/or closed; 708 * no further values can be added. 709 * 710 * @see utrie_unserialize() 711 * 712 * @param trie the build-time trie 713 * @param data a pointer to 32-bit-aligned memory for the trie data 714 * @param capacity the number of bytes available at data 715 * @param getFoldedValue a callback function that calculates the value for 716 * a lead surrogate from all of its supplementary code points 717 * and the folding offset; 718 * if NULL, then a default function is used which returns just 719 * the input offset when there are any non-initial-value entries 720 * @param reduceTo16Bits flag for whether the values are to be reduced to a 721 * width of 16 bits for serialization and runtime 722 * @param pErrorCode a UErrorCode argument; among other possible error codes: 723 * - U_BUFFER_OVERFLOW_ERROR if the data storage block is too small for serialization 724 * - U_MEMORY_ALLOCATION_ERROR if the trie data array is too small 725 * - U_INDEX_OUTOFBOUNDS_ERROR if the index or data arrays are too long after compaction for serialization 726 * 727 * @return the number of bytes written for the trie 728 */ 729 U_CAPI int32_t U_EXPORT2 730 utrie_serialize(UNewTrie *trie, void *data, int32_t capacity, 731 UNewTrieGetFoldedValue *getFoldedValue, 732 UBool reduceTo16Bits, 733 UErrorCode *pErrorCode); 734 735 /* serialization ------------------------------------------------------------ */ 736 737 // UTrie signature values, in platform endianness and opposite endianness. 738 // The UTrie signature ASCII byte values spell "Trie". 739 #define UTRIE_SIG 0x54726965 740 #define UTRIE_OE_SIG 0x65697254 741 742 /** 743 * Trie data structure in serialized form: 744 * 745 * UTrieHeader header; 746 * uint16_t index[header.indexLength]; 747 * uint16_t data[header.dataLength]; 748 * @internal 749 */ 750 typedef struct UTrieHeader { 751 /** "Trie" in big-endian US-ASCII (0x54726965) */ 752 uint32_t signature; 753 754 /** 755 * options bit field: 756 * 9 1=Latin-1 data is stored linearly at data+UTRIE_DATA_BLOCK_LENGTH 757 * 8 0=16-bit data, 1=32-bit data 758 * 7..4 UTRIE_INDEX_SHIFT // 0..UTRIE_SHIFT 759 * 3..0 UTRIE_SHIFT // 1..9 760 */ 761 uint32_t options; 762 763 /** indexLength is a multiple of UTRIE_SURROGATE_BLOCK_COUNT */ 764 int32_t indexLength; 765 766 /** dataLength>=UTRIE_DATA_BLOCK_LENGTH */ 767 int32_t dataLength; 768 } UTrieHeader; 769 770 /** 771 * Constants for use with UTrieHeader.options. 772 * @internal 773 */ 774 enum { 775 /** Mask to get the UTRIE_SHIFT value from options. */ 776 UTRIE_OPTIONS_SHIFT_MASK=0xf, 777 778 /** Shift options right this much to get the UTRIE_INDEX_SHIFT value. */ 779 UTRIE_OPTIONS_INDEX_SHIFT=4, 780 781 /** If set, then the data (stage 2) array is 32 bits wide. */ 782 UTRIE_OPTIONS_DATA_IS_32_BIT=0x100, 783 784 /** 785 * If set, then Latin-1 data (for U+0000..U+00ff) is stored in the data (stage 2) array 786 * as a simple, linear array at data+UTRIE_DATA_BLOCK_LENGTH. 787 */ 788 UTRIE_OPTIONS_LATIN1_IS_LINEAR=0x200 789 }; 790 791 U_CDECL_END 792 793 #endif 794