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