source/i18n/ucoleitr.cpp

/*
******************************************************************************
*   Copyright (C) 2001-2010, International Business Machines
*   Corporation and others.  All Rights Reserved.
******************************************************************************
*
* File ucoleitr.cpp
*
* Modification History:
*
* Date        Name        Description
* 02/15/2001  synwee      Modified all methods to process its own function
*                         instead of calling the equivalent c++ api (coleitr.h)
******************************************************************************/

#include "unicode/utypes.h"

#if !UCONFIG_NO_COLLATION

#include "unicode/ucoleitr.h"
#include "unicode/ustring.h"
#include "unicode/sortkey.h"
#include "unicode/uobject.h"
#include "ucol_imp.h"
#include "cmemory.h"

U_NAMESPACE_USE

#define BUFFER_LENGTH             100

#define DEFAULT_BUFFER_SIZE 16
#define BUFFER_GROW 8

#define ARRAY_SIZE(array) (sizeof array / sizeof array[0])

#define ARRAY_COPY(dst, src, count) uprv_memcpy((void *) (dst), (void *) (src), (count) * sizeof (src)[0])

#define NEW_ARRAY(type, count) (type *) uprv_malloc((count) * sizeof(type))

#define GROW_ARRAY(array, newSize) uprv_realloc((void *) (array), (newSize) * sizeof (array)[0])

#define DELETE_ARRAY(array) uprv_free((void *) (array))

typedef struct collIterate collIterator;

struct RCEI
{
    uint32_t ce;
    int32_t  low;
    int32_t  high;
};

U_NAMESPACE_BEGIN

struct RCEBuffer
{
    RCEI    defaultBuffer[DEFAULT_BUFFER_SIZE];
    RCEI   *buffer;
    int32_t bufferIndex;
    int32_t bufferSize;

    RCEBuffer();
    ~RCEBuffer();

    UBool empty() const;
    void  put(uint32_t ce, int32_t ixLow, int32_t ixHigh);
    const RCEI *get();
};

RCEBuffer::RCEBuffer()
{
    buffer = defaultBuffer;
    bufferIndex = 0;
    bufferSize = DEFAULT_BUFFER_SIZE;
}

RCEBuffer::~RCEBuffer()
{
    if (buffer != defaultBuffer) {
        DELETE_ARRAY(buffer);
    }
}

UBool RCEBuffer::empty() const
{
    return bufferIndex <= 0;
}

void RCEBuffer::put(uint32_t ce, int32_t ixLow, int32_t ixHigh)
{
    if (bufferIndex >= bufferSize) {
        RCEI *newBuffer = NEW_ARRAY(RCEI, bufferSize + BUFFER_GROW);

        ARRAY_COPY(newBuffer, buffer, bufferSize);

        if (buffer != defaultBuffer) {
            DELETE_ARRAY(buffer);
        }

        buffer = newBuffer;
        bufferSize += BUFFER_GROW;
    }

    buffer[bufferIndex].ce   = ce;
    buffer[bufferIndex].low  = ixLow;
    buffer[bufferIndex].high = ixHigh;

    bufferIndex += 1;
}

const RCEI *RCEBuffer::get()
{
    if (bufferIndex > 0) {
     return &buffer[--bufferIndex];
    }

    return NULL;
}

struct PCEI
{
    uint64_t ce;
    int32_t  low;
    int32_t  high;
};

struct PCEBuffer
{
    PCEI    defaultBuffer[DEFAULT_BUFFER_SIZE];
    PCEI   *buffer;
    int32_t bufferIndex;
    int32_t bufferSize;

    PCEBuffer();
    ~PCEBuffer();

    void  reset();
    UBool empty() const;
    void  put(uint64_t ce, int32_t ixLow, int32_t ixHigh);
    const PCEI *get();
};

PCEBuffer::PCEBuffer()
{
    buffer = defaultBuffer;
    bufferIndex = 0;
    bufferSize = DEFAULT_BUFFER_SIZE;
}

PCEBuffer::~PCEBuffer()
{
    if (buffer != defaultBuffer) {
        DELETE_ARRAY(buffer);
    }
}

void PCEBuffer::reset()
{
    bufferIndex = 0;
}

UBool PCEBuffer::empty() const
{
    return bufferIndex <= 0;
}

