source/i18n/sortkey.cpp

/*
*****************************************************************************************
*                                                                                       *
* COPYRIGHT:                                                                            *
*   (C) Copyright Taligent, Inc.,  1996                                                 *
*   (C) Copyright International Business Machines Corporation,  1996-1998               *
*   Licensed Material - Program-Property of IBM - All Rights Reserved.                  *
*   US Government Users Restricted Rights - Use, duplication, or disclosure             *
*   restricted by GSA ADP Schedule Contract with IBM Corp.                              *
*                                                                                       *
*****************************************************************************************
*/
//===============================================================================
//
// 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.
//===============================================================================

#ifndef _SORTKEY
#include "sortkey.h"
#endif

#ifndef _CMEMORY
#include "cmemory.h"
#endif

// 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.
const int32_t CollationKey::kInvalidHashCode = 0;
const int32_t CollationKey::kEmptyHashCode = 1;

CollationKey::CollationKey()
    : fCount(0), fCapacity(0), fBogus(FALSE),
      fHashCode(kEmptyHashCode), fBytes(NULL)
{
}

// Create a collation key from a bit array.
CollationKey::CollationKey(const uint8_t* newValues, int32_t count)
    : fCount(count), fCapacity(count), fBogus(FALSE),
      fHashCode(kInvalidHashCode)
{
    fBytes = new uint8_t[count];

    if (fBytes == NULL)
    {
        setToBogus();
        return;
    }

    ::icu_memset(fBytes, 0, fCount);
    ::icu_memcpy(fBytes, newValues, fCount);
}

CollationKey::CollationKey(const UnicodeString& value)
{
    copyUnicodeString(value);
}

CollationKey::CollationKey(const CollationKey& other)
    : fCount(other.fCount), fCapacity(other.fCapacity), fBogus(FALSE),
      fHashCode(other.fHashCode), fBytes(NULL)
{
    if (other.fBogus)
    {
        setToBogus();
        return;
    }

    fBytes = new uint8_t[fCapacity];

    if (fBytes == NULL)
    {
        setToBogus();
        return;
    }

    ::icu_memset(fBytes, 0, fCapacity);
    ::icu_memcpy(fBytes, other.fBytes, other.fCount);
}

CollationKey::~CollationKey()
{
    delete[] fBytes;
}

// 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()
{
    delete[] fBytes;
    fBytes = NULL;

    fCapacity = 0;
    fCount = 0;
    fHashCode = kInvalidHashCode;

    return *this;
}

bool_t
CollationKey::operator==(const CollationKey& source) const
{
    return (this->fCount == source.fCount &&
            (this->fBytes == source.fBytes ||
             ::icu_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;
            ::icu_memcpy(fBytes, other.fBytes, fCount);
        }
        else
        {
            reset();
        }
    }

    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
{
    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 result = ::icu_memcmp(this->fBytes, target.fBytes, count);

    if (result < 0)
    {
        return Collator::LESS;
    }

    if (result > 0)
    {
        return Collator::GREATER;
    }

    return Collator::EQUAL;
}

CollationKey&
CollationKey::ensureCapacity(int32_t newSize)
{
    if (fCapacity < newSize)
    {
        delete[] fBytes;

        fBytes = new uint8_t[newSize];

        if (fBytes == NULL)
        {
            return setToBogus();
        }

        ::icu_memset(fBytes, 0, fCapacity);
        fCapacity = newSize;
    }

    fBogus = FALSE;
    fCount = newSize;
    fHashCode = kInvalidHashCode;

    return *this;
}

int32_t
CollationKey::storeUnicodeString(int32_t cursor, const UnicodeString &value)
{
    UTextOffset input = 0;
    int32_t charCount = value.size();

    while (input < charCount)
    {
        cursor = storeBytes(cursor, value[input++]);
    }

    return storeBytes(cursor, 0);
}

CollationKey&
CollationKey::copyUnicodeString(const UnicodeString &value)
{
    int32_t charCount = value.size();

    // We allocate enough space for two null bytes at the end.
    ensureCapacity((charCount * 2) + 2);

    if (isBogus())
    {
        return *this;
    }

    storeUnicodeString(0, value);

    return *this;
}

void
CollationKey::reverseBytes(UTextOffset from, UTextOffset to)
{
    uint8_t *left  = &fBytes[from];
    uint8_t *right = &fBytes[to - 2];

    while (left < right)
    {
        uint8_t swap[2];

        swap[0] = right[0];
        swap[1] = right[1]; 

        right[0] = left[0];
        right[1] = left[1];

        left[0]  = swap[0];
        left[1]  = swap[1];
        
        left += 2;
        right -= 2;
    }
}
        
// Create a copy of the byte array.
uint8_t*
CollationKey::toByteArray(int32_t& count) const
{
    uint8_t *result = new uint8_t[fCount];
    
    if (result == NULL)
    {
        count = 0;
    }
    else
    {
        count = fCount;
        ::icu_memset(result, 0, fCount);
        ::icu_memcpy(result, fBytes, fCount);
    }

    return result;  
}

uint16_t*
CollationKey::copyValues(int32_t &size) const
{
    uint16_t *result;
    uint8_t *input = fBytes;
    UTextOffset output = 0;

    size = fCount / 2;
    result = new uint16_t[size];

    if (result == NULL)
    {
        size = 0;
    }
    else
    {
        while (output < size)
        {
            result[output] = (input[0] << 8) | input[1];
            output += 1;
            input += 2;
        }
    }

    return result;
}

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)
    {
        // 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
    }

    return fHashCode;
}