1 /* 2 ******************************************************************************* 3 * Copyright (C) 2013-2014, International Business Machines 4 * Corporation and others. All Rights Reserved. 5 ******************************************************************************* 6 * collationrootelements.h 7 * 8 * created on: 2013mar01 9 * created by: Markus W. Scherer 10 */ 11 12 #ifndef __COLLATIONROOTELEMENTS_H__ 13 #define __COLLATIONROOTELEMENTS_H__ 14 15 #include "unicode/utypes.h" 16 17 #if !UCONFIG_NO_COLLATION 18 19 #include "unicode/uobject.h" 20 #include "collation.h" 21 22 U_NAMESPACE_BEGIN 23 24 /** 25 * Container and access methods for collation elements and weights 26 * that occur in the root collator. 27 * Needed for finding boundaries for building a tailoring. 28 * 29 * This class takes and returns 16-bit secondary and tertiary weights. 30 */ 31 class U_I18N_API CollationRootElements : public UMemory { 32 public: CollationRootElements(const uint32_t * rootElements,int32_t rootElementsLength)33 CollationRootElements(const uint32_t *rootElements, int32_t rootElementsLength) 34 : elements(rootElements), length(rootElementsLength) {} 35 36 /** 37 * Higher than any root primary. 38 */ 39 static const uint32_t PRIMARY_SENTINEL = 0xffffff00; 40 41 /** 42 * Flag in a root element, set if the element contains secondary & tertiary weights, 43 * rather than a primary. 44 */ 45 static const uint32_t SEC_TER_DELTA_FLAG = 0x80; 46 /** 47 * Mask for getting the primary range step value from a primary-range-end element. 48 */ 49 static const uint8_t PRIMARY_STEP_MASK = 0x7f; 50 51 enum { 52 /** 53 * Index of the first CE with a non-zero tertiary weight. 54 * Same as the start of the compact root elements table. 55 */ 56 IX_FIRST_TERTIARY_INDEX, 57 /** 58 * Index of the first CE with a non-zero secondary weight. 59 */ 60 IX_FIRST_SECONDARY_INDEX, 61 /** 62 * Index of the first CE with a non-zero primary weight. 63 */ 64 IX_FIRST_PRIMARY_INDEX, 65 /** 66 * Must match Collation::COMMON_SEC_AND_TER_CE. 67 */ 68 IX_COMMON_SEC_AND_TER_CE, 69 /** 70 * Secondary & tertiary boundaries. 71 * Bits 31..24: [fixed last secondary common byte 45] 72 * Bits 23..16: [fixed first ignorable secondary byte 80] 73 * Bits 15.. 8: reserved, 0 74 * Bits 7.. 0: [fixed first ignorable tertiary byte 3C] 75 */ 76 IX_SEC_TER_BOUNDARIES, 77 /** 78 * The current number of indexes. 79 * Currently the same as elements[IX_FIRST_TERTIARY_INDEX]. 80 */ 81 IX_COUNT 82 }; 83 84 /** 85 * Returns the boundary between tertiary weights of primary/secondary CEs 86 * and those of tertiary CEs. 87 * This is the upper limit for tertiaries of primary/secondary CEs. 88 * This minus one is the lower limit for tertiaries of tertiary CEs. 89 */ getTertiaryBoundary()90 uint32_t getTertiaryBoundary() const { 91 return (elements[IX_SEC_TER_BOUNDARIES] << 8) & 0xff00; 92 } 93 94 /** 95 * Returns the first assigned tertiary CE. 96 */ getFirstTertiaryCE()97 uint32_t getFirstTertiaryCE() const { 98 return elements[elements[IX_FIRST_TERTIARY_INDEX]] & ~SEC_TER_DELTA_FLAG; 99 } 100 101 /** 102 * Returns the last assigned tertiary CE. 103 */ getLastTertiaryCE()104 uint32_t getLastTertiaryCE() const { 105 return elements[elements[IX_FIRST_SECONDARY_INDEX] - 1] & ~SEC_TER_DELTA_FLAG; 106 } 107 108 /** 109 * Returns the last common secondary weight. 110 * This is the lower limit for secondaries of primary CEs. 111 */ getLastCommonSecondary()112 uint32_t getLastCommonSecondary() const { 113 return (elements[IX_SEC_TER_BOUNDARIES] >> 16) & 0xff00; 114 } 115 116 /** 117 * Returns the boundary between secondary weights of primary CEs 118 * and those of secondary CEs. 119 * This is the upper limit for secondaries of primary CEs. 120 * This minus one is the lower limit for secondaries of secondary CEs. 121 */ getSecondaryBoundary()122 uint32_t getSecondaryBoundary() const { 123 return (elements[IX_SEC_TER_BOUNDARIES] >> 8) & 0xff00; 124 } 125 126 /** 127 * Returns the first assigned secondary CE. 128 */ getFirstSecondaryCE()129 uint32_t getFirstSecondaryCE() const { 130 return elements[elements[IX_FIRST_SECONDARY_INDEX]] & ~SEC_TER_DELTA_FLAG; 131 } 132 133 /** 134 * Returns the last assigned secondary CE. 135 */ getLastSecondaryCE()136 uint32_t getLastSecondaryCE() const { 137 return elements[elements[IX_FIRST_PRIMARY_INDEX] - 1] & ~SEC_TER_DELTA_FLAG; 138 } 139 140 /** 141 * Returns the first assigned primary weight. 142 */ getFirstPrimary()143 uint32_t getFirstPrimary() const { 144 return elements[elements[IX_FIRST_PRIMARY_INDEX]]; // step=0: cannot be a range end 145 } 146 147 /** 148 * Returns the first assigned primary CE. 149 */ getFirstPrimaryCE()150 int64_t getFirstPrimaryCE() const { 151 return Collation::makeCE(getFirstPrimary()); 152 } 153 154 /** 155 * Returns the last root CE with a primary weight before p. 156 * Intended only for reordering group boundaries. 157 */ 158 int64_t lastCEWithPrimaryBefore(uint32_t p) const; 159 160 /** 161 * Returns the first root CE with a primary weight of at least p. 162 * Intended only for reordering group boundaries. 163 */ 164 int64_t firstCEWithPrimaryAtLeast(uint32_t p) const; 165 166 /** 167 * Returns the primary weight before p. 168 * p must be greater than the first root primary. 169 */ 170 uint32_t getPrimaryBefore(uint32_t p, UBool isCompressible) const; 171 172 /** Returns the secondary weight before [p, s]. */ 173 uint32_t getSecondaryBefore(uint32_t p, uint32_t s) const; 174 175 /** Returns the tertiary weight before [p, s, t]. */ 176 uint32_t getTertiaryBefore(uint32_t p, uint32_t s, uint32_t t) const; 177 178 /** 179 * Finds the index of the input primary. 180 * p must occur as a root primary, and must not be 0. 181 */ 182 int32_t findPrimary(uint32_t p) const; 183 184 /** 185 * Returns the primary weight after p where index=findPrimary(p). 186 * p must be at least the first root primary. 187 */ 188 uint32_t getPrimaryAfter(uint32_t p, int32_t index, UBool isCompressible) const; 189 /** 190 * Returns the secondary weight after [p, s] where index=findPrimary(p) 191 * except use index=0 for p=0. 192 * 193 * Must return a weight for every root [p, s] as well as for every weight 194 * returned by getSecondaryBefore(). If p!=0 then s can be BEFORE_WEIGHT16. 195 * 196 * Exception: [0, 0] is handled by the CollationBuilder: 197 * Both its lower and upper boundaries are special. 198 */ 199 uint32_t getSecondaryAfter(int32_t index, uint32_t s) const; 200 /** 201 * Returns the tertiary weight after [p, s, t] where index=findPrimary(p) 202 * except use index=0 for p=0. 203 * 204 * Must return a weight for every root [p, s, t] as well as for every weight 205 * returned by getTertiaryBefore(). If s!=0 then t can be BEFORE_WEIGHT16. 206 * 207 * Exception: [0, 0, 0] is handled by the CollationBuilder: 208 * Both its lower and upper boundaries are special. 209 */ 210 uint32_t getTertiaryAfter(int32_t index, uint32_t s, uint32_t t) const; 211 212 private: 213 /** 214 * Returns the first secondary & tertiary weights for p where index=findPrimary(p)+1. 215 */ 216 uint32_t getFirstSecTerForPrimary(int32_t index) const; 217 218 /** 219 * Finds the largest index i where elements[i]<=p. 220 * Requires first primary<=p<0xffffff00 (PRIMARY_SENTINEL). 221 * Does not require that p is a root collator primary. 222 */ 223 int32_t findP(uint32_t p) const; 224 isEndOfPrimaryRange(uint32_t q)225 static inline UBool isEndOfPrimaryRange(uint32_t q) { 226 return (q & SEC_TER_DELTA_FLAG) == 0 && (q & PRIMARY_STEP_MASK) != 0; 227 } 228 229 /** 230 * Data structure: 231 * 232 * The first few entries are indexes, up to elements[IX_FIRST_TERTIARY_INDEX]. 233 * See the comments on the IX_ constants. 234 * 235 * All other elements are a compact form of the root collator CEs 236 * in mostly collation order. 237 * 238 * A sequence of one or more root CEs with the same primary weight is stored as 239 * one element with the primary weight, with the SEC_TER_DELTA_FLAG flag not set, 240 * followed by elements with only the secondary/tertiary weights, 241 * each with that flag set. 242 * If the lowest secondary/tertiary combination is Collation::COMMON_SEC_AND_TER_CE, 243 * then the element for that combination is omitted. 244 * 245 * Note: If the first actual secondary/tertiary combination is higher than 246 * Collation::COMMON_SEC_AND_TER_CE (which is unusual), 247 * the runtime code will assume anyway that Collation::COMMON_SEC_AND_TER_CE is present. 248 * 249 * A range of only-primary CEs with a consistent "step" increment 250 * from each primary to the next may be stored as a range. 251 * Only the first and last primary are stored, and the last has the step 252 * value in the low bits (PRIMARY_STEP_MASK). 253 * 254 * An range-end element may also either start a new range or be followed by 255 * elements with secondary/tertiary deltas. 256 * 257 * A primary element that is not a range end has zero step bits. 258 * 259 * There is no element for the completely ignorable CE (all weights 0). 260 * 261 * Before elements[IX_FIRST_PRIMARY_INDEX], all elements are secondary/tertiary deltas, 262 * for all of the ignorable root CEs. 263 * 264 * There are no elements for unassigned-implicit primary CEs. 265 * All primaries stored here are at most 3 bytes long. 266 */ 267 const uint32_t *elements; 268 int32_t length; 269 }; 270 271 U_NAMESPACE_END 272 273 #endif // !UCONFIG_NO_COLLATION 274 #endif // __COLLATIONROOTELEMENTS_H__ 275