• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // © 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-2014, International Business Machines
7 *   Corporation and others.  All Rights Reserved.
8 *
9 ******************************************************************************
10 *   file name:  utrie2.h
11 *   encoding:   UTF-8
12 *   tab size:   8 (not used)
13 *   indentation:4
14 *
15 *   created on: 2008aug16 (starting from a copy of utrie.h)
16 *   created by: Markus W. Scherer
17 */
18 
19 #ifndef __UTRIE2_H__
20 #define __UTRIE2_H__
21 
22 #include "unicode/utypes.h"
23 #include "unicode/utf8.h"
24 #include "putilimp.h"
25 
26 U_CDECL_BEGIN
27 
28 struct UTrie;  /* forward declaration */
29 #ifndef __UTRIE_H__
30 typedef struct UTrie UTrie;
31 #endif
32 
33 /**
34  * \file
35  *
36  * This is a common implementation of a Unicode trie.
37  * It is a kind of compressed, serializable table of 16- or 32-bit values associated with
38  * Unicode code points (0..0x10ffff). (A map from code points to integers.)
39  *
40  * This is the second common version of a Unicode trie (hence the name UTrie2).
41  * Compared with UTrie version 1:
42  * - Still splitting BMP code points 11:5 bits for index and data table lookups.
43  * - Still separate data for lead surrogate code _units_ vs. code _points_,
44  *   but the lead surrogate code unit values are not required any more
45  *   for data lookup for supplementary code points.
46  * - The "folding" mechanism is removed. In UTrie version 1, this somewhat
47  *   hard-to-explain mechanism was meant to be used for optimized UTF-16
48  *   processing, with application-specific encoding of indexing bits
49  *   in the lead surrogate data for the associated supplementary code points.
50  * - For the last single-value code point range (ending with U+10ffff),
51  *   the starting code point ("highStart") and the value are stored.
52  * - For supplementary code points U+10000..highStart-1 a three-table lookup
53  *   (two index tables and one data table) is used. The first index
54  *   is truncated, omitting both the BMP portion and the high range.
55  * - There is a special small index for 2-byte UTF-8, and the initial data
56  *   entries are designed for fast 1/2-byte UTF-8 lookup.
57  *   Starting with ICU 60, C0 and C1 are not recognized as UTF-8 lead bytes any more at all,
58  *   and the associated 2-byte indexes are unused.
59  */
60 
61 /**
62  * Trie structure.
63  * Use only with public API macros and functions.
64  */
65 struct UTrie2;
66 typedef struct UTrie2 UTrie2;
67 
68 /* Public UTrie2 API functions: read-only access ---------------------------- */
69 
70 /**
71  * Selectors for the width of a UTrie2 data value.
72  */
73 enum UTrie2ValueBits {
74     /** 16 bits per UTrie2 data value. */
75     UTRIE2_16_VALUE_BITS,
76     /** 32 bits per UTrie2 data value. */
77     UTRIE2_32_VALUE_BITS,
78     /** Number of selectors for the width of UTrie2 data values. */
79     UTRIE2_COUNT_VALUE_BITS
80 };
81 typedef enum UTrie2ValueBits UTrie2ValueBits;
82 
83 /**
84  * Open a frozen trie from its serialized from, stored in 32-bit-aligned memory.
85  * Inverse of utrie2_serialize().
86  * The memory must remain valid and unchanged as long as the trie is used.
87  * You must utrie2_close() the trie once you are done using it.
88  *
89  * @param valueBits selects the data entry size; results in an
90  *                  U_INVALID_FORMAT_ERROR if it does not match the serialized form
91  * @param data a pointer to 32-bit-aligned memory containing the serialized form of a UTrie2
92  * @param length the number of bytes available at data;
93  *               can be more than necessary
94  * @param pActualLength receives the actual number of bytes at data taken up by the trie data;
95  *                      can be NULL
96  * @param pErrorCode an in/out ICU UErrorCode
97  * @return the unserialized trie
98  *
99  * @see utrie2_open
100  * @see utrie2_serialize
101  */
102 U_CAPI UTrie2 * U_EXPORT2
103 utrie2_openFromSerialized(UTrie2ValueBits valueBits,
104                           const void *data, int32_t length, int32_t *pActualLength,
105                           UErrorCode *pErrorCode);
106 
107 /**
108  * Open a frozen, empty "dummy" trie.
109  * A dummy trie is an empty trie, used when a real data trie cannot
110  * be loaded. Equivalent to calling utrie2_open() and utrie2_freeze(),
111  * but without internally creating and compacting/serializing the
112  * builder data structure.
113  *
114  * The trie always returns the initialValue,
115  * or the errorValue for out-of-range code points and illegal UTF-8.
116  *
117  * You must utrie2_close() the trie once you are done using it.
118  *
119  * @param valueBits selects the data entry size
120  * @param initialValue the initial value that is set for all code points
121  * @param errorValue the value for out-of-range code points and illegal UTF-8
122  * @param pErrorCode an in/out ICU UErrorCode
123  * @return the dummy trie
124  *
125  * @see utrie2_openFromSerialized
126  * @see utrie2_open
127  */
128 U_CAPI UTrie2 * U_EXPORT2
129 utrie2_openDummy(UTrie2ValueBits valueBits,
130                  uint32_t initialValue, uint32_t errorValue,
131                  UErrorCode *pErrorCode);
132 
133 /**
134  * Get a value from a code point as stored in the trie.
135  * Easier to use than UTRIE2_GET16() and UTRIE2_GET32() but slower.
136  * Easier to use because, unlike the macros, this function works on all UTrie2
137  * objects, frozen or not, holding 16-bit or 32-bit data values.
138  *
139  * @param trie the trie
140  * @param c the code point
141  * @return the value
142  */
143 U_CAPI uint32_t U_EXPORT2
144 utrie2_get32(const UTrie2 *trie, UChar32 c);
145 
146 /* enumeration callback types */
147 
148 /**
149  * Callback from utrie2_enum(), extracts a uint32_t value from a
150  * trie value. This value will be passed on to the UTrie2EnumRange function.
151  *
152  * @param context an opaque pointer, as passed into utrie2_enum()
153  * @param value a value from the trie
154  * @return the value that is to be passed on to the UTrie2EnumRange function
155  */
156 typedef uint32_t U_CALLCONV
157 UTrie2EnumValue(const void *context, uint32_t value);
158 
159 /**
160  * Callback from utrie2_enum(), is called for each contiguous range
161  * of code points with the same value as retrieved from the trie and
162  * transformed by the UTrie2EnumValue function.
163  *
164  * The callback function can stop the enumeration by returning FALSE.
165  *
166  * @param context an opaque pointer, as passed into utrie2_enum()
167  * @param start the first code point in a contiguous range with value
168  * @param end the last code point in a contiguous range with value (inclusive)
169  * @param value the value that is set for all code points in [start..end]
170  * @return FALSE to stop the enumeration
171  */
172 typedef UBool U_CALLCONV
173 UTrie2EnumRange(const void *context, UChar32 start, UChar32 end, uint32_t value);
174 
175 /**
176  * Enumerate efficiently all values in a trie.
177  * Do not modify the trie during the enumeration.
178  *
179  * For each entry in the trie, the value to be delivered is passed through
180  * the UTrie2EnumValue function.
181  * The value is unchanged if that function pointer is NULL.
182  *
183  * For each contiguous range of code points with a given (transformed) value,
184  * the UTrie2EnumRange function is called.
185  *
186  * @param trie a pointer to the trie
187  * @param enumValue a pointer to a function that may transform the trie entry value,
188  *                  or NULL if the values from the trie are to be used directly
189  * @param enumRange a pointer to a function that is called for each contiguous range
190  *                  of code points with the same (transformed) value
191  * @param context an opaque pointer that is passed on to the callback functions
192  */
193 U_CAPI void U_EXPORT2
194 utrie2_enum(const UTrie2 *trie,
195             UTrie2EnumValue *enumValue, UTrie2EnumRange *enumRange, const void *context);
196 
197 /* Building a trie ---------------------------------------------------------- */
198 
199 /**
200  * Open an empty, writable trie. At build time, 32-bit data values are used.
201  * utrie2_freeze() takes a valueBits parameter
202  * which determines the data value width in the serialized and frozen forms.
203  * You must utrie2_close() the trie once you are done using it.
204  *
205  * @param initialValue the initial value that is set for all code points
206  * @param errorValue the value for out-of-range code points and illegal UTF-8
207  * @param pErrorCode an in/out ICU UErrorCode
208  * @return a pointer to the allocated and initialized new trie
209  */
210 U_CAPI UTrie2 * U_EXPORT2
211 utrie2_open(uint32_t initialValue, uint32_t errorValue, UErrorCode *pErrorCode);
212 
213 /**
214  * Clone a trie.
215  * You must utrie2_close() the clone once you are done using it.
216  *
217  * @param other the trie to clone
218  * @param pErrorCode an in/out ICU UErrorCode
219  * @return a pointer to the new trie clone
220  */
221 U_CAPI UTrie2 * U_EXPORT2
222 utrie2_clone(const UTrie2 *other, UErrorCode *pErrorCode);
223 
224 /**
225  * Clone a trie. The clone will be mutable/writable even if the other trie
226  * is frozen. (See utrie2_freeze().)
227  * You must utrie2_close() the clone once you are done using it.
228  *
229  * @param other the trie to clone
230  * @param pErrorCode an in/out ICU UErrorCode
231  * @return a pointer to the new trie clone
232  */
233 U_CAPI UTrie2 * U_EXPORT2
234 utrie2_cloneAsThawed(const UTrie2 *other, UErrorCode *pErrorCode);
235 
236 /**
237  * Close a trie and release associated memory.
238  *
239  * @param trie the trie
240  */
241 U_CAPI void U_EXPORT2
242 utrie2_close(UTrie2 *trie);
243 
244 /**
245  * Set a value for a code point.
246  *
247  * @param trie the unfrozen trie
248  * @param c the code point
249  * @param value the value
250  * @param pErrorCode an in/out ICU UErrorCode; among other possible error codes:
251  * - U_NO_WRITE_PERMISSION if the trie is frozen
252  */
253 U_CAPI void U_EXPORT2
254 utrie2_set32(UTrie2 *trie, UChar32 c, uint32_t value, UErrorCode *pErrorCode);
255 
256 /**
257  * Set a value in a range of code points [start..end].
258  * All code points c with start<=c<=end will get the value if
259  * overwrite is TRUE or if the old value is the initial value.
260  *
261  * @param trie the unfrozen trie
262  * @param start the first code point to get the value
263  * @param end the last code point to get the value (inclusive)
264  * @param value the value
265  * @param overwrite flag for whether old non-initial values are to be overwritten
266  * @param pErrorCode an in/out ICU UErrorCode; among other possible error codes:
267  * - U_NO_WRITE_PERMISSION if the trie is frozen
268  */
269 U_CAPI void U_EXPORT2
270 utrie2_setRange32(UTrie2 *trie,
271                   UChar32 start, UChar32 end,
272                   uint32_t value, UBool overwrite,
273                   UErrorCode *pErrorCode);
274 
275 /**
276  * Freeze a trie. Make it immutable (read-only) and compact it,
277  * ready for serialization and for use with fast macros.
278  * Functions to set values will fail after serializing.
279  *
280  * A trie can be frozen only once. If this function is called again with different
281  * valueBits then it will set a U_ILLEGAL_ARGUMENT_ERROR.
282  *
283  * @param trie the trie
284  * @param valueBits selects the data entry size; if smaller than 32 bits, then
285  *                  the values stored in the trie will be truncated
286  * @param pErrorCode an in/out ICU UErrorCode; among other possible error codes:
287  * - U_INDEX_OUTOFBOUNDS_ERROR if the compacted index or data arrays are too long
288  *                             for serialization
289  *                             (the trie will be immutable and usable,
290  *                             but not frozen and not usable with the fast macros)
291  *
292  * @see utrie2_cloneAsThawed
293  */
294 U_CAPI void U_EXPORT2
295 utrie2_freeze(UTrie2 *trie, UTrie2ValueBits valueBits, UErrorCode *pErrorCode);
296 
297 /**
298  * Test if the trie is frozen. (See utrie2_freeze().)
299  *
300  * @param trie the trie
301  * @return TRUE if the trie is frozen, that is, immutable, ready for serialization
302  *         and for use with fast macros
303  */
304 U_CAPI UBool U_EXPORT2
305 utrie2_isFrozen(const UTrie2 *trie);
306 
307 /**
308  * Serialize a frozen trie into 32-bit aligned memory.
309  * If the trie is not frozen, then the function returns with a U_ILLEGAL_ARGUMENT_ERROR.
310  * A trie can be serialized multiple times.
311  *
312  * @param trie the frozen trie
313  * @param data a pointer to 32-bit-aligned memory to be filled with the trie data,
314  *             can be NULL if capacity==0
315  * @param capacity the number of bytes available at data,
316  *                 or 0 for preflighting
317  * @param pErrorCode an in/out ICU UErrorCode; among other possible error codes:
318  * - U_BUFFER_OVERFLOW_ERROR if the data storage block is too small for serialization
319  * - U_ILLEGAL_ARGUMENT_ERROR if the trie is not frozen or the data and capacity
320  *                            parameters are bad
321  * @return the number of bytes written or needed for the trie
322  *
323  * @see utrie2_openFromSerialized()
324  */
325 U_CAPI int32_t U_EXPORT2
326 utrie2_serialize(const UTrie2 *trie,
327                  void *data, int32_t capacity,
328                  UErrorCode *pErrorCode);
329 
330 /* Public UTrie2 API: miscellaneous functions ------------------------------- */
331 
332 /**
333  * Build a UTrie2 (version 2) from a UTrie (version 1).
334  * Enumerates all values in the UTrie and builds a UTrie2 with the same values.
335  * The resulting UTrie2 will be frozen.
336  *
337  * @param trie1 the runtime UTrie structure to be enumerated
338  * @param errorValue the value for out-of-range code points and illegal UTF-8
339  * @param pErrorCode an in/out ICU UErrorCode
340  * @return The frozen UTrie2 with the same values as the UTrie.
341  */
342 U_CAPI UTrie2 * U_EXPORT2
343 utrie2_fromUTrie(const UTrie *trie1, uint32_t errorValue, UErrorCode *pErrorCode);
344 
345 /* Public UTrie2 API macros ------------------------------------------------- */
346 
347 /*
348  * These macros provide fast data lookup from a frozen trie.
349  * They will crash when used on an unfrozen trie.
350  */
351 
352 /**
353  * Return a 16-bit trie value from a code point, with range checking.
354  * Returns trie->errorValue if c is not in the range 0..U+10ffff.
355  *
356  * @param trie (const UTrie2 *, in) a frozen trie
357  * @param c (UChar32, in) the input code point
358  * @return (uint16_t) The code point's trie value.
359  */
360 #define UTRIE2_GET16(trie, c) _UTRIE2_GET((trie), index, (trie)->indexLength, (c))
361 
362 /**
363  * Return a 32-bit trie value from a code point, with range checking.
364  * Returns trie->errorValue if c is not in the range 0..U+10ffff.
365  *
366  * @param trie (const UTrie2 *, in) a frozen trie
367  * @param c (UChar32, in) the input code point
368  * @return (uint32_t) The code point's trie value.
369  */
370 #define UTRIE2_GET32(trie, c) _UTRIE2_GET((trie), data32, 0, (c))
371 
372 /**
373  * UTF-16: Get the next code point (UChar32 c, out), post-increment src,
374  * and get a 16-bit value from the trie.
375  *
376  * @param trie (const UTrie2 *, in) a frozen trie
377  * @param src (const UChar *, in/out) the source text pointer
378  * @param limit (const UChar *, in) the limit pointer for the text, or NULL if NUL-terminated
379  * @param c (UChar32, out) variable for the code point
380  * @param result (uint16_t, out) uint16_t variable for the trie lookup result
381  */
382 #define UTRIE2_U16_NEXT16(trie, src, limit, c, result) _UTRIE2_U16_NEXT(trie, index, src, limit, c, result)
383 
384 /**
385  * UTF-16: Get the next code point (UChar32 c, out), post-increment src,
386  * and get a 32-bit value from the trie.
387  *
388  * @param trie (const UTrie2 *, in) a frozen trie
389  * @param src (const UChar *, in/out) the source text pointer
390  * @param limit (const UChar *, in) the limit pointer for the text, or NULL if NUL-terminated
391  * @param c (UChar32, out) variable for the code point
392  * @param result (uint32_t, out) uint32_t variable for the trie lookup result
393  */
394 #define UTRIE2_U16_NEXT32(trie, src, limit, c, result) _UTRIE2_U16_NEXT(trie, data32, src, limit, c, result)
395 
396 /**
397  * UTF-16: Get the previous code point (UChar32 c, out), pre-decrement src,
398  * and get a 16-bit value from the trie.
399  *
400  * @param trie (const UTrie2 *, in) a frozen trie
401  * @param start (const UChar *, in) the start pointer for the text
402  * @param src (const UChar *, in/out) the source text pointer
403  * @param c (UChar32, out) variable for the code point
404  * @param result (uint16_t, out) uint16_t variable for the trie lookup result
405  */
406 #define UTRIE2_U16_PREV16(trie, start, src, c, result) _UTRIE2_U16_PREV(trie, index, start, src, c, result)
407 
408 /**
409  * UTF-16: Get the previous code point (UChar32 c, out), pre-decrement src,
410  * and get a 32-bit value from the trie.
411  *
412  * @param trie (const UTrie2 *, in) a frozen trie
413  * @param start (const UChar *, in) the start pointer for the text
414  * @param src (const UChar *, in/out) the source text pointer
415  * @param c (UChar32, out) variable for the code point
416  * @param result (uint32_t, out) uint32_t variable for the trie lookup result
417  */
418 #define UTRIE2_U16_PREV32(trie, start, src, c, result) _UTRIE2_U16_PREV(trie, data32, start, src, c, result)
419 
420 /**
421  * UTF-8: Post-increment src and get a 16-bit value from the trie.
422  *
423  * @param trie (const UTrie2 *, in) a frozen trie
424  * @param src (const char *, in/out) the source text pointer
425  * @param limit (const char *, in) the limit pointer for the text (must not be NULL)
426  * @param result (uint16_t, out) uint16_t variable for the trie lookup result
427  */
428 #define UTRIE2_U8_NEXT16(trie, src, limit, result)\
429     _UTRIE2_U8_NEXT(trie, data16, index, src, limit, result)
430 
431 /**
432  * UTF-8: Post-increment src and get a 32-bit value from the trie.
433  *
434  * @param trie (const UTrie2 *, in) a frozen trie
435  * @param src (const char *, in/out) the source text pointer
436  * @param limit (const char *, in) the limit pointer for the text (must not be NULL)
437  * @param result (uint16_t, out) uint32_t variable for the trie lookup result
438  */
439 #define UTRIE2_U8_NEXT32(trie, src, limit, result) \
440     _UTRIE2_U8_NEXT(trie, data32, data32, src, limit, result)
441 
442 /**
443  * UTF-8: Pre-decrement src and get a 16-bit value from the trie.
444  *
445  * @param trie (const UTrie2 *, in) a frozen trie
446  * @param start (const char *, in) the start pointer for the text
447  * @param src (const char *, in/out) the source text pointer
448  * @param result (uint16_t, out) uint16_t variable for the trie lookup result
449  */
450 #define UTRIE2_U8_PREV16(trie, start, src, result) \
451     _UTRIE2_U8_PREV(trie, data16, index, start, src, result)
452 
453 /**
454  * UTF-8: Pre-decrement src and get a 32-bit value from the trie.
455  *
456  * @param trie (const UTrie2 *, in) a frozen trie
457  * @param start (const char *, in) the start pointer for the text
458  * @param src (const char *, in/out) the source text pointer
459  * @param result (uint16_t, out) uint32_t variable for the trie lookup result
460  */
461 #define UTRIE2_U8_PREV32(trie, start, src, result) \
462     _UTRIE2_U8_PREV(trie, data32, data32, start, src, result)
463 
464 /* Public UTrie2 API: optimized UTF-16 access ------------------------------- */
465 
466 /*
467  * The following functions and macros are used for highly optimized UTF-16
468  * text processing. The UTRIE2_U16_NEXTxy() macros do not depend on these.
469  *
470  * A UTrie2 stores separate values for lead surrogate code _units_ vs. code _points_.
471  * UTF-16 text processing can be optimized by detecting surrogate pairs and
472  * assembling supplementary code points only when there is non-trivial data
473  * available.
474  *
475  * At build-time, use utrie2_enumForLeadSurrogate() to see if there
476  * is non-trivial (non-initialValue) data for any of the supplementary
477  * code points associated with a lead surrogate.
478  * If so, then set a special (application-specific) value for the
479  * lead surrogate code _unit_, with utrie2_set32ForLeadSurrogateCodeUnit().
480  *
481  * At runtime, use UTRIE2_GET16_FROM_U16_SINGLE_LEAD() or
482  * UTRIE2_GET32_FROM_U16_SINGLE_LEAD() per code unit. If there is non-trivial
483  * data and the code unit is a lead surrogate, then check if a trail surrogate
484  * follows. If so, assemble the supplementary code point with
485  * U16_GET_SUPPLEMENTARY() and look up its value with UTRIE2_GET16_FROM_SUPP()
486  * or UTRIE2_GET32_FROM_SUPP(); otherwise reset the lead
487  * surrogate's value or do a code point lookup for it.
488  *
489  * If there is only trivial data for lead and trail surrogates, then processing
490  * can often skip them. For example, in normalization or case mapping
491  * all characters that do not have any mappings are simply copied as is.
492  */
493 
494 /**
495  * Get a value from a lead surrogate code unit as stored in the trie.
496  *
497  * @param trie the trie
498  * @param c the code unit (U+D800..U+DBFF)
499  * @return the value
500  */
501 U_CAPI uint32_t U_EXPORT2
502 utrie2_get32FromLeadSurrogateCodeUnit(const UTrie2 *trie, UChar32 c);
503 
504 /**
505  * Enumerate the trie values for the 1024=0x400 code points
506  * corresponding to a given lead surrogate.
507  * For example, for the lead surrogate U+D87E it will enumerate the values
508  * for [U+2F800..U+2FC00[.
509  * Used by data builder code that sets special lead surrogate code unit values
510  * for optimized UTF-16 string processing.
511  *
512  * Do not modify the trie during the enumeration.
513  *
514  * Except for the limited code point range, this functions just like utrie2_enum():
515  * For each entry in the trie, the value to be delivered is passed through
516  * the UTrie2EnumValue function.
517  * The value is unchanged if that function pointer is NULL.
518  *
519  * For each contiguous range of code points with a given (transformed) value,
520  * the UTrie2EnumRange function is called.
521  *
522  * @param trie a pointer to the trie
523  * @param enumValue a pointer to a function that may transform the trie entry value,
524  *                  or NULL if the values from the trie are to be used directly
525  * @param enumRange a pointer to a function that is called for each contiguous range
526  *                  of code points with the same (transformed) value
527  * @param context an opaque pointer that is passed on to the callback functions
528  */
529 U_CAPI void U_EXPORT2
530 utrie2_enumForLeadSurrogate(const UTrie2 *trie, UChar32 lead,
531                             UTrie2EnumValue *enumValue, UTrie2EnumRange *enumRange,
532                             const void *context);
533 
534 /**
535  * Set a value for a lead surrogate code unit.
536  *
537  * @param trie the unfrozen trie
538  * @param lead the lead surrogate code unit (U+D800..U+DBFF)
539  * @param value the value
540  * @param pErrorCode an in/out ICU UErrorCode; among other possible error codes:
541  * - U_NO_WRITE_PERMISSION if the trie is frozen
542  */
543 U_CAPI void U_EXPORT2
544 utrie2_set32ForLeadSurrogateCodeUnit(UTrie2 *trie,
545                                      UChar32 lead, uint32_t value,
546                                      UErrorCode *pErrorCode);
547 
548 /**
549  * Return a 16-bit trie value from a UTF-16 single/lead code unit (<=U+ffff).
550  * Same as UTRIE2_GET16() if c is a BMP code point except for lead surrogates,
551  * but smaller and faster.
552  *
553  * @param trie (const UTrie2 *, in) a frozen trie
554  * @param c (UChar32, in) the input code unit, must be 0<=c<=U+ffff
555  * @return (uint16_t) The code unit's trie value.
556  */
557 #define UTRIE2_GET16_FROM_U16_SINGLE_LEAD(trie, c) _UTRIE2_GET_FROM_U16_SINGLE_LEAD((trie), index, c)
558 
559 /**
560  * Return a 32-bit trie value from a UTF-16 single/lead code unit (<=U+ffff).
561  * Same as UTRIE2_GET32() if c is a BMP code point except for lead surrogates,
562  * but smaller and faster.
563  *
564  * @param trie (const UTrie2 *, in) a frozen trie
565  * @param c (UChar32, in) the input code unit, must be 0<=c<=U+ffff
566  * @return (uint32_t) The code unit's trie value.
567  */
568 #define UTRIE2_GET32_FROM_U16_SINGLE_LEAD(trie, c) _UTRIE2_GET_FROM_U16_SINGLE_LEAD((trie), data32, c)
569 
570 /**
571  * Return a 16-bit trie value from a supplementary code point (U+10000..U+10ffff).
572  *
573  * @param trie (const UTrie2 *, in) a frozen trie
574  * @param c (UChar32, in) the input code point, must be U+10000<=c<=U+10ffff
575  * @return (uint16_t) The code point's trie value.
576  */
577 #define UTRIE2_GET16_FROM_SUPP(trie, c) _UTRIE2_GET_FROM_SUPP((trie), index, c)
578 
579 /**
580  * Return a 32-bit trie value from a supplementary code point (U+10000..U+10ffff).
581  *
582  * @param trie (const UTrie2 *, in) a frozen trie
583  * @param c (UChar32, in) the input code point, must be U+10000<=c<=U+10ffff
584  * @return (uint32_t) The code point's trie value.
585  */
586 #define UTRIE2_GET32_FROM_SUPP(trie, c) _UTRIE2_GET_FROM_SUPP((trie), data32, c)
587 
588 U_CDECL_END
589 
590 /* C++ convenience wrappers ------------------------------------------------- */
591 
592 #ifdef __cplusplus
593 
594 #include "unicode/utf.h"
595 #include "mutex.h"
596 
597 U_NAMESPACE_BEGIN
598 
599 // Use the Forward/Backward subclasses below.
600 class UTrie2StringIterator : public UMemory {
601 public:
UTrie2StringIterator(const UTrie2 * t,const UChar * p)602     UTrie2StringIterator(const UTrie2 *t, const UChar *p) :
603         trie(t), codePointStart(p), codePointLimit(p), codePoint(U_SENTINEL) {}
604 
605     const UTrie2 *trie;
606     const UChar *codePointStart, *codePointLimit;
607     UChar32 codePoint;
608 };
609 
610 class BackwardUTrie2StringIterator : public UTrie2StringIterator {
611 public:
BackwardUTrie2StringIterator(const UTrie2 * t,const UChar * s,const UChar * p)612     BackwardUTrie2StringIterator(const UTrie2 *t, const UChar *s, const UChar *p) :
613         UTrie2StringIterator(t, p), start(s) {}
614 
615     uint16_t previous16();
616 
617     const UChar *start;
618 };
619 
620 class ForwardUTrie2StringIterator : public UTrie2StringIterator {
621 public:
622     // Iteration limit l can be NULL.
623     // In that case, the caller must detect c==0 and stop.
ForwardUTrie2StringIterator(const UTrie2 * t,const UChar * p,const UChar * l)624     ForwardUTrie2StringIterator(const UTrie2 *t, const UChar *p, const UChar *l) :
625         UTrie2StringIterator(t, p), limit(l) {}
626 
627     uint16_t next16();
628 
629     const UChar *limit;
630 };
631 
632 U_NAMESPACE_END
633 
634 #endif
635 
636 /* Internal definitions ----------------------------------------------------- */
637 
638 U_CDECL_BEGIN
639 
640 /** Build-time trie structure. */
641 struct UNewTrie2;
642 typedef struct UNewTrie2 UNewTrie2;
643 
644 /*
645  * Trie structure definition.
646  *
647  * Either the data table is 16 bits wide and accessed via the index
648  * pointer, with each index item increased by indexLength;
649  * in this case, data32==NULL, and data16 is used for direct ASCII access.
650  *
651  * Or the data table is 32 bits wide and accessed via the data32 pointer.
652  */
653 struct UTrie2 {
654     /* protected: used by macros and functions for reading values */
655     const uint16_t *index;
656     const uint16_t *data16;     /* for fast UTF-8 ASCII access, if 16b data */
657     const uint32_t *data32;     /* NULL if 16b data is used via index */
658 
659     int32_t indexLength, dataLength;
660     uint16_t index2NullOffset;  /* 0xffff if there is no dedicated index-2 null block */
661     uint16_t dataNullOffset;
662     uint32_t initialValue;
663     /** Value returned for out-of-range code points and illegal UTF-8. */
664     uint32_t errorValue;
665 
666     /* Start of the last range which ends at U+10ffff, and its value. */
667     UChar32 highStart;
668     int32_t highValueIndex;
669 
670     /* private: used by builder and unserialization functions */
671     void *memory;           /* serialized bytes; NULL if not frozen yet */
672     int32_t length;         /* number of serialized bytes at memory; 0 if not frozen yet */
673     UBool isMemoryOwned;    /* TRUE if the trie owns the memory */
674     UBool padding1;
675     int16_t padding2;
676     UNewTrie2 *newTrie;     /* builder object; NULL when frozen */
677 
678 #ifdef UTRIE2_DEBUG
679     const char *name;
680 #endif
681 };
682 
683 /**
684  * Trie constants, defining shift widths, index array lengths, etc.
685  *
686  * These are needed for the runtime macros but users can treat these as
687  * implementation details and skip to the actual public API further below.
688  */
689 enum {
690     /** Shift size for getting the index-1 table offset. */
691     UTRIE2_SHIFT_1=6+5,
692 
693     /** Shift size for getting the index-2 table offset. */
694     UTRIE2_SHIFT_2=5,
695 
696     /**
697      * Difference between the two shift sizes,
698      * for getting an index-1 offset from an index-2 offset. 6=11-5
699      */
700     UTRIE2_SHIFT_1_2=UTRIE2_SHIFT_1-UTRIE2_SHIFT_2,
701 
702     /**
703      * Number of index-1 entries for the BMP. 32=0x20
704      * This part of the index-1 table is omitted from the serialized form.
705      */
706     UTRIE2_OMITTED_BMP_INDEX_1_LENGTH=0x10000>>UTRIE2_SHIFT_1,
707 
708     /** Number of code points per index-1 table entry. 2048=0x800 */
709     UTRIE2_CP_PER_INDEX_1_ENTRY=1<<UTRIE2_SHIFT_1,
710 
711     /** Number of entries in an index-2 block. 64=0x40 */
712     UTRIE2_INDEX_2_BLOCK_LENGTH=1<<UTRIE2_SHIFT_1_2,
713 
714     /** Mask for getting the lower bits for the in-index-2-block offset. */
715     UTRIE2_INDEX_2_MASK=UTRIE2_INDEX_2_BLOCK_LENGTH-1,
716 
717     /** Number of entries in a data block. 32=0x20 */
718     UTRIE2_DATA_BLOCK_LENGTH=1<<UTRIE2_SHIFT_2,
719 
720     /** Mask for getting the lower bits for the in-data-block offset. */
721     UTRIE2_DATA_MASK=UTRIE2_DATA_BLOCK_LENGTH-1,
722 
723     /**
724      * Shift size for shifting left the index array values.
725      * Increases possible data size with 16-bit index values at the cost
726      * of compactability.
727      * This requires data blocks to be aligned by UTRIE2_DATA_GRANULARITY.
728      */
729     UTRIE2_INDEX_SHIFT=2,
730 
731     /** The alignment size of a data block. Also the granularity for compaction. */
732     UTRIE2_DATA_GRANULARITY=1<<UTRIE2_INDEX_SHIFT,
733 
734     /* Fixed layout of the first part of the index array. ------------------- */
735 
736     /**
737      * The BMP part of the index-2 table is fixed and linear and starts at offset 0.
738      * Length=2048=0x800=0x10000>>UTRIE2_SHIFT_2.
739      */
740     UTRIE2_INDEX_2_OFFSET=0,
741 
742     /**
743      * The part of the index-2 table for U+D800..U+DBFF stores values for
744      * lead surrogate code _units_ not code _points_.
745      * Values for lead surrogate code _points_ are indexed with this portion of the table.
746      * Length=32=0x20=0x400>>UTRIE2_SHIFT_2. (There are 1024=0x400 lead surrogates.)
747      */
748     UTRIE2_LSCP_INDEX_2_OFFSET=0x10000>>UTRIE2_SHIFT_2,
749     UTRIE2_LSCP_INDEX_2_LENGTH=0x400>>UTRIE2_SHIFT_2,
750 
751     /** Count the lengths of both BMP pieces. 2080=0x820 */
752     UTRIE2_INDEX_2_BMP_LENGTH=UTRIE2_LSCP_INDEX_2_OFFSET+UTRIE2_LSCP_INDEX_2_LENGTH,
753 
754     /**
755      * The 2-byte UTF-8 version of the index-2 table follows at offset 2080=0x820.
756      * Length 32=0x20 for lead bytes C0..DF, regardless of UTRIE2_SHIFT_2.
757      */
758     UTRIE2_UTF8_2B_INDEX_2_OFFSET=UTRIE2_INDEX_2_BMP_LENGTH,
759     UTRIE2_UTF8_2B_INDEX_2_LENGTH=0x800>>6,  /* U+0800 is the first code point after 2-byte UTF-8 */
760 
761     /**
762      * The index-1 table, only used for supplementary code points, at offset 2112=0x840.
763      * Variable length, for code points up to highStart, where the last single-value range starts.
764      * Maximum length 512=0x200=0x100000>>UTRIE2_SHIFT_1.
765      * (For 0x100000 supplementary code points U+10000..U+10ffff.)
766      *
767      * The part of the index-2 table for supplementary code points starts
768      * after this index-1 table.
769      *
770      * Both the index-1 table and the following part of the index-2 table
771      * are omitted completely if there is only BMP data.
772      */
773     UTRIE2_INDEX_1_OFFSET=UTRIE2_UTF8_2B_INDEX_2_OFFSET+UTRIE2_UTF8_2B_INDEX_2_LENGTH,
774     UTRIE2_MAX_INDEX_1_LENGTH=0x100000>>UTRIE2_SHIFT_1,
775 
776     /*
777      * Fixed layout of the first part of the data array. -----------------------
778      * Starts with 4 blocks (128=0x80 entries) for ASCII.
779      */
780 
781     /**
782      * The illegal-UTF-8 data block follows the ASCII block, at offset 128=0x80.
783      * Used with linear access for single bytes 0..0xbf for simple error handling.
784      * Length 64=0x40, not UTRIE2_DATA_BLOCK_LENGTH.
785      */
786     UTRIE2_BAD_UTF8_DATA_OFFSET=0x80,
787 
788     /** The start of non-linear-ASCII data blocks, at offset 192=0xc0. */
789     UTRIE2_DATA_START_OFFSET=0xc0
790 };
791 
792 /* Internal functions and macros -------------------------------------------- */
793 
794 /**
795  * Internal function for part of the UTRIE2_U8_NEXTxx() macro implementations.
796  * Do not call directly.
797  * @internal
798  */
799 U_INTERNAL int32_t U_EXPORT2
800 utrie2_internalU8NextIndex(const UTrie2 *trie, UChar32 c,
801                            const uint8_t *src, const uint8_t *limit);
802 
803 /**
804  * Internal function for part of the UTRIE2_U8_PREVxx() macro implementations.
805  * Do not call directly.
806  * @internal
807  */
808 U_INTERNAL int32_t U_EXPORT2
809 utrie2_internalU8PrevIndex(const UTrie2 *trie, UChar32 c,
810                            const uint8_t *start, const uint8_t *src);
811 
812 
813 /** Internal low-level trie getter. Returns a data index. */
814 #define _UTRIE2_INDEX_RAW(offset, trieIndex, c) \
815     (((int32_t)((trieIndex)[(offset)+((c)>>UTRIE2_SHIFT_2)]) \
816     <<UTRIE2_INDEX_SHIFT)+ \
817     ((c)&UTRIE2_DATA_MASK))
818 
819 /** Internal trie getter from a UTF-16 single/lead code unit. Returns the data index. */
820 #define _UTRIE2_INDEX_FROM_U16_SINGLE_LEAD(trieIndex, c) _UTRIE2_INDEX_RAW(0, trieIndex, c)
821 
822 /** Internal trie getter from a lead surrogate code point (D800..DBFF). Returns the data index. */
823 #define _UTRIE2_INDEX_FROM_LSCP(trieIndex, c) \
824     _UTRIE2_INDEX_RAW(UTRIE2_LSCP_INDEX_2_OFFSET-(0xd800>>UTRIE2_SHIFT_2), trieIndex, c)
825 
826 /** Internal trie getter from a BMP code point. Returns the data index. */
827 #define _UTRIE2_INDEX_FROM_BMP(trieIndex, c) \
828     _UTRIE2_INDEX_RAW(U_IS_LEAD(c) ? UTRIE2_LSCP_INDEX_2_OFFSET-(0xd800>>UTRIE2_SHIFT_2) : 0, \
829                       trieIndex, c)
830 
831 /** Internal trie getter from a supplementary code point below highStart. Returns the data index. */
832 #define _UTRIE2_INDEX_FROM_SUPP(trieIndex, c) \
833     (((int32_t)((trieIndex)[ \
834         (trieIndex)[(UTRIE2_INDEX_1_OFFSET-UTRIE2_OMITTED_BMP_INDEX_1_LENGTH)+ \
835                       ((c)>>UTRIE2_SHIFT_1)]+ \
836         (((c)>>UTRIE2_SHIFT_2)&UTRIE2_INDEX_2_MASK)]) \
837     <<UTRIE2_INDEX_SHIFT)+ \
838     ((c)&UTRIE2_DATA_MASK))
839 
840 /**
841  * Internal trie getter from a code point, with checking that c is in 0..10FFFF.
842  * Returns the data index.
843  */
844 #define _UTRIE2_INDEX_FROM_CP(trie, asciiOffset, c) \
845     ((uint32_t)(c)<0xd800 ? \
846         _UTRIE2_INDEX_RAW(0, (trie)->index, c) : \
847         (uint32_t)(c)<=0xffff ? \
848             _UTRIE2_INDEX_RAW( \
849                 (c)<=0xdbff ? UTRIE2_LSCP_INDEX_2_OFFSET-(0xd800>>UTRIE2_SHIFT_2) : 0, \
850                 (trie)->index, c) : \
851             (uint32_t)(c)>0x10ffff ? \
852                 (asciiOffset)+UTRIE2_BAD_UTF8_DATA_OFFSET : \
853                 (c)>=(trie)->highStart ? \
854                     (trie)->highValueIndex : \
855                     _UTRIE2_INDEX_FROM_SUPP((trie)->index, c))
856 
857 /** Internal trie getter from a UTF-16 single/lead code unit. Returns the data. */
858 #define _UTRIE2_GET_FROM_U16_SINGLE_LEAD(trie, data, c) \
859     (trie)->data[_UTRIE2_INDEX_FROM_U16_SINGLE_LEAD((trie)->index, c)]
860 
861 /** Internal trie getter from a supplementary code point. Returns the data. */
862 #define _UTRIE2_GET_FROM_SUPP(trie, data, c) \
863     (trie)->data[(c)>=(trie)->highStart ? (trie)->highValueIndex : \
864                  _UTRIE2_INDEX_FROM_SUPP((trie)->index, c)]
865 
866 /**
867  * Internal trie getter from a code point, with checking that c is in 0..10FFFF.
868  * Returns the data.
869  */
870 #define _UTRIE2_GET(trie, data, asciiOffset, c) \
871     (trie)->data[_UTRIE2_INDEX_FROM_CP(trie, asciiOffset, c)]
872 
873 /** Internal next-post-increment: get the next code point (c) and its data. */
874 #define _UTRIE2_U16_NEXT(trie, data, src, limit, c, result) { \
875     { \
876         uint16_t __c2; \
877         (c)=*(src)++; \
878         if(!U16_IS_LEAD(c)) { \
879             (result)=_UTRIE2_GET_FROM_U16_SINGLE_LEAD(trie, data, c); \
880         } else if((src)==(limit) || !U16_IS_TRAIL(__c2=*(src))) { \
881             (result)=(trie)->data[_UTRIE2_INDEX_FROM_LSCP((trie)->index, c)]; \
882         } else { \
883             ++(src); \
884             (c)=U16_GET_SUPPLEMENTARY((c), __c2); \
885             (result)=_UTRIE2_GET_FROM_SUPP((trie), data, (c)); \
886         } \
887     } \
888 }
889 
890 /** Internal pre-decrement-previous: get the previous code point (c) and its data */
891 #define _UTRIE2_U16_PREV(trie, data, start, src, c, result) { \
892     { \
893         uint16_t __c2; \
894         (c)=*--(src); \
895         if(!U16_IS_TRAIL(c) || (src)==(start) || !U16_IS_LEAD(__c2=*((src)-1))) { \
896             (result)=(trie)->data[_UTRIE2_INDEX_FROM_BMP((trie)->index, c)]; \
897         } else { \
898             --(src); \
899             (c)=U16_GET_SUPPLEMENTARY(__c2, (c)); \
900             (result)=_UTRIE2_GET_FROM_SUPP((trie), data, (c)); \
901         } \
902     } \
903 }
904 
905 /** Internal UTF-8 next-post-increment: get the next code point's data. */
906 #define _UTRIE2_U8_NEXT(trie, ascii, data, src, limit, result) { \
907     uint8_t __lead=(uint8_t)*(src)++; \
908     if(U8_IS_SINGLE(__lead)) { \
909         (result)=(trie)->ascii[__lead]; \
910     } else { \
911         uint8_t __t1, __t2; \
912         if( /* handle U+0800..U+FFFF inline */ \
913             0xe0<=__lead && __lead<0xf0 && ((src)+1)<(limit) && \
914             U8_IS_VALID_LEAD3_AND_T1(__lead, __t1=(uint8_t)*(src)) && \
915             (__t2=(uint8_t)(*((src)+1)-0x80))<= 0x3f \
916         ) { \
917             (src)+=2; \
918             (result)=(trie)->data[ \
919                 ((int32_t)((trie)->index[((__lead-0xe0)<<(12-UTRIE2_SHIFT_2))+ \
920                                          ((__t1&0x3f)<<(6-UTRIE2_SHIFT_2))+(__t2>>UTRIE2_SHIFT_2)]) \
921                 <<UTRIE2_INDEX_SHIFT)+ \
922                 (__t2&UTRIE2_DATA_MASK)]; \
923         } else if( /* handle U+0080..U+07FF inline */ \
924             __lead<0xe0 && __lead>=0xc2 && (src)<(limit) && \
925             (__t1=(uint8_t)(*(src)-0x80))<=0x3f \
926         ) { \
927             ++(src); \
928             (result)=(trie)->data[ \
929                 (trie)->index[(UTRIE2_UTF8_2B_INDEX_2_OFFSET-0xc0)+__lead]+ \
930                 __t1]; \
931         } else { \
932             int32_t __index=utrie2_internalU8NextIndex((trie), __lead, (const uint8_t *)(src), \
933                                                                        (const uint8_t *)(limit)); \
934             (src)+=__index&7; \
935             (result)=(trie)->data[__index>>3]; \
936         } \
937     } \
938 }
939 
940 /** Internal UTF-8 pre-decrement-previous: get the previous code point's data. */
941 #define _UTRIE2_U8_PREV(trie, ascii, data, start, src, result) { \
942     uint8_t __b=(uint8_t)*--(src); \
943     if(U8_IS_SINGLE(__b)) { \
944         (result)=(trie)->ascii[__b]; \
945     } else { \
946         int32_t __index=utrie2_internalU8PrevIndex((trie), __b, (const uint8_t *)(start), \
947                                                                 (const uint8_t *)(src)); \
948         (src)-=__index&7; \
949         (result)=(trie)->data[__index>>3]; \
950     } \
951 }
952 
953 U_CDECL_END
954 
955 #endif
956