OLD | NEW |
(Empty) | |
| 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 |
| 23 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 |
| 69 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 |
| 87 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 |
| 117 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 |
| 141 CollationRootElements::getTertiaryBefore(uint32_t p, uint32_t s, uint32_t t) con
st { |
| 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 |
| 171 CollationRootElements::getPrimaryAfter(uint32_t p, int32_t index, UBool isCompre
ssible) 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, ste
p); |
| 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 |
| 193 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 |
| 216 CollationRootElements::getTertiaryAfter(int32_t index, uint32_t s, uint32_t t) c
onst { |
| 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 te
rLimit; } |
| 239 secTer &= ~SEC_TER_DELTA_FLAG; |
| 240 if(secTer > st) { return secTer & 0xffff; } |
| 241 ++index; |
| 242 } |
| 243 } |
| 244 |
| 245 int32_t |
| 246 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 th
is 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 |
| 258 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 prim
ary. |
| 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 |
OLD | NEW |