/*

******************************************************************************

*

*   Copyright (C) 2001-2005, International Business Machines

*   Corporation and others.  All Rights Reserved.

*

******************************************************************************

*   file name:  utrie.h

*   encoding:   US-ASCII

*   tab size:   8 (not used)

*   indentation:4

*

*   created on: 2001nov08

*   created by: Markus W. Scherer

*/

#ifndef __UTRIE_H__

#define __UTRIE_H__

#include "unicode/utypes.h"

#include "udataswp.h"

U_CDECL_BEGIN

/**

 * \file

 *

 * This is a common implementation of a "folded" trie.

 * It is a kind of compressed, serializable table of 16- or 32-bit values associated with

 * Unicode code points (0..0x10ffff).

 *

 * This implementation is optimized for getting values while walking forward

 * through a UTF-16 string.

 * Therefore, the simplest and fastest access macros are the

 * _FROM_LEAD() and _FROM_OFFSET_TRAIL() macros.

 *

 * The _FROM_BMP() macros are a little more complicated; they get values

 * even for lead surrogate code _points_, while the _FROM_LEAD() macros

 * get special "folded" values for lead surrogate code _units_ if

 * there is relevant data associated with them.

 * From such a folded value, an offset needs to be extracted to supply

 * to the _FROM_OFFSET_TRAIL() macros.

 *

 * Most of the more complex (and more convenient) functions/macros call a callback function

 * to get that offset from the folded value for a lead surrogate unit.

 */

/**

 * Trie constants, defining shift widths, index array lengths, etc.

 */

enum {

    /** Shift size for shifting right the input index. 1..9 */

    UTRIE_SHIFT=5,

    /** Number of data values in a stage 2 (data array) block. 2, 4, 8, .., 0x200 */

    UTRIE_DATA_BLOCK_LENGTH=1<<UTRIE_SHIFT,

    /** Mask for getting the lower bits from the input index. */

    UTRIE_MASK=UTRIE_DATA_BLOCK_LENGTH-1,

    /**

     * Lead surrogate code points' index displacement in the index array.

     * 0x10000-0xd800=0x2800

     */

    UTRIE_LEAD_INDEX_DISP=0x2800>>UTRIE_SHIFT,

    /**

     * Shift size for shifting left the index array values.

     * Increases possible data size with 16-bit index values at the cost

     * of compactability.

     * This requires blocks of stage 2 data to be aligned by UTRIE_DATA_GRANULARITY.

     * 0..UTRIE_SHIFT

     */

    UTRIE_INDEX_SHIFT=2,

    /** The alignment size of a stage 2 data block. Also the granularity for compaction. */

    UTRIE_DATA_GRANULARITY=1<<UTRIE_INDEX_SHIFT,

    /** Number of bits of a trail surrogate that are used in index table lookups. */

    UTRIE_SURROGATE_BLOCK_BITS=10-UTRIE_SHIFT,

    /**

     * Number of index (stage 1) entries per lead surrogate.

     * Same as number of index entries for 1024 trail surrogates,

     * ==0x400>>UTRIE_SHIFT

     */

    UTRIE_SURROGATE_BLOCK_COUNT=(1<<UTRIE_SURROGATE_BLOCK_BITS),

    /** Length of the BMP portion of the index (stage 1) array. */

    UTRIE_BMP_INDEX_LENGTH=0x10000>>UTRIE_SHIFT

};

/**

 * Length of the index (stage 1) array before folding.

 * Maximum number of Unicode code points (0x110000) shifted right by UTRIE_SHIFT.

 */

#define UTRIE_MAX_INDEX_LENGTH (0x110000>>UTRIE_SHIFT)

/**

 * Maximum length of the runtime data (stage 2) array.

 * Limited by 16-bit index values that are left-shifted by UTRIE_INDEX_SHIFT.

 */

#define UTRIE_MAX_DATA_LENGTH (0x10000<<UTRIE_INDEX_SHIFT)

