source/i18n/collationrootelements.h

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