Check in the pristine copy of ICU 4.6...

icu46/source/i18n/sortkey.cpp

+/*
+*******************************************************************************
+* Copyright (C) 1996-2006, 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 "uhash.h"
+
+U_NAMESPACE_BEGIN
+
+// A hash code of kInvalidHashCode indicates that the has 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.
+#define kInvalidHashCode ((int32_t)0)
+#define kEmptyHashCode ((int32_t)1)
+
+UOBJECT_DEFINE_RTTI_IMPLEMENTATION(CollationKey)
+
+CollationKey::CollationKey()
+    : UObject(), fBogus(FALSE), fCount(0), fCapacity(0),
+      fHashCode(kEmptyHashCode), fBytes(NULL)
+{
+}
+
+// Create a collation key from a bit array.
+CollationKey::CollationKey(const uint8_t* newValues, int32_t count)
+    : UObject(), fBogus(FALSE), fCount(count), fCapacity(count),
+      fHashCode(kInvalidHashCode)
+{
+    fBytes = (uint8_t *)uprv_malloc(count);
+
+    if (fBytes == NULL)
+    {
+        setToBogus();
+        return;
+    }
+
+    uprv_memcpy(fBytes, newValues, fCount);
+}
+
+CollationKey::CollationKey(const CollationKey& other)
+: UObject(other), fBogus(FALSE), fCount(other.fCount), fCapacity(other.fCapacity),
+  fHashCode(other.fHashCode), fBytes(NULL)
+{
+    if (other.fBogus)
+    {
+        setToBogus();
+        return;
+    }
+
+    fBytes = (uint8_t *)uprv_malloc(fCapacity);
+
+    if (fBytes == NULL)
+    {
+        setToBogus();
+        return;
+    }
+
+    uprv_memcpy(fBytes, other.fBytes, other.fCount);
+    if(fCapacity>fCount) {
+        uprv_memset(fBytes+fCount, 0, fCapacity-fCount);
+    }
+}
+
+CollationKey::~CollationKey()
+{
+        uprv_free(fBytes);
+}
+
+void CollationKey::adopt(uint8_t *values, int32_t count) {
+    if(fBytes != NULL) {
+        uprv_free(fBytes);
+    }
+    fBogus = FALSE;
+    fBytes = values;
+    fCount = count;
+    fCapacity = count;
+    fHashCode = kInvalidHashCode;
+}
+
+// set the key to an empty state
+CollationKey&
+CollationKey::reset()
+{
+    fCount = 0;
+    fBogus = FALSE;
+    fHashCode = kEmptyHashCode;
+
+    return *this;
+}
+
+// set the key to a "bogus" or invalid state
+CollationKey&
+CollationKey::setToBogus()
+{
+    uprv_free(fBytes);
+    fBytes = NULL;
+
+    fCapacity = 0;
+    fCount = 0;
+    fHashCode = kInvalidHashCode;
+
+    return *this;
+}
+
+UBool
+CollationKey::operator==(const CollationKey& source) const
+{
+    return (this->fCount == source.fCount &&
+            (this->fBytes == source.fBytes ||
+             uprv_memcmp(this->fBytes, source.fBytes, this->fCount) == 0));
+}
+
+const CollationKey&
+CollationKey::operator=(const CollationKey& other)
+{
+    if (this != &other)
+    {
+        if (other.isBogus())
+        {
+            return setToBogus();
+        }
+
+        if (other.fBytes != NULL)
+        {
+            ensureCapacity(other.fCount);
+
+            if (isBogus())
+            {
+                return *this;
+            }
+
+            fHashCode = other.fHashCode;
+            uprv_memcpy(fBytes, other.fBytes, fCount);
+        }
+        else
+        {
+            fCount = 0;
+            fBogus = FALSE;
+            fHashCode = kEmptyHashCode;
+        }
+    }
+
+    return *this;
+}
+
+// Bitwise comparison for the collation keys.
+// NOTE: this is somewhat messy 'cause we can't count
+// on memcmp returning the exact values which match
+// Collator::EComparisonResult
+Collator::EComparisonResult
+CollationKey::compareTo(const CollationKey& target) const
+{
+    uint8_t *src = this->fBytes;
+    uint8_t *tgt = target.fBytes;
+
+    // are we comparing the same string
+    if (src == tgt)
+        return  Collator::EQUAL;
+
+        /*
+        int count = (this->fCount < target.fCount) ? this->fCount : target.fCount;
+        if (count == 0)
+        {
+        // If count is 0, at least one of the keys is empty.
+        // An empty key is always LESS than a non-empty one
+        // and EQUAL to another empty
+        if (this->fCount < target.fCount)
+        {
+        return Collator::LESS;
+        }
+
+          if (this->fCount > target.fCount)
+          {
+          return Collator::GREATER;
+          }
+          return Collator::EQUAL;
+          }
+    */
+
+    int                         minLength;
+    Collator::EComparisonResult result;
+
+    // are we comparing different lengths?
+    if (this->fCount != target.fCount) {
+        if (this->fCount < target.fCount) {
+            minLength = this->fCount;
+            result    =  Collator::LESS;
+        }
+        else {
+            minLength = target.fCount;
+            result    =  Collator::GREATER;
+        }
+    }
+    else {
+        minLength = target.fCount;
+        result    =  Collator::EQUAL;
+    }
+
+    if (minLength > 0) {
+        int diff = uprv_memcmp(src, tgt, minLength);
+        if (diff > 0) {
+            return Collator::GREATER;
+        }
+        else
+            if (diff < 0) {
+                return Collator::LESS;
+            }
+    }
+
+    return result;
+    /*
+    if (result < 0)
+    {
+    return Collator::LESS;
+    }
+
+      if (result > 0)
+      {
+      return Collator::GREATER;
+      }
+      return Collator::EQUAL;
+    */
+}
+
+// Bitwise comparison for the collation keys.
+UCollationResult
+CollationKey::compareTo(const CollationKey& target, UErrorCode &status) const
+{
+  if(U_SUCCESS(status)) {
+    uint8_t *src = this->fBytes;
+    uint8_t *tgt = target.fBytes;
+
+    // are we comparing the same string
+    if (src == tgt)
+        return  UCOL_EQUAL;
+
+    int                         minLength;
+    UCollationResult result;
+
+    // are we comparing different lengths?
+    if (this->fCount != target.fCount) {
+        if (this->fCount < target.fCount) {
+            minLength = this->fCount;
+            result    =  UCOL_LESS;
+        }
+        else {
+            minLength = target.fCount;
+            result    =  UCOL_GREATER;
+        }
+    }
+    else {
+        minLength = target.fCount;
+        result    =  UCOL_EQUAL;
+    }
+
+    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;
+  }
+}
+
+CollationKey&
+CollationKey::ensureCapacity(int32_t newSize)
+{
+    if (fCapacity < newSize)
+    {
+        uprv_free(fBytes);
+
+        fBytes = (uint8_t *)uprv_malloc(newSize);
+
+        if (fBytes == NULL)
+        {
+            return setToBogus();
+        }
+
+        uprv_memset(fBytes, 0, fCapacity);
+        fCapacity = newSize;
+    }
+
+    fBogus = FALSE;
+    fCount = newSize;
+    fHashCode = kInvalidHashCode;
+
+    return *this;
+}
+
+#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;
+        uprv_memcpy(result, fBytes, fCount);
+    }
+
+    return result;
+}
+#endif
+
+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)
+    {
+        UHashTok key;
+        key.pointer = fBytes;
+        ((CollationKey *)this)->fHashCode = uhash_hashChars(key);
+#if 0
+        // We compute the hash by iterating sparsely over 64 (at most) characters
+        // spaced evenly through the string.  For each character, we multiply the
+        // previous hash value by a prime number and add the new character in,
+        // in the manner of a additive linear congruential random number generator,
+        // thus producing a pseudorandom deterministic value which should be well
+        // distributed over the output range. [LIU]
+        const uint8_t   *p = fBytes, *limit = fBytes + fCount;
+        int32_t         inc = (fCount >= 256) ? fCount/128 : 2; // inc = max(fSize/64, 1);
+        int32_t         hash = 0;
+
+        while (p < limit)
+        {
+            hash = ( hash * 37 ) + ((p[0] << 8) + p[1]);
+            p += inc;
+        }
+
+        // If we happened to get kInvalidHashCode, replace it with kEmptyHashCode
+        if (hash == kInvalidHashCode)
+        {
+            hash = kEmptyHashCode;
+        }
+
+        ((CollationKey *)this)->fHashCode = hash; // cast away const
+#endif
+    }
+
+    return fHashCode;
+}
+
+U_NAMESPACE_END
+
+U_CAPI int32_t U_EXPORT2
+ucol_keyHashCode(const uint8_t *key, 
+                       int32_t  length)
+{
+    U_NAMESPACE_QUALIFIER CollationKey newKey(key, length);
+    return newKey.hashCode();
+}
+
+#endif /* #if !UCONFIG_NO_COLLATION */