// © 2016 and later: Unicode, Inc. and others.
// License & terms of use: http://www.unicode.org/copyright.html
/*
*******************************************************************************
* Copyright (C) 2013-2014, International Business Machines
* Corporation and others. All Rights Reserved.
*******************************************************************************
* collationrootelements.cpp
*
* created on: 2013mar05
* created by: Markus W. Scherer
*/
#include "unicode/utypes.h"
#if !UCONFIG_NO_COLLATION
#include "collation.h"
#include "collationrootelements.h"
#include "uassert.h"
U_NAMESPACE_BEGIN
int64_t
CollationRootElements::lastCEWithPrimaryBefore(uint32_t p)
const {
if(p == 0) {
return 0; }
U_ASSERT(p > elements[elements[IX_FIRST_PRIMARY_INDEX]]);
int32_t index = findP(p);
uint32_t q = elements[index];
uint32_t secTer;
if(p == (q & 0xffffff00)) {
// p == elements[index] is a root primary. Find the CE before it.
// We must not be in a primary range.
U_ASSERT((q & PRIMARY_STEP_MASK) == 0);
secTer = elements[index - 1];
if((secTer & SEC_TER_DELTA_FLAG) == 0) {
// Primary CE just before p.
p = secTer & 0xffffff00;
secTer = Collation::COMMON_SEC_AND_TER_CE;
}
else {
// secTer = last secondary & tertiary for the previous primary
index -= 2;
for(;;) {
p = elements[index];
if((p & SEC_TER_DELTA_FLAG) == 0) {
p &= 0xffffff00;
break;
}
--index;
}
}
}
else {
// p > elements[index] which is the previous primary.
// Find the last secondary & tertiary weights for it.
p = q & 0xffffff00;
secTer = Collation::COMMON_SEC_AND_TER_CE;
for(;;) {
q = elements[++index];
if((q & SEC_TER_DELTA_FLAG) == 0) {
// We must not be in a primary range.
U_ASSERT((q & PRIMARY_STEP_MASK) == 0);
break;
}
secTer = q;
}
}
return (
static_cast<int64_t>(p) << 32) | (secTer & ~SEC_TER_DELTA_FLAG);
}
int64_t
CollationRootElements::firstCEWithPrimaryAtLeast(uint32_t p)
const {
if(p == 0) {
return 0; }
int32_t index = findP(p);
if(p != (elements[index] & 0xffffff00)) {
for(;;) {
p = elements[++index];
if((p & SEC_TER_DELTA_FLAG) == 0) {
// First primary after p. We must not be in a primary range.
U_ASSERT((p & PRIMARY_STEP_MASK) == 0);
break;
}
}
}
// The code above guarantees that p has at most 3 bytes: (p & 0xff) == 0.
return (
static_cast<int64_t>(p) << 32) | Collation::COMMON_SEC_AND_TER_CE;
}
uint32_t
CollationRootElements::getPrimaryBefore(uint32_t p, UBool isCompressible)
const {
int32_t index = findPrimary(p);
int32_t step;
uint32_t q = elements[index];
if(p == (q & 0xffffff00)) {
// Found p itself. Return the previous primary.
// See if p is at the end of a previous range.
step =
static_cast<int32_t>(q) & PRIMARY_STEP_MASK;
if(step == 0) {
// p is not at the end of a range. Look for the previous primary.
do {
p = elements[--index];
}
while((p & SEC_TER_DELTA_FLAG) != 0);
return p & 0xffffff00;
}
}
else {
// p is in a range, and not at the start.
uint32_t nextElement = elements[index + 1];
U_ASSERT(isEndOfPrimaryRange(nextElement));
step =
static_cast<int32_t>(nextElement) & PRIMARY_STEP_MASK;
}
// Return the previous range primary.
if((p & 0xffff) == 0) {
return Collation::decTwoBytePrimaryByOneStep(p, isCompressible, step);
}
else {
return Collation::decThreeBytePrimaryByOneStep(p, isCompressible, step);
}
}
uint32_t
CollationRootElements::getSecondaryBefore(uint32_t p, uint32_t s)
const {
int32_t index;
uint32_t previousSec, sec;
if(p == 0) {
index =
static_cast<int32_t>(elements[IX_FIRST_SECONDARY_INDEX]);
// Gap at the beginning of the secondary CE range.
previousSec = 0;
sec = elements[index] >> 16;
}
else {
index = findPrimary(p) + 1;
previousSec = Collation::BEFORE_WEIGHT16;
sec = getFirstSecTerForPrimary(index) >> 16;
}
U_ASSERT(s >= sec);
while(s > sec) {
previousSec = sec;
U_ASSERT((elements[index] & SEC_TER_DELTA_FLAG) != 0);
sec = elements[index++] >> 16;
}
U_ASSERT(sec == s);
return previousSec;
}
uint32_t
CollationRootElements::getTertiaryBefore(uint32_t p, uint32_t s, uint32_t t)
const {
U_ASSERT((t & ~Collation::ONLY_TERTIARY_MASK) == 0);
int32_t index;
uint32_t previousTer, secTer;
if(p == 0) {
if(s == 0) {
index =
static_cast<int32_t>(elements[IX_FIRST_TERTIARY_INDEX]);
// Gap at the beginning of the tertiary CE range.
previousTer = 0;
}
else {
index =
static_cast<int32_t>(elements[IX_FIRST_SECONDARY_INDEX]);
previousTer = Collation::BEFORE_WEIGHT16;
}
secTer = elements[index] & ~SEC_TER_DELTA_FLAG;
}
else {
index = findPrimary(p) + 1;
previousTer = Collation::BEFORE_WEIGHT16;
secTer = getFirstSecTerForPrimary(index);
}
uint32_t st = (s << 16) | t;
while(st > secTer) {
if((secTer >> 16) == s) { previousTer = secTer; }
U_ASSERT((elements[index] & SEC_TER_DELTA_FLAG) != 0);
secTer = elements[index++] & ~SEC_TER_DELTA_FLAG;
}
U_ASSERT(secTer == st);
return previousTer & 0xffff;
}
uint32_t
CollationRootElements::getPrimaryAfter(uint32_t p, int32_t index, UBool isCompressibl
e) const {
U_ASSERT(p == (elements[index] & 0xffffff00) || isEndOfPrimaryRange(elements[index + 1]));
uint32_t q = elements[++index];
int32_t step;
if ((q & SEC_TER_DELTA_FLAG) == 0 && (step = static_cast<int32_t>(q) & PRIMARY_STEP_MASK) != 0) {
// Return the next primary in this range.
if((p & 0xffff) == 0) {
return Collation::incTwoBytePrimaryByOffset(p, isCompressible, step);
} else {
return Collation::incThreeBytePrimaryByOffset(p, isCompressible, step);
}
} else {
// Return the next primary in the list.
while((q & SEC_TER_DELTA_FLAG) != 0) {
q = elements[++index];
}
U_ASSERT((q & PRIMARY_STEP_MASK) == 0);
return q;
}
}
uint32_t
CollationRootElements::getSecondaryAfter(int32_t index, uint32_t s) const {
uint32_t secTer;
uint32_t secLimit;
if(index == 0) {
// primary = 0
U_ASSERT(s != 0);
index = static_cast<int32_t>(elements[IX_FIRST_SECONDARY_INDEX]);
secTer = elements[index];
// Gap at the end of the secondary CE range.
secLimit = 0x10000;
} else {
U_ASSERT(index >= (int32_t)elements[IX_FIRST_PRIMARY_INDEX]);
secTer = getFirstSecTerForPrimary(index + 1);
// If this is an explicit sec/ter unit, then it will be read once more.
// Gap for secondaries of primary CEs.
secLimit = getSecondaryBoundary();
}
for(;;) {
uint32_t sec = secTer >> 16;
if(sec > s) { return sec; }
secTer = elements[++index];
if((secTer & SEC_TER_DELTA_FLAG) == 0) { return secLimit; }
}
}
uint32_t
CollationRootElements::getTertiaryAfter(int32_t index, uint32_t s, uint32_t t) const {
uint32_t secTer;
uint32_t terLimit;
if(index == 0) {
// primary = 0
if(s == 0) {
U_ASSERT(t != 0);
index = static_cast<int32_t>(elements[IX_FIRST_TERTIARY_INDEX]);
// Gap at the end of the tertiary CE range.
terLimit = 0x4000;
} else {
index = static_cast<int32_t>(elements[IX_FIRST_SECONDARY_INDEX]);
// Gap for tertiaries of primary/secondary CEs.
terLimit = getTertiaryBoundary();
}
secTer = elements[index] & ~SEC_TER_DELTA_FLAG;
} else {
U_ASSERT(index >= (int32_t)elements[IX_FIRST_PRIMARY_INDEX]);
secTer = getFirstSecTerForPrimary(index + 1);
// If this is an explicit sec/ter unit, then it will be read once more.
terLimit = getTertiaryBoundary();
}
uint32_t st = (s << 16) | t;
for(;;) {
if(secTer > st) {
U_ASSERT((secTer >> 16) == s);
return secTer & 0xffff;
}
secTer = elements[++index];
// No tertiary greater than t for this primary+secondary.
if((secTer & SEC_TER_DELTA_FLAG) == 0 || (secTer >> 16) > s) { return terLimit; }
secTer &= ~SEC_TER_DELTA_FLAG;
}
}
uint32_t
CollationRootElements::getFirstSecTerForPrimary(int32_t index) const {
uint32_t secTer = elements[index];
if((secTer & SEC_TER_DELTA_FLAG) == 0) {
// No sec/ter delta.
return Collation::COMMON_SEC_AND_TER_CE;
}
secTer &= ~SEC_TER_DELTA_FLAG;
if(secTer > Collation::COMMON_SEC_AND_TER_CE) {
// Implied sec/ter.
return Collation::COMMON_SEC_AND_TER_CE;
}
// Explicit sec/ter below common/common.
return secTer;
}
int32_t
CollationRootElements::findPrimary(uint32_t p) const {
// Requirement: p must occur as a root primary.
U_ASSERT((p & 0xff) == 0); // at most a 3-byte primary
int32_t index = findP(p);
// If p is in a range, then we just assume that p is an actual primary in this range.
// (Too cumbersome/expensive to check.)
// Otherwise, it must be an exact match.
U_ASSERT(isEndOfPrimaryRange(elements[index + 1]) || p == (elements[index] & 0xffffff00));
return index;
}
int32_t
CollationRootElements::findP(uint32_t p) const {
// p need not occur as a root primary.
// For example, it might be a reordering group boundary.
U_ASSERT((p >> 24) != Collation::UNASSIGNED_IMPLICIT_BYTE);
// modified binary search
int32_t start = static_cast<int32_t>(elements[IX_FIRST_PRIMARY_INDEX]);
U_ASSERT(p >= elements[start]);
int32_t limit = length - 1;
U_ASSERT(elements[limit] >= PRIMARY_SENTINEL);
U_ASSERT(p < elements[limit]);
while((start + 1) < limit) {
// Invariant: elements[start] and elements[limit] are primaries,
// and elements[start]<=p<=elements[limit].
int32_t i = (start + limit) / 2;
uint32_t q = elements[i];
if((q & SEC_TER_DELTA_FLAG) != 0) {
// Find the next primary.
int32_t j = i + 1;
for(;;) {
if(j == limit) { break; }
q = elements[j];
if((q & SEC_TER_DELTA_FLAG) == 0) {
i = j;
break;
}
++j;
}
if((q & SEC_TER_DELTA_FLAG) != 0) {
// Find the preceding primary.
j = i - 1;
for(;;) {
if(j == start) { break; }
q = elements[j];
if((q & SEC_TER_DELTA_FLAG) == 0) {
i = j;
break;
}
--j;
}
if((q & SEC_TER_DELTA_FLAG) != 0) {
// No primary between start and limit.
break;
}
}
}
if(p < (q & 0xffffff00)) { // Reset the "step" bits of a range end primary.
limit = i;
} else {
start = i;
}
}
return start;
}
U_NAMESPACE_END
#endif // !UCONFIG_NO_COLLATION
