The Tor Browser / file revision

 /*

 *******************************************************************************

 * Copyright (C) 1996-2012, International Business Machines Corporation and

 * others. All Rights Reserved.

 *******************************************************************************

 */

 //===============================================================================

 //

 // File sortkey.cpp

 //

 //

 //

 // Created by: Helena Shih

 //

 // Modification History:

 //

 //  Date         Name          Description

 //

 //  6/20/97      helena        Java class name change.

 //  6/23/97      helena        Added comments to make code more readable.

 //  6/26/98      erm           Canged to use byte arrays instead of UnicodeString

 //  7/31/98      erm           hashCode: minimum inc should be 2 not 1,

 //                             Cleaned up operator=

 // 07/12/99      helena        HPUX 11 CC port.

 // 03/06/01      synwee        Modified compareTo, to handle the result of

 //                             2 string similar in contents, but one is longer

 //                             than the other

 //===============================================================================

 #include "unicode/utypes.h"

 #if !UCONFIG_NO_COLLATION

 #include "unicode/sortkey.h"

 #include "cmemory.h"

 #include "uelement.h"

 #include "ustr_imp.h"

 U_NAMESPACE_BEGIN

 // A hash code of kInvalidHashCode indicates that the hash code needs

 // to be computed. A hash code of kEmptyHashCode is used for empty keys

 // and for any key whose computed hash code is kInvalidHashCode.

 static const int32_t kInvalidHashCode = 0;

 static const int32_t kEmptyHashCode = 1;

 // The "bogus hash code" replaces a separate fBogus flag.

 static const int32_t kBogusHashCode = 2;

 UOBJECT_DEFINE_RTTI_IMPLEMENTATION(CollationKey)

 CollationKey::CollationKey()

     : UObject(), fFlagAndLength(0),

       fHashCode(kEmptyHashCode)

 {

 }

 // Create a collation key from a bit array.

 CollationKey::CollationKey(const uint8_t* newValues, int32_t count)

     : UObject(), fFlagAndLength(count),

       fHashCode(kInvalidHashCode)

 {

     if (count < 0 || (newValues == NULL && count != 0) ||

             (count > getCapacity() && reallocate(count, 0) == NULL)) {

         setToBogus();

         return;

     }

     if (count > 0) {

         uprv_memcpy(getBytes(), newValues, count);

     }

 }

 CollationKey::CollationKey(const CollationKey& other)

     : UObject(other), fFlagAndLength(other.getLength()),

       fHashCode(other.fHashCode)

 {

     if (other.isBogus())

     {

         setToBogus();

         return;

     }

     int32_t length = fFlagAndLength;

     if (length > getCapacity() && reallocate(length, 0) == NULL) {

         setToBogus();

         return;

     }

     if (length > 0) {

         uprv_memcpy(getBytes(), other.getBytes(), length);

     }

 }

 CollationKey::~CollationKey()

 {

     if(fFlagAndLength < 0) { uprv_free(fUnion.fFields.fBytes); }

 }

 uint8_t *CollationKey::reallocate(int32_t newCapacity, int32_t length) {

     uint8_t *newBytes = static_cast<uint8_t *>(uprv_malloc(newCapacity));

     if(newBytes == NULL) { return NULL; }

     if(length > 0) {

         uprv_memcpy(newBytes, getBytes(), length);

     }

     if(fFlagAndLength < 0) { uprv_free(fUnion.fFields.fBytes); }

     fUnion.fFields.fBytes = newBytes;

     fUnion.fFields.fCapacity = newCapacity;

     fFlagAndLength |= 0x80000000;

     return newBytes;

 }

 void CollationKey::setLength(int32_t newLength) {

     // U_ASSERT(newLength >= 0 && newLength <= getCapacity());

     fFlagAndLength = (fFlagAndLength & 0x80000000) | newLength;

     fHashCode = kInvalidHashCode;

 }

 // set the key to an empty state

 CollationKey&

 CollationKey::reset()

 {

     fFlagAndLength &= 0x80000000;

     fHashCode = kEmptyHashCode;

     return *this;

 }

 // set the key to a "bogus" or invalid state

 CollationKey&

 CollationKey::setToBogus()

 {

     fFlagAndLength &= 0x80000000;

     fHashCode = kBogusHashCode;

     return *this;

 }

 UBool

 CollationKey::operator==(const CollationKey& source) const

 {

     return getLength() == source.getLength() &&

             (this == &source ||

              uprv_memcmp(getBytes(), source.getBytes(), getLength()) == 0);

 }

 const CollationKey&

 CollationKey::operator=(const CollationKey& other)

 {

     if (this != &other)

     {

         if (other.isBogus())

         {

             return setToBogus();

         }

         int32_t length = other.getLength();

         if (length > getCapacity() && reallocate(length, 0) == NULL) {

             return setToBogus();

         }

         if (length > 0) {

             uprv_memcpy(getBytes(), other.getBytes(), length);

         }

         fFlagAndLength = (fFlagAndLength & 0x80000000) | length;

         fHashCode = other.fHashCode;

     }

     return *this;

 }

 // Bitwise comparison for the collation keys.

 Collator::EComparisonResult

 CollationKey::compareTo(const CollationKey& target) const

 {

     UErrorCode errorCode = U_ZERO_ERROR;

     return static_cast<Collator::EComparisonResult>(compareTo(target, errorCode));

 }

 // Bitwise comparison for the collation keys.

 UCollationResult

 CollationKey::compareTo(const CollationKey& target, UErrorCode &status) const

 {

   if(U_SUCCESS(status)) {

     const uint8_t *src = getBytes();

     const uint8_t *tgt = target.getBytes();

     // are we comparing the same string

     if (src == tgt)

         return  UCOL_EQUAL;

     UCollationResult result;

     // are we comparing different lengths?

     int32_t minLength = getLength();

     int32_t targetLength = target.getLength();

     if (minLength < targetLength) {

         result = UCOL_LESS;

     } else if (minLength == targetLength) {

         result = UCOL_EQUAL;

     } else {

         minLength = targetLength;

         result = UCOL_GREATER;

     }

     if (minLength > 0) {

         int diff = uprv_memcmp(src, tgt, minLength);

         if (diff > 0) {

             return UCOL_GREATER;

         }

         else

             if (diff < 0) {

                 return UCOL_LESS;

             }

     }

     return result;

   } else {

     return UCOL_EQUAL;

   }

 }

 #ifdef U_USE_COLLATION_KEY_DEPRECATES

 // Create a copy of the byte array.

 uint8_t*

 CollationKey::toByteArray(int32_t& count) const

 {

     uint8_t *result = (uint8_t*) uprv_malloc( sizeof(uint8_t) * fCount );

     if (result == NULL)

     {

         count = 0;

     }

     else

     {

         count = fCount;

         if (count > 0) {

             uprv_memcpy(result, fBytes, fCount);

         }

     }

     return result;

 }

 #endif

 static int32_t

 computeHashCode(const uint8_t *key, int32_t  length) {

     const char *s = reinterpret_cast<const char *>(key);

     int32_t hash;

     if (s == NULL || length == 0) {

         hash = kEmptyHashCode;

     } else {

         hash = ustr_hashCharsN(s, length);

         if (hash == kInvalidHashCode || hash == kBogusHashCode) {

             hash = kEmptyHashCode;

         }

     }

     return hash;

 }

 int32_t

 CollationKey::hashCode() const

 {

     // (Cribbed from UnicodeString)

     // We cache the hashCode; when it becomes invalid, due to any change to the

     // string, we note this by setting it to kInvalidHashCode. [LIU]

     // Note: This method is semantically const, but physically non-const.

     if (fHashCode == kInvalidHashCode)

     {

         fHashCode = computeHashCode(getBytes(), getLength());

     }

     return fHashCode;

 }

 U_NAMESPACE_END

 U_CAPI int32_t U_EXPORT2

 ucol_keyHashCode(const uint8_t *key, 

                        int32_t  length)

 {

     return icu::computeHashCode(key, length);

 }

 #endif /* #if !UCONFIG_NO_COLLATION */