1 /* 2 ******************************************************************************* 3 * Copyright (C) 2010-2014, International Business Machines 4 * Corporation and others. All Rights Reserved. 5 ******************************************************************************* 6 * collationiterator.h 7 * 8 * created on: 2010oct27 9 * created by: Markus W. Scherer 10 */ 11 12 #ifndef __COLLATIONITERATOR_H__ 13 #define __COLLATIONITERATOR_H__ 14 15 #include "unicode/utypes.h" 16 17 #if !UCONFIG_NO_COLLATION 18 19 #include "cmemory.h" 20 #include "collation.h" 21 #include "collationdata.h" 22 23 U_NAMESPACE_BEGIN 24 25 class SkippedState; 26 class UCharsTrie; 27 class UVector32; 28 29 /** 30 * Collation element iterator and abstract character iterator. 31 * 32 * When a method returns a code point value, it must be in 0..10FFFF, 33 * except it can be negative as a sentinel value. 34 */ 35 class U_I18N_API CollationIterator : public UObject { 36 private: 37 class CEBuffer { 38 private: 39 /** Large enough for CEs of most short strings. */ 40 static const int32_t INITIAL_CAPACITY = 40; 41 public: 42 CEBuffer() : length(0) {} 43 ~CEBuffer(); 44 45 inline void append(int64_t ce, UErrorCode &errorCode) { 46 if(length < INITIAL_CAPACITY || ensureAppendCapacity(1, errorCode)) { 47 buffer[length++] = ce; 48 } 49 } 50 51 inline void appendUnsafe(int64_t ce) { 52 buffer[length++] = ce; 53 } 54 55 UBool ensureAppendCapacity(int32_t appCap, UErrorCode &errorCode); 56 57 inline UBool incLength(UErrorCode &errorCode) { 58 // Use INITIAL_CAPACITY for a very simple fastpath. 59 // (Rather than buffer.getCapacity().) 60 if(length < INITIAL_CAPACITY || ensureAppendCapacity(1, errorCode)) { 61 ++length; 62 return TRUE; 63 } else { 64 return FALSE; 65 } 66 } 67 68 inline int64_t set(int32_t i, int64_t ce) { 69 return buffer[i] = ce; 70 } 71 inline int64_t get(int32_t i) const { return buffer[i]; } 72 73 const int64_t *getCEs() const { return buffer.getAlias(); } 74 75 int32_t length; 76 77 private: 78 CEBuffer(const CEBuffer &); 79 void operator=(const CEBuffer &); 80 81 MaybeStackArray<int64_t, INITIAL_CAPACITY> buffer; 82 }; 83 84 public: 85 CollationIterator(const CollationData *d, UBool numeric) 86 : trie(d->trie), 87 data(d), 88 cesIndex(0), 89 skipped(NULL), 90 numCpFwd(-1), 91 isNumeric(numeric) {} 92 93 virtual ~CollationIterator(); 94 95 virtual UBool operator==(const CollationIterator &other) const; 96 inline UBool operator!=(const CollationIterator &other) const { 97 return !operator==(other); 98 } 99 100 /** 101 * Resets the iterator state and sets the position to the specified offset. 102 * Subclasses must implement, and must call the parent class method, 103 * or CollationIterator::reset(). 104 */ 105 virtual void resetToOffset(int32_t newOffset) = 0; 106 107 virtual int32_t getOffset() const = 0; 108 109 /** 110 * Returns the next collation element. 111 */ 112 inline int64_t nextCE(UErrorCode &errorCode) { 113 if(cesIndex < ceBuffer.length) { 114 // Return the next buffered CE. 115 return ceBuffer.get(cesIndex++); 116 } 117 // assert cesIndex == ceBuffer.length; 118 if(!ceBuffer.incLength(errorCode)) { 119 return Collation::NO_CE; 120 } 121 UChar32 c; 122 uint32_t ce32 = handleNextCE32(c, errorCode); 123 uint32_t t = ce32 & 0xff; 124 if(t < Collation::SPECIAL_CE32_LOW_BYTE) { // Forced-inline of isSpecialCE32(ce32). 125 // Normal CE from the main data. 126 // Forced-inline of ceFromSimpleCE32(ce32). 127 return ceBuffer.set(cesIndex++, 128 ((int64_t)(ce32 & 0xffff0000) << 32) | ((ce32 & 0xff00) << 16) | (t << 8)); 129 } 130 const CollationData *d; 131 // The compiler should be able to optimize the previous and the following 132 // comparisons of t with the same constant. 133 if(t == Collation::SPECIAL_CE32_LOW_BYTE) { 134 if(c < 0) { 135 return ceBuffer.set(cesIndex++, Collation::NO_CE); 136 } 137 d = data->base; 138 ce32 = d->getCE32(c); 139 t = ce32 & 0xff; 140 if(t < Collation::SPECIAL_CE32_LOW_BYTE) { 141 // Normal CE from the base data. 142 return ceBuffer.set(cesIndex++, 143 ((int64_t)(ce32 & 0xffff0000) << 32) | ((ce32 & 0xff00) << 16) | (t << 8)); 144 } 145 } else { 146 d = data; 147 } 148 if(t == Collation::LONG_PRIMARY_CE32_LOW_BYTE) { 149 // Forced-inline of ceFromLongPrimaryCE32(ce32). 150 return ceBuffer.set(cesIndex++, 151 ((int64_t)(ce32 - t) << 32) | Collation::COMMON_SEC_AND_TER_CE); 152 } 153 return nextCEFromCE32(d, c, ce32, errorCode); 154 } 155 156 /** 157 * Fetches all CEs. 158 * @return getCEsLength() 159 */ 160 int32_t fetchCEs(UErrorCode &errorCode); 161 162 /** 163 * Overwrites the current CE (the last one returned by nextCE()). 164 */ 165 void setCurrentCE(int64_t ce) { 166 // assert cesIndex > 0; 167 ceBuffer.set(cesIndex - 1, ce); 168 } 169 170 /** 171 * Returns the previous collation element. 172 */ 173 int64_t previousCE(UVector32 &offsets, UErrorCode &errorCode); 174 175 inline int32_t getCEsLength() const { 176 return ceBuffer.length; 177 } 178 179 inline int64_t getCE(int32_t i) const { 180 return ceBuffer.get(i); 181 } 182 183 const int64_t *getCEs() const { 184 return ceBuffer.getCEs(); 185 } 186 187 void clearCEs() { 188 cesIndex = ceBuffer.length = 0; 189 } 190 191 void clearCEsIfNoneRemaining() { 192 if(cesIndex == ceBuffer.length) { clearCEs(); } 193 } 194 195 /** 196 * Returns the next code point (with post-increment). 197 * Public for identical-level comparison and for testing. 198 */ 199 virtual UChar32 nextCodePoint(UErrorCode &errorCode) = 0; 200 201 /** 202 * Returns the previous code point (with pre-decrement). 203 * Public for identical-level comparison and for testing. 204 */ 205 virtual UChar32 previousCodePoint(UErrorCode &errorCode) = 0; 206 207 protected: 208 CollationIterator(const CollationIterator &other); 209 210 void reset(); 211 212 /** 213 * Returns the next code point and its local CE32 value. 214 * Returns Collation::FALLBACK_CE32 at the end of the text (c<0) 215 * or when c's CE32 value is to be looked up in the base data (fallback). 216 * 217 * The code point is used for fallbacks, context and implicit weights. 218 * It is ignored when the returned CE32 is not special (e.g., FFFD_CE32). 219 */ 220 virtual uint32_t handleNextCE32(UChar32 &c, UErrorCode &errorCode); 221 222 /** 223 * Called when handleNextCE32() returns a LEAD_SURROGATE_TAG for a lead surrogate code unit. 224 * Returns the trail surrogate in that case and advances past it, 225 * if a trail surrogate follows the lead surrogate. 226 * Otherwise returns any other code unit and does not advance. 227 */ 228 virtual UChar handleGetTrailSurrogate(); 229 230 /** 231 * Called when handleNextCE32() returns with c==0, to see whether it is a NUL terminator. 232 * (Not needed in Java.) 233 */ 234 virtual UBool foundNULTerminator(); 235 236 /** 237 * @return FALSE if surrogate code points U+D800..U+DFFF 238 * map to their own implicit primary weights (for UTF-16), 239 * or TRUE if they map to CE(U+FFFD) (for UTF-8) 240 */ 241 virtual UBool forbidSurrogateCodePoints() const; 242 243 virtual void forwardNumCodePoints(int32_t num, UErrorCode &errorCode) = 0; 244 245 virtual void backwardNumCodePoints(int32_t num, UErrorCode &errorCode) = 0; 246 247 /** 248 * Returns the CE32 from the data trie. 249 * Normally the same as data->getCE32(), but overridden in the builder. 250 * Call this only when the faster data->getCE32() cannot be used. 251 */ 252 virtual uint32_t getDataCE32(UChar32 c) const; 253 254 virtual uint32_t getCE32FromBuilderData(uint32_t ce32, UErrorCode &errorCode); 255 256 void appendCEsFromCE32(const CollationData *d, UChar32 c, uint32_t ce32, 257 UBool forward, UErrorCode &errorCode); 258 259 // Main lookup trie of the data object. 260 const UTrie2 *trie; 261 const CollationData *data; 262 263 private: 264 int64_t nextCEFromCE32(const CollationData *d, UChar32 c, uint32_t ce32, 265 UErrorCode &errorCode); 266 267 uint32_t getCE32FromPrefix(const CollationData *d, uint32_t ce32, 268 UErrorCode &errorCode); 269 270 UChar32 nextSkippedCodePoint(UErrorCode &errorCode); 271 272 void backwardNumSkipped(int32_t n, UErrorCode &errorCode); 273 274 uint32_t nextCE32FromContraction( 275 const CollationData *d, uint32_t contractionCE32, 276 const UChar *p, uint32_t ce32, UChar32 c, 277 UErrorCode &errorCode); 278 279 uint32_t nextCE32FromDiscontiguousContraction( 280 const CollationData *d, UCharsTrie &suffixes, uint32_t ce32, 281 int32_t lookAhead, UChar32 c, 282 UErrorCode &errorCode); 283 284 /** 285 * Returns the previous CE when data->isUnsafeBackward(c, isNumeric). 286 */ 287 int64_t previousCEUnsafe(UChar32 c, UVector32 &offsets, UErrorCode &errorCode); 288 289 /** 290 * Turns a string of digits (bytes 0..9) 291 * into a sequence of CEs that will sort in numeric order. 292 * 293 * Starts from this ce32's digit value and consumes the following/preceding digits. 294 * The digits string must not be empty and must not have leading zeros. 295 */ 296 void appendNumericCEs(uint32_t ce32, UBool forward, UErrorCode &errorCode); 297 298 /** 299 * Turns 1..254 digits into a sequence of CEs. 300 * Called by appendNumericCEs() for each segment of at most 254 digits. 301 */ 302 void appendNumericSegmentCEs(const char *digits, int32_t length, UErrorCode &errorCode); 303 304 CEBuffer ceBuffer; 305 int32_t cesIndex; 306 307 SkippedState *skipped; 308 309 // Number of code points to read forward, or -1. 310 // Used as a forward iteration limit in previousCEUnsafe(). 311 int32_t numCpFwd; 312 // Numeric collation (CollationSettings::NUMERIC). 313 UBool isNumeric; 314 }; 315 316 U_NAMESPACE_END 317 318 #endif // !UCONFIG_NO_COLLATION 319 #endif // __COLLATIONITERATOR_H__ 320
