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
26U_CDECL_BEGIN
27
28struct UTrie; /* forward declaration */
29#ifndef __UTRIE_H__
30typedef 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 */
65struct UTrie2;
66typedef 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 */
73enum 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};
81typedef 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 */
102U_CAPI UTrie2 * U_EXPORT2
103utrie2_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 */
128U_CAPI UTrie2 * U_EXPORT2
129utrie2_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 */
143U_CAPI uint32_t U_EXPORT2
144utrie2_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 */
156typedef uint32_t U_CALLCONV
157UTrie2EnumValue(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 */
172typedef UBool U_CALLCONV
173UTrie2EnumRange(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 */
193U_CAPI void U_EXPORT2
194utrie2_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 */
210U_CAPI UTrie2 * U_EXPORT2
211utrie2_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 */
221U_CAPI UTrie2 * U_EXPORT2
222utrie2_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 */
233U_CAPI UTrie2 * U_EXPORT2
234utrie2_cloneAsThawed(const UTrie2 *other, UErrorCode *pErrorCode);
235
236/**
237 * Close a trie and release associated memory.
238 *
239 * @param trie the trie
240 */
241U_CAPI void U_EXPORT2
242utrie2_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 */
253U_CAPI void U_EXPORT2
254utrie2_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 */
269U_CAPI void U_EXPORT2
270utrie2_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 */
294U_CAPI void U_EXPORT2
295utrie2_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 */
304U_CAPI UBool U_EXPORT2
305utrie2_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 */
325U_CAPI int32_t U_EXPORT2
326utrie2_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 */
342U_CAPI UTrie2 * U_EXPORT2
343utrie2_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 */
501U_CAPI uint32_t U_EXPORT2
502utrie2_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 */
529U_CAPI void U_EXPORT2
530utrie2_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 */
543U_CAPI void U_EXPORT2
544utrie2_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
588U_CDECL_END
589
590/* C++ convenience wrappers ------------------------------------------------- */
591
592#ifdef __cplusplus
593
594#include "unicode/uobject.h"
595#include "unicode/utf.h"
596
597U_NAMESPACE_BEGIN
598
599// Use the Forward/Backward subclasses below.
600class UTrie2StringIterator : public UMemory {
601public:
602 UTrie2StringIterator(const UTrie2 *t, const char16_t *p) :
603 trie(t), codePointStart(p), codePointLimit(p), codePoint(U_SENTINEL) {}
604
605 const UTrie2 *trie;
606 const char16_t *codePointStart, *codePointLimit;
607 UChar32 codePoint;
608};
609
610class BackwardUTrie2StringIterator : public UTrie2StringIterator {
611public:
612 BackwardUTrie2StringIterator(const UTrie2 *t, const char16_t *s, const char16_t *p) :
613 UTrie2StringIterator(t, p), start(s) {}
614
615 uint16_t previous16();
616
617 const char16_t *start;
618};
619
620class ForwardUTrie2StringIterator : public UTrie2StringIterator {
621public:
622 // Iteration limit l can be nullptr.
623 // In that case, the caller must detect c==0 and stop.
624 ForwardUTrie2StringIterator(const UTrie2 *t, const char16_t *p, const char16_t *l) :
625 UTrie2StringIterator(t, p), limit(l) {}
626
627 uint16_t next16();
628
629 const char16_t *limit;
630};
631
632U_NAMESPACE_END
633
634#endif
635
636/* Internal definitions ----------------------------------------------------- */
637
638U_CDECL_BEGIN
639
640/** Build-time trie structure. */
641struct UNewTrie2;
642typedef 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 */
653struct 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 */
689enum {
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 */
799U_CAPI int32_t U_EXPORT2
800utrie2_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 */
808U_CAPI int32_t U_EXPORT2
809utrie2_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) UPRV_BLOCK_MACRO_BEGIN { \
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} UPRV_BLOCK_MACRO_END
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) UPRV_BLOCK_MACRO_BEGIN { \
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} UPRV_BLOCK_MACRO_END
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) UPRV_BLOCK_MACRO_BEGIN { \
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} UPRV_BLOCK_MACRO_END
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) UPRV_BLOCK_MACRO_BEGIN { \
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} UPRV_BLOCK_MACRO_END
952
953U_CDECL_END
954
955#endif
956