1 /*
2 *******************************************************************************
3 * Copyright (C) 2013-2014, International Business Machines
4 * Corporation and others. All Rights Reserved.
5 *******************************************************************************
6 * collationrootelements.cpp
7 *
8 * created on: 2013mar05
9 * created by: Markus W. Scherer
10 */
11
12 #include "unicode/utypes.h"
13
14 #if !UCONFIG_NO_COLLATION
15
16 #include "collation.h"
17 #include "collationrootelements.h"
18 #include "uassert.h"
19
20 U_NAMESPACE_BEGIN
21
22 int64_t
lastCEWithPrimaryBefore(uint32_t p) const23 CollationRootElements::lastCEWithPrimaryBefore(uint32_t p) const {
24 if(p == 0) { return 0; }
25 U_ASSERT(p > elements[elements[IX_FIRST_PRIMARY_INDEX]]);
26 int32_t index = findP(p);
27 uint32_t q = elements[index];
28 uint32_t secTer;
29 if(p == (q & 0xffffff00)) {
30 // p == elements[index] is a root primary. Find the CE before it.
31 // We must not be in a primary range.
32 U_ASSERT((q & PRIMARY_STEP_MASK) == 0);
33 secTer = elements[index - 1];
34 if((secTer & SEC_TER_DELTA_FLAG) == 0) {
35 // Primary CE just before p.
36 p = secTer & 0xffffff00;
37 secTer = Collation::COMMON_SEC_AND_TER_CE;
38 } else {
39 // secTer = last secondary & tertiary for the previous primary
40 index -= 2;
41 for(;;) {
42 p = elements[index];
43 if((p & SEC_TER_DELTA_FLAG) == 0) {
44 p &= 0xffffff00;
45 break;
46 }
47 --index;
48 }
49 }
50 } else {
51 // p > elements[index] which is the previous primary.
52 // Find the last secondary & tertiary weights for it.
53 p = q & 0xffffff00;
54 secTer = Collation::COMMON_SEC_AND_TER_CE;
55 for(;;) {
56 q = elements[++index];
57 if((q & SEC_TER_DELTA_FLAG) == 0) {
58 // We must not be in a primary range.
59 U_ASSERT((q & PRIMARY_STEP_MASK) == 0);
60 break;
61 }
62 secTer = q;
63 }
64 }
65 return ((int64_t)p << 32) | (secTer & ~SEC_TER_DELTA_FLAG);
66 }
67
68 int64_t
firstCEWithPrimaryAtLeast(uint32_t p) const69 CollationRootElements::firstCEWithPrimaryAtLeast(uint32_t p) const {
70 if(p == 0) { return 0; }
71 int32_t index = findP(p);
72 if(p != (elements[index] & 0xffffff00)) {
73 for(;;) {
74 p = elements[++index];
75 if((p & SEC_TER_DELTA_FLAG) == 0) {
76 // First primary after p. We must not be in a primary range.
77 U_ASSERT((p & PRIMARY_STEP_MASK) == 0);
78 break;
79 }
80 }
81 }
82 // The code above guarantees that p has at most 3 bytes: (p & 0xff) == 0.
83 return ((int64_t)p << 32) | Collation::COMMON_SEC_AND_TER_CE;
84 }
85
86 uint32_t
getPrimaryBefore(uint32_t p,UBool isCompressible) const87 CollationRootElements::getPrimaryBefore(uint32_t p, UBool isCompressible) const {
88 int32_t index = findPrimary(p);
89 int32_t step;
90 uint32_t q = elements[index];
91 if(p == (q & 0xffffff00)) {
92 // Found p itself. Return the previous primary.
93 // See if p is at the end of a previous range.
94 step = (int32_t)q & PRIMARY_STEP_MASK;
95 if(step == 0) {
96 // p is not at the end of a range. Look for the previous primary.
97 do {
98 p = elements[--index];
99 } while((p & SEC_TER_DELTA_FLAG) != 0);
100 return p & 0xffffff00;
101 }
102 } else {
103 // p is in a range, and not at the start.
104 uint32_t nextElement = elements[index + 1];
105 U_ASSERT(isEndOfPrimaryRange(nextElement));
106 step = (int32_t)nextElement & PRIMARY_STEP_MASK;
107 }
108 // Return the previous range primary.
109 if((p & 0xffff) == 0) {
110 return Collation::decTwoBytePrimaryByOneStep(p, isCompressible, step);
111 } else {
112 return Collation::decThreeBytePrimaryByOneStep(p, isCompressible, step);
113 }
114 }
115
116 uint32_t
getSecondaryBefore(uint32_t p,uint32_t s) const117 CollationRootElements::getSecondaryBefore(uint32_t p, uint32_t s) const {
118 int32_t index;
119 uint32_t previousSec, sec;
120 if(p == 0) {
121 index = (int32_t)elements[IX_FIRST_SECONDARY_INDEX];
122 // Gap at the beginning of the secondary CE range.
123 previousSec = 0;
124 sec = elements[index] >> 16;
125 } else {
126 index = findPrimary(p) + 1;
127 previousSec = Collation::MERGE_SEPARATOR_WEIGHT16;
128 sec = Collation::COMMON_WEIGHT16;
129 }
130 U_ASSERT(s >= sec);
131 while(s > sec) {
132 previousSec = sec;
133 U_ASSERT((elements[index] & SEC_TER_DELTA_FLAG) != 0);
134 sec = elements[index++] >> 16;
135 }
136 U_ASSERT(sec == s);
137 return previousSec;
138 }
139
140 uint32_t
getTertiaryBefore(uint32_t p,uint32_t s,uint32_t t) const141 CollationRootElements::getTertiaryBefore(uint32_t p, uint32_t s, uint32_t t) const {
142 U_ASSERT((t & ~Collation::ONLY_TERTIARY_MASK) == 0);
143 int32_t index;
144 uint32_t previousTer, secTer;
145 if(p == 0) {
146 if(s == 0) {
147 index = (int32_t)elements[IX_FIRST_TERTIARY_INDEX];
148 // Gap at the beginning of the tertiary CE range.
149 previousTer = 0;
150 } else {
151 index = (int32_t)elements[IX_FIRST_SECONDARY_INDEX];
152 previousTer = Collation::MERGE_SEPARATOR_WEIGHT16;
153 }
154 secTer = elements[index] & ~SEC_TER_DELTA_FLAG;
155 } else {
156 index = findPrimary(p) + 1;
157 previousTer = Collation::MERGE_SEPARATOR_WEIGHT16;
158 secTer = Collation::COMMON_SEC_AND_TER_CE;
159 }
160 uint32_t st = (s << 16) | t;
161 while(st > secTer) {
162 if((secTer >> 16) == s) { previousTer = secTer; }
163 U_ASSERT((elements[index] & SEC_TER_DELTA_FLAG) != 0);
164 secTer = elements[index++] & ~SEC_TER_DELTA_FLAG;
165 }
166 U_ASSERT(secTer == st);
167 return previousTer & 0xffff;
168 }
169
170 uint32_t
getPrimaryAfter(uint32_t p,int32_t index,UBool isCompressible) const171 CollationRootElements::getPrimaryAfter(uint32_t p, int32_t index, UBool isCompressible) const {
172 U_ASSERT(p == (elements[index] & 0xffffff00) || isEndOfPrimaryRange(elements[index + 1]));
173 uint32_t q = elements[++index];
174 int32_t step;
175 if((q & SEC_TER_DELTA_FLAG) == 0 && (step = (int32_t)q & PRIMARY_STEP_MASK) != 0) {
176 // Return the next primary in this range.
177 if((p & 0xffff) == 0) {
178 return Collation::incTwoBytePrimaryByOffset(p, isCompressible, step);
179 } else {
180 return Collation::incThreeBytePrimaryByOffset(p, isCompressible, step);
181 }
182 } else {
183 // Return the next primary in the list.
184 while((q & SEC_TER_DELTA_FLAG) != 0) {
185 q = elements[++index];
186 }
187 U_ASSERT((q & PRIMARY_STEP_MASK) == 0);
188 return q;
189 }
190 }
191
192 uint32_t
getSecondaryAfter(int32_t index,uint32_t s) const193 CollationRootElements::getSecondaryAfter(int32_t index, uint32_t s) const {
194 uint32_t secLimit;
195 if(index == 0) {
196 // primary = 0
197 index = (int32_t)elements[IX_FIRST_SECONDARY_INDEX];
198 // Gap at the end of the secondary CE range.
199 secLimit = 0x10000;
200 } else {
201 U_ASSERT(index >= (int32_t)elements[IX_FIRST_PRIMARY_INDEX]);
202 ++index;
203 // Gap for secondaries of primary CEs.
204 secLimit = getSecondaryBoundary();
205 }
206 for(;;) {
207 uint32_t secTer = elements[index];
208 if((secTer & SEC_TER_DELTA_FLAG) == 0) { return secLimit; }
209 uint32_t sec = secTer >> 16;
210 if(sec > s) { return sec; }
211 ++index;
212 }
213 }
214
215 uint32_t
getTertiaryAfter(int32_t index,uint32_t s,uint32_t t) const216 CollationRootElements::getTertiaryAfter(int32_t index, uint32_t s, uint32_t t) const {
217 uint32_t terLimit;
218 if(index == 0) {
219 // primary = 0
220 if(s == 0) {
221 index = (int32_t)elements[IX_FIRST_TERTIARY_INDEX];
222 // Gap at the end of the tertiary CE range.
223 terLimit = 0x4000;
224 } else {
225 index = (int32_t)elements[IX_FIRST_SECONDARY_INDEX];
226 // Gap for tertiaries of primary/secondary CEs.
227 terLimit = getTertiaryBoundary();
228 }
229 } else {
230 U_ASSERT(index >= (int32_t)elements[IX_FIRST_PRIMARY_INDEX]);
231 ++index;
232 terLimit = getTertiaryBoundary();
233 }
234 uint32_t st = (s << 16) | t;
235 for(;;) {
236 uint32_t secTer = elements[index];
237 // No tertiary greater than t for this primary+secondary.
238 if((secTer & SEC_TER_DELTA_FLAG) == 0 || (secTer >> 16) > s) { return terLimit; }
239 secTer &= ~SEC_TER_DELTA_FLAG;
240 if(secTer > st) { return secTer & 0xffff; }
241 ++index;
242 }
243 }
244
245 int32_t
findPrimary(uint32_t p) const246 CollationRootElements::findPrimary(uint32_t p) const {
247 // Requirement: p must occur as a root primary.
248 U_ASSERT((p & 0xff) == 0); // at most a 3-byte primary
249 int32_t index = findP(p);
250 // If p is in a range, then we just assume that p is an actual primary in this range.
251 // (Too cumbersome/expensive to check.)
252 // Otherwise, it must be an exact match.
253 U_ASSERT(isEndOfPrimaryRange(elements[index + 1]) || p == (elements[index] & 0xffffff00));
254 return index;
255 }
256
257 int32_t
findP(uint32_t p) const258 CollationRootElements::findP(uint32_t p) const {
259 // p need not occur as a root primary.
260 // For example, it might be a reordering group boundary.
261 U_ASSERT((p >> 24) != Collation::UNASSIGNED_IMPLICIT_BYTE);
262 // modified binary search
263 int32_t start = (int32_t)elements[IX_FIRST_PRIMARY_INDEX];
264 U_ASSERT(p >= elements[start]);
265 int32_t limit = length - 1;
266 U_ASSERT(elements[limit] >= PRIMARY_SENTINEL);
267 U_ASSERT(p < elements[limit]);
268 while((start + 1) < limit) {
269 // Invariant: elements[start] and elements[limit] are primaries,
270 // and elements[start]<=p<=elements[limit].
271 int32_t i = (start + limit) / 2;
272 uint32_t q = elements[i];
273 if((q & SEC_TER_DELTA_FLAG) != 0) {
274 // Find the next primary.
275 int32_t j = i + 1;
276 for(;;) {
277 if(j == limit) { break; }
278 q = elements[j];
279 if((q & SEC_TER_DELTA_FLAG) == 0) {
280 i = j;
281 break;
282 }
283 ++j;
284 }
285 if((q & SEC_TER_DELTA_FLAG) != 0) {
286 // Find the preceding primary.
287 j = i - 1;
288 for(;;) {
289 if(j == start) { break; }
290 q = elements[j];
291 if((q & SEC_TER_DELTA_FLAG) == 0) {
292 i = j;
293 break;
294 }
295 --j;
296 }
297 if((q & SEC_TER_DELTA_FLAG) != 0) {
298 // No primary between start and limit.
299 break;
300 }
301 }
302 }
303 if(p < (q & 0xffffff00)) { // Reset the "step" bits of a range end primary.
304 limit = i;
305 } else {
306 start = i;
307 }
308 }
309 return start;
310 }
311
312 U_NAMESPACE_END
313
314 #endif // !UCONFIG_NO_COLLATION
315