icuSources/i18n/sortkey.cpp

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