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) 1996-2012, International Business Machines Corporation and 6 * others. All Rights Reserved. 7 ******************************************************************************* 8 */ 9 //=============================================================================== 10 // 11 // File sortkey.cpp 12 // 13 // 14 // 15 // Created by: Helena Shih 16 // 17 // Modification History: 18 // 19 // Date Name Description 20 // 21 // 6/20/97 helena Java class name change. 22 // 6/23/97 helena Added comments to make code more readable. 23 // 6/26/98 erm Canged to use byte arrays instead of UnicodeString 24 // 7/31/98 erm hashCode: minimum inc should be 2 not 1, 25 // Cleaned up operator= 26 // 07/12/99 helena HPUX 11 CC port. 27 // 03/06/01 synwee Modified compareTo, to handle the result of 28 // 2 string similar in contents, but one is longer 29 // than the other 30 //=============================================================================== 31 32 #include "unicode/utypes.h" 33 34 #if !UCONFIG_NO_COLLATION 35 36 #include "unicode/sortkey.h" 37 #include "cmemory.h" 38 #include "uelement.h" 39 #include "ustr_imp.h" 40 41 U_NAMESPACE_BEGIN 42 43 // A hash code of kInvalidHashCode indicates that the hash code needs 44 // to be computed. A hash code of kEmptyHashCode is used for empty keys 45 // and for any key whose computed hash code is kInvalidHashCode. 46 static const int32_t kInvalidHashCode = 0; 47 static const int32_t kEmptyHashCode = 1; 48 // The "bogus hash code" replaces a separate fBogus flag. 49 static const int32_t kBogusHashCode = 2; 50 51 UOBJECT_DEFINE_RTTI_IMPLEMENTATION(CollationKey) 52 53 CollationKey::CollationKey() 54 : UObject(), fFlagAndLength(0), 55 fHashCode(kEmptyHashCode) 56 { 57 } 58 59 // Create a collation key from a bit array. 60 CollationKey::CollationKey(const uint8_t* newValues, int32_t count) 61 : UObject(), fFlagAndLength(count), 62 fHashCode(kInvalidHashCode) 63 { 64 if (count < 0 || (newValues == NULL && count != 0) || 65 (count > getCapacity() && reallocate(count, 0) == NULL)) { 66 setToBogus(); 67 return; 68 } 69 70 if (count > 0) { 71 uprv_memcpy(getBytes(), newValues, count); 72 } 73 } 74 75 CollationKey::CollationKey(const CollationKey& other) 76 : UObject(other), fFlagAndLength(other.getLength()), 77 fHashCode(other.fHashCode) 78 { 79 if (other.isBogus()) 80 { 81 setToBogus(); 82 return; 83 } 84 85 int32_t length = fFlagAndLength; 86 if (length > getCapacity() && reallocate(length, 0) == NULL) { 87 setToBogus(); 88 return; 89 } 90 91 if (length > 0) { 92 uprv_memcpy(getBytes(), other.getBytes(), length); 93 } 94 } 95 96 CollationKey::~CollationKey() 97 { 98 if(fFlagAndLength < 0) { uprv_free(fUnion.fFields.fBytes); } 99 } 100 101 uint8_t *CollationKey::reallocate(int32_t newCapacity, int32_t length) { 102 uint8_t *newBytes = static_cast<uint8_t *>(uprv_malloc(newCapacity)); 103 if(newBytes == NULL) { return NULL; } 104 if(length > 0) { 105 uprv_memcpy(newBytes, getBytes(), length); 106 } 107 if(fFlagAndLength < 0) { uprv_free(fUnion.fFields.fBytes); } 108 fUnion.fFields.fBytes = newBytes; 109 fUnion.fFields.fCapacity = newCapacity; 110 fFlagAndLength |= 0x80000000; 111 return newBytes; 112 } 113 114 void CollationKey::setLength(int32_t newLength) { 115 // U_ASSERT(newLength >= 0 && newLength <= getCapacity()); 116 fFlagAndLength = (fFlagAndLength & 0x80000000) | newLength; 117 fHashCode = kInvalidHashCode; 118 } 119 120 // set the key to an empty state 121 CollationKey& 122 CollationKey::reset() 123 { 124 fFlagAndLength &= 0x80000000; 125 fHashCode = kEmptyHashCode; 126 127 return *this; 128 } 129 130 // set the key to a "bogus" or invalid state 131 CollationKey& 132 CollationKey::setToBogus() 133 { 134 fFlagAndLength &= 0x80000000; 135 fHashCode = kBogusHashCode; 136 137 return *this; 138 } 139 140 UBool 141 CollationKey::operator==(const CollationKey& source) const 142 { 143 return getLength() == source.getLength() && 144 (this == &source || 145 uprv_memcmp(getBytes(), source.getBytes(), getLength()) == 0); 146 } 147 148 const CollationKey& 149 CollationKey::operator=(const CollationKey& other) 150 { 151 if (this != &other) 152 { 153 if (other.isBogus()) 154 { 155 return setToBogus(); 156 } 157 158 int32_t length = other.getLength(); 159 if (length > getCapacity() && reallocate(length, 0) == NULL) { 160 return setToBogus(); 161 } 162 if (length > 0) { 163 uprv_memcpy(getBytes(), other.getBytes(), length); 164 } 165 fFlagAndLength = (fFlagAndLength & 0x80000000) | length; 166 fHashCode = other.fHashCode; 167 } 168 169 return *this; 170 } 171 172 // Bitwise comparison for the collation keys. 173 Collator::EComparisonResult 174 CollationKey::compareTo(const CollationKey& target) const 175 { 176 UErrorCode errorCode = U_ZERO_ERROR; 177 return static_cast<Collator::EComparisonResult>(compareTo(target, errorCode)); 178 } 179 180 // Bitwise comparison for the collation keys. 181 UCollationResult 182 CollationKey::compareTo(const CollationKey& target, UErrorCode &status) const 183 { 184 if(U_SUCCESS(status)) { 185 const uint8_t *src = getBytes(); 186 const uint8_t *tgt = target.getBytes(); 187 188 // are we comparing the same string 189 if (src == tgt) 190 return UCOL_EQUAL; 191 192 UCollationResult result; 193 194 // are we comparing different lengths? 195 int32_t minLength = getLength(); 196 int32_t targetLength = target.getLength(); 197 if (minLength < targetLength) { 198 result = UCOL_LESS; 199 } else if (minLength == targetLength) { 200 result = UCOL_EQUAL; 201 } else { 202 minLength = targetLength; 203 result = UCOL_GREATER; 204 } 205 206 if (minLength > 0) { 207 int diff = uprv_memcmp(src, tgt, minLength); 208 if (diff > 0) { 209 return UCOL_GREATER; 210 } 211 else 212 if (diff < 0) { 213 return UCOL_LESS; 214 } 215 } 216 217 return result; 218 } else { 219 return UCOL_EQUAL; 220 } 221 } 222 223 #ifdef U_USE_COLLATION_KEY_DEPRECATES 224 // Create a copy of the byte array. 225 uint8_t* 226 CollationKey::toByteArray(int32_t& count) const 227 { 228 uint8_t *result = (uint8_t*) uprv_malloc( sizeof(uint8_t) * fCount ); 229 230 if (result == NULL) 231 { 232 count = 0; 233 } 234 else 235 { 236 count = fCount; 237 if (count > 0) { 238 uprv_memcpy(result, fBytes, fCount); 239 } 240 } 241 242 return result; 243 } 244 #endif 245 246 static int32_t 247 computeHashCode(const uint8_t *key, int32_t length) { 248 const char *s = reinterpret_cast<const char *>(key); 249 int32_t hash; 250 if (s == NULL || length == 0) { 251 hash = kEmptyHashCode; 252 } else { 253 hash = ustr_hashCharsN(s, length); 254 if (hash == kInvalidHashCode || hash == kBogusHashCode) { 255 hash = kEmptyHashCode; 256 } 257 } 258 return hash; 259 } 260 261 int32_t 262 CollationKey::hashCode() const 263 { 264 // (Cribbed from UnicodeString) 265 // We cache the hashCode; when it becomes invalid, due to any change to the 266 // string, we note this by setting it to kInvalidHashCode. [LIU] 267 268 // Note: This method is semantically const, but physically non-const. 269 270 if (fHashCode == kInvalidHashCode) 271 { 272 fHashCode = computeHashCode(getBytes(), getLength()); 273 } 274 275 return fHashCode; 276 } 277 278 U_NAMESPACE_END 279 280 U_CAPI int32_t U_EXPORT2 281 ucol_keyHashCode(const uint8_t *key, 282 int32_t length) 283 { 284 return icu::computeHashCode(key, length); 285 } 286 287 #endif /* #if !UCONFIG_NO_COLLATION */ 288