diff options
Diffstat (limited to 'Build/source/libs/icu/icu-xetex/common/uvector.cpp')
-rw-r--r-- | Build/source/libs/icu/icu-xetex/common/uvector.cpp | 472 |
1 files changed, 472 insertions, 0 deletions
diff --git a/Build/source/libs/icu/icu-xetex/common/uvector.cpp b/Build/source/libs/icu/icu-xetex/common/uvector.cpp new file mode 100644 index 00000000000..028ef39f3b4 --- /dev/null +++ b/Build/source/libs/icu/icu-xetex/common/uvector.cpp @@ -0,0 +1,472 @@ +/* +****************************************************************************** +* Copyright (C) 1999-2004, International Business Machines Corporation and * +* others. All Rights Reserved. * +****************************************************************************** +* Date Name Description +* 10/22/99 alan Creation. +********************************************************************** +*/ + +#include "uvector.h" +#include "cmemory.h" + +U_NAMESPACE_BEGIN + +#define DEFUALT_CAPACITY 8 + +/* + * Constants for hinting whether a key is an integer + * or a pointer. If a hint bit is zero, then the associated + * token is assumed to be an integer. This is needed for iSeries + */ +#define HINT_KEY_POINTER (1) +#define HINT_KEY_INTEGER (0) + +UOBJECT_DEFINE_RTTI_IMPLEMENTATION(UVector) + +UVector::UVector(UErrorCode &status) : + count(0), + capacity(0), + elements(0), + deleter(0), + comparer(0) +{ + _init(DEFUALT_CAPACITY, status); +} + +UVector::UVector(int32_t initialCapacity, UErrorCode &status) : + count(0), + capacity(0), + elements(0), + deleter(0), + comparer(0) +{ + _init(initialCapacity, status); +} + +UVector::UVector(UObjectDeleter *d, UKeyComparator *c, UErrorCode &status) : + count(0), + capacity(0), + elements(0), + deleter(d), + comparer(c) +{ + _init(DEFUALT_CAPACITY, status); +} + +UVector::UVector(UObjectDeleter *d, UKeyComparator *c, int32_t initialCapacity, UErrorCode &status) : + count(0), + capacity(0), + elements(0), + deleter(d), + comparer(c) +{ + _init(initialCapacity, status); +} + +void UVector::_init(int32_t initialCapacity, UErrorCode &status) { + if (U_FAILURE(status)) { + return; + } + // Fix bogus initialCapacity values; avoid malloc(0) + if (initialCapacity < 1) { + initialCapacity = DEFUALT_CAPACITY; + } + elements = (UHashTok *)uprv_malloc(sizeof(UHashTok)*initialCapacity); + if (elements == 0) { + status = U_MEMORY_ALLOCATION_ERROR; + } else { + capacity = initialCapacity; + } +} + +UVector::~UVector() { + removeAllElements(); + uprv_free(elements); + elements = 0; +} + +/** + * Assign this object to another (make this a copy of 'other'). + * Use the 'assign' function to assign each element. + */ +void UVector::assign(const UVector& other, UTokenAssigner *assign, UErrorCode &ec) { + if (ensureCapacity(other.count, ec)) { + setSize(other.count); + for (int32_t i=0; i<other.count; ++i) { + if (elements[i].pointer != 0 && deleter != 0) { + (*deleter)(elements[i].pointer); + } + (*assign)(&elements[i], &other.elements[i]); + } + } +} + +// This only does something sensible if this object has a non-null comparer +UBool UVector::operator==(const UVector& other) { + int32_t i; + if (count != other.count) return FALSE; + if (comparer != NULL) { + // Compare using this object's comparer + for (i=0; i<count; ++i) { + if (!(*comparer)(elements[i], other.elements[i])) { + return FALSE; + } + } + } + return TRUE; +} + +void UVector::addElement(void* obj, UErrorCode &status) { + if (ensureCapacity(count + 1, status)) { + elements[count++].pointer = obj; + } +} + +void UVector::addElement(int32_t elem, UErrorCode &status) { + if (ensureCapacity(count + 1, status)) { + elements[count].pointer = NULL; // Pointers may be bigger than ints. + elements[count].integer = elem; + count++; + } +} + +void UVector::setElementAt(void* obj, int32_t index) { + if (0 <= index && index < count) { + if (elements[index].pointer != 0 && deleter != 0) { + (*deleter)(elements[index].pointer); + } + elements[index].pointer = obj; + } + /* else index out of range */ +} + +void UVector::setElementAt(int32_t elem, int32_t index) { + if (0 <= index && index < count) { + if (elements[index].pointer != 0 && deleter != 0) { + // TODO: this should be an error. mixing up ints and pointers. + (*deleter)(elements[index].pointer); + } + elements[index].pointer = NULL; + elements[index].integer = elem; + } + /* else index out of range */ +} + +void UVector::insertElementAt(void* obj, int32_t index, UErrorCode &status) { + // must have 0 <= index <= count + if (0 <= index && index <= count && ensureCapacity(count + 1, status)) { + for (int32_t i=count; i>index; --i) { + elements[i] = elements[i-1]; + } + elements[index].pointer = obj; + ++count; + } + /* else index out of range */ +} + +void UVector::insertElementAt(int32_t elem, int32_t index, UErrorCode &status) { + // must have 0 <= index <= count + if (0 <= index && index <= count && ensureCapacity(count + 1, status)) { + for (int32_t i=count; i>index; --i) { + elements[i] = elements[i-1]; + } + elements[index].pointer = NULL; + elements[index].integer = elem; + ++count; + } + /* else index out of range */ +} + +void* UVector::elementAt(int32_t index) const { + return (0 <= index && index < count) ? elements[index].pointer : 0; +} + +int32_t UVector::elementAti(int32_t index) const { + return (0 <= index && index < count) ? elements[index].integer : 0; +} + +UBool UVector::containsAll(const UVector& other) const { + for (int32_t i=0; i<other.size(); ++i) { + if (indexOf(other.elements[i]) < 0) { + return FALSE; + } + } + return TRUE; +} + +UBool UVector::containsNone(const UVector& other) const { + for (int32_t i=0; i<other.size(); ++i) { + if (indexOf(other.elements[i]) >= 0) { + return FALSE; + } + } + return TRUE; +} + +UBool UVector::removeAll(const UVector& other) { + UBool changed = FALSE; + for (int32_t i=0; i<other.size(); ++i) { + int32_t j = indexOf(other.elements[i]); + if (j >= 0) { + removeElementAt(j); + changed = TRUE; + } + } + return changed; +} + +UBool UVector::retainAll(const UVector& other) { + UBool changed = FALSE; + for (int32_t j=size()-1; j>=0; --j) { + int32_t i = other.indexOf(elements[j]); + if (i < 0) { + removeElementAt(j); + changed = TRUE; + } + } + return changed; +} + +void UVector::removeElementAt(int32_t index) { + void* e = orphanElementAt(index); + if (e != 0 && deleter != 0) { + (*deleter)(e); + } +} + +UBool UVector::removeElement(void* obj) { + int32_t i = indexOf(obj); + if (i >= 0) { + removeElementAt(i); + return TRUE; + } + return FALSE; +} + +void UVector::removeAllElements(void) { + if (deleter != 0) { + for (int32_t i=0; i<count; ++i) { + if (elements[i].pointer != 0) { + (*deleter)(elements[i].pointer); + } + } + } + count = 0; +} + +UBool UVector::equals(const UVector &other) const { + int i; + + if (this->count != other.count) { + return FALSE; + } + if (comparer == 0) { + for (i=0; i<count; i++) { + if (elements[i].pointer != other.elements[i].pointer) { + return FALSE; + } + } + } else { + UHashTok key; + for (i=0; i<count; i++) { + key.pointer = &other.elements[i]; + if (!(*comparer)(key, elements[i])) { + return FALSE; + } + } + } + return TRUE; +} + + + +int32_t UVector::indexOf(void* obj, int32_t startIndex) const { + UHashTok key; + key.pointer = obj; + return indexOf(key, startIndex, HINT_KEY_POINTER); +} + +int32_t UVector::indexOf(int32_t obj, int32_t startIndex) const { + UHashTok key; + key.integer = obj; + return indexOf(key, startIndex, HINT_KEY_INTEGER); +} + +// This only works if this object has a non-null comparer +int32_t UVector::indexOf(UHashTok key, int32_t startIndex, int8_t hint) const { + int32_t i; + if (comparer != 0) { + for (i=startIndex; i<count; ++i) { + if ((*comparer)(key, elements[i])) { + return i; + } + } + } else { + for (i=startIndex; i<count; ++i) { + /* Pointers are not always the same size as ints so to perform + * a valid comparision we need to know whether we are being + * provided an int or a pointer. */ + if (hint & HINT_KEY_POINTER) { + if (key.pointer == elements[i].pointer) { + return i; + } + } else { + if (key.integer == elements[i].integer) { + return i; + } + } + } + } + return -1; +} + +UBool UVector::ensureCapacity(int32_t minimumCapacity, UErrorCode &status) { + if (capacity >= minimumCapacity) { + return TRUE; + } else { + int32_t newCap = capacity * 2; + if (newCap < minimumCapacity) { + newCap = minimumCapacity; + } + UHashTok* newElems = (UHashTok *)uprv_malloc(sizeof(UHashTok)*newCap); + if (newElems == 0) { + status = U_MEMORY_ALLOCATION_ERROR; + return FALSE; + } + uprv_memcpy(newElems, elements, sizeof(elements[0]) * count); + uprv_free(elements); + elements = newElems; + capacity = newCap; + return TRUE; + } +} + +/** + * Change the size of this vector as follows: If newSize is smaller, + * then truncate the array, possibly deleting held elements for i >= + * newSize. If newSize is larger, grow the array, filling in new + * slots with NULL. + */ +void UVector::setSize(int32_t newSize) { + int32_t i; + if (newSize < 0) { + return; + } + if (newSize > count) { + UErrorCode ec = U_ZERO_ERROR; + if (!ensureCapacity(newSize, ec)) { + return; + } + UHashTok empty; + empty.pointer = NULL; + empty.integer = 0; + for (i=count; i<newSize; ++i) { + elements[i] = empty; + } + } else { + /* Most efficient to count down */ + for (i=count-1; i>=newSize; --i) { + removeElementAt(i); + } + } + count = newSize; +} + +/** + * Fill in the given array with all elements of this vector. + */ +void** UVector::toArray(void** result) const { + void** a = result; + for (int i=0; i<count; ++i) { + *a++ = elements[i].pointer; + } + return result; +} + +UObjectDeleter *UVector::setDeleter(UObjectDeleter *d) { + UObjectDeleter *old = deleter; + deleter = d; + return old; +} + +UKeyComparator *UVector::setComparer(UKeyComparator *d) { + UKeyComparator *old = comparer; + comparer = d; + return old; +} + +/** + * Removes the element at the given index from this vector and + * transfer ownership of it to the caller. After this call, the + * caller owns the result and must delete it and the vector entry + * at 'index' is removed, shifting all subsequent entries back by + * one index and shortening the size of the vector by one. If the + * index is out of range or if there is no item at the given index + * then 0 is returned and the vector is unchanged. + */ +void* UVector::orphanElementAt(int32_t index) { + void* e = 0; + if (0 <= index && index < count) { + e = elements[index].pointer; + for (int32_t i=index; i<count-1; ++i) { + elements[i] = elements[i+1]; + } + --count; + } + /* else index out of range */ + return e; +} + +/** + * Insert the given object into this vector at its sorted position + * as defined by 'compare'. The current elements are assumed to + * be sorted already. + */ +void UVector::sortedInsert(void* obj, USortComparator *compare, UErrorCode& ec) { + UHashTok tok; + tok.pointer = obj; + sortedInsert(tok, compare, ec); +} + +/** + * Insert the given integer into this vector at its sorted position + * as defined by 'compare'. The current elements are assumed to + * be sorted already. + */ +void UVector::sortedInsert(int32_t obj, USortComparator *compare, UErrorCode& ec) { + UHashTok tok; + tok.integer = obj; + sortedInsert(tok, compare, ec); +} + +// ASSUME elements[] IS CURRENTLY SORTED +void UVector::sortedInsert(UHashTok tok, USortComparator *compare, UErrorCode& ec) { + // Perform a binary search for the location to insert tok at. Tok + // will be inserted between two elements a and b such that a <= + // tok && tok < b, where there is a 'virtual' elements[-1] always + // less than tok and a 'virtual' elements[count] always greater + // than tok. + int32_t min = 0, max = count; + while (min != max) { + int32_t probe = (min + max) / 2; + int8_t c = (*compare)(elements[probe], tok); + if (c > 0) { + max = probe; + } else { + // assert(c <= 0); + min = probe + 1; + } + } + if (ensureCapacity(count + 1, ec)) { + for (int32_t i=count; i>min; --i) { + elements[i] = elements[i-1]; + } + elements[min] = tok; + ++count; + } +} + +U_NAMESPACE_END + |