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