| /* | |
| ****************************************************************************** | |
| * | |
| * Copyright (C) 2001-2008, International Business Machines | |
| * Corporation and others. All Rights Reserved. | |
| * | |
| ****************************************************************************** | |
| * file name: utrie2_impl.h | |
| * encoding: US-ASCII | |
| * tab size: 8 (not used) | |
| * indentation:4 | |
| * | |
| * created on: 2008sep26 (split off from utrie2.c) | |
| * created by: Markus W. Scherer | |
| * | |
| * Definitions needed for both runtime and builder code for UTrie2, | |
| * used by utrie2.c and utrie2_builder.c. | |
| */ | |
| #ifndef __UTRIE2_IMPL_H__ | |
| #define __UTRIE2_IMPL_H__ | |
| #include "utrie2.h" | |
| /* Public UTrie2 API implementation ----------------------------------------- */ | |
| /* | |
| * These definitions are mostly needed by utrie2.c, | |
| * but also by utrie2_serialize() and utrie2_swap(). | |
| */ | |
| /* | |
| * UTrie and UTrie2 signature values, | |
| * in platform endianness and opposite endianness. | |
| */ | |
| #define UTRIE_SIG 0x54726965 | |
| #define UTRIE_OE_SIG 0x65697254 | |
| #define UTRIE2_SIG 0x54726932 | |
| #define UTRIE2_OE_SIG 0x32697254 | |
| /** | |
| * Trie data structure in serialized form: | |
| * | |
| * UTrie2Header header; | |
| * uint16_t index[header.index2Length]; | |
| * uint16_t data[header.shiftedDataLength<<2]; -- or uint32_t data[...] | |
| * @internal | |
| */ | |
| typedef struct UTrie2Header { | |
| /** "Tri2" in big-endian US-ASCII (0x54726932) */ | |
| uint32_t signature; | |
| /** | |
| * options bit field: | |
| * 15.. 4 reserved (0) | |
| * 3.. 0 UTrie2ValueBits valueBits | |
| */ | |
| uint16_t options; | |
| /** UTRIE2_INDEX_1_OFFSET..UTRIE2_MAX_INDEX_LENGTH */ | |
| uint16_t indexLength; | |
| /** (UTRIE2_DATA_START_OFFSET..UTRIE2_MAX_DATA_LENGTH)>>UTRIE2_INDEX_SHIFT */ | |
| uint16_t shiftedDataLength; | |
| /** Null index and data blocks, not shifted. */ | |
| uint16_t index2NullOffset, dataNullOffset; | |
| /** | |
| * First code point of the single-value range ending with U+10ffff, | |
| * rounded up and then shifted right by UTRIE2_SHIFT_1. | |
| */ | |
| uint16_t shiftedHighStart; | |
| } UTrie2Header; | |
| /** | |
| * Constants for use with UTrie2Header.options. | |
| * @internal | |
| */ | |
| enum { | |
| /** Mask to get the UTrie2ValueBits valueBits from options. */ | |
| UTRIE2_OPTIONS_VALUE_BITS_MASK=0xf | |
| }; | |
| /* Building a trie ---------------------------------------------------------- */ | |
| /* | |
| * These definitions are mostly needed by utrie2_builder.c, but also by | |
| * utrie2_get32() and utrie2_enum(). | |
| */ | |
| enum { | |
| /** | |
| * At build time, leave a gap in the index-2 table, | |
| * at least as long as the maximum lengths of the 2-byte UTF-8 index-2 table | |
| * and the supplementary index-1 table. | |
| * Round up to UTRIE2_INDEX_2_BLOCK_LENGTH for proper compacting. | |
| */ | |
| UNEWTRIE2_INDEX_GAP_OFFSET=UTRIE2_INDEX_2_BMP_LENGTH, | |
| UNEWTRIE2_INDEX_GAP_LENGTH= | |
| ((UTRIE2_UTF8_2B_INDEX_2_LENGTH+UTRIE2_MAX_INDEX_1_LENGTH)+UTRIE2_INDEX_2_MASK)& | |
| ~UTRIE2_INDEX_2_MASK, | |
| /** | |
| * Maximum length of the build-time index-2 array. | |
| * Maximum number of Unicode code points (0x110000) shifted right by UTRIE2_SHIFT_2, | |
| * plus the part of the index-2 table for lead surrogate code points, | |
| * plus the build-time index gap, | |
| * plus the null index-2 block. | |
| */ | |
| UNEWTRIE2_MAX_INDEX_2_LENGTH= | |
| (0x110000>>UTRIE2_SHIFT_2)+ | |
| UTRIE2_LSCP_INDEX_2_LENGTH+ | |
| UNEWTRIE2_INDEX_GAP_LENGTH+ | |
| UTRIE2_INDEX_2_BLOCK_LENGTH, | |
| UNEWTRIE2_INDEX_1_LENGTH=0x110000>>UTRIE2_SHIFT_1 | |
| }; | |
| /** | |
| * Maximum length of the build-time data array. | |
| * One entry per 0x110000 code points, plus the illegal-UTF-8 block and the null block, | |
| * plus values for the 0x400 surrogate code units. | |
| */ | |
| #define UNEWTRIE2_MAX_DATA_LENGTH (0x110000+0x40+0x40+0x400) | |
| /* | |
| * Build-time trie structure. | |
| * | |
| * Just using a boolean flag for "repeat use" could lead to data array overflow | |
| * because we would not be able to detect when a data block becomes unused. | |
| * It also leads to orphan data blocks that are kept through serialization. | |
| * | |
| * Need to use reference counting for data blocks, | |
| * and allocDataBlock() needs to look for a free block before increasing dataLength. | |
| * | |
| * This scheme seems like overkill for index-2 blocks since the whole index array is | |
| * preallocated anyway (unlike the growable data array). | |
| * Just allocating multiple index-2 blocks as needed. | |
| */ | |
| struct UNewTrie2 { | |
| int32_t index1[UNEWTRIE2_INDEX_1_LENGTH]; | |
| int32_t index2[UNEWTRIE2_MAX_INDEX_2_LENGTH]; | |
| uint32_t *data; | |
| uint32_t initialValue, errorValue; | |
| int32_t index2Length, dataCapacity, dataLength; | |
| int32_t firstFreeBlock; | |
| int32_t index2NullOffset, dataNullOffset; | |
| UChar32 highStart; | |
| UBool isCompacted; | |
| /** | |
| * Multi-purpose per-data-block table. | |
| * | |
| * Before compacting: | |
| * | |
| * Per-data-block reference counters/free-block list. | |
| * 0: unused | |
| * >0: reference counter (number of index-2 entries pointing here) | |
| * <0: next free data block in free-block list | |
| * | |
| * While compacting: | |
| * | |
| * Map of adjusted indexes, used in compactData() and compactIndex2(). | |
| * Maps from original indexes to new ones. | |
| */ | |
| int32_t map[UNEWTRIE2_MAX_DATA_LENGTH>>UTRIE2_SHIFT_2]; | |
| }; | |
| #endif |