/**

 * Maximum length of the build-time data (stage 2) array.

 * The maximum length is 0x110000+UTRIE_DATA_BLOCK_LENGTH+0x400.

 * (Number of Unicode code points + one all-initial-value block +

 *  possible duplicate entries for 1024 lead surrogates.)

 */

#define UTRIE_MAX_BUILD_TIME_DATA_LENGTH (0x110000+UTRIE_DATA_BLOCK_LENGTH+0x400)

/**

 * Number of bytes for a dummy trie.

 * A dummy trie is an empty runtime trie, used when a real data trie cannot

 * be loaded.

 * The number of bytes works for Latin-1-linear tries with 32-bit data

 * (worst case).

 *

 * Calculation:

 *   BMP index + 1 index block for lead surrogate code points +

 *   Latin-1-linear array + 1 data block for lead surrogate code points

 *

 * Latin-1: if(UTRIE_SHIFT<=8) { 256 } else { included in first data block }

 *

 * @see utrie_unserializeDummy

 */

#define UTRIE_DUMMY_SIZE ((UTRIE_BMP_INDEX_LENGTH+UTRIE_SURROGATE_BLOCK_COUNT)*2+(UTRIE_SHIFT<=8?256:UTRIE_DATA_BLOCK_LENGTH)*4+UTRIE_DATA_BLOCK_LENGTH*4)

/**

 * Runtime UTrie callback function.

 * Extract from a lead surrogate's data the

 * index array offset of the indexes for that lead surrogate.

 *

 * @param data data value for a surrogate from the trie, including the folding offset

 * @return offset>=UTRIE_BMP_INDEX_LENGTH, or 0 if there is no data for the lead surrogate

 */

typedef int32_t U_CALLCONV

UTrieGetFoldingOffset(uint32_t data);

/**

 * Run-time Trie structure.

 *

 * Either the data table is 16 bits wide and accessed via the index

 * pointer, with each index item increased by indexLength;

 * in this case, data32==NULL.

 *

 * Or the data table is 32 bits wide and accessed via the data32 pointer.

 */

struct UTrie {

    const uint16_t *index;

    const uint32_t *data32; /* NULL if 16b data is used via index */

    /**

     * This function is not used in _FROM_LEAD, _FROM_BMP, and _FROM_OFFSET_TRAIL macros.

     * If convenience macros like _GET16 or _NEXT32 are used, this function must be set.

     *

     * utrie_unserialize() sets a default function which simply returns

     * the lead surrogate's value itself - which is the inverse of the default

     * folding function used by utrie_serialize().

     *

     * @see UTrieGetFoldingOffset

     */

    UTrieGetFoldingOffset *getFoldingOffset;

    int32_t indexLength, dataLength;

    uint32_t initialValue;

    UBool isLatin1Linear;

};

typedef struct UTrie UTrie;

/** Internal trie getter from an offset (0 if c16 is a BMP/lead units) and a 16-bit unit */

#define _UTRIE_GET_RAW(trie, data, offset, c16) \

    (trie)->data[ \

        ((int32_t)((trie)->index[(offset)+((c16)>>UTRIE_SHIFT)])<<UTRIE_INDEX_SHIFT)+ \

        ((c16)&UTRIE_MASK) \

    ]

/** Internal trie getter from a pair of surrogates */

#define _UTRIE_GET_FROM_PAIR(trie, data, c, c2, result, resultType) { \

    int32_t __offset; \

\

    /* get data for lead surrogate */ \

    (result)=_UTRIE_GET_RAW((trie), data, 0, (c)); \

    __offset=(trie)->getFoldingOffset(result); \

\

    /* get the real data from the folded lead/trail units */ \

    if(__offset>0) { \

        (result)=_UTRIE_GET_RAW((trie), data, __offset, (c2)&0x3ff); \

    } else { \

        (result)=(resultType)((trie)->initialValue); \

    } \

}

/** Internal trie getter from a BMP code point, treating a lead surrogate as a normal code point */

