1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
|
/*
******************************************************************************
*
* 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
|
