1 /*
2 ******************************************************************************
3 *
4 *   Copyright (C) 2001-2008, International Business Machines
5 *   Corporation and others.  All Rights Reserved.
6 *
7 ******************************************************************************
8 *   file name:  utrie2_impl.h
9 *   encoding:   US-ASCII
10 *   tab size:   8 (not used)
11 *   indentation:4
12 *
13 *   created on: 2008sep26 (split off from utrie2.c)
14 *   created by: Markus W. Scherer
15 *
16 *   Definitions needed for both runtime and builder code for UTrie2,
17 *   used by utrie2.c and utrie2_builder.c.
18 */
19 
20 #ifndef __UTRIE2_IMPL_H__
21 #define __UTRIE2_IMPL_H__
22 
23 #include "utrie2.h"
24 
25 /* Public UTrie2 API implementation ----------------------------------------- */
26 
27 /*
28  * These definitions are mostly needed by utrie2.c,
29  * but also by utrie2_serialize() and utrie2_swap().
30  */
31 
32 /*
33  * UTrie and UTrie2 signature values,
34  * in platform endianness and opposite endianness.
35  */
36 #define UTRIE_SIG       0x54726965
37 #define UTRIE_OE_SIG    0x65697254
38 
39 #define UTRIE2_SIG      0x54726932
40 #define UTRIE2_OE_SIG   0x32697254
41 
42 /**
43  * Trie data structure in serialized form:
44  *
45  * UTrie2Header header;
46  * uint16_t index[header.index2Length];
47  * uint16_t data[header.shiftedDataLength<<2];  -- or uint32_t data[...]
48  * @internal
49  */
50 typedef struct UTrie2Header {
51     /** "Tri2" in big-endian US-ASCII (0x54726932) */
52     uint32_t signature;
53 
54     /**
55      * options bit field:
56      * 15.. 4   reserved (0)
57      *  3.. 0   UTrie2ValueBits valueBits
58      */
59     uint16_t options;
60 
61     /** UTRIE2_INDEX_1_OFFSET..UTRIE2_MAX_INDEX_LENGTH */
62     uint16_t indexLength;
63 
64     /** (UTRIE2_DATA_START_OFFSET..UTRIE2_MAX_DATA_LENGTH)>>UTRIE2_INDEX_SHIFT */
65     uint16_t shiftedDataLength;
66 
67     /** Null index and data blocks, not shifted. */
68     uint16_t index2NullOffset, dataNullOffset;
69 
70     /**
71      * First code point of the single-value range ending with U+10ffff,
72      * rounded up and then shifted right by UTRIE2_SHIFT_1.
73      */
74     uint16_t shiftedHighStart;
75 } UTrie2Header;
76 
77 /**
78  * Constants for use with UTrie2Header.options.
79  * @internal
80  */
81 enum {
82     /** Mask to get the UTrie2ValueBits valueBits from options. */
83     UTRIE2_OPTIONS_VALUE_BITS_MASK=0xf
84 };
85 
86 /* Building a trie ---------------------------------------------------------- */
87 
88 /*
89  * These definitions are mostly needed by utrie2_builder.c, but also by
90  * utrie2_get32() and utrie2_enum().
91  */
92 
93 enum {
94     /**
95      * At build time, leave a gap in the index-2 table,
96      * at least as long as the maximum lengths of the 2-byte UTF-8 index-2 table
97      * and the supplementary index-1 table.
98      * Round up to UTRIE2_INDEX_2_BLOCK_LENGTH for proper compacting.
99      */
100     UNEWTRIE2_INDEX_GAP_OFFSET=UTRIE2_INDEX_2_BMP_LENGTH,
101     UNEWTRIE2_INDEX_GAP_LENGTH=
102         ((UTRIE2_UTF8_2B_INDEX_2_LENGTH+UTRIE2_MAX_INDEX_1_LENGTH)+UTRIE2_INDEX_2_MASK)&
103         ~UTRIE2_INDEX_2_MASK,
104 
105     /**
106      * Maximum length of the build-time index-2 array.
107      * Maximum number of Unicode code points (0x110000) shifted right by UTRIE2_SHIFT_2,
108      * plus the part of the index-2 table for lead surrogate code points,
109      * plus the build-time index gap,
110      * plus the null index-2 block.
111      */
112     UNEWTRIE2_MAX_INDEX_2_LENGTH=
113         (0x110000>>UTRIE2_SHIFT_2)+
114         UTRIE2_LSCP_INDEX_2_LENGTH+
115         UNEWTRIE2_INDEX_GAP_LENGTH+
116         UTRIE2_INDEX_2_BLOCK_LENGTH,
117 
118     UNEWTRIE2_INDEX_1_LENGTH=0x110000>>UTRIE2_SHIFT_1
119 };
120 
121 /**
122  * Maximum length of the build-time data array.
123  * One entry per 0x110000 code points, plus the illegal-UTF-8 block and the null block,
124  * plus values for the 0x400 surrogate code units.
125  */
126 #define UNEWTRIE2_MAX_DATA_LENGTH (0x110000+0x40+0x40+0x400)
127 
128 /*
129  * Build-time trie structure.
130  *
131  * Just using a boolean flag for "repeat use" could lead to data array overflow
132  * because we would not be able to detect when a data block becomes unused.
133  * It also leads to orphan data blocks that are kept through serialization.
134  *
135  * Need to use reference counting for data blocks,
136  * and allocDataBlock() needs to look for a free block before increasing dataLength.
137  *
138  * This scheme seems like overkill for index-2 blocks since the whole index array is
139  * preallocated anyway (unlike the growable data array).
140  * Just allocating multiple index-2 blocks as needed.
141  */
142 struct UNewTrie2 {
143     int32_t index1[UNEWTRIE2_INDEX_1_LENGTH];
144     int32_t index2[UNEWTRIE2_MAX_INDEX_2_LENGTH];
145     uint32_t *data;
146 
147     uint32_t initialValue, errorValue;
148     int32_t index2Length, dataCapacity, dataLength;
149     int32_t firstFreeBlock;
150     int32_t index2NullOffset, dataNullOffset;
151     UChar32 highStart;
152     UBool isCompacted;
153 
154     /**
155      * Multi-purpose per-data-block table.
156      *
157      * Before compacting:
158      *
159      * Per-data-block reference counters/free-block list.
160      *  0: unused
161      * >0: reference counter (number of index-2 entries pointing here)
162      * <0: next free data block in free-block list
163      *
164      * While compacting:
165      *
166      * Map of adjusted indexes, used in compactData() and compactIndex2().
167      * Maps from original indexes to new ones.
168      */
169     int32_t map[UNEWTRIE2_MAX_DATA_LENGTH>>UTRIE2_SHIFT_2];
170 };
171 
172 #endif
173