#define _UTRIE_GET_FROM_BMP(trie, data, c16) \

    _UTRIE_GET_RAW(trie, data, 0xd800<=(c16) && (c16)<=0xdbff ? UTRIE_LEAD_INDEX_DISP : 0, c16);

/**

 * Internal trie getter from a code point.

 * Could be faster(?) but longer with

 *   if((c32)<=0xd7ff) { (result)=_UTRIE_GET_RAW(trie, data, 0, c32); }

 */

#define _UTRIE_GET(trie, data, c32, result, resultType) \

    if((uint32_t)(c32)<=0xffff) { \

        /* BMP code points */ \

        (result)=_UTRIE_GET_FROM_BMP(trie, data, c32); \

    } else if((uint32_t)(c32)<=0x10ffff) { \

        /* supplementary code point */ \

        UChar __lead16=UTF16_LEAD(c32); \

        _UTRIE_GET_FROM_PAIR(trie, data, __lead16, c32, result, resultType); \

    } else { \

        /* out of range */ \

        (result)=(resultType)((trie)->initialValue); \

    }

/** Internal next-post-increment: get the next code point (c, c2) and its data */

#define _UTRIE_NEXT(trie, data, src, limit, c, c2, result, resultType) { \

    (c)=*(src)++; \

    if(!UTF_IS_LEAD(c)) { \

        (c2)=0; \

        (result)=_UTRIE_GET_RAW((trie), data, 0, (c)); \

    } else if((src)!=(limit) && UTF_IS_TRAIL((c2)=*(src))) { \

        ++(src); \

        _UTRIE_GET_FROM_PAIR((trie), data, (c), (c2), (result), resultType); \

    } else { \

        /* unpaired lead surrogate code point */ \

        (c2)=0; \

        (result)=_UTRIE_GET_RAW((trie), data, UTRIE_LEAD_INDEX_DISP, (c)); \

    } \

}

/** Internal previous: get the previous code point (c, c2) and its data */

#define _UTRIE_PREVIOUS(trie, data, start, src, c, c2, result, resultType) { \

    (c)=*--(src); \

    if(!UTF_IS_SURROGATE(c)) { \

        (c2)=0; \

        (result)=_UTRIE_GET_RAW((trie), data, 0, (c)); \

    } else if(!UTF_IS_SURROGATE_FIRST(c)) { \

        /* trail surrogate */ \

        if((start)!=(src) && UTF_IS_LEAD((c2)=*((src)-1))) { \

            --(src); \

            (result)=(c); (c)=(c2); (c2)=(UChar)(result); /* swap c, c2 */ \

            _UTRIE_GET_FROM_PAIR((trie), data, (c), (c2), (result), resultType); \

        } else { \

            /* unpaired trail surrogate code point */ \

            (c2)=0; \

            (result)=_UTRIE_GET_RAW((trie), data, 0, (c)); \

        } \

    } else { \

        /* unpaired lead surrogate code point */ \

        (c2)=0; \

        (result)=_UTRIE_GET_RAW((trie), data, UTRIE_LEAD_INDEX_DISP, (c)); \

    } \

}

/* Public UTrie API ---------------------------------------------------------*/

/**

 * Get a pointer to the contiguous part of the data array

 * for the Latin-1 range (U+0000..U+00ff).

 * Must be used only if the Latin-1 range is in fact linear

 * (trie->isLatin1Linear).

 *

 * @param trie (const UTrie *, in) a pointer to the runtime trie structure

 * @return (const uint16_t *) pointer to values for Latin-1 code points

 */

#define UTRIE_GET16_LATIN1(trie) ((trie)->index+(trie)->indexLength+UTRIE_DATA_BLOCK_LENGTH)

/**

 * Get a pointer to the contiguous part of the data array

 * for the Latin-1 range (U+0000..U+00ff).

 * Must be used only if the Latin-1 range is in fact linear

 * (trie->isLatin1Linear).

 *

 * @param trie (const UTrie *, in) a pointer to the runtime trie structure

 * @return (const uint32_t *) pointer to values for Latin-1 code points

 */

