michael@0: /* michael@0: ****************************************************************************** michael@0: * michael@0: * Copyright (C) 2001-2013, International Business Machines michael@0: * Corporation and others. All Rights Reserved. michael@0: * michael@0: ****************************************************************************** michael@0: * file name: utrie2.h michael@0: * encoding: US-ASCII michael@0: * tab size: 8 (not used) michael@0: * indentation:4 michael@0: * michael@0: * created on: 2008aug16 (starting from a copy of utrie.h) michael@0: * created by: Markus W. Scherer michael@0: */ michael@0: michael@0: #ifndef __UTRIE2_H__ michael@0: #define __UTRIE2_H__ michael@0: michael@0: #include "unicode/utypes.h" michael@0: #include "putilimp.h" michael@0: #include "udataswp.h" michael@0: michael@0: U_CDECL_BEGIN michael@0: michael@0: struct UTrie; /* forward declaration */ michael@0: #ifndef __UTRIE_H__ michael@0: typedef struct UTrie UTrie; michael@0: #endif michael@0: michael@0: /** michael@0: * \file michael@0: * michael@0: * This is a common implementation of a Unicode trie. michael@0: * It is a kind of compressed, serializable table of 16- or 32-bit values associated with michael@0: * Unicode code points (0..0x10ffff). (A map from code points to integers.) michael@0: * michael@0: * This is the second common version of a Unicode trie (hence the name UTrie2). michael@0: * Compared with UTrie version 1: michael@0: * - Still splitting BMP code points 11:5 bits for index and data table lookups. michael@0: * - Still separate data for lead surrogate code _units_ vs. code _points_, michael@0: * but the lead surrogate code unit values are not required any more michael@0: * for data lookup for supplementary code points. michael@0: * - The "folding" mechanism is removed. In UTrie version 1, this somewhat michael@0: * hard-to-explain mechanism was meant to be used for optimized UTF-16 michael@0: * processing, with application-specific encoding of indexing bits michael@0: * in the lead surrogate data for the associated supplementary code points. michael@0: * - For the last single-value code point range (ending with U+10ffff), michael@0: * the starting code point ("highStart") and the value are stored. michael@0: * - For supplementary code points U+10000..highStart-1 a three-table lookup michael@0: * (two index tables and one data table) is used. The first index michael@0: * is truncated, omitting both the BMP portion and the high range. michael@0: * - There is a special small index for 2-byte UTF-8, and the initial data michael@0: * entries are designed for fast 1/2-byte UTF-8 lookup. michael@0: */ michael@0: michael@0: /** michael@0: * Trie structure. michael@0: * Use only with public API macros and functions. michael@0: */ michael@0: struct UTrie2; michael@0: typedef struct UTrie2 UTrie2; michael@0: michael@0: /* Public UTrie2 API functions: read-only access ---------------------------- */ michael@0: michael@0: /** michael@0: * Selectors for the width of a UTrie2 data value. michael@0: */ michael@0: enum UTrie2ValueBits { michael@0: /** 16 bits per UTrie2 data value. */ michael@0: UTRIE2_16_VALUE_BITS, michael@0: /** 32 bits per UTrie2 data value. */ michael@0: UTRIE2_32_VALUE_BITS, michael@0: /** Number of selectors for the width of UTrie2 data values. */ michael@0: UTRIE2_COUNT_VALUE_BITS michael@0: }; michael@0: typedef enum UTrie2ValueBits UTrie2ValueBits; michael@0: michael@0: /** michael@0: * Open a frozen trie from its serialized from, stored in 32-bit-aligned memory. michael@0: * Inverse of utrie2_serialize(). michael@0: * The memory must remain valid and unchanged as long as the trie is used. michael@0: * You must utrie2_close() the trie once you are done using it. michael@0: * michael@0: * @param valueBits selects the data entry size; results in an michael@0: * U_INVALID_FORMAT_ERROR if it does not match the serialized form michael@0: * @param data a pointer to 32-bit-aligned memory containing the serialized form of a UTrie2 michael@0: * @param length the number of bytes available at data; michael@0: * can be more than necessary michael@0: * @param pActualLength receives the actual number of bytes at data taken up by the trie data; michael@0: * can be NULL michael@0: * @param pErrorCode an in/out ICU UErrorCode michael@0: * @return the unserialized trie michael@0: * michael@0: * @see utrie2_open michael@0: * @see utrie2_serialize michael@0: */ michael@0: U_CAPI UTrie2 * U_EXPORT2 michael@0: utrie2_openFromSerialized(UTrie2ValueBits valueBits, michael@0: const void *data, int32_t length, int32_t *pActualLength, michael@0: UErrorCode *pErrorCode); michael@0: michael@0: /** michael@0: * Open a frozen, empty "dummy" trie. michael@0: * A dummy trie is an empty trie, used when a real data trie cannot michael@0: * be loaded. Equivalent to calling utrie2_open() and utrie2_freeze(), michael@0: * but without internally creating and compacting/serializing the michael@0: * builder data structure. michael@0: * michael@0: * The trie always returns the initialValue, michael@0: * or the errorValue for out-of-range code points and illegal UTF-8. michael@0: * michael@0: * You must utrie2_close() the trie once you are done using it. michael@0: * michael@0: * @param valueBits selects the data entry size michael@0: * @param initialValue the initial value that is set for all code points michael@0: * @param errorValue the value for out-of-range code points and illegal UTF-8 michael@0: * @param pErrorCode an in/out ICU UErrorCode michael@0: * @return the dummy trie michael@0: * michael@0: * @see utrie2_openFromSerialized michael@0: * @see utrie2_open michael@0: */ michael@0: U_CAPI UTrie2 * U_EXPORT2 michael@0: utrie2_openDummy(UTrie2ValueBits valueBits, michael@0: uint32_t initialValue, uint32_t errorValue, michael@0: UErrorCode *pErrorCode); michael@0: michael@0: /** michael@0: * Get a value from a code point as stored in the trie. michael@0: * Easier to use than UTRIE2_GET16() and UTRIE2_GET32() but slower. michael@0: * Easier to use because, unlike the macros, this function works on all UTrie2 michael@0: * objects, frozen or not, holding 16-bit or 32-bit data values. michael@0: * michael@0: * @param trie the trie michael@0: * @param c the code point michael@0: * @return the value michael@0: */ michael@0: U_CAPI uint32_t U_EXPORT2 michael@0: utrie2_get32(const UTrie2 *trie, UChar32 c); michael@0: michael@0: /* enumeration callback types */ michael@0: michael@0: /** michael@0: * Callback from utrie2_enum(), extracts a uint32_t value from a michael@0: * trie value. This value will be passed on to the UTrie2EnumRange function. michael@0: * michael@0: * @param context an opaque pointer, as passed into utrie2_enum() michael@0: * @param value a value from the trie michael@0: * @return the value that is to be passed on to the UTrie2EnumRange function michael@0: */ michael@0: typedef uint32_t U_CALLCONV michael@0: UTrie2EnumValue(const void *context, uint32_t value); michael@0: michael@0: /** michael@0: * Callback from utrie2_enum(), is called for each contiguous range michael@0: * of code points with the same value as retrieved from the trie and michael@0: * transformed by the UTrie2EnumValue function. michael@0: * michael@0: * The callback function can stop the enumeration by returning FALSE. michael@0: * michael@0: * @param context an opaque pointer, as passed into utrie2_enum() michael@0: * @param start the first code point in a contiguous range with value michael@0: * @param end the last code point in a contiguous range with value (inclusive) michael@0: * @param value the value that is set for all code points in [start..end] michael@0: * @return FALSE to stop the enumeration michael@0: */ michael@0: typedef UBool U_CALLCONV michael@0: UTrie2EnumRange(const void *context, UChar32 start, UChar32 end, uint32_t value); michael@0: michael@0: /** michael@0: * Enumerate efficiently all values in a trie. michael@0: * Do not modify the trie during the enumeration. michael@0: * michael@0: * For each entry in the trie, the value to be delivered is passed through michael@0: * the UTrie2EnumValue function. michael@0: * The value is unchanged if that function pointer is NULL. michael@0: * michael@0: * For each contiguous range of code points with a given (transformed) value, michael@0: * the UTrie2EnumRange function is called. michael@0: * michael@0: * @param trie a pointer to the trie michael@0: * @param enumValue a pointer to a function that may transform the trie entry value, michael@0: * or NULL if the values from the trie are to be used directly michael@0: * @param enumRange a pointer to a function that is called for each contiguous range michael@0: * of code points with the same (transformed) value michael@0: * @param context an opaque pointer that is passed on to the callback functions michael@0: */ michael@0: U_CAPI void U_EXPORT2 michael@0: utrie2_enum(const UTrie2 *trie, michael@0: UTrie2EnumValue *enumValue, UTrie2EnumRange *enumRange, const void *context); michael@0: michael@0: /* Building a trie ---------------------------------------------------------- */ michael@0: michael@0: /** michael@0: * Open an empty, writable trie. At build time, 32-bit data values are used. michael@0: * utrie2_freeze() takes a valueBits parameter michael@0: * which determines the data value width in the serialized and frozen forms. michael@0: * You must utrie2_close() the trie once you are done using it. michael@0: * michael@0: * @param initialValue the initial value that is set for all code points michael@0: * @param errorValue the value for out-of-range code points and illegal UTF-8 michael@0: * @param pErrorCode an in/out ICU UErrorCode michael@0: * @return a pointer to the allocated and initialized new trie michael@0: */ michael@0: U_CAPI UTrie2 * U_EXPORT2 michael@0: utrie2_open(uint32_t initialValue, uint32_t errorValue, UErrorCode *pErrorCode); michael@0: michael@0: /** michael@0: * Clone a trie. michael@0: * You must utrie2_close() the clone once you are done using it. michael@0: * michael@0: * @param other the trie to clone michael@0: * @param pErrorCode an in/out ICU UErrorCode michael@0: * @return a pointer to the new trie clone michael@0: */ michael@0: U_CAPI UTrie2 * U_EXPORT2 michael@0: utrie2_clone(const UTrie2 *other, UErrorCode *pErrorCode); michael@0: michael@0: /** michael@0: * Clone a trie. The clone will be mutable/writable even if the other trie michael@0: * is frozen. (See utrie2_freeze().) michael@0: * You must utrie2_close() the clone once you are done using it. michael@0: * michael@0: * @param other the trie to clone michael@0: * @param pErrorCode an in/out ICU UErrorCode michael@0: * @return a pointer to the new trie clone michael@0: */ michael@0: U_CAPI UTrie2 * U_EXPORT2 michael@0: utrie2_cloneAsThawed(const UTrie2 *other, UErrorCode *pErrorCode); michael@0: michael@0: /** michael@0: * Close a trie and release associated memory. michael@0: * michael@0: * @param trie the trie michael@0: */ michael@0: U_CAPI void U_EXPORT2 michael@0: utrie2_close(UTrie2 *trie); michael@0: michael@0: /** michael@0: * Set a value for a code point. michael@0: * michael@0: * @param trie the unfrozen trie michael@0: * @param c the code point michael@0: * @param value the value michael@0: * @param pErrorCode an in/out ICU UErrorCode; among other possible error codes: michael@0: * - U_NO_WRITE_PERMISSION if the trie is frozen michael@0: */ michael@0: U_CAPI void U_EXPORT2 michael@0: utrie2_set32(UTrie2 *trie, UChar32 c, uint32_t value, UErrorCode *pErrorCode); michael@0: michael@0: /** michael@0: * Set a value in a range of code points [start..end]. michael@0: * All code points c with start<=c<=end will get the value if michael@0: * overwrite is TRUE or if the old value is the initial value. michael@0: * michael@0: * @param trie the unfrozen trie michael@0: * @param start the first code point to get the value michael@0: * @param end the last code point to get the value (inclusive) michael@0: * @param value the value michael@0: * @param overwrite flag for whether old non-initial values are to be overwritten michael@0: * @param pErrorCode an in/out ICU UErrorCode; among other possible error codes: michael@0: * - U_NO_WRITE_PERMISSION if the trie is frozen michael@0: */ michael@0: U_CAPI void U_EXPORT2 michael@0: utrie2_setRange32(UTrie2 *trie, michael@0: UChar32 start, UChar32 end, michael@0: uint32_t value, UBool overwrite, michael@0: UErrorCode *pErrorCode); michael@0: michael@0: /** michael@0: * Freeze a trie. Make it immutable (read-only) and compact it, michael@0: * ready for serialization and for use with fast macros. michael@0: * Functions to set values will fail after serializing. michael@0: * michael@0: * A trie can be frozen only once. If this function is called again with different michael@0: * valueBits then it will set a U_ILLEGAL_ARGUMENT_ERROR. michael@0: * michael@0: * @param trie the trie michael@0: * @param valueBits selects the data entry size; if smaller than 32 bits, then michael@0: * the values stored in the trie will be truncated michael@0: * @param pErrorCode an in/out ICU UErrorCode; among other possible error codes: michael@0: * - U_INDEX_OUTOFBOUNDS_ERROR if the compacted index or data arrays are too long michael@0: * for serialization michael@0: * (the trie will be immutable and usable, michael@0: * but not frozen and not usable with the fast macros) michael@0: * michael@0: * @see utrie2_cloneAsThawed michael@0: */ michael@0: U_CAPI void U_EXPORT2 michael@0: utrie2_freeze(UTrie2 *trie, UTrie2ValueBits valueBits, UErrorCode *pErrorCode); michael@0: michael@0: /** michael@0: * Test if the trie is frozen. (See utrie2_freeze().) michael@0: * michael@0: * @param trie the trie michael@0: * @return TRUE if the trie is frozen, that is, immutable, ready for serialization michael@0: * and for use with fast macros michael@0: */ michael@0: U_CAPI UBool U_EXPORT2 michael@0: utrie2_isFrozen(const UTrie2 *trie); michael@0: michael@0: /** michael@0: * Serialize a frozen trie into 32-bit aligned memory. michael@0: * If the trie is not frozen, then the function returns with a U_ILLEGAL_ARGUMENT_ERROR. michael@0: * A trie can be serialized multiple times. michael@0: * michael@0: * @param trie the frozen trie michael@0: * @param data a pointer to 32-bit-aligned memory to be filled with the trie data, michael@0: * can be NULL if capacity==0 michael@0: * @param capacity the number of bytes available at data, michael@0: * or 0 for preflighting michael@0: * @param pErrorCode an in/out ICU UErrorCode; among other possible error codes: michael@0: * - U_BUFFER_OVERFLOW_ERROR if the data storage block is too small for serialization michael@0: * - U_ILLEGAL_ARGUMENT_ERROR if the trie is not frozen or the data and capacity michael@0: * parameters are bad michael@0: * @return the number of bytes written or needed for the trie michael@0: * michael@0: * @see utrie2_openFromSerialized() michael@0: */ michael@0: U_CAPI int32_t U_EXPORT2 michael@0: utrie2_serialize(UTrie2 *trie, michael@0: void *data, int32_t capacity, michael@0: UErrorCode *pErrorCode); michael@0: michael@0: /* Public UTrie2 API: miscellaneous functions ------------------------------- */ michael@0: michael@0: /** michael@0: * Get the UTrie version from 32-bit-aligned memory containing the serialized form michael@0: * of either a UTrie (version 1) or a UTrie2 (version 2). michael@0: * michael@0: * @param data a pointer to 32-bit-aligned memory containing the serialized form michael@0: * of a UTrie, version 1 or 2 michael@0: * @param length the number of bytes available at data; michael@0: * can be more than necessary (see return value) michael@0: * @param anyEndianOk If FALSE, only platform-endian serialized forms are recognized. michael@0: * If TRUE, opposite-endian serialized forms are recognized as well. michael@0: * @return the UTrie version of the serialized form, or 0 if it is not michael@0: * recognized as a serialized UTrie michael@0: */ michael@0: U_CAPI int32_t U_EXPORT2 michael@0: utrie2_getVersion(const void *data, int32_t length, UBool anyEndianOk); michael@0: michael@0: /** michael@0: * Swap a serialized UTrie2. michael@0: * @internal michael@0: */ michael@0: U_CAPI int32_t U_EXPORT2 michael@0: utrie2_swap(const UDataSwapper *ds, michael@0: const void *inData, int32_t length, void *outData, michael@0: UErrorCode *pErrorCode); michael@0: michael@0: /** michael@0: * Swap a serialized UTrie or UTrie2. michael@0: * @internal michael@0: */ michael@0: U_CAPI int32_t U_EXPORT2 michael@0: utrie2_swapAnyVersion(const UDataSwapper *ds, michael@0: const void *inData, int32_t length, void *outData, michael@0: UErrorCode *pErrorCode); michael@0: michael@0: /** michael@0: * Build a UTrie2 (version 2) from a UTrie (version 1). michael@0: * Enumerates all values in the UTrie and builds a UTrie2 with the same values. michael@0: * The resulting UTrie2 will be frozen. michael@0: * michael@0: * @param trie1 the runtime UTrie structure to be enumerated michael@0: * @param errorValue the value for out-of-range code points and illegal UTF-8 michael@0: * @param pErrorCode an in/out ICU UErrorCode michael@0: * @return The frozen UTrie2 with the same values as the UTrie. michael@0: */ michael@0: U_CAPI UTrie2 * U_EXPORT2 michael@0: utrie2_fromUTrie(const UTrie *trie1, uint32_t errorValue, UErrorCode *pErrorCode); michael@0: michael@0: /* Public UTrie2 API macros ------------------------------------------------- */ michael@0: michael@0: /* michael@0: * These macros provide fast data lookup from a frozen trie. michael@0: * They will crash when used on an unfrozen trie. michael@0: */ michael@0: michael@0: /** michael@0: * Return a 16-bit trie value from a code point, with range checking. michael@0: * Returns trie->errorValue if c is not in the range 0..U+10ffff. michael@0: * michael@0: * @param trie (const UTrie2 *, in) a frozen trie michael@0: * @param c (UChar32, in) the input code point michael@0: * @return (uint16_t) The code point's trie value. michael@0: */ michael@0: #define UTRIE2_GET16(trie, c) _UTRIE2_GET((trie), index, (trie)->indexLength, (c)) michael@0: michael@0: /** michael@0: * Return a 32-bit trie value from a code point, with range checking. michael@0: * Returns trie->errorValue if c is not in the range 0..U+10ffff. michael@0: * michael@0: * @param trie (const UTrie2 *, in) a frozen trie michael@0: * @param c (UChar32, in) the input code point michael@0: * @return (uint32_t) The code point's trie value. michael@0: */ michael@0: #define UTRIE2_GET32(trie, c) _UTRIE2_GET((trie), data32, 0, (c)) michael@0: michael@0: /** michael@0: * UTF-16: Get the next code point (UChar32 c, out), post-increment src, michael@0: * and get a 16-bit value from the trie. michael@0: * michael@0: * @param trie (const UTrie2 *, in) a frozen trie michael@0: * @param src (const UChar *, in/out) the source text pointer michael@0: * @param limit (const UChar *, in) the limit pointer for the text, or NULL if NUL-terminated michael@0: * @param c (UChar32, out) variable for the code point michael@0: * @param result (uint16_t, out) uint16_t variable for the trie lookup result michael@0: */ michael@0: #define UTRIE2_U16_NEXT16(trie, src, limit, c, result) _UTRIE2_U16_NEXT(trie, index, src, limit, c, result) michael@0: michael@0: /** michael@0: * UTF-16: Get the next code point (UChar32 c, out), post-increment src, michael@0: * and get a 32-bit value from the trie. michael@0: * michael@0: * @param trie (const UTrie2 *, in) a frozen trie michael@0: * @param src (const UChar *, in/out) the source text pointer michael@0: * @param limit (const UChar *, in) the limit pointer for the text, or NULL if NUL-terminated michael@0: * @param c (UChar32, out) variable for the code point michael@0: * @param result (uint32_t, out) uint32_t variable for the trie lookup result michael@0: */ michael@0: #define UTRIE2_U16_NEXT32(trie, src, limit, c, result) _UTRIE2_U16_NEXT(trie, data32, src, limit, c, result) michael@0: michael@0: /** michael@0: * UTF-16: Get the previous code point (UChar32 c, out), pre-decrement src, michael@0: * and get a 16-bit value from the trie. michael@0: * michael@0: * @param trie (const UTrie2 *, in) a frozen trie michael@0: * @param start (const UChar *, in) the start pointer for the text michael@0: * @param src (const UChar *, in/out) the source text pointer michael@0: * @param c (UChar32, out) variable for the code point michael@0: * @param result (uint16_t, out) uint16_t variable for the trie lookup result michael@0: */ michael@0: #define UTRIE2_U16_PREV16(trie, start, src, c, result) _UTRIE2_U16_PREV(trie, index, start, src, c, result) michael@0: michael@0: /** michael@0: * UTF-16: Get the previous code point (UChar32 c, out), pre-decrement src, michael@0: * and get a 32-bit value from the trie. michael@0: * michael@0: * @param trie (const UTrie2 *, in) a frozen trie michael@0: * @param start (const UChar *, in) the start pointer for the text michael@0: * @param src (const UChar *, in/out) the source text pointer michael@0: * @param c (UChar32, out) variable for the code point michael@0: * @param result (uint32_t, out) uint32_t variable for the trie lookup result michael@0: */ michael@0: #define UTRIE2_U16_PREV32(trie, start, src, c, result) _UTRIE2_U16_PREV(trie, data32, start, src, c, result) michael@0: michael@0: /** michael@0: * UTF-8: Post-increment src and get a 16-bit value from the trie. michael@0: * michael@0: * @param trie (const UTrie2 *, in) a frozen trie michael@0: * @param src (const char *, in/out) the source text pointer michael@0: * @param limit (const char *, in) the limit pointer for the text (must not be NULL) michael@0: * @param result (uint16_t, out) uint16_t variable for the trie lookup result michael@0: */ michael@0: #define UTRIE2_U8_NEXT16(trie, src, limit, result)\ michael@0: _UTRIE2_U8_NEXT(trie, data16, index, src, limit, result) michael@0: michael@0: /** michael@0: * UTF-8: Post-increment src and get a 32-bit value from the trie. michael@0: * michael@0: * @param trie (const UTrie2 *, in) a frozen trie michael@0: * @param src (const char *, in/out) the source text pointer michael@0: * @param limit (const char *, in) the limit pointer for the text (must not be NULL) michael@0: * @param result (uint16_t, out) uint32_t variable for the trie lookup result michael@0: */ michael@0: #define UTRIE2_U8_NEXT32(trie, src, limit, result) \ michael@0: _UTRIE2_U8_NEXT(trie, data32, data32, src, limit, result) michael@0: michael@0: /** michael@0: * UTF-8: Pre-decrement src and get a 16-bit value from the trie. michael@0: * michael@0: * @param trie (const UTrie2 *, in) a frozen trie michael@0: * @param start (const char *, in) the start pointer for the text michael@0: * @param src (const char *, in/out) the source text pointer michael@0: * @param result (uint16_t, out) uint16_t variable for the trie lookup result michael@0: */ michael@0: #define UTRIE2_U8_PREV16(trie, start, src, result) \ michael@0: _UTRIE2_U8_PREV(trie, data16, index, start, src, result) michael@0: michael@0: /** michael@0: * UTF-8: Pre-decrement src and get a 32-bit value from the trie. michael@0: * michael@0: * @param trie (const UTrie2 *, in) a frozen trie michael@0: * @param start (const char *, in) the start pointer for the text michael@0: * @param src (const char *, in/out) the source text pointer michael@0: * @param result (uint16_t, out) uint32_t variable for the trie lookup result michael@0: */ michael@0: #define UTRIE2_U8_PREV32(trie, start, src, result) \ michael@0: _UTRIE2_U8_PREV(trie, data32, data32, start, src, result) michael@0: michael@0: /* Public UTrie2 API: optimized UTF-16 access ------------------------------- */ michael@0: michael@0: /* michael@0: * The following functions and macros are used for highly optimized UTF-16 michael@0: * text processing. The UTRIE2_U16_NEXTxy() macros do not depend on these. michael@0: * michael@0: * A UTrie2 stores separate values for lead surrogate code _units_ vs. code _points_. michael@0: * UTF-16 text processing can be optimized by detecting surrogate pairs and michael@0: * assembling supplementary code points only when there is non-trivial data michael@0: * available. michael@0: * michael@0: * At build-time, use utrie2_enumForLeadSurrogate() to see if there michael@0: * is non-trivial (non-initialValue) data for any of the supplementary michael@0: * code points associated with a lead surrogate. michael@0: * If so, then set a special (application-specific) value for the michael@0: * lead surrogate code _unit_, with utrie2_set32ForLeadSurrogateCodeUnit(). michael@0: * michael@0: * At runtime, use UTRIE2_GET16_FROM_U16_SINGLE_LEAD() or michael@0: * UTRIE2_GET32_FROM_U16_SINGLE_LEAD() per code unit. If there is non-trivial michael@0: * data and the code unit is a lead surrogate, then check if a trail surrogate michael@0: * follows. If so, assemble the supplementary code point with michael@0: * U16_GET_SUPPLEMENTARY() and look up its value with UTRIE2_GET16_FROM_SUPP() michael@0: * or UTRIE2_GET32_FROM_SUPP(); otherwise reset the lead michael@0: * surrogate's value or do a code point lookup for it. michael@0: * michael@0: * If there is only trivial data for lead and trail surrogates, then processing michael@0: * can often skip them. For example, in normalization or case mapping michael@0: * all characters that do not have any mappings are simply copied as is. michael@0: */ michael@0: michael@0: /** michael@0: * Get a value from a lead surrogate code unit as stored in the trie. michael@0: * michael@0: * @param trie the trie michael@0: * @param c the code unit (U+D800..U+DBFF) michael@0: * @return the value michael@0: */ michael@0: U_CAPI uint32_t U_EXPORT2 michael@0: utrie2_get32FromLeadSurrogateCodeUnit(const UTrie2 *trie, UChar32 c); michael@0: michael@0: /** michael@0: * Enumerate the trie values for the 1024=0x400 code points michael@0: * corresponding to a given lead surrogate. michael@0: * For example, for the lead surrogate U+D87E it will enumerate the values michael@0: * for [U+2F800..U+2FC00[. michael@0: * Used by data builder code that sets special lead surrogate code unit values michael@0: * for optimized UTF-16 string processing. michael@0: * michael@0: * Do not modify the trie during the enumeration. michael@0: * michael@0: * Except for the limited code point range, this functions just like utrie2_enum(): michael@0: * For each entry in the trie, the value to be delivered is passed through michael@0: * the UTrie2EnumValue function. michael@0: * The value is unchanged if that function pointer is NULL. michael@0: * michael@0: * For each contiguous range of code points with a given (transformed) value, michael@0: * the UTrie2EnumRange function is called. michael@0: * michael@0: * @param trie a pointer to the trie michael@0: * @param enumValue a pointer to a function that may transform the trie entry value, michael@0: * or NULL if the values from the trie are to be used directly michael@0: * @param enumRange a pointer to a function that is called for each contiguous range michael@0: * of code points with the same (transformed) value michael@0: * @param context an opaque pointer that is passed on to the callback functions michael@0: */ michael@0: U_CAPI void U_EXPORT2 michael@0: utrie2_enumForLeadSurrogate(const UTrie2 *trie, UChar32 lead, michael@0: UTrie2EnumValue *enumValue, UTrie2EnumRange *enumRange, michael@0: const void *context); michael@0: michael@0: /** michael@0: * Set a value for a lead surrogate code unit. michael@0: * michael@0: * @param trie the unfrozen trie michael@0: * @param lead the lead surrogate code unit (U+D800..U+DBFF) michael@0: * @param value the value michael@0: * @param pErrorCode an in/out ICU UErrorCode; among other possible error codes: michael@0: * - U_NO_WRITE_PERMISSION if the trie is frozen michael@0: */ michael@0: U_CAPI void U_EXPORT2 michael@0: utrie2_set32ForLeadSurrogateCodeUnit(UTrie2 *trie, michael@0: UChar32 lead, uint32_t value, michael@0: UErrorCode *pErrorCode); michael@0: michael@0: /** michael@0: * Return a 16-bit trie value from a UTF-16 single/lead code unit (<=U+ffff). michael@0: * Same as UTRIE2_GET16() if c is a BMP code point except for lead surrogates, michael@0: * but smaller and faster. michael@0: * michael@0: * @param trie (const UTrie2 *, in) a frozen trie michael@0: * @param c (UChar32, in) the input code unit, must be 0<=c<=U+ffff michael@0: * @return (uint16_t) The code unit's trie value. michael@0: */ michael@0: #define UTRIE2_GET16_FROM_U16_SINGLE_LEAD(trie, c) _UTRIE2_GET_FROM_U16_SINGLE_LEAD((trie), index, c) michael@0: michael@0: /** michael@0: * Return a 32-bit trie value from a UTF-16 single/lead code unit (<=U+ffff). michael@0: * Same as UTRIE2_GET32() if c is a BMP code point except for lead surrogates, michael@0: * but smaller and faster. michael@0: * michael@0: * @param trie (const UTrie2 *, in) a frozen trie michael@0: * @param c (UChar32, in) the input code unit, must be 0<=c<=U+ffff michael@0: * @return (uint32_t) The code unit's trie value. michael@0: */ michael@0: #define UTRIE2_GET32_FROM_U16_SINGLE_LEAD(trie, c) _UTRIE2_GET_FROM_U16_SINGLE_LEAD((trie), data32, c) michael@0: michael@0: /** michael@0: * Return a 16-bit trie value from a supplementary code point (U+10000..U+10ffff). michael@0: * michael@0: * @param trie (const UTrie2 *, in) a frozen trie michael@0: * @param c (UChar32, in) the input code point, must be U+10000<=c<=U+10ffff michael@0: * @return (uint16_t) The code point's trie value. michael@0: */ michael@0: #define UTRIE2_GET16_FROM_SUPP(trie, c) _UTRIE2_GET_FROM_SUPP((trie), index, c) michael@0: michael@0: /** michael@0: * Return a 32-bit trie value from a supplementary code point (U+10000..U+10ffff). michael@0: * michael@0: * @param trie (const UTrie2 *, in) a frozen trie michael@0: * @param c (UChar32, in) the input code point, must be U+10000<=c<=U+10ffff michael@0: * @return (uint32_t) The code point's trie value. michael@0: */ michael@0: #define UTRIE2_GET32_FROM_SUPP(trie, c) _UTRIE2_GET_FROM_SUPP((trie), data32, c) michael@0: michael@0: U_CDECL_END michael@0: michael@0: /* C++ convenience wrappers ------------------------------------------------- */ michael@0: michael@0: #ifdef __cplusplus michael@0: michael@0: #include "unicode/utf.h" michael@0: #include "mutex.h" michael@0: michael@0: U_NAMESPACE_BEGIN michael@0: michael@0: // Use the Forward/Backward subclasses below. michael@0: class UTrie2StringIterator : public UMemory { michael@0: public: michael@0: UTrie2StringIterator(const UTrie2 *t, const UChar *p) : michael@0: trie(t), codePointStart(p), codePointLimit(p), codePoint(U_SENTINEL) {} michael@0: michael@0: const UTrie2 *trie; michael@0: const UChar *codePointStart, *codePointLimit; michael@0: UChar32 codePoint; michael@0: }; michael@0: michael@0: class BackwardUTrie2StringIterator : public UTrie2StringIterator { michael@0: public: michael@0: BackwardUTrie2StringIterator(const UTrie2 *t, const UChar *s, const UChar *p) : michael@0: UTrie2StringIterator(t, p), start(s) {} michael@0: michael@0: uint16_t previous16(); michael@0: michael@0: const UChar *start; michael@0: }; michael@0: michael@0: class ForwardUTrie2StringIterator : public UTrie2StringIterator { michael@0: public: michael@0: // Iteration limit l can be NULL. michael@0: // In that case, the caller must detect c==0 and stop. michael@0: ForwardUTrie2StringIterator(const UTrie2 *t, const UChar *p, const UChar *l) : michael@0: UTrie2StringIterator(t, p), limit(l) {} michael@0: michael@0: uint16_t next16(); michael@0: michael@0: const UChar *limit; michael@0: }; michael@0: michael@0: U_NAMESPACE_END michael@0: michael@0: #endif michael@0: michael@0: /* Internal definitions ----------------------------------------------------- */ michael@0: michael@0: U_CDECL_BEGIN michael@0: michael@0: /** Build-time trie structure. */ michael@0: struct UNewTrie2; michael@0: typedef struct UNewTrie2 UNewTrie2; michael@0: michael@0: /* michael@0: * Trie structure definition. michael@0: * michael@0: * Either the data table is 16 bits wide and accessed via the index michael@0: * pointer, with each index item increased by indexLength; michael@0: * in this case, data32==NULL, and data16 is used for direct ASCII access. michael@0: * michael@0: * Or the data table is 32 bits wide and accessed via the data32 pointer. michael@0: */ michael@0: struct UTrie2 { michael@0: /* protected: used by macros and functions for reading values */ michael@0: const uint16_t *index; michael@0: const uint16_t *data16; /* for fast UTF-8 ASCII access, if 16b data */ michael@0: const uint32_t *data32; /* NULL if 16b data is used via index */ michael@0: michael@0: int32_t indexLength, dataLength; michael@0: uint16_t index2NullOffset; /* 0xffff if there is no dedicated index-2 null block */ michael@0: uint16_t dataNullOffset; michael@0: uint32_t initialValue; michael@0: /** Value returned for out-of-range code points and illegal UTF-8. */ michael@0: uint32_t errorValue; michael@0: michael@0: /* Start of the last range which ends at U+10ffff, and its value. */ michael@0: UChar32 highStart; michael@0: int32_t highValueIndex; michael@0: michael@0: /* private: used by builder and unserialization functions */ michael@0: void *memory; /* serialized bytes; NULL if not frozen yet */ michael@0: int32_t length; /* number of serialized bytes at memory; 0 if not frozen yet */ michael@0: UBool isMemoryOwned; /* TRUE if the trie owns the memory */ michael@0: UBool padding1; michael@0: int16_t padding2; michael@0: UNewTrie2 *newTrie; /* builder object; NULL when frozen */ michael@0: }; michael@0: michael@0: /** michael@0: * Trie constants, defining shift widths, index array lengths, etc. michael@0: * michael@0: * These are needed for the runtime macros but users can treat these as michael@0: * implementation details and skip to the actual public API further below. michael@0: */ michael@0: enum { michael@0: /** Shift size for getting the index-1 table offset. */ michael@0: UTRIE2_SHIFT_1=6+5, michael@0: michael@0: /** Shift size for getting the index-2 table offset. */ michael@0: UTRIE2_SHIFT_2=5, michael@0: michael@0: /** michael@0: * Difference between the two shift sizes, michael@0: * for getting an index-1 offset from an index-2 offset. 6=11-5 michael@0: */ michael@0: UTRIE2_SHIFT_1_2=UTRIE2_SHIFT_1-UTRIE2_SHIFT_2, michael@0: michael@0: /** michael@0: * Number of index-1 entries for the BMP. 32=0x20 michael@0: * This part of the index-1 table is omitted from the serialized form. michael@0: */ michael@0: UTRIE2_OMITTED_BMP_INDEX_1_LENGTH=0x10000>>UTRIE2_SHIFT_1, michael@0: michael@0: /** Number of code points per index-1 table entry. 2048=0x800 */ michael@0: UTRIE2_CP_PER_INDEX_1_ENTRY=1<>UTRIE2_SHIFT_2. michael@0: */ michael@0: UTRIE2_INDEX_2_OFFSET=0, michael@0: michael@0: /** michael@0: * The part of the index-2 table for U+D800..U+DBFF stores values for michael@0: * lead surrogate code _units_ not code _points_. michael@0: * Values for lead surrogate code _points_ are indexed with this portion of the table. michael@0: * Length=32=0x20=0x400>>UTRIE2_SHIFT_2. (There are 1024=0x400 lead surrogates.) michael@0: */ michael@0: UTRIE2_LSCP_INDEX_2_OFFSET=0x10000>>UTRIE2_SHIFT_2, michael@0: UTRIE2_LSCP_INDEX_2_LENGTH=0x400>>UTRIE2_SHIFT_2, michael@0: michael@0: /** Count the lengths of both BMP pieces. 2080=0x820 */ michael@0: UTRIE2_INDEX_2_BMP_LENGTH=UTRIE2_LSCP_INDEX_2_OFFSET+UTRIE2_LSCP_INDEX_2_LENGTH, michael@0: michael@0: /** michael@0: * The 2-byte UTF-8 version of the index-2 table follows at offset 2080=0x820. michael@0: * Length 32=0x20 for lead bytes C0..DF, regardless of UTRIE2_SHIFT_2. michael@0: */ michael@0: UTRIE2_UTF8_2B_INDEX_2_OFFSET=UTRIE2_INDEX_2_BMP_LENGTH, michael@0: UTRIE2_UTF8_2B_INDEX_2_LENGTH=0x800>>6, /* U+0800 is the first code point after 2-byte UTF-8 */ michael@0: michael@0: /** michael@0: * The index-1 table, only used for supplementary code points, at offset 2112=0x840. michael@0: * Variable length, for code points up to highStart, where the last single-value range starts. michael@0: * Maximum length 512=0x200=0x100000>>UTRIE2_SHIFT_1. michael@0: * (For 0x100000 supplementary code points U+10000..U+10ffff.) michael@0: * michael@0: * The part of the index-2 table for supplementary code points starts michael@0: * after this index-1 table. michael@0: * michael@0: * Both the index-1 table and the following part of the index-2 table michael@0: * are omitted completely if there is only BMP data. michael@0: */ michael@0: UTRIE2_INDEX_1_OFFSET=UTRIE2_UTF8_2B_INDEX_2_OFFSET+UTRIE2_UTF8_2B_INDEX_2_LENGTH, michael@0: UTRIE2_MAX_INDEX_1_LENGTH=0x100000>>UTRIE2_SHIFT_1, michael@0: michael@0: /* michael@0: * Fixed layout of the first part of the data array. ----------------------- michael@0: * Starts with 4 blocks (128=0x80 entries) for ASCII. michael@0: */ michael@0: michael@0: /** michael@0: * The illegal-UTF-8 data block follows the ASCII block, at offset 128=0x80. michael@0: * Used with linear access for single bytes 0..0xbf for simple error handling. michael@0: * Length 64=0x40, not UTRIE2_DATA_BLOCK_LENGTH. michael@0: */ michael@0: UTRIE2_BAD_UTF8_DATA_OFFSET=0x80, michael@0: michael@0: /** The start of non-linear-ASCII data blocks, at offset 192=0xc0. */ michael@0: UTRIE2_DATA_START_OFFSET=0xc0 michael@0: }; michael@0: michael@0: /* Internal functions and macros -------------------------------------------- */ michael@0: michael@0: /** michael@0: * Internal function for part of the UTRIE2_U8_NEXTxx() macro implementations. michael@0: * Do not call directly. michael@0: * @internal michael@0: */ michael@0: U_INTERNAL int32_t U_EXPORT2 michael@0: utrie2_internalU8NextIndex(const UTrie2 *trie, UChar32 c, michael@0: const uint8_t *src, const uint8_t *limit); michael@0: michael@0: /** michael@0: * Internal function for part of the UTRIE2_U8_PREVxx() macro implementations. michael@0: * Do not call directly. michael@0: * @internal michael@0: */ michael@0: U_INTERNAL int32_t U_EXPORT2 michael@0: utrie2_internalU8PrevIndex(const UTrie2 *trie, UChar32 c, michael@0: const uint8_t *start, const uint8_t *src); michael@0: michael@0: michael@0: /** Internal low-level trie getter. Returns a data index. */ michael@0: #define _UTRIE2_INDEX_RAW(offset, trieIndex, c) \ michael@0: (((int32_t)((trieIndex)[(offset)+((c)>>UTRIE2_SHIFT_2)]) \ michael@0: <>UTRIE2_SHIFT_2), trieIndex, c) michael@0: michael@0: /** Internal trie getter from a BMP code point. Returns the data index. */ michael@0: #define _UTRIE2_INDEX_FROM_BMP(trieIndex, c) \ michael@0: _UTRIE2_INDEX_RAW(U_IS_LEAD(c) ? UTRIE2_LSCP_INDEX_2_OFFSET-(0xd800>>UTRIE2_SHIFT_2) : 0, \ michael@0: trieIndex, c) michael@0: michael@0: /** Internal trie getter from a supplementary code point below highStart. Returns the data index. */ michael@0: #define _UTRIE2_INDEX_FROM_SUPP(trieIndex, c) \ michael@0: (((int32_t)((trieIndex)[ \ michael@0: (trieIndex)[(UTRIE2_INDEX_1_OFFSET-UTRIE2_OMITTED_BMP_INDEX_1_LENGTH)+ \ michael@0: ((c)>>UTRIE2_SHIFT_1)]+ \ michael@0: (((c)>>UTRIE2_SHIFT_2)&UTRIE2_INDEX_2_MASK)]) \ michael@0: <index, c) : \ michael@0: (uint32_t)(c)<=0xffff ? \ michael@0: _UTRIE2_INDEX_RAW( \ michael@0: (c)<=0xdbff ? UTRIE2_LSCP_INDEX_2_OFFSET-(0xd800>>UTRIE2_SHIFT_2) : 0, \ michael@0: (trie)->index, c) : \ michael@0: (uint32_t)(c)>0x10ffff ? \ michael@0: (asciiOffset)+UTRIE2_BAD_UTF8_DATA_OFFSET : \ michael@0: (c)>=(trie)->highStart ? \ michael@0: (trie)->highValueIndex : \ michael@0: _UTRIE2_INDEX_FROM_SUPP((trie)->index, c)) michael@0: michael@0: /** Internal trie getter from a UTF-16 single/lead code unit. Returns the data. */ michael@0: #define _UTRIE2_GET_FROM_U16_SINGLE_LEAD(trie, data, c) \ michael@0: (trie)->data[_UTRIE2_INDEX_FROM_U16_SINGLE_LEAD((trie)->index, c)] michael@0: michael@0: /** Internal trie getter from a supplementary code point. Returns the data. */ michael@0: #define _UTRIE2_GET_FROM_SUPP(trie, data, c) \ michael@0: (trie)->data[(c)>=(trie)->highStart ? (trie)->highValueIndex : \ michael@0: _UTRIE2_INDEX_FROM_SUPP((trie)->index, c)] michael@0: michael@0: /** michael@0: * Internal trie getter from a code point, with checking that c is in 0..10FFFF. michael@0: * Returns the data. michael@0: */ michael@0: #define _UTRIE2_GET(trie, data, asciiOffset, c) \ michael@0: (trie)->data[_UTRIE2_INDEX_FROM_CP(trie, asciiOffset, c)] michael@0: michael@0: /** Internal next-post-increment: get the next code point (c) and its data. */ michael@0: #define _UTRIE2_U16_NEXT(trie, data, src, limit, c, result) { \ michael@0: { \ michael@0: uint16_t __c2; \ michael@0: (c)=*(src)++; \ michael@0: if(!U16_IS_LEAD(c)) { \ michael@0: (result)=_UTRIE2_GET_FROM_U16_SINGLE_LEAD(trie, data, c); \ michael@0: } else if((src)==(limit) || !U16_IS_TRAIL(__c2=*(src))) { \ michael@0: (result)=(trie)->data[_UTRIE2_INDEX_FROM_LSCP((trie)->index, c)]; \ michael@0: } else { \ michael@0: ++(src); \ michael@0: (c)=U16_GET_SUPPLEMENTARY((c), __c2); \ michael@0: (result)=_UTRIE2_GET_FROM_SUPP((trie), data, (c)); \ michael@0: } \ michael@0: } \ michael@0: } michael@0: michael@0: /** Internal pre-decrement-previous: get the previous code point (c) and its data */ michael@0: #define _UTRIE2_U16_PREV(trie, data, start, src, c, result) { \ michael@0: { \ michael@0: uint16_t __c2; \ michael@0: (c)=*--(src); \ michael@0: if(!U16_IS_TRAIL(c) || (src)==(start) || !U16_IS_LEAD(__c2=*((src)-1))) { \ michael@0: (result)=(trie)->data[_UTRIE2_INDEX_FROM_BMP((trie)->index, c)]; \ michael@0: } else { \ michael@0: --(src); \ michael@0: (c)=U16_GET_SUPPLEMENTARY(__c2, (c)); \ michael@0: (result)=_UTRIE2_GET_FROM_SUPP((trie), data, (c)); \ michael@0: } \ michael@0: } \ michael@0: } michael@0: michael@0: /** Internal UTF-8 next-post-increment: get the next code point's data. */ michael@0: #define _UTRIE2_U8_NEXT(trie, ascii, data, src, limit, result) { \ michael@0: uint8_t __lead=(uint8_t)*(src)++; \ michael@0: if(__lead<0xc0) { \ michael@0: (result)=(trie)->ascii[__lead]; \ michael@0: } else { \ michael@0: uint8_t __t1, __t2; \ michael@0: if( /* handle U+0000..U+07FF inline */ \ michael@0: __lead<0xe0 && (src)<(limit) && \ michael@0: (__t1=(uint8_t)(*(src)-0x80))<=0x3f \ michael@0: ) { \ michael@0: ++(src); \ michael@0: (result)=(trie)->data[ \ michael@0: (trie)->index[(UTRIE2_UTF8_2B_INDEX_2_OFFSET-0xc0)+__lead]+ \ michael@0: __t1]; \ michael@0: } else if( /* handle U+0000..U+CFFF inline */ \ michael@0: __lead<0xed && ((src)+1)<(limit) && \ michael@0: (__t1=(uint8_t)(*(src)-0x80))<=0x3f && (__lead>0xe0 || __t1>=0x20) && \ michael@0: (__t2=(uint8_t)(*((src)+1)-0x80))<= 0x3f \ michael@0: ) { \ michael@0: (src)+=2; \ michael@0: (result)=(trie)->data[ \ michael@0: ((int32_t)((trie)->index[((__lead-0xe0)<<(12-UTRIE2_SHIFT_2))+ \ michael@0: (__t1<<(6-UTRIE2_SHIFT_2))+(__t2>>UTRIE2_SHIFT_2)]) \ michael@0: <data[__index>>3]; \ michael@0: } \ michael@0: } \ michael@0: } michael@0: michael@0: /** Internal UTF-8 pre-decrement-previous: get the previous code point's data. */ michael@0: #define _UTRIE2_U8_PREV(trie, ascii, data, start, src, result) { \ michael@0: uint8_t __b=(uint8_t)*--(src); \ michael@0: if(__b<0x80) { \ michael@0: (result)=(trie)->ascii[__b]; \ michael@0: } else { \ michael@0: int32_t __index=utrie2_internalU8PrevIndex((trie), __b, (const uint8_t *)(start), \ michael@0: (const uint8_t *)(src)); \ michael@0: (src)-=__index&7; \ michael@0: (result)=(trie)->data[__index>>3]; \ michael@0: } \ michael@0: } michael@0: michael@0: U_CDECL_END michael@0: michael@0: /** michael@0: * Work around MSVC 2003 optimization bugs. michael@0: */ michael@0: #if defined (U_HAVE_MSVC_2003_OR_EARLIER) michael@0: #pragma optimize("", off) michael@0: #endif michael@0: michael@0: #endif