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