#define UTRIE_GET32_LATIN1(trie) ((trie)->data32+UTRIE_DATA_BLOCK_LENGTH)

/**

 * Get a 16-bit trie value from a BMP code point (UChar, <=U+ffff).

 * c16 may be a lead surrogate, which may have a value including a folding offset.

 *

 * @param trie (const UTrie *, in) a pointer to the runtime trie structure

 * @param c16 (UChar, in) the input BMP code point

 * @return (uint16_t) trie lookup result

 */

#define UTRIE_GET16_FROM_LEAD(trie, c16) _UTRIE_GET_RAW(trie, index, 0, c16)

/**

 * Get a 32-bit trie value from a BMP code point (UChar, <=U+ffff).

 * c16 may be a lead surrogate, which may have a value including a folding offset.

 *

 * @param trie (const UTrie *, in) a pointer to the runtime trie structure

 * @param c16 (UChar, in) the input BMP code point

 * @return (uint32_t) trie lookup result

 */

#define UTRIE_GET32_FROM_LEAD(trie, c16) _UTRIE_GET_RAW(trie, data32, 0, c16)

/**

 * Get a 16-bit trie value from a BMP code point (UChar, <=U+ffff).

 * Even lead surrogate code points are treated as normal code points,

 * with unfolded values that may differ from _FROM_LEAD() macro results for them.

 *

 * @param trie (const UTrie *, in) a pointer to the runtime trie structure

 * @param c16 (UChar, in) the input BMP code point

 * @return (uint16_t) trie lookup result

 */

#define UTRIE_GET16_FROM_BMP(trie, c16) _UTRIE_GET_FROM_BMP(trie, index, c16)

/**

 * Get a 32-bit trie value from a BMP code point (UChar, <=U+ffff).

 * Even lead surrogate code points are treated as normal code points,

 * with unfolded values that may differ from _FROM_LEAD() macro results for them.

 *

 * @param trie (const UTrie *, in) a pointer to the runtime trie structure

 * @param c16 (UChar, in) the input BMP code point

 * @return (uint32_t) trie lookup result

 */

#define UTRIE_GET32_FROM_BMP(trie, c16) _UTRIE_GET_FROM_BMP(trie, data32, c16)

/**

 * Get a 16-bit trie value from a code point.

 * Even lead surrogate code points are treated as normal code points,

 * with unfolded values that may differ from _FROM_LEAD() macro results for them.

 *

 * @param trie (const UTrie *, in) a pointer to the runtime trie structure

 * @param c32 (UChar32, in) the input code point

 * @param result (uint16_t, out) uint16_t variable for the trie lookup result

 */

#define UTRIE_GET16(trie, c32, result) _UTRIE_GET(trie, index, c32, result, uint16_t)

/**

 * Get a 32-bit trie value from a code point.

 * Even lead surrogate code points are treated as normal code points,

 * with unfolded values that may differ from _FROM_LEAD() macro results for them.

 *

 * @param trie (const UTrie *, in) a pointer to the runtime trie structure

 * @param c32 (UChar32, in) the input code point

 * @param result (uint32_t, out) uint32_t variable for the trie lookup result

 */

#define UTRIE_GET32(trie, c32, result) _UTRIE_GET(trie, data32, c32, result, uint32_t)

/**

 * Get the next code point (c, c2), post-increment src,

 * and get a 16-bit value from the trie.

 *

 * @param trie (const UTrie *, in) a pointer to the runtime trie structure

 * @param src (const UChar *, in/out) the source text pointer

 * @param limit (const UChar *, in) the limit pointer for the text, or NULL

 * @param c (UChar, out) variable for the BMP or lead code unit

 * @param c2 (UChar, out) variable for 0 or the trail code unit

 * @param result (uint16_t, out) uint16_t variable for the trie lookup result

 */

#define UTRIE_NEXT16(trie, src, limit, c, c2, result) _UTRIE_NEXT(trie, index, src, limit, c, c2, result, uint16_t)

