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