icuSources/i18n/collationrootelements.h

   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:
  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      */
  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      */
  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      */
 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      */
 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      */
 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      */
 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      */
 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      */
 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      */
 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
 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__