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