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