/**

 * Get the next code point (c, c2), post-increment src,

 * and get a 32-bit value from the trie.

 *

 * @param trie (const UTrie *, in) a pointer to the runtime trie structure

 * @param src (const UChar *, in/out) the source text pointer

 * @param limit (const UChar *, in) the limit pointer for the text, or NULL

 * @param c (UChar, out) variable for the BMP or lead code unit

 * @param c2 (UChar, out) variable for 0 or the trail code unit

 * @param result (uint32_t, out) uint32_t variable for the trie lookup result

 */

#define UTRIE_NEXT32(trie, src, limit, c, c2, result) _UTRIE_NEXT(trie, data32, src, limit, c, c2, result, uint32_t)

/**

 * Get the previous code point (c, c2), pre-decrement src,

 * and get a 16-bit value from the trie.

 *

 * @param trie (const UTrie *, in) a pointer to the runtime trie structure

 * @param start (const UChar *, in) the start pointer for the text, or NULL

 * @param src (const UChar *, in/out) the source text pointer

 * @param c (UChar, out) variable for the BMP or lead code unit

 * @param c2 (UChar, out) variable for 0 or the trail code unit

 * @param result (uint16_t, out) uint16_t variable for the trie lookup result

 */

#define UTRIE_PREVIOUS16(trie, start, src, c, c2, result) _UTRIE_PREVIOUS(trie, index, start, src, c, c2, result, uint16_t)

/**

 * Get the previous code point (c, c2), pre-decrement src,

 * and get a 32-bit value from the trie.

 *

 * @param trie (const UTrie *, in) a pointer to the runtime trie structure

 * @param start (const UChar *, in) the start pointer for the text, or NULL

 * @param src (const UChar *, in/out) the source text pointer

 * @param c (UChar, out) variable for the BMP or lead code unit

 * @param c2 (UChar, out) variable for 0 or the trail code unit

 * @param result (uint32_t, out) uint32_t variable for the trie lookup result

 */

#define UTRIE_PREVIOUS32(trie, start, src, c, c2, result) _UTRIE_PREVIOUS(trie, data32, start, src, c, c2, result, uint32_t)

/**

 * Get a 16-bit trie value from a pair of surrogates.

 *

 * @param trie (const UTrie *, in) a pointer to the runtime trie structure

 * @param c (UChar, in) a lead surrogate

 * @param c2 (UChar, in) a trail surrogate

 * @param result (uint16_t, out) uint16_t variable for the trie lookup result

 */

#define UTRIE_GET16_FROM_PAIR(trie, c, c2, result) _UTRIE_GET_FROM_PAIR(trie, index, c, c2, result, uint16_t)

/**

 * Get a 32-bit trie value from a pair of surrogates.

 *

 * @param trie (const UTrie *, in) a pointer to the runtime trie structure

 * @param c (UChar, in) a lead surrogate

 * @param c2 (UChar, in) a trail surrogate

 * @param result (uint32_t, out) uint32_t variable for the trie lookup result

 */

#define UTRIE_GET32_FROM_PAIR(trie, c, c2, result) _UTRIE_GET_FROM_PAIR(trie, data32, c, c2, result, uint32_t)

/**

 * Get a 16-bit trie value from a folding offset (from the value of a lead surrogate)

 * and a trail surrogate.

 *

 * @param trie (const UTrie *, in) a pointer to the runtime trie structure

 * @param offset (int32_t, in) the folding offset from the value of a lead surrogate

 * @param c2 (UChar, in) a trail surrogate (only the 10 low bits are significant)

 * @return (uint16_t) trie lookup result

 */

#define UTRIE_GET16_FROM_OFFSET_TRAIL(trie, offset, c2) _UTRIE_GET_RAW(trie, index, offset, (c2)&0x3ff)

/**

 * Get a 32-bit trie value from a folding offset (from the value of a lead surrogate)

 * and a trail surrogate.

 *

 * @param trie (const UTrie *, in) a pointer to the runtime trie structure

 * @param offset (int32_t, in) the folding offset from the value of a lead surrogate

 * @param c2 (UChar, in) a trail surrogate (only the 10 low bits are significant)

 * @return (uint32_t) trie lookup result

 */

#define UTRIE_GET32_FROM_OFFSET_TRAIL(trie, offset, c2) _UTRIE_GET_RAW(trie, data32, offset, (c2)&0x3ff)

/* enumeration callback types */

/**

 * Callback from utrie_enum(), extracts a uint32_t value from a

 * trie value. This value will be passed on to the UTrieEnumRange function.

 *

 * @param context an opaque pointer, as passed into utrie_enum()

 * @param value a value from the trie

 * @return the value that is to be passed on to the UTrieEnumRange function

 */

typedef uint32_t U_CALLCONV

UTrieEnumValue(const void *context, uint32_t value);

/**

 * Callback from utrie_enum(), is called for each contiguous range

 * of code points with the same value as retrieved from the trie and

 * transformed by the UTrieEnumValue function.

 *

 * The callback function can stop the enumeration by returning FALSE.

 *

 * @param context an opaque pointer, as passed into utrie_enum()

 * @param start the first code point in a contiguous range with value

 * @param limit one past the last code point in a contiguous range with value

 * @param value the value that is set for all code points in [start..limit[

 * @return FALSE to stop the enumeration

 */

typedef UBool U_CALLCONV

UTrieEnumRange(const void *context, UChar32 start, UChar32 limit, uint32_t value);

/**

 * Enumerate efficiently all values in a trie.

 * For each entry in the trie, the value to be delivered is passed through

 * the UTrieEnumValue function.

 * The value is unchanged if that function pointer is NULL.

 *

 * For each contiguous range of code points with a given value,

 * the UTrieEnumRange function is called.

 *

 * @param trie a pointer to the runtime trie structure

 * @param enumValue a pointer to a function that may transform the trie entry value,

 *                  or NULL if the values from the trie are to be used directly

 * @param enumRange a pointer to a function that is called for each contiguous range

 *                  of code points with the same value

 * @param context an opaque pointer that is passed on to the callback functions

 */

U_CAPI void U_EXPORT2

utrie_enum(const UTrie *trie,

           UTrieEnumValue *enumValue, UTrieEnumRange *enumRange, const void *context);

/**

 * Unserialize a trie from 32-bit-aligned memory.

 * Inverse of utrie_serialize().

 * Fills the UTrie runtime trie structure with the settings for the trie data.

 *

 * @param trie a pointer to the runtime trie structure

 * @param data a pointer to 32-bit-aligned memory containing trie data

 * @param length the number of bytes available at data

 * @param pErrorCode an in/out ICU UErrorCode

 * @return the number of bytes at data taken up by the trie data

 */

U_CAPI int32_t U_EXPORT2

utrie_unserialize(UTrie *trie, const void *data, int32_t length, UErrorCode *pErrorCode);

/**

 * "Unserialize" a dummy trie.

 * A dummy trie is an empty runtime trie, used when a real data trie cannot

 * be loaded.

 *

 * The input memory is filled so that the trie always returns the initialValue,

 * or the leadUnitValue for lead surrogate code points.

 * The Latin-1 part is always set up to be linear.

 *

 * @param trie a pointer to the runtime trie structure

 * @param data a pointer to 32-bit-aligned memory to be filled with the dummy trie data

 * @param length the number of bytes available at data (recommended to use UTRIE_DUMMY_SIZE)

 * @param initialValue the initial value that is set for all code points

 * @param leadUnitValue the value for lead surrogate code _units_ that do not

 *                      have associated supplementary data

 * @param pErrorCode an in/out ICU UErrorCode

 *

 * @see UTRIE_DUMMY_SIZE

 * @see utrie_open

 */

U_CAPI int32_t U_EXPORT2

utrie_unserializeDummy(UTrie *trie,

                       void *data, int32_t length,

                       uint32_t initialValue, uint32_t leadUnitValue,

                       UBool make16BitTrie,

                       UErrorCode *pErrorCode);