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