void PCEBuffer::put(uint64_t ce, int32_t ixLow, int32_t ixHigh)
{
    if (bufferIndex >= bufferSize) {
        PCEI *newBuffer = NEW_ARRAY(PCEI, bufferSize + BUFFER_GROW);

        ARRAY_COPY(newBuffer, buffer, bufferSize);

        if (buffer != defaultBuffer) {
            DELETE_ARRAY(buffer);
        }

        buffer = newBuffer;
        bufferSize += BUFFER_GROW;
    }

    buffer[bufferIndex].ce   = ce;
    buffer[bufferIndex].low  = ixLow;
    buffer[bufferIndex].high = ixHigh;

    bufferIndex += 1;
}

const PCEI *PCEBuffer::get()
{
    if (bufferIndex > 0) {
     return &buffer[--bufferIndex];
    }

    return NULL;
}

/*
 * This inherits from UObject so that
 * it can be allocated by new and the
 * constructor for PCEBuffer is called.
 */
struct UCollationPCE : public UObject
{
    PCEBuffer          pceBuffer;
    UCollationStrength strength;
    UBool              toShift;
    UBool              isShifted;
    uint32_t           variableTop;

    UCollationPCE(UCollationElements *elems);
    ~UCollationPCE();

    void init(const UCollator *coll);

    virtual UClassID getDynamicClassID() const;
    static UClassID getStaticClassID();
};

UOBJECT_DEFINE_RTTI_IMPLEMENTATION(UCollationPCE)

UCollationPCE::UCollationPCE(UCollationElements *elems)
{
    init(elems->iteratordata_.coll);
}

void UCollationPCE::init(const UCollator *coll)
{
    UErrorCode status = U_ZERO_ERROR;

    strength    = ucol_getStrength(coll);
    toShift     = ucol_getAttribute(coll, UCOL_ALTERNATE_HANDLING, &status) == UCOL_SHIFTED;
    isShifted   = FALSE;
    variableTop = coll->variableTopValue << 16;
}

UCollationPCE::~UCollationPCE()
{
    // nothing to do
}


U_NAMESPACE_END


inline uint64_t processCE(UCollationElements *elems, uint32_t ce)
{
    uint64_t primary = 0, secondary = 0, tertiary = 0, quaternary = 0;

    // This is clean, but somewhat slow...
    // We could apply the mask to ce and then
    // just get all three orders...
    switch(elems->pce->strength) {
    default:
        tertiary = ucol_tertiaryOrder(ce);
        /* note fall-through */

    case UCOL_SECONDARY:
        secondary = ucol_secondaryOrder(ce);
        /* note fall-through */

    case UCOL_PRIMARY:
        primary = ucol_primaryOrder(ce);
    }

    // **** This should probably handle continuations too.  ****
    // **** That means that we need 24 bits for the primary ****
    // **** instead of the 16 that we're currently using.   ****
    // **** So we can lay out the 64 bits as: 24.12.12.16.  ****
    // **** Another complication with continuations is that ****
    // **** the *second* CE is marked as a continuation, so ****
    // **** we always have to peek ahead to know how long   ****
    // **** the primary is...                               ****
    if ((elems->pce->toShift && elems->pce->variableTop > ce && primary != 0)
                || (elems->pce->isShifted && primary == 0)) {

        if (primary == 0) {
            return UCOL_IGNORABLE;
        }

        if (elems->pce->strength >= UCOL_QUATERNARY) {
            quaternary = primary;
        }

        primary = secondary = tertiary = 0;
        elems->pce->isShifted = TRUE;
    } else {
        if (elems->pce->strength >= UCOL_QUATERNARY) {
            quaternary = 0xFFFF;
        }

        elems->pce->isShifted = FALSE;
    }

    return primary << 48 | secondary << 32 | tertiary << 16 | quaternary;
}

U_CAPI void U_EXPORT2
uprv_init_pce(const UCollationElements *elems)
{
    if (elems->pce != NULL) {
        elems->pce->init(elems->iteratordata_.coll);
    }
}


/* public methods ---------------------------------------------------- */

U_CAPI UCollationElements* U_EXPORT2
ucol_openElements(const UCollator  *coll,
                  const UChar      *text,
                        int32_t    textLength,
                        UErrorCode *status)
{
    if (U_FAILURE(*status)) {
        return NULL;
    }

    UCollationElements *result = new UCollationElements;
    if (result == NULL) {
        *status = U_MEMORY_ALLOCATION_ERROR;
        return NULL;
    }

    result->reset_ = TRUE;
    result->isWritable = FALSE;
    result->pce = NULL;

    if (text == NULL) {
        textLength = 0;
    }
    uprv_init_collIterate(coll, text, textLength, &result->iteratordata_, status);

    return result;
}


U_CAPI void U_EXPORT2
ucol_closeElements(UCollationElements *elems)
{
	if (elems != NULL) {
	  collIterate *ci = &elems->iteratordata_;

	  if (ci->extendCEs) {
		  uprv_free(ci->extendCEs);
	  }

	  if (ci->offsetBuffer) {
		  uprv_free(ci->offsetBuffer);
	  }

	  if (elems->isWritable && elems->iteratordata_.string != NULL)
	  {
		uprv_free((UChar *)elems->iteratordata_.string);
	  }

	  if (elems->pce != NULL) {
		  delete elems->pce;
	  }

	  delete elems;
	}
}

U_CAPI void U_EXPORT2
ucol_reset(UCollationElements *elems)
{
    collIterate *ci = &(elems->iteratordata_);
    elems->reset_   = TRUE;
    ci->pos         = ci->string;
    if ((ci->flags & UCOL_ITER_HASLEN) == 0 || ci->endp == NULL) {
        ci->endp      = ci->string + u_strlen(ci->string);
    }
    ci->CEpos       = ci->toReturn = ci->CEs;
    ci->flags       = (ci->flags & UCOL_FORCE_HAN_IMPLICIT) | UCOL_ITER_HASLEN;
    if (ci->coll->normalizationMode == UCOL_ON) {
        ci->flags |= UCOL_ITER_NORM;
    }

    ci->writableBuffer.remove();
    ci->fcdPosition = NULL;

  //ci->offsetReturn = ci->offsetStore = NULL;
	ci->offsetRepeatCount = ci->offsetRepeatValue = 0;
}

U_CAPI void U_EXPORT2
ucol_forceHanImplicit(UCollationElements *elems, UErrorCode *status)
{
    if (U_FAILURE(*status)) {
        return;
    }

    if (elems == NULL) {
        *status = U_ILLEGAL_ARGUMENT_ERROR;
        return;
    }

    elems->iteratordata_.flags |= UCOL_FORCE_HAN_IMPLICIT;
}

U_CAPI int32_t U_EXPORT2
ucol_next(UCollationElements *elems,
          UErrorCode         *status)
{
    int32_t result;
    if (U_FAILURE(*status)) {
        return UCOL_NULLORDER;
    }

    elems->reset_ = FALSE;

    result = (int32_t)ucol_getNextCE(elems->iteratordata_.coll,
                                     &elems->iteratordata_,
                                     status);

    if (result == UCOL_NO_MORE_CES) {
        result = UCOL_NULLORDER;
    }
    return result;
}

U_CAPI int64_t U_EXPORT2
ucol_nextProcessed(UCollationElements *elems,
                   int32_t            *ixLow,
                   int32_t            *ixHigh,
                   UErrorCode         *status)
{
    const UCollator *coll = elems->iteratordata_.coll;
    int64_t result = UCOL_IGNORABLE;
    uint32_t low = 0, high = 0;

    if (U_FAILURE(*status)) {
        return UCOL_PROCESSED_NULLORDER;
    }

    if (elems->pce == NULL) {
        elems->pce = new UCollationPCE(elems);
    } else {
        elems->pce->pceBuffer.reset();
    }

    elems->reset_ = FALSE;

    do {
        low = ucol_getOffset(elems);
        uint32_t ce = (uint32_t) ucol_getNextCE(coll, &elems->iteratordata_, status);
        high = ucol_getOffset(elems);

        if (ce == UCOL_NO_MORE_CES) {
             result = UCOL_PROCESSED_NULLORDER;
             break;
        }

        result = processCE(elems, ce);
    } while (result == UCOL_IGNORABLE);

    if (ixLow != NULL) {
        *ixLow = low;
    }

    if (ixHigh != NULL) {
        *ixHigh = high;
    }

    return result;
}

U_CAPI int32_t U_EXPORT2
ucol_previous(UCollationElements *elems,
              UErrorCode         *status)
{
    if(U_FAILURE(*status)) {
        return UCOL_NULLORDER;
    }
    else
    {
        int32_t result;

        if (elems->reset_ && (elems->iteratordata_.pos == elems->iteratordata_.string)) {
            if (elems->iteratordata_.endp == NULL) {
                elems->iteratordata_.endp = elems->iteratordata_.string +
                                            u_strlen(elems->iteratordata_.string);
                elems->iteratordata_.flags |= UCOL_ITER_HASLEN;
            }
            elems->iteratordata_.pos = elems->iteratordata_.endp;
            elems->iteratordata_.fcdPosition = elems->iteratordata_.endp;
        }

        elems->reset_ = FALSE;

        result = (int32_t)ucol_getPrevCE(elems->iteratordata_.coll,
                                         &(elems->iteratordata_),
                                         status);

        if (result == UCOL_NO_MORE_CES) {
            result = UCOL_NULLORDER;
        }

        return result;
    }
}

U_CAPI int64_t U_EXPORT2
ucol_previousProcessed(UCollationElements *elems,
                   int32_t            *ixLow,
                   int32_t            *ixHigh,
                   UErrorCode         *status)
{
    const UCollator *coll = elems->iteratordata_.coll;
    int64_t result = UCOL_IGNORABLE;
 // int64_t primary = 0, secondary = 0, tertiary = 0, quaternary = 0;
 // UCollationStrength strength = ucol_getStrength(coll);
 //  UBool toShift   = ucol_getAttribute(coll, UCOL_ALTERNATE_HANDLING, status) ==  UCOL_SHIFTED;
 // uint32_t variableTop = coll->variableTopValue;
    int32_t  low = 0, high = 0;

    if (U_FAILURE(*status)) {
        return UCOL_PROCESSED_NULLORDER;
    }

    if (elems->reset_ &&
        (elems->iteratordata_.pos == elems->iteratordata_.string)) {
        if (elems->iteratordata_.endp == NULL) {
            elems->iteratordata_.endp = elems->iteratordata_.string +
                                        u_strlen(elems->iteratordata_.string);
            elems->iteratordata_.flags |= UCOL_ITER_HASLEN;
        }

        elems->iteratordata_.pos = elems->iteratordata_.endp;
        elems->iteratordata_.fcdPosition = elems->iteratordata_.endp;
    }

    if (elems->pce == NULL) {
        elems->pce = new UCollationPCE(elems);
    } else {
      //elems->pce->pceBuffer.reset();
    }

    elems->reset_ = FALSE;

    while (elems->pce->pceBuffer.empty()) {
        // buffer raw CEs up to non-ignorable primary
        RCEBuffer rceb;
        uint32_t ce;

        // **** do we need to reset rceb, or will it always be empty at this point ****
        do {
            high = ucol_getOffset(elems);
            ce   = ucol_getPrevCE(coll, &elems->iteratordata_, status);
            low  = ucol_getOffset(elems);

            if (ce == UCOL_NO_MORE_CES) {
                if (! rceb.empty()) {
                    break;
                }

                goto finish;
            }

            rceb.put(ce, low, high);
        } while ((ce & UCOL_PRIMARYMASK) == 0);

        // process the raw CEs
        while (! rceb.empty()) {
            const RCEI *rcei = rceb.get();

            result = processCE(elems, rcei->ce);

            if (result != UCOL_IGNORABLE) {
                elems->pce->pceBuffer.put(result, rcei->low, rcei->high);
            }
        }
    }

finish:
    if (elems->pce->pceBuffer.empty()) {
        // **** Is -1 the right value for ixLow, ixHigh? ****
    	if (ixLow != NULL) {
    		*ixLow = -1;
    	}

    	if (ixHigh != NULL) {
    		*ixHigh = -1
    		;
    	}
        return UCOL_PROCESSED_NULLORDER;
    }

    const PCEI *pcei = elems->pce->pceBuffer.get();

    if (ixLow != NULL) {
        *ixLow = pcei->low;
    }

    if (ixHigh != NULL) {
        *ixHigh = pcei->high;
    }

    return pcei->ce;
}

U_CAPI int32_t U_EXPORT2
ucol_getMaxExpansion(const UCollationElements *elems,
                           int32_t            order)
{
    uint8_t result;

#if 0
    UCOL_GETMAXEXPANSION(elems->iteratordata_.coll, (uint32_t)order, result);
#else
    const UCollator *coll = elems->iteratordata_.coll;
    const uint32_t *start;
    const uint32_t *limit;
    const uint32_t *mid;
          uint32_t strengthMask = 0;
          uint32_t mOrder = (uint32_t) order;

    switch (coll->strength)
    {
    default:
        strengthMask |= UCOL_TERTIARYORDERMASK;
        /* fall through */

    case UCOL_SECONDARY:
        strengthMask |= UCOL_SECONDARYORDERMASK;
        /* fall through */

    case UCOL_PRIMARY:
        strengthMask |= UCOL_PRIMARYORDERMASK;
    }

    mOrder &= strengthMask;
    start = (coll)->endExpansionCE;
    limit = (coll)->lastEndExpansionCE;

    while (start < limit - 1) {
        mid = start + ((limit - start) >> 1);
        if (mOrder <= (*mid & strengthMask)) {
          limit = mid;
        } else {
          start = mid;
        }
    }

    // FIXME: with a masked search, there might be more than one hit,
    // so we need to look forward and backward from the match to find all
    // of the hits...
    if ((*start & strengthMask) == mOrder) {
        result = *((coll)->expansionCESize + (start - (coll)->endExpansionCE));
    } else if ((*limit & strengthMask) == mOrder) {
         result = *(coll->expansionCESize + (limit - coll->endExpansionCE));
   } else if ((mOrder & 0xFFFF) == 0x00C0) {
        result = 2;
   } else {
       result = 1;
   }
#endif

    return result;
}

U_CAPI void U_EXPORT2
ucol_setText(      UCollationElements *elems,
             const UChar              *text,
                   int32_t            textLength,
                   UErrorCode         *status)
{
    if (U_FAILURE(*status)) {
        return;
    }

    if (elems->isWritable && elems->iteratordata_.string != NULL)
    {
        uprv_free((UChar *)elems->iteratordata_.string);
    }

    if (text == NULL) {
        textLength = 0;
    }

    elems->isWritable = FALSE;

    /* free offset buffer to avoid memory leak before initializing. */
    ucol_freeOffsetBuffer(&(elems->iteratordata_));
    /* Ensure that previously allocated extendCEs is freed before setting to NULL. */
    if (elems->iteratordata_.extendCEs != NULL) {
        uprv_free(elems->iteratordata_.extendCEs);
    }
    uprv_init_collIterate(elems->iteratordata_.coll, text, textLength,
                          &elems->iteratordata_, status);

    elems->reset_   = TRUE;
}

U_CAPI int32_t U_EXPORT2
ucol_getOffset(const UCollationElements *elems)
{
  const collIterate *ci = &(elems->iteratordata_);

  if (ci->offsetRepeatCount > 0 && ci->offsetRepeatValue != 0) {
      return ci->offsetRepeatValue;
  }

  if (ci->offsetReturn != NULL) {
      return *ci->offsetReturn;
  }

  // while processing characters in normalization buffer getOffset will
  // return the next non-normalized character.
  // should be inline with the old implementation since the old codes uses
  // nextDecomp in normalizer which also decomposes the string till the
  // first base character is found.
  if (ci->flags & UCOL_ITER_INNORMBUF) {
      if (ci->fcdPosition == NULL) {
        return 0;
      }
      return (int32_t)(ci->fcdPosition - ci->string);
  }
  else {
      return (int32_t)(ci->pos - ci->string);
  }
}

U_CAPI void U_EXPORT2
ucol_setOffset(UCollationElements    *elems,
               int32_t           offset,
               UErrorCode            *status)
{
    if (U_FAILURE(*status)) {
        return;
    }

    // this methods will clean up any use of the writable buffer and points to
    // the original string
    collIterate *ci = &(elems->iteratordata_);
    ci->pos         = ci->string + offset;
    ci->CEpos       = ci->toReturn = ci->CEs;
    if (ci->flags & UCOL_ITER_INNORMBUF) {
        ci->flags = ci->origFlags;
    }
    if ((ci->flags & UCOL_ITER_HASLEN) == 0) {
        ci->endp  = ci->string + u_strlen(ci->string);
        ci->flags |= UCOL_ITER_HASLEN;
    }
    ci->fcdPosition = NULL;
    elems->reset_ = FALSE;

	ci->offsetReturn = NULL;
    ci->offsetStore = ci->offsetBuffer;
	ci->offsetRepeatCount = ci->offsetRepeatValue = 0;
}

U_CAPI int32_t U_EXPORT2
ucol_primaryOrder (int32_t order)
{
    order &= UCOL_PRIMARYMASK;
    return (order >> UCOL_PRIMARYORDERSHIFT);
}

U_CAPI int32_t U_EXPORT2
ucol_secondaryOrder (int32_t order)
{
    order &= UCOL_SECONDARYMASK;
    return (order >> UCOL_SECONDARYORDERSHIFT);
}

U_CAPI int32_t U_EXPORT2
ucol_tertiaryOrder (int32_t order)
{
    return (order & UCOL_TERTIARYMASK);
}


void ucol_freeOffsetBuffer(collIterate *s) {
    if (s != NULL && s->offsetBuffer != NULL) {
        uprv_free(s->offsetBuffer);
        s->offsetBuffer = NULL;
        s->offsetBufferSize = 0;
    }
}

#endif /* #if !UCONFIG_NO_COLLATION */