icuSources/common/utrie.h

   1 /*
   2 ******************************************************************************
   3 *
   4 *   Copyright (C) 2001-2004, 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  * Runtime UTrie callback function.
 115  * Extract from a lead surrogate's data the
 116  * index array offset of the indexes for that lead surrogate.
 117  *
 118  * @param data data value for a surrogate from the trie, including the folding offset
 119  * @return offset>=UTRIE_BMP_INDEX_LENGTH, or 0 if there is no data for the lead surrogate
 120  */
 121 typedef int32_t U_CALLCONV
 122 UTrieGetFoldingOffset(uint32_t data);
 123
 124 /**
 125  * Run-time Trie structure.
 126  *
 127  * Either the data table is 16 bits wide and accessed via the index
 128  * pointer, with each index item increased by indexLength;
 129  * in this case, data32==NULL.
 130  *
 131  * Or the data table is 32 bits wide and accessed via the data32 pointer.
 132  */
 133 struct UTrie {
 134     const uint16_t *index;
 135     const uint32_t *data32; /* NULL if 16b data is used via index */
 136
 137     /**
 138      * This function is not used in _FROM_LEAD, _FROM_BMP, and _FROM_OFFSET_TRAIL macros.
 139      * If convenience macros like _GET16 or _NEXT32 are used, this function must be set.
 140      *
 141      * utrie_unserialize() sets a default function which simply returns
 142      * the lead surrogate's value itself - which is the inverse of the default
 143      * folding function used by utrie_serialize().
 144      *
 145      * @see UTrieGetFoldingOffset
 146      */
 147     UTrieGetFoldingOffset *getFoldingOffset;
 148
 149     int32_t indexLength, dataLength;
 150     uint32_t initialValue;
 151     UBool isLatin1Linear;
 152 };
 153
 154 typedef struct UTrie UTrie;
 155
 156 /** Internal trie getter from an offset (0 if c16 is a BMP/lead units) and a 16-bit unit */
 157 #define _UTRIE_GET_RAW(trie, data, offset, c16) \
 158     (trie)->data[ \
 159         ((int32_t)((trie)->index[(offset)+((c16)>>UTRIE_SHIFT)])<<UTRIE_INDEX_SHIFT)+ \
 160         ((c16)&UTRIE_MASK) \
 161     ]
 162
 163 /** Internal trie getter from a pair of surrogates */
 164 #define _UTRIE_GET_FROM_PAIR(trie, data, c, c2, result, resultType) { \
 165     int32_t __offset; \
 166 \
 167     /* get data for lead surrogate */ \
 168     (result)=_UTRIE_GET_RAW((trie), data, 0, (c)); \
 169     __offset=(trie)->getFoldingOffset(result); \
 170 \
 171     /* get the real data from the folded lead/trail units */ \
 172     if(__offset>0) { \
 173         (result)=_UTRIE_GET_RAW((trie), data, __offset, (c2)&0x3ff); \
 174     } else { \
 175         (result)=(resultType)((trie)->initialValue); \
 176     } \
 177 }
 178
 179 /** Internal trie getter from a BMP code point, treating a lead surrogate as a normal code point */
 180 #define _UTRIE_GET_FROM_BMP(trie, data, c16) \
 181     _UTRIE_GET_RAW(trie, data, 0xd800<=(c16) && (c16)<=0xdbff ? UTRIE_LEAD_INDEX_DISP : 0, c16);
 182
 183 /**
 184  * Internal trie getter from a code point.
 185  * Could be faster(?) but longer with
 186  *   if((c32)<=0xd7ff) { (result)=_UTRIE_GET_RAW(trie, data, 0, c32); }
 187  */
 188 #define _UTRIE_GET(trie, data, c32, result, resultType) \
 189     if((uint32_t)(c32)<=0xffff) { \
 190         /* BMP code points */ \
 191         (result)=_UTRIE_GET_FROM_BMP(trie, data, c32); \
 192     } else if((uint32_t)(c32)<=0x10ffff) { \
 193         /* supplementary code point */ \
 194         UChar __lead16=UTF16_LEAD(c32); \
 195         _UTRIE_GET_FROM_PAIR(trie, data, __lead16, c32, result, resultType); \
 196     } else { \
 197         /* out of range */ \
 198         (result)=(resultType)((trie)->initialValue); \
 199     }
 200
 201 /** Internal next-post-increment: get the next code point (c, c2) and its data */
 202 #define _UTRIE_NEXT(trie, data, src, limit, c, c2, result, resultType) { \
 203     (c)=*(src)++; \
 204     if(!UTF_IS_LEAD(c)) { \
 205         (c2)=0; \
 206         (result)=_UTRIE_GET_RAW((trie), data, 0, (c)); \
 207     } else if((src)!=(limit) && UTF_IS_TRAIL((c2)=*(src))) { \
 208         ++(src); \
 209         _UTRIE_GET_FROM_PAIR((trie), data, (c), (c2), (result), resultType); \
 210     } else { \
 211         /* unpaired lead surrogate code point */ \
 212         (c2)=0; \
 213         (result)=_UTRIE_GET_RAW((trie), data, UTRIE_LEAD_INDEX_DISP, (c)); \
 214     } \
 215 }
 216
 217 /** Internal previous: get the previous code point (c, c2) and its data */
 218 #define _UTRIE_PREVIOUS(trie, data, start, src, c, c2, result, resultType) { \
 219     (c)=*--(src); \
 220     if(!UTF_IS_SURROGATE(c)) { \
 221         (c2)=0; \
 222         (result)=_UTRIE_GET_RAW((trie), data, 0, (c)); \
 223     } else if(!UTF_IS_SURROGATE_FIRST(c)) { \
 224         /* trail surrogate */ \
 225         if((start)!=(src) && UTF_IS_LEAD((c2)=*((src)-1))) { \
 226             --(src); \
 227             (result)=(c); (c)=(c2); (c2)=(UChar)(result); /* swap c, c2 */ \
 228             _UTRIE_GET_FROM_PAIR((trie), data, (c), (c2), (result), resultType); \
 229         } else { \
 230             /* unpaired trail surrogate code point */ \
 231             (c2)=0; \
 232             (result)=_UTRIE_GET_RAW((trie), data, 0, (c)); \
 233         } \
 234     } else { \
 235         /* unpaired lead surrogate code point */ \
 236         (c2)=0; \
 237         (result)=_UTRIE_GET_RAW((trie), data, UTRIE_LEAD_INDEX_DISP, (c)); \
 238     } \
 239 }
 240
 241 /* Public UTrie API ---------------------------------------------------------*/
 242
 243 /**
 244  * Get a pointer to the contiguous part of the data array
 245  * for the Latin-1 range (U+0000..U+00ff).
 246  * Must be used only if the Latin-1 range is in fact linear
 247  * (trie->isLatin1Linear).
 248  *
 249  * @param trie (const UTrie *, in) a pointer to the runtime trie structure
 250  * @return (const uint16_t *) pointer to values for Latin-1 code points
 251  */
 252 #define UTRIE_GET16_LATIN1(trie) ((trie)->index+(trie)->indexLength+UTRIE_DATA_BLOCK_LENGTH)
 253
 254 /**
 255  * Get a pointer to the contiguous part of the data array
 256  * for the Latin-1 range (U+0000..U+00ff).
 257  * Must be used only if the Latin-1 range is in fact linear
 258  * (trie->isLatin1Linear).
 259  *
 260  * @param trie (const UTrie *, in) a pointer to the runtime trie structure
 261  * @return (const uint32_t *) pointer to values for Latin-1 code points
 262  */
 263 #define UTRIE_GET32_LATIN1(trie) ((trie)->data32+UTRIE_DATA_BLOCK_LENGTH)
 264
 265 /**
 266  * Get a 16-bit trie value from a BMP code point (UChar, <=U+ffff).
 267  * c16 may be a lead surrogate, which may have a value including a folding offset.
 268  *
 269  * @param trie (const UTrie *, in) a pointer to the runtime trie structure
 270  * @param c16 (UChar, in) the input BMP code point
 271  * @return (uint16_t) trie lookup result
 272  */
 273 #define UTRIE_GET16_FROM_LEAD(trie, c16) _UTRIE_GET_RAW(trie, index, 0, c16)
 274
 275 /**
 276  * Get a 32-bit trie value from a BMP code point (UChar, <=U+ffff).
 277  * c16 may be a lead surrogate, which may have a value including a folding offset.
 278  *
 279  * @param trie (const UTrie *, in) a pointer to the runtime trie structure
 280  * @param c16 (UChar, in) the input BMP code point
 281  * @return (uint32_t) trie lookup result
 282  */
 283 #define UTRIE_GET32_FROM_LEAD(trie, c16) _UTRIE_GET_RAW(trie, data32, 0, c16)
 284
 285 /**
 286  * Get a 16-bit trie value from a BMP code point (UChar, <=U+ffff).
 287  * Even lead surrogate code points are treated as normal code points,
 288  * with unfolded values that may differ from _FROM_LEAD() macro results for them.
 289  *
 290  * @param trie (const UTrie *, in) a pointer to the runtime trie structure
 291  * @param c16 (UChar, in) the input BMP code point
 292  * @return (uint16_t) trie lookup result
 293  */
 294 #define UTRIE_GET16_FROM_BMP(trie, c16) _UTRIE_GET_FROM_BMP(trie, index, c16)
 295
 296 /**
 297  * Get a 32-bit trie value from a BMP code point (UChar, <=U+ffff).
 298  * Even lead surrogate code points are treated as normal code points,
 299  * with unfolded values that may differ from _FROM_LEAD() macro results for them.
 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_BMP(trie, c16) _UTRIE_GET_FROM_BMP(trie, data32, c16)
 306
 307 /**
 308  * Get a 16-bit trie value from a code point.
 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 c32 (UChar32, in) the input code point
 314  * @param result (uint16_t, out) uint16_t variable for the trie lookup result
 315  */
 316 #define UTRIE_GET16(trie, c32, result) _UTRIE_GET(trie, index, c32, result, uint16_t)
 317
 318 /**
 319  * Get a 32-bit trie value from a code point.
 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 c32 (UChar32, in) the input code point
 325  * @param result (uint32_t, out) uint32_t variable for the trie lookup result
 326  */
 327 #define UTRIE_GET32(trie, c32, result) _UTRIE_GET(trie, data32, c32, result, uint32_t)
 328
 329 /**
 330  * Get the next code point (c, c2), post-increment src,
 331  * and get a 16-bit value from the trie.
 332  *
 333  * @param trie (const UTrie *, in) a pointer to the runtime trie structure
 334  * @param src (const UChar *, in/out) the source text pointer
 335  * @param limit (const UChar *, in) the limit pointer for the text, or NULL
 336  * @param c (UChar, out) variable for the BMP or lead code unit
 337  * @param c2 (UChar, out) variable for 0 or the trail code unit
 338  * @param result (uint16_t, out) uint16_t variable for the trie lookup result
 339  */
 340 #define UTRIE_NEXT16(trie, src, limit, c, c2, result) _UTRIE_NEXT(trie, index, src, limit, c, c2, result, uint16_t)
 341
 342 /**
 343  * Get the next code point (c, c2), post-increment src,
 344  * and get a 32-bit value from the trie.
 345  *
 346  * @param trie (const UTrie *, in) a pointer to the runtime trie structure
 347  * @param src (const UChar *, in/out) the source text pointer
 348  * @param limit (const UChar *, in) the limit pointer for the text, or NULL
 349  * @param c (UChar, out) variable for the BMP or lead code unit
 350  * @param c2 (UChar, out) variable for 0 or the trail code unit
 351  * @param result (uint32_t, out) uint32_t variable for the trie lookup result
 352  */
 353 #define UTRIE_NEXT32(trie, src, limit, c, c2, result) _UTRIE_NEXT(trie, data32, src, limit, c, c2, result, uint32_t)
 354
 355 /**
 356  * Get the previous code point (c, c2), pre-decrement src,
 357  * and get a 16-bit value from the trie.
 358  *
 359  * @param trie (const UTrie *, in) a pointer to the runtime trie structure
 360  * @param start (const UChar *, in) the start pointer for the text, or NULL
 361  * @param src (const UChar *, in/out) the source text pointer
 362  * @param c (UChar, out) variable for the BMP or lead code unit
 363  * @param c2 (UChar, out) variable for 0 or the trail code unit
 364  * @param result (uint16_t, out) uint16_t variable for the trie lookup result
 365  */
 366 #define UTRIE_PREVIOUS16(trie, start, src, c, c2, result) _UTRIE_PREVIOUS(trie, index, start, src, c, c2, result, uint16_t)
 367
 368 /**
 369  * Get the previous code point (c, c2), pre-decrement src,
 370  * and get a 32-bit value from the trie.
 371  *
 372  * @param trie (const UTrie *, in) a pointer to the runtime trie structure
 373  * @param start (const UChar *, in) the start pointer for the text, or NULL
 374  * @param src (const UChar *, in/out) the source text pointer
 375  * @param c (UChar, out) variable for the BMP or lead code unit
 376  * @param c2 (UChar, out) variable for 0 or the trail code unit
 377  * @param result (uint32_t, out) uint32_t variable for the trie lookup result
 378  */
 379 #define UTRIE_PREVIOUS32(trie, start, src, c, c2, result) _UTRIE_PREVIOUS(trie, data32, start, src, c, c2, result, uint32_t)
 380
 381 /**
 382  * Get a 16-bit trie value from a pair of surrogates.
 383  *
 384  * @param trie (const UTrie *, in) a pointer to the runtime trie structure
 385  * @param c (UChar, in) a lead surrogate
 386  * @param c2 (UChar, in) a trail surrogate
 387  * @param result (uint16_t, out) uint16_t variable for the trie lookup result
 388  */
 389 #define UTRIE_GET16_FROM_PAIR(trie, c, c2, result) _UTRIE_GET_FROM_PAIR(trie, index, c, c2, result, uint16_t)
 390
 391 /**
 392  * Get a 32-bit trie value from a pair of surrogates.
 393  *
 394  * @param trie (const UTrie *, in) a pointer to the runtime trie structure
 395  * @param c (UChar, in) a lead surrogate
 396  * @param c2 (UChar, in) a trail surrogate
 397  * @param result (uint32_t, out) uint32_t variable for the trie lookup result
 398  */
 399 #define UTRIE_GET32_FROM_PAIR(trie, c, c2, result) _UTRIE_GET_FROM_PAIR(trie, data32, c, c2, result, uint32_t)
 400
 401 /**
 402  * Get a 16-bit trie value from a folding offset (from the value of a lead surrogate)
 403  * and a trail surrogate.
 404  *
 405  * @param trie (const UTrie *, in) a pointer to the runtime trie structure
 406  * @param offset (int32_t, in) the folding offset from the value of a lead surrogate
 407  * @param c2 (UChar, in) a trail surrogate (only the 10 low bits are significant)
 408  * @return (uint16_t) trie lookup result
 409  */
 410 #define UTRIE_GET16_FROM_OFFSET_TRAIL(trie, offset, c2) _UTRIE_GET_RAW(trie, index, offset, (c2)&0x3ff)
 411
 412 /**
 413  * Get a 32-bit trie value from a folding offset (from the value of a lead surrogate)
 414  * and a trail surrogate.
 415  *
 416  * @param trie (const UTrie *, in) a pointer to the runtime trie structure
 417  * @param offset (int32_t, in) the folding offset from the value of a lead surrogate
 418  * @param c2 (UChar, in) a trail surrogate (only the 10 low bits are significant)
 419  * @return (uint32_t) trie lookup result
 420  */
 421 #define UTRIE_GET32_FROM_OFFSET_TRAIL(trie, offset, c2) _UTRIE_GET_RAW(trie, data32, offset, (c2)&0x3ff)
 422
 423 /* enumeration callback types */
 424
 425 /**
 426  * Callback from utrie_enum(), extracts a uint32_t value from a
 427  * trie value. This value will be passed on to the UTrieEnumRange function.
 428  *
 429  * @param context an opaque pointer, as passed into utrie_enum()
 430  * @param value a value from the trie
 431  * @return the value that is to be passed on to the UTrieEnumRange function
 432  */
 433 typedef uint32_t U_CALLCONV
 434 UTrieEnumValue(const void *context, uint32_t value);
 435
 436 /**
 437  * Callback from utrie_enum(), is called for each contiguous range
 438  * of code points with the same value as retrieved from the trie and
 439  * transformed by the UTrieEnumValue function.
 440  *
 441  * The callback function can stop the enumeration by returning FALSE.
 442  *
 443  * @param context an opaque pointer, as passed into utrie_enum()
 444  * @param start the first code point in a contiguous range with value
 445  * @param limit one past the last code point in a contiguous range with value
 446  * @param value the value that is set for all code points in [start..limit[
 447  * @return FALSE to stop the enumeration
 448  */
 449 typedef UBool U_CALLCONV
 450 UTrieEnumRange(const void *context, UChar32 start, UChar32 limit, uint32_t value);
 451
 452 /**
 453  * Enumerate efficiently all values in a trie.
 454  * For each entry in the trie, the value to be delivered is passed through
 455  * the UTrieEnumValue function.
 456  * The value is unchanged if that function pointer is NULL.
 457  *
 458  * For each contiguous range of code points with a given value,
 459  * the UTrieEnumRange function is called.
 460  *
 461  * @param trie a pointer to the runtime trie structure
 462  * @param enumValue a pointer to a function that may transform the trie entry value,
 463  *                  or NULL if the values from the trie are to be used directly
 464  * @param enumRange a pointer to a function that is called for each contiguous range
 465  *                  of code points with the same value
 466  * @param context an opaque pointer that is passed on to the callback functions
 467  */
 468 U_CAPI void U_EXPORT2
 469 utrie_enum(const UTrie *trie,
 470            UTrieEnumValue *enumValue, UTrieEnumRange *enumRange, const void *context);
 471
 472 /**
 473  * Unserialize a trie from 32-bit-aligned memory.
 474  * Inverse of utrie_serialize().
 475  * Fills the UTrie runtime trie structure with the settings for the trie data.
 476  *
 477  * @param trie a pointer to the runtime trie structure
 478  * @param data a pointer to 32-bit-aligned memory containing trie data
 479  * @param length the number of bytes available at data
 480  * @param pErrorCode an in/out ICU UErrorCode
 481  * @return the number of bytes at data taken up by the trie data
 482  */
 483 U_CAPI int32_t U_EXPORT2
 484 utrie_unserialize(UTrie *trie, const void *data, int32_t length, UErrorCode *pErrorCode);
 485
 486 /* Building a trie ----------------------------------------------------------*/
 487
 488 /**
 489  * Build-time trie structure.
 490  * Opaque definition, here only to make fillIn parameters possible
 491  * for utrie_open() and utrie_clone().
 492  */
 493 struct UNewTrie {
 494     /**
 495      * Index values at build-time are 32 bits wide for easier processing.
 496      * Bit 31 is set if the data block is used by multiple index values (from utrie_setRange()).
 497      */
 498     int32_t index[UTRIE_MAX_INDEX_LENGTH];
 499     uint32_t *data;
 500
 501     uint32_t leadUnitValue;
 502     int32_t indexLength, dataCapacity, dataLength;
 503     UBool isAllocated, isDataAllocated;
 504     UBool isLatin1Linear, isCompacted;
 505
 506     /**
 507      * Map of adjusted indexes, used in utrie_compact().
 508      * Maps from original indexes to new ones.
 509      */
 510     int32_t map[UTRIE_MAX_BUILD_TIME_DATA_LENGTH>>UTRIE_SHIFT];
 511 };
 512
 513 typedef struct UNewTrie UNewTrie;
 514
 515 /**
 516  * Build-time trie callback function, used with utrie_serialize().
 517  * This function calculates a lead surrogate's value including a folding offset
 518  * from the 1024 supplementary code points [start..start+1024[ .
 519  * It is U+10000 <= start <= U+10fc00 and (start&0x3ff)==0.
 520  *
 521  * The folding offset is provided by the caller.
 522  * It is offset=UTRIE_BMP_INDEX_LENGTH+n*UTRIE_SURROGATE_BLOCK_COUNT with n=0..1023.
 523  * Instead of the offset itself, n can be stored in 10 bits -
 524  * or fewer if it can be assumed that few lead surrogates have associated data.
 525  *
 526  * The returned value must be
 527  * - not zero if and only if there is relevant data
 528  *   for the corresponding 1024 supplementary code points
 529  * - such that UTrie.getFoldingOffset(UNewTrieGetFoldedValue(..., offset))==offset
 530  *
 531  * @return a folded value, or 0 if there is no relevant data for the lead surrogate.
 532  */
 533 typedef uint32_t U_CALLCONV
 534 UNewTrieGetFoldedValue(UNewTrie *trie, UChar32 start, int32_t offset);
 535
 536 /**
 537  * Open a build-time trie structure.
 538  * The size of the build-time data array is specified to avoid allocating a large
 539  * array in all cases. The array itself can also be passed in.
 540  *
 541  * Although the trie is never fully expanded to a linear array, especially when
 542  * utrie_setRange32() is used, the data array could be large during build time.
 543  * The maximum length is
 544  * UTRIE_MAX_BUILD_TIME_DATA_LENGTH=0x110000+UTRIE_DATA_BLOCK_LENGTH+0x400.
 545  * (Number of Unicode code points + one all-initial-value block +
 546  *  possible duplicate entries for 1024 lead surrogates.)
 547  * (UTRIE_DATA_BLOCK_LENGTH<=0x200 in all cases.)
 548  *
 549  * @param fillIn a pointer to a UNewTrie structure to be initialized (will not be released), or
 550  *               NULL if one is to be allocated
 551  * @param aliasData a pointer to a data array to be used (will not be released), or
 552  *                  NULL if one is to be allocated
 553  * @param maxDataLength the capacity of aliasData (if not NULL) or
 554  *                      the length of the data array to be allocated
 555  * @param initialValue the initial value that is set for all code points
 556  * @param leadUnitValue the value for lead surrogate code _units_ that do not
 557  *                      have associated supplementary data
 558  * @param latin1Linear a flag indicating whether the Latin-1 range is to be allocated and
 559  *                     kept in a linear, contiguous part of the data array
 560  * @return a pointer to the initialized fillIn or the allocated and initialized new UNewTrie
 561  */
 562 U_CAPI UNewTrie * U_EXPORT2
 563 utrie_open(UNewTrie *fillIn,
 564            uint32_t *aliasData, int32_t maxDataLength,
 565            uint32_t initialValue, uint32_t leadUnitValue,
 566            UBool latin1Linear);
 567
 568 /**
 569  * Clone a build-time trie structure with all entries.
 570  *
 571  * @param fillIn like in utrie_open()
 572  * @param other the build-time trie structure to clone
 573  * @param aliasData like in utrie_open(),
 574  *                  used if aliasDataLength>=(capacity of other's data array)
 575  * @param aliasDataLength the length of aliasData
 576  * @return a pointer to the initialized fillIn or the allocated and initialized new UNewTrie
 577  */
 578 U_CAPI UNewTrie * U_EXPORT2
 579 utrie_clone(UNewTrie *fillIn, const UNewTrie *other, uint32_t *aliasData, int32_t aliasDataLength);
 580
 581 /**
 582  * Close a build-time trie structure, and release memory
 583  * that was allocated by utrie_open() or utrie_clone().
 584  *
 585  * @param trie the build-time trie
 586  */
 587 U_CAPI void U_EXPORT2
 588 utrie_close(UNewTrie *trie);
 589
 590 /**
 591  * Get the data array of a build-time trie.
 592  * The data may be modified, but entries that are equal before
 593  * must still be equal after modification.
 594  *
 595  * @param trie the build-time trie
 596  * @param pLength (out) a pointer to a variable that receives the number
 597  *                of entries in the data array
 598  * @return the data array
 599  */
 600 U_CAPI uint32_t * U_EXPORT2
 601 utrie_getData(UNewTrie *trie, int32_t *pLength);
 602
 603 /**
 604  * Set a value for a code point.
 605  *
 606  * @param trie the build-time trie
 607  * @param c the code point
 608  * @param value the value
 609  * @return FALSE if a failure occurred (illegal argument or data array overrun)
 610  */
 611 U_CAPI UBool U_EXPORT2
 612 utrie_set32(UNewTrie *trie, UChar32 c, uint32_t value);
 613
 614 /**
 615  * Get a value from a code point as stored in the build-time trie.
 616  *
 617  * @param trie the build-time trie
 618  * @param c the code point
 619  * @param pInBlockZero if not NULL, then *pInBlockZero is set to TRUE
 620  *                     iff the value is retrieved from block 0;
 621  *                     block 0 is the all-initial-value initial block
 622  * @return the value
 623  */
 624 U_CAPI uint32_t U_EXPORT2
 625 utrie_get32(UNewTrie *trie, UChar32 c, UBool *pInBlockZero);
 626
 627 /**
 628  * Set a value in a range of code points [start..limit[.
 629  * All code points c with start<=c<limit will get the value if
 630  * overwrite is TRUE or if the old value is 0.
 631  *
 632  * @param trie the build-time trie
 633  * @param start the first code point to get the value
 634  * @param limit one past the last code point to get the value
 635  * @param value the value
 636  * @param overwrite flag for whether old non-initial values are to be overwritten
 637  * @return FALSE if a failure occurred (illegal argument or data array overrun)
 638  */
 639 U_CAPI UBool U_EXPORT2
 640 utrie_setRange32(UNewTrie *trie, UChar32 start, UChar32 limit, uint32_t value, UBool overwrite);
 641
 642 /**
 643  * Compact the build-time trie after all values are set, and then
 644  * serialize it into 32-bit aligned memory.
 645  *
 646  * After this, the trie can only be serizalized again and/or closed;
 647  * no further values can be added.
 648  *
 649  * @see utrie_unserialize()
 650  *
 651  * @param trie the build-time trie
 652  * @param data a pointer to 32-bit-aligned memory for the trie data
 653  * @param capacity the number of bytes available at data
 654  * @param getFoldedValue a callback function that calculates the value for
 655  *                       a lead surrogate from all of its supplementary code points
 656  *                       and the folding offset;
 657  *                       if NULL, then a default function is used which returns just
 658  *                       the input offset when there are any non-initial-value entries
 659  * @param reduceTo16Bits flag for whether the values are to be reduced to a
 660  *                       width of 16 bits for serialization and runtime
 661  * @param pErrorCode a UErrorCode argument; among other possible error codes:
 662  * - U_BUFFER_OVERFLOW_ERROR if the data storage block is too small for serialization
 663  * - U_MEMORY_ALLOCATION_ERROR if the trie data array is too small
 664  * - U_INDEX_OUTOFBOUNDS_ERROR if the index or data arrays are too long after compaction for serialization
 665  *
 666  * @return the number of bytes written for the trie
 667  */
 668 U_CAPI int32_t U_EXPORT2
 669 utrie_serialize(UNewTrie *trie, void *data, int32_t capacity,
 670                 UNewTrieGetFoldedValue *getFoldedValue,
 671                 UBool reduceTo16Bits,
 672                 UErrorCode *pErrorCode);
 673
 674 /**
 675  * Swap a serialized UTrie.
 676  * @internal
 677  */
 678 U_CAPI int32_t U_EXPORT2
 679 utrie_swap(const UDataSwapper *ds,
 680            const void *inData, int32_t length, void *outData,
 681            UErrorCode *pErrorCode);
 682
 683 U_CDECL_END
 684
 685 #endif