1 /*

     2 ******************************************************************************

     3 *

     4 *   Copyright (C) 2001-2005, International Business Machines

     5 *   Corporation and others.  All Rights Reserved.

     6 *

     7 ******************************************************************************

     8 *   file name:  utrie.h

     9 *   encoding:   US-ASCII

    10 *   tab size:   8 (not used)

    11 *   indentation:4

    12 *

    13 *   created on: 2001nov08

    14 *   created by: Markus W. Scherer

    15 */

    16 

    17 #ifndef __UTRIE_H__

    18 #define __UTRIE_H__

    19 

    20 #include "unicode/utypes.h"

    21 #include "udataswp.h"

    22 

    23 U_CDECL_BEGIN

    24 

    25 /**

    26  * \file

    27  *

    28  * This is a common implementation of a "folded" trie.

    29  * It is a kind of compressed, serializable table of 16- or 32-bit values associated with

    30  * Unicode code points (0..0x10ffff).

    31  *

    32  * This implementation is optimized for getting values while walking forward

    33  * through a UTF-16 string.

    34  * Therefore, the simplest and fastest access macros are the

    35  * _FROM_LEAD() and _FROM_OFFSET_TRAIL() macros.

    36  *

    37  * The _FROM_BMP() macros are a little more complicated; they get values

    38  * even for lead surrogate code _points_, while the _FROM_LEAD() macros

    39  * get special "folded" values for lead surrogate code _units_ if

    40  * there is relevant data associated with them.

    41  * From such a folded value, an offset needs to be extracted to supply

    42  * to the _FROM_OFFSET_TRAIL() macros.

    43  *

    44  * Most of the more complex (and more convenient) functions/macros call a callback function

    45  * to get that offset from the folded value for a lead surrogate unit.

    46  */

    47 

    48 /**

    49  * Trie constants, defining shift widths, index array lengths, etc.

    50  */

    51 enum {

    52     /** Shift size for shifting right the input index. 1..9 */

    53     UTRIE_SHIFT=5,

    54 

    55     /** Number of data values in a stage 2 (data array) block. 2, 4, 8, .., 0x200 */

    56     UTRIE_DATA_BLOCK_LENGTH=1<<UTRIE_SHIFT,

    57 

    58     /** Mask for getting the lower bits from the input index. */

    59     UTRIE_MASK=UTRIE_DATA_BLOCK_LENGTH-1,

    60 

    61     /**

    62      * Lead surrogate code points' index displacement in the index array.

    63      * 0x10000-0xd800=0x2800

    64      */

    65     UTRIE_LEAD_INDEX_DISP=0x2800>>UTRIE_SHIFT,

    66 

    67     /**

    68      * Shift size for shifting left the index array values.

    69      * Increases possible data size with 16-bit index values at the cost

    70      * of compactability.

    71      * This requires blocks of stage 2 data to be aligned by UTRIE_DATA_GRANULARITY.

    72      * 0..UTRIE_SHIFT

    73      */

    74     UTRIE_INDEX_SHIFT=2,

    75 

    76     /** The alignment size of a stage 2 data block. Also the granularity for compaction. */

    77     UTRIE_DATA_GRANULARITY=1<<UTRIE_INDEX_SHIFT,

    78 

    79     /** Number of bits of a trail surrogate that are used in index table lookups. */

    80     UTRIE_SURROGATE_BLOCK_BITS=10-UTRIE_SHIFT,

    81 

    82     /**

    83      * Number of index (stage 1) entries per lead surrogate.

    84      * Same as number of index entries for 1024 trail surrogates,

    85      * ==0x400>>UTRIE_SHIFT

    86      */

    87     UTRIE_SURROGATE_BLOCK_COUNT=(1<<UTRIE_SURROGATE_BLOCK_BITS),

    88 

    89     /** Length of the BMP portion of the index (stage 1) array. */

    90     UTRIE_BMP_INDEX_LENGTH=0x10000>>UTRIE_SHIFT

    91 };

    92 

    93 /**

    94  * Length of the index (stage 1) array before folding.

    95  * Maximum number of Unicode code points (0x110000) shifted right by UTRIE_SHIFT.

    96  */

    97 #define UTRIE_MAX_INDEX_LENGTH (0x110000>>UTRIE_SHIFT)

    98 

    99 /**

   100  * Maximum length of the runtime data (stage 2) array.

   101  * Limited by 16-bit index values that are left-shifted by UTRIE_INDEX_SHIFT.

   102  */

   103 #define UTRIE_MAX_DATA_LENGTH (0x10000<<UTRIE_INDEX_SHIFT)

   104 

   105 /**

   106  * Maximum length of the build-time data (stage 2) array.

   107  * The maximum length is 0x110000+UTRIE_DATA_BLOCK_LENGTH+0x400.

   108  * (Number of Unicode code points + one all-initial-value block +

   109  *  possible duplicate entries for 1024 lead surrogates.)

   110  */

   111 #define UTRIE_MAX_BUILD_TIME_DATA_LENGTH (0x110000+UTRIE_DATA_BLOCK_LENGTH+0x400)

   112 

   113 /**

   114  * Number of bytes for a dummy trie.

   115  * A dummy trie is an empty runtime trie, used when a real data trie cannot

   116  * be loaded.

   117  * The number of bytes works for Latin-1-linear tries with 32-bit data

   118  * (worst case).

   119  *

   120  * Calculation:

   121  *   BMP index + 1 index block for lead surrogate code points +

   122  *   Latin-1-linear array + 1 data block for lead surrogate code points

   123  *

   124  * Latin-1: if(UTRIE_SHIFT<=8) { 256 } else { included in first data block }

   125  *

   126  * @see utrie_unserializeDummy

   127  */

   128 #define UTRIE_DUMMY_SIZE ((UTRIE_BMP_INDEX_LENGTH+UTRIE_SURROGATE_BLOCK_COUNT)*2+(UTRIE_SHIFT<=8?256:UTRIE_DATA_BLOCK_LENGTH)*4+UTRIE_DATA_BLOCK_LENGTH*4)

   129 

   130 /**

   131  * Runtime UTrie callback function.

   132  * Extract from a lead surrogate's data the

   133  * index array offset of the indexes for that lead surrogate.

   134  *

   135  * @param data data value for a surrogate from the trie, including the folding offset

   136  * @return offset>=UTRIE_BMP_INDEX_LENGTH, or 0 if there is no data for the lead surrogate

   137  */

   138 typedef int32_t U_CALLCONV

   139 UTrieGetFoldingOffset(uint32_t data);

   140 

   141 /**

   142  * Run-time Trie structure.

   143  *

   144  * Either the data table is 16 bits wide and accessed via the index

   145  * pointer, with each index item increased by indexLength;

   146  * in this case, data32==NULL.

   147  *

   148  * Or the data table is 32 bits wide and accessed via the data32 pointer.

   149  */

   150 struct UTrie {

   151     const uint16_t *index;

   152     const uint32_t *data32; /* NULL if 16b data is used via index */

   153 

   154     /**

   155      * This function is not used in _FROM_LEAD, _FROM_BMP, and _FROM_OFFSET_TRAIL macros.

   156      * If convenience macros like _GET16 or _NEXT32 are used, this function must be set.

   157      *

   158      * utrie_unserialize() sets a default function which simply returns

   159      * the lead surrogate's value itself - which is the inverse of the default

   160      * folding function used by utrie_serialize().

   161      *

   162      * @see UTrieGetFoldingOffset

   163      */

   164     UTrieGetFoldingOffset *getFoldingOffset;

   165 

   166     int32_t indexLength, dataLength;

   167     uint32_t initialValue;

   168     UBool isLatin1Linear;

   169 };

   170 

   171 typedef struct UTrie UTrie;

   172 

   173 /** Internal trie getter from an offset (0 if c16 is a BMP/lead units) and a 16-bit unit */

   174 #define _UTRIE_GET_RAW(trie, data, offset, c16) \

   175     (trie)->data[ \

   176         ((int32_t)((trie)->index[(offset)+((c16)>>UTRIE_SHIFT)])<<UTRIE_INDEX_SHIFT)+ \

   177         ((c16)&UTRIE_MASK) \

   178     ]

   179 

   180 /** Internal trie getter from a pair of surrogates */

   181 #define _UTRIE_GET_FROM_PAIR(trie, data, c, c2, result, resultType) { \

   182     int32_t __offset; \

   183 \

   184     /* get data for lead surrogate */ \

   185     (result)=_UTRIE_GET_RAW((trie), data, 0, (c)); \

   186     __offset=(trie)->getFoldingOffset(result); \

   187 \

   188     /* get the real data from the folded lead/trail units */ \

   189     if(__offset>0) { \

   190         (result)=_UTRIE_GET_RAW((trie), data, __offset, (c2)&0x3ff); \

   191     } else { \

   192         (result)=(resultType)((trie)->initialValue); \

   193     } \

   194 }

   195 

   196 /** Internal trie getter from a BMP code point, treating a lead surrogate as a normal code point */

   197 #define _UTRIE_GET_FROM_BMP(trie, data, c16) \

   198     _UTRIE_GET_RAW(trie, data, 0xd800<=(c16) && (c16)<=0xdbff ? UTRIE_LEAD_INDEX_DISP : 0, c16);

   199 

   200 /**

   201  * Internal trie getter from a code point.

   202  * Could be faster(?) but longer with

   203  *   if((c32)<=0xd7ff) { (result)=_UTRIE_GET_RAW(trie, data, 0, c32); }

   204  */

   205 #define _UTRIE_GET(trie, data, c32, result, resultType) \

   206     if((uint32_t)(c32)<=0xffff) { \

   207         /* BMP code points */ \

   208         (result)=_UTRIE_GET_FROM_BMP(trie, data, c32); \

   209     } else if((uint32_t)(c32)<=0x10ffff) { \

   210         /* supplementary code point */ \

   211         UChar __lead16=UTF16_LEAD(c32); \

   212         _UTRIE_GET_FROM_PAIR(trie, data, __lead16, c32, result, resultType); \

   213     } else { \

   214         /* out of range */ \

   215         (result)=(resultType)((trie)->initialValue); \

   216     }

   217 

   218 /** Internal next-post-increment: get the next code point (c, c2) and its data */

   219 #define _UTRIE_NEXT(trie, data, src, limit, c, c2, result, resultType) { \

   220     (c)=*(src)++; \

   221     if(!UTF_IS_LEAD(c)) { \

   222         (c2)=0; \

   223         (result)=_UTRIE_GET_RAW((trie), data, 0, (c)); \

   224     } else if((src)!=(limit) && UTF_IS_TRAIL((c2)=*(src))) { \

   225         ++(src); \

   226         _UTRIE_GET_FROM_PAIR((trie), data, (c), (c2), (result), resultType); \

   227     } else { \

   228         /* unpaired lead surrogate code point */ \

   229         (c2)=0; \

   230         (result)=_UTRIE_GET_RAW((trie), data, UTRIE_LEAD_INDEX_DISP, (c)); \

   231     } \

   232 }

   233 

   234 /** Internal previous: get the previous code point (c, c2) and its data */

   235 #define _UTRIE_PREVIOUS(trie, data, start, src, c, c2, result, resultType) { \

   236     (c)=*--(src); \

   237     if(!UTF_IS_SURROGATE(c)) { \

   238         (c2)=0; \

   239         (result)=_UTRIE_GET_RAW((trie), data, 0, (c)); \

   240     } else if(!UTF_IS_SURROGATE_FIRST(c)) { \

   241         /* trail surrogate */ \

   242         if((start)!=(src) && UTF_IS_LEAD((c2)=*((src)-1))) { \

   243             --(src); \

   244             (result)=(c); (c)=(c2); (c2)=(UChar)(result); /* swap c, c2 */ \

   245             _UTRIE_GET_FROM_PAIR((trie), data, (c), (c2), (result), resultType); \

   246         } else { \

   247             /* unpaired trail surrogate code point */ \

   248             (c2)=0; \

   249             (result)=_UTRIE_GET_RAW((trie), data, 0, (c)); \

   250         } \

   251     } else { \

   252         /* unpaired lead surrogate code point */ \

   253         (c2)=0; \

   254         (result)=_UTRIE_GET_RAW((trie), data, UTRIE_LEAD_INDEX_DISP, (c)); \

   255     } \

   256 }

   257 

   258 /* Public UTrie API ---------------------------------------------------------*/

   259 

   260 /**

   261  * Get a pointer to the contiguous part of the data array

   262  * for the Latin-1 range (U+0000..U+00ff).

   263  * Must be used only if the Latin-1 range is in fact linear

   264  * (trie->isLatin1Linear).

   265  *

   266  * @param trie (const UTrie *, in) a pointer to the runtime trie structure

   267  * @return (const uint16_t *) pointer to values for Latin-1 code points

   268  */

   269 #define UTRIE_GET16_LATIN1(trie) ((trie)->index+(trie)->indexLength+UTRIE_DATA_BLOCK_LENGTH)

   270 

   271 /**

   272  * Get a pointer to the contiguous part of the data array

   273  * for the Latin-1 range (U+0000..U+00ff).

   274  * Must be used only if the Latin-1 range is in fact linear

   275  * (trie->isLatin1Linear).

   276  *

   277  * @param trie (const UTrie *, in) a pointer to the runtime trie structure

   278  * @return (const uint32_t *) pointer to values for Latin-1 code points

   279  */

   280 #define UTRIE_GET32_LATIN1(trie) ((trie)->data32+UTRIE_DATA_BLOCK_LENGTH)

   281 

   282 /**

   283  * Get a 16-bit trie value from a BMP code point (UChar, <=U+ffff).

   284  * c16 may be a lead surrogate, which may have a value including a folding offset.

   285  *

   286  * @param trie (const UTrie *, in) a pointer to the runtime trie structure

   287  * @param c16 (UChar, in) the input BMP code point

   288  * @return (uint16_t) trie lookup result

   289  */

   290 #define UTRIE_GET16_FROM_LEAD(trie, c16) _UTRIE_GET_RAW(trie, index, 0, c16)

   291 

   292 /**

   293  * Get a 32-bit trie value from a BMP code point (UChar, <=U+ffff).

   294  * c16 may be a lead surrogate, which may have a value including a folding offset.

   295  *

   296  * @param trie (const UTrie *, in) a pointer to the runtime trie structure

   297  * @param c16 (UChar, in) the input BMP code point

   298  * @return (uint32_t) trie lookup result

   299  */

   300 #define UTRIE_GET32_FROM_LEAD(trie, c16) _UTRIE_GET_RAW(trie, data32, 0, c16)

   301 

   302 /**

   303  * Get a 16-bit trie value from a BMP code point (UChar, <=U+ffff).

   304  * Even lead surrogate code points are treated as normal code points,

   305  * with unfolded values that may differ from _FROM_LEAD() macro results for them.

   306  *

   307  * @param trie (const UTrie *, in) a pointer to the runtime trie structure

   308  * @param c16 (UChar, in) the input BMP code point

   309  * @return (uint16_t) trie lookup result

   310  */

   311 #define UTRIE_GET16_FROM_BMP(trie, c16) _UTRIE_GET_FROM_BMP(trie, index, c16)

   312 

   313 /**

   314  * Get a 32-bit trie value from a BMP code point (UChar, <=U+ffff).

   315  * Even lead surrogate code points are treated as normal code points,

   316  * with unfolded values that may differ from _FROM_LEAD() macro results for them.

   317  *

   318  * @param trie (const UTrie *, in) a pointer to the runtime trie structure

   319  * @param c16 (UChar, in) the input BMP code point

   320  * @return (uint32_t) trie lookup result

   321  */

   322 #define UTRIE_GET32_FROM_BMP(trie, c16) _UTRIE_GET_FROM_BMP(trie, data32, c16)

   323 

   324 /**

   325  * Get a 16-bit trie value from a code point.

   326  * Even lead surrogate code points are treated as normal code points,

   327  * with unfolded values that may differ from _FROM_LEAD() macro results for them.

   328  *

   329  * @param trie (const UTrie *, in) a pointer to the runtime trie structure

   330  * @param c32 (UChar32, in) the input code point

   331  * @param result (uint16_t, out) uint16_t variable for the trie lookup result

   332  */

   333 #define UTRIE_GET16(trie, c32, result) _UTRIE_GET(trie, index, c32, result, uint16_t)

   334 

   335 /**

   336  * Get a 32-bit trie value from a code point.

   337  * Even lead surrogate code points are treated as normal code points,

   338  * with unfolded values that may differ from _FROM_LEAD() macro results for them.

   339  *

   340  * @param trie (const UTrie *, in) a pointer to the runtime trie structure

   341  * @param c32 (UChar32, in) the input code point

   342  * @param result (uint32_t, out) uint32_t variable for the trie lookup result

   343  */

   344 #define UTRIE_GET32(trie, c32, result) _UTRIE_GET(trie, data32, c32, result, uint32_t)

   345 

   346 /**

   347  * Get the next code point (c, c2), post-increment src,

   348  * and get a 16-bit value from the trie.

   349  *

   350  * @param trie (const UTrie *, in) a pointer to the runtime trie structure

   351  * @param src (const UChar *, in/out) the source text pointer

   352  * @param limit (const UChar *, in) the limit pointer for the text, or NULL

   353  * @param c (UChar, out) variable for the BMP or lead code unit

   354  * @param c2 (UChar, out) variable for 0 or the trail code unit

   355  * @param result (uint16_t, out) uint16_t variable for the trie lookup result

   356  */

   357 #define UTRIE_NEXT16(trie, src, limit, c, c2, result) _UTRIE_NEXT(trie, index, src, limit, c, c2, result, uint16_t)

   358 

   359 /**

   360  * Get the next code point (c, c2), post-increment src,

   361  * and get a 32-bit value from the trie.

   362  *

   363  * @param trie (const UTrie *, in) a pointer to the runtime trie structure

   364  * @param src (const UChar *, in/out) the source text pointer

   365  * @param limit (const UChar *, in) the limit pointer for the text, or NULL

   366  * @param c (UChar, out) variable for the BMP or lead code unit

   367  * @param c2 (UChar, out) variable for 0 or the trail code unit

   368  * @param result (uint32_t, out) uint32_t variable for the trie lookup result

   369  */

   370 #define UTRIE_NEXT32(trie, src, limit, c, c2, result) _UTRIE_NEXT(trie, data32, src, limit, c, c2, result, uint32_t)

   371 

   372 /**

   373  * Get the previous code point (c, c2), pre-decrement src,

   374  * and get a 16-bit value from the trie.

   375  *

   376  * @param trie (const UTrie *, in) a pointer to the runtime trie structure

   377  * @param start (const UChar *, in) the start pointer for the text, or NULL

   378  * @param src (const UChar *, in/out) the source text pointer

   379  * @param c (UChar, out) variable for the BMP or lead code unit

   380  * @param c2 (UChar, out) variable for 0 or the trail code unit

   381  * @param result (uint16_t, out) uint16_t variable for the trie lookup result

   382  */

   383 #define UTRIE_PREVIOUS16(trie, start, src, c, c2, result) _UTRIE_PREVIOUS(trie, index, start, src, c, c2, result, uint16_t)

   384 

   385 /**

   386  * Get the previous code point (c, c2), pre-decrement src,

   387  * and get a 32-bit value from the trie.

   388  *

   389  * @param trie (const UTrie *, in) a pointer to the runtime trie structure

   390  * @param start (const UChar *, in) the start pointer for the text, or NULL

   391  * @param src (const UChar *, in/out) the source text pointer

   392  * @param c (UChar, out) variable for the BMP or lead code unit

   393  * @param c2 (UChar, out) variable for 0 or the trail code unit

   394  * @param result (uint32_t, out) uint32_t variable for the trie lookup result

   395  */

   396 #define UTRIE_PREVIOUS32(trie, start, src, c, c2, result) _UTRIE_PREVIOUS(trie, data32, start, src, c, c2, result, uint32_t)

   397 

   398 /**

   399  * Get a 16-bit trie value from a pair of surrogates.

   400  *

   401  * @param trie (const UTrie *, in) a pointer to the runtime trie structure

   402  * @param c (UChar, in) a lead surrogate

   403  * @param c2 (UChar, in) a trail surrogate

   404  * @param result (uint16_t, out) uint16_t variable for the trie lookup result

   405  */

   406 #define UTRIE_GET16_FROM_PAIR(trie, c, c2, result) _UTRIE_GET_FROM_PAIR(trie, index, c, c2, result, uint16_t)

   407 

   408 /**

   409  * Get a 32-bit trie value from a pair of surrogates.

   410  *

   411  * @param trie (const UTrie *, in) a pointer to the runtime trie structure

   412  * @param c (UChar, in) a lead surrogate

   413  * @param c2 (UChar, in) a trail surrogate

   414  * @param result (uint32_t, out) uint32_t variable for the trie lookup result

   415  */

   416 #define UTRIE_GET32_FROM_PAIR(trie, c, c2, result) _UTRIE_GET_FROM_PAIR(trie, data32, c, c2, result, uint32_t)

   417 

   418 /**

   419  * Get a 16-bit trie value from a folding offset (from the value of a lead surrogate)

   420  * and a trail surrogate.

   421  *

   422  * @param trie (const UTrie *, in) a pointer to the runtime trie structure

   423  * @param offset (int32_t, in) the folding offset from the value of a lead surrogate

   424  * @param c2 (UChar, in) a trail surrogate (only the 10 low bits are significant)

   425  * @return (uint16_t) trie lookup result

   426  */

   427 #define UTRIE_GET16_FROM_OFFSET_TRAIL(trie, offset, c2) _UTRIE_GET_RAW(trie, index, offset, (c2)&0x3ff)

   428 

   429 /**

   430  * Get a 32-bit trie value from a folding offset (from the value of a lead surrogate)

   431  * and a trail surrogate.

   432  *

   433  * @param trie (const UTrie *, in) a pointer to the runtime trie structure

   434  * @param offset (int32_t, in) the folding offset from the value of a lead surrogate

   435  * @param c2 (UChar, in) a trail surrogate (only the 10 low bits are significant)

   436  * @return (uint32_t) trie lookup result

   437  */

   438 #define UTRIE_GET32_FROM_OFFSET_TRAIL(trie, offset, c2) _UTRIE_GET_RAW(trie, data32, offset, (c2)&0x3ff)

   439 

   440 /* enumeration callback types */

   441 

   442 /**

   443  * Callback from utrie_enum(), extracts a uint32_t value from a

   444  * trie value. This value will be passed on to the UTrieEnumRange function.

   445  *

   446  * @param context an opaque pointer, as passed into utrie_enum()

   447  * @param value a value from the trie

   448  * @return the value that is to be passed on to the UTrieEnumRange function

   449  */

   450 typedef uint32_t U_CALLCONV

   451 UTrieEnumValue(const void *context, uint32_t value);

   452 

   453 /**

   454  * Callback from utrie_enum(), is called for each contiguous range

   455  * of code points with the same value as retrieved from the trie and

   456  * transformed by the UTrieEnumValue function.

   457  *

   458  * The callback function can stop the enumeration by returning FALSE.

   459  *

   460  * @param context an opaque pointer, as passed into utrie_enum()

   461  * @param start the first code point in a contiguous range with value

   462  * @param limit one past the last code point in a contiguous range with value

   463  * @param value the value that is set for all code points in [start..limit[

   464  * @return FALSE to stop the enumeration

   465  */

   466 typedef UBool U_CALLCONV

   467 UTrieEnumRange(const void *context, UChar32 start, UChar32 limit, uint32_t value);

   468 

   469 /**

   470  * Enumerate efficiently all values in a trie.

   471  * For each entry in the trie, the value to be delivered is passed through

   472  * the UTrieEnumValue function.

   473  * The value is unchanged if that function pointer is NULL.

   474  *

   475  * For each contiguous range of code points with a given value,

   476  * the UTrieEnumRange function is called.

   477  *

   478  * @param trie a pointer to the runtime trie structure

   479  * @param enumValue a pointer to a function that may transform the trie entry value,

   480  *                  or NULL if the values from the trie are to be used directly

   481  * @param enumRange a pointer to a function that is called for each contiguous range

   482  *                  of code points with the same value

   483  * @param context an opaque pointer that is passed on to the callback functions

   484  */

   485 U_CAPI void U_EXPORT2

   486 utrie_enum(const UTrie *trie,

   487            UTrieEnumValue *enumValue, UTrieEnumRange *enumRange, const void *context);

   488 

   489 /**

   490  * Unserialize a trie from 32-bit-aligned memory.

   491  * Inverse of utrie_serialize().

   492  * Fills the UTrie runtime trie structure with the settings for the trie data.

   493  *

   494  * @param trie a pointer to the runtime trie structure

   495  * @param data a pointer to 32-bit-aligned memory containing trie data

   496  * @param length the number of bytes available at data

   497  * @param pErrorCode an in/out ICU UErrorCode

   498  * @return the number of bytes at data taken up by the trie data

   499  */

   500 U_CAPI int32_t U_EXPORT2

   501 utrie_unserialize(UTrie *trie, const void *data, int32_t length, UErrorCode *pErrorCode);

   502 

   503 /**

   504  * "Unserialize" a dummy trie.

   505  * A dummy trie is an empty runtime trie, used when a real data trie cannot

   506  * be loaded.

   507  *

   508  * The input memory is filled so that the trie always returns the initialValue,

   509  * or the leadUnitValue for lead surrogate code points.

   510  * The Latin-1 part is always set up to be linear.

   511  *

   512  * @param trie a pointer to the runtime trie structure

   513  * @param data a pointer to 32-bit-aligned memory to be filled with the dummy trie data

   514  * @param length the number of bytes available at data (recommended to use UTRIE_DUMMY_SIZE)

   515  * @param initialValue the initial value that is set for all code points

   516  * @param leadUnitValue the value for lead surrogate code _units_ that do not

   517  *                      have associated supplementary data

   518  * @param pErrorCode an in/out ICU UErrorCode

   519  *

   520  * @see UTRIE_DUMMY_SIZE

   521  * @see utrie_open

   522  */

   523 U_CAPI int32_t U_EXPORT2

   524 utrie_unserializeDummy(UTrie *trie,

   525                        void *data, int32_t length,

   526                        uint32_t initialValue, uint32_t leadUnitValue,

   527                        UBool make16BitTrie,

   528                        UErrorCode *pErrorCode);

   529 

   530 /**

   531  * Default implementation for UTrie.getFoldingOffset, set automatically by

   532  * utrie_unserialize().

   533  * Simply returns the lead surrogate's value itself - which is the inverse

   534  * of the default folding function used by utrie_serialize().

   535  * Exported for static const UTrie structures.

   536  *

   537  * @see UTrieGetFoldingOffset

   538  */

   539 U_CAPI int32_t U_EXPORT2

   540 utrie_defaultGetFoldingOffset(uint32_t data);

   541 

   542 /* Building a trie ----------------------------------------------------------*/

   543 

   544 /**

   545  * Build-time trie structure.

   546  * Opaque definition, here only to make fillIn parameters possible

   547  * for utrie_open() and utrie_clone().

   548  */

   549 struct UNewTrie {

   550     /**

   551      * Index values at build-time are 32 bits wide for easier processing.

   552      * Bit 31 is set if the data block is used by multiple index values (from utrie_setRange()).

   553      */

   554     int32_t index[UTRIE_MAX_INDEX_LENGTH];

   555     uint32_t *data;

   556 

   557     uint32_t leadUnitValue;

   558     int32_t indexLength, dataCapacity, dataLength;

   559     UBool isAllocated, isDataAllocated;

   560     UBool isLatin1Linear, isCompacted;

   561 

   562     /**

   563      * Map of adjusted indexes, used in utrie_compact().

   564      * Maps from original indexes to new ones.

   565      */

   566     int32_t map[UTRIE_MAX_BUILD_TIME_DATA_LENGTH>>UTRIE_SHIFT];

   567 };

   568 

   569 typedef struct UNewTrie UNewTrie;

   570 

   571 /**

   572  * Build-time trie callback function, used with utrie_serialize().

   573  * This function calculates a lead surrogate's value including a folding offset

   574  * from the 1024 supplementary code points [start..start+1024[ .

   575  * It is U+10000 <= start <= U+10fc00 and (start&0x3ff)==0.

   576  *

   577  * The folding offset is provided by the caller.

   578  * It is offset=UTRIE_BMP_INDEX_LENGTH+n*UTRIE_SURROGATE_BLOCK_COUNT with n=0..1023.

   579  * Instead of the offset itself, n can be stored in 10 bits -

   580  * or fewer if it can be assumed that few lead surrogates have associated data.

   581  *

   582  * The returned value must be

   583  * - not zero if and only if there is relevant data

   584  *   for the corresponding 1024 supplementary code points

   585  * - such that UTrie.getFoldingOffset(UNewTrieGetFoldedValue(..., offset))==offset

   586  *

   587  * @return a folded value, or 0 if there is no relevant data for the lead surrogate.

   588  */

   589 typedef uint32_t U_CALLCONV

   590 UNewTrieGetFoldedValue(UNewTrie *trie, UChar32 start, int32_t offset);

   591 

   592 /**

   593  * Open a build-time trie structure.

   594  * The size of the build-time data array is specified to avoid allocating a large

   595  * array in all cases. The array itself can also be passed in.

   596  *

   597  * Although the trie is never fully expanded to a linear array, especially when

   598  * utrie_setRange32() is used, the data array could be large during build time.

   599  * The maximum length is

   600  * UTRIE_MAX_BUILD_TIME_DATA_LENGTH=0x110000+UTRIE_DATA_BLOCK_LENGTH+0x400.

   601  * (Number of Unicode code points + one all-initial-value block +

   602  *  possible duplicate entries for 1024 lead surrogates.)

   603  * (UTRIE_DATA_BLOCK_LENGTH<=0x200 in all cases.)

   604  *

   605  * @param fillIn a pointer to a UNewTrie structure to be initialized (will not be released), or

   606  *               NULL if one is to be allocated

   607  * @param aliasData a pointer to a data array to be used (will not be released), or

   608  *                  NULL if one is to be allocated

   609  * @param maxDataLength the capacity of aliasData (if not NULL) or

   610  *                      the length of the data array to be allocated

   611  * @param initialValue the initial value that is set for all code points

   612  * @param leadUnitValue the value for lead surrogate code _units_ that do not

   613  *                      have associated supplementary data

   614  * @param latin1Linear a flag indicating whether the Latin-1 range is to be allocated and

   615  *                     kept in a linear, contiguous part of the data array

   616  * @return a pointer to the initialized fillIn or the allocated and initialized new UNewTrie

   617  */

   618 U_CAPI UNewTrie * U_EXPORT2

   619 utrie_open(UNewTrie *fillIn,

   620            uint32_t *aliasData, int32_t maxDataLength,

   621            uint32_t initialValue, uint32_t leadUnitValue,

   622            UBool latin1Linear);

   623 

   624 /**

   625  * Clone a build-time trie structure with all entries.

   626  *

   627  * @param fillIn like in utrie_open()

   628  * @param other the build-time trie structure to clone

   629  * @param aliasData like in utrie_open(),

   630  *                  used if aliasDataLength>=(capacity of other's data array)

   631  * @param aliasDataLength the length of aliasData

   632  * @return a pointer to the initialized fillIn or the allocated and initialized new UNewTrie

   633  */

   634 U_CAPI UNewTrie * U_EXPORT2

   635 utrie_clone(UNewTrie *fillIn, const UNewTrie *other, uint32_t *aliasData, int32_t aliasDataLength);

   636 

   637 /**

   638  * Close a build-time trie structure, and release memory

   639  * that was allocated by utrie_open() or utrie_clone().

   640  *

   641  * @param trie the build-time trie

   642  */

   643 U_CAPI void U_EXPORT2

   644 utrie_close(UNewTrie *trie);

   645 

   646 /**

   647  * Get the data array of a build-time trie.

   648  * The data may be modified, but entries that are equal before

   649  * must still be equal after modification.

   650  *

   651  * @param trie the build-time trie

   652  * @param pLength (out) a pointer to a variable that receives the number

   653  *                of entries in the data array

   654  * @return the data array

   655  */

   656 U_CAPI uint32_t * U_EXPORT2

   657 utrie_getData(UNewTrie *trie, int32_t *pLength);

   658 

   659 /**

   660  * Set a value for a code point.

   661  *

   662  * @param trie the build-time trie

   663  * @param c the code point

   664  * @param value the value

   665  * @return FALSE if a failure occurred (illegal argument or data array overrun)

   666  */

   667 U_CAPI UBool U_EXPORT2

   668 utrie_set32(UNewTrie *trie, UChar32 c, uint32_t value);

   669 

   670 /**

   671  * Get a value from a code point as stored in the build-time trie.

   672  *

   673  * @param trie the build-time trie

   674  * @param c the code point

   675  * @param pInBlockZero if not NULL, then *pInBlockZero is set to TRUE

   676  *                     iff the value is retrieved from block 0;

   677  *                     block 0 is the all-initial-value initial block

   678  * @return the value

   679  */

   680 U_CAPI uint32_t U_EXPORT2

   681 utrie_get32(UNewTrie *trie, UChar32 c, UBool *pInBlockZero);

   682 

   683 /**

   684  * Set a value in a range of code points [start..limit[.

   685  * All code points c with start<=c<limit will get the value if

   686  * overwrite is TRUE or if the old value is 0.

   687  *

   688  * @param trie the build-time trie

   689  * @param start the first code point to get the value

   690  * @param limit one past the last code point to get the value

   691  * @param value the value

   692  * @param overwrite flag for whether old non-initial values are to be overwritten

   693  * @return FALSE if a failure occurred (illegal argument or data array overrun)

   694  */

   695 U_CAPI UBool U_EXPORT2

   696 utrie_setRange32(UNewTrie *trie, UChar32 start, UChar32 limit, uint32_t value, UBool overwrite);

   697 

   698 /**

   699  * Compact the build-time trie after all values are set, and then

   700  * serialize it into 32-bit aligned memory.

   701  *

   702  * After this, the trie can only be serizalized again and/or closed;

   703  * no further values can be added.

   704  *

   705  * @see utrie_unserialize()

   706  *

   707  * @param trie the build-time trie

   708  * @param data a pointer to 32-bit-aligned memory for the trie data

   709  * @param capacity the number of bytes available at data

   710  * @param getFoldedValue a callback function that calculates the value for

   711  *                       a lead surrogate from all of its supplementary code points

   712  *                       and the folding offset;

   713  *                       if NULL, then a default function is used which returns just

   714  *                       the input offset when there are any non-initial-value entries

   715  * @param reduceTo16Bits flag for whether the values are to be reduced to a

   716  *                       width of 16 bits for serialization and runtime

   717  * @param pErrorCode a UErrorCode argument; among other possible error codes:

   718  * - U_BUFFER_OVERFLOW_ERROR if the data storage block is too small for serialization

   719  * - U_MEMORY_ALLOCATION_ERROR if the trie data array is too small

   720  * - U_INDEX_OUTOFBOUNDS_ERROR if the index or data arrays are too long after compaction for serialization

   721  *

   722  * @return the number of bytes written for the trie

   723  */

   724 U_CAPI int32_t U_EXPORT2

   725 utrie_serialize(UNewTrie *trie, void *data, int32_t capacity,

   726                 UNewTrieGetFoldedValue *getFoldedValue,

   727                 UBool reduceTo16Bits,

   728                 UErrorCode *pErrorCode);

   729 

   730 /**

   731  * Swap a serialized UTrie.

   732  * @internal

   733  */

   734 U_CAPI int32_t U_EXPORT2

   735 utrie_swap(const UDataSwapper *ds,

   736            const void *inData, int32_t length, void *outData,

   737            UErrorCode *pErrorCode);

   738 

   739 U_CDECL_END

   740 

   741 #endif