/*
*******************************************************************************
* 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 */