icuSources/common/utrie.h

   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