X-Git-Url: https://git.saurik.com/apple/icu.git/blobdiff_plain/b75a7d8f3b4adbae880cab104ce2c6a50eee4db2..9f1b115531acc2f3640893f76e8bcf6680033062:/icuSources/common/uvector.cpp diff --git a/icuSources/common/uvector.cpp b/icuSources/common/uvector.cpp index 8da15992..cf19edf6 100644 --- a/icuSources/common/uvector.cpp +++ b/icuSources/common/uvector.cpp @@ -1,7 +1,9 @@ +// © 2016 and later: Unicode, Inc. and others. +// License & terms of use: http://www.unicode.org/copyright.html /* ****************************************************************************** -* Copyright (C) 1999-2001, International Business Machines Corporation and * -* others. All Rights Reserved. * +* Copyright (C) 1999-2013, International Business Machines Corporation and +* others. All Rights Reserved. ****************************************************************************** * Date Name Description * 10/22/99 alan Creation. @@ -10,10 +12,12 @@ #include "uvector.h" #include "cmemory.h" +#include "uarrsort.h" +#include "uelement.h" U_NAMESPACE_BEGIN -#define DEFUALT_CAPACITY 8 +#define DEFAULT_CAPACITY 8 /* * Constants for hinting whether a key is an integer @@ -23,7 +27,7 @@ U_NAMESPACE_BEGIN #define HINT_KEY_POINTER (1) #define HINT_KEY_INTEGER (0) -const char UVector::fgClassID=0; +UOBJECT_DEFINE_RTTI_IMPLEMENTATION(UVector) UVector::UVector(UErrorCode &status) : count(0), @@ -32,7 +36,7 @@ UVector::UVector(UErrorCode &status) : deleter(0), comparer(0) { - _init(DEFUALT_CAPACITY, status); + _init(DEFAULT_CAPACITY, status); } UVector::UVector(int32_t initialCapacity, UErrorCode &status) : @@ -45,17 +49,17 @@ UVector::UVector(int32_t initialCapacity, UErrorCode &status) : _init(initialCapacity, status); } -UVector::UVector(UObjectDeleter *d, UKeyComparator *c, UErrorCode &status) : +UVector::UVector(UObjectDeleter *d, UElementsAreEqual *c, UErrorCode &status) : count(0), capacity(0), elements(0), deleter(d), comparer(c) { - _init(DEFUALT_CAPACITY, status); + _init(DEFAULT_CAPACITY, status); } -UVector::UVector(UObjectDeleter *d, UKeyComparator *c, int32_t initialCapacity, UErrorCode &status) : +UVector::UVector(UObjectDeleter *d, UElementsAreEqual *c, int32_t initialCapacity, UErrorCode &status) : count(0), capacity(0), elements(0), @@ -66,11 +70,14 @@ UVector::UVector(UObjectDeleter *d, UKeyComparator *c, int32_t initialCapacity, } void UVector::_init(int32_t initialCapacity, UErrorCode &status) { - // Fix bogus initialCapacity values; avoid malloc(0) - if (initialCapacity < 1) { - initialCapacity = DEFUALT_CAPACITY; + if (U_FAILURE(status)) { + return; + } + // Fix bogus initialCapacity values; avoid malloc(0) and integer overflow + if ((initialCapacity < 1) || (initialCapacity > (int32_t)(INT32_MAX / sizeof(UElement)))) { + initialCapacity = DEFAULT_CAPACITY; } - elements = (UHashTok *)uprv_malloc(sizeof(UHashTok)*initialCapacity); + elements = (UElement *)uprv_malloc(sizeof(UElement)*initialCapacity); if (elements == 0) { status = U_MEMORY_ALLOCATION_ERROR; } else { @@ -88,14 +95,16 @@ UVector::~UVector() { * 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) { +void UVector::assign(const UVector& other, UElementAssigner *assign, UErrorCode &ec) { if (ensureCapacity(other.count, ec)) { - setSize(other.count); - for (int32_t i=0; i= minimumCapacity) { - return TRUE; - } else { + if (minimumCapacity < 0) { + status = U_ILLEGAL_ARGUMENT_ERROR; + return FALSE; + } + if (capacity < minimumCapacity) { + if (capacity > (INT32_MAX - 1) / 2) { // integer overflow check + status = U_ILLEGAL_ARGUMENT_ERROR; + return FALSE; + } int32_t newCap = capacity * 2; if (newCap < minimumCapacity) { newCap = minimumCapacity; } - UHashTok* newElems = (UHashTok *)uprv_malloc(sizeof(UHashTok)*newCap); - if (newElems == 0) { + if (newCap > (int32_t)(INT32_MAX / sizeof(UElement))) { // integer overflow check + // We keep the original memory contents on bad minimumCapacity. + status = U_ILLEGAL_ARGUMENT_ERROR; + return FALSE; + } + UElement* newElems = (UElement *)uprv_realloc(elements, sizeof(UElement)*newCap); + if (newElems == NULL) { + // We keep the original contents on the memory failure on realloc or bad minimumCapacity. status = U_MEMORY_ALLOCATION_ERROR; return FALSE; } - uprv_memcpy(newElems, elements, sizeof(elements[0]) * count); - uprv_free(elements); elements = newElems; capacity = newCap; - return TRUE; } + return TRUE; } /** @@ -346,17 +365,16 @@ UBool UVector::ensureCapacity(int32_t minimumCapacity, UErrorCode &status) { * newSize. If newSize is larger, grow the array, filling in new * slots with NULL. */ -void UVector::setSize(int32_t newSize) { +void UVector::setSize(int32_t newSize, UErrorCode &status) { int32_t i; if (newSize < 0) { return; } if (newSize > count) { - UErrorCode ec = U_ZERO_ERROR; - if (!ensureCapacity(newSize, ec)) { + if (!ensureCapacity(newSize, status)) { return; } - UHashTok empty; + UElement empty; empty.pointer = NULL; empty.integer = 0; for (i=count; i 0) { max = probe; } else { @@ -460,56 +478,89 @@ void UVector::sortedInsert(UHashTok tok, USortComparator *compare, UErrorCode& e for (int32_t i=count; i>min; --i) { elements[i] = elements[i-1]; } - elements[min] = tok; + elements[min] = e; ++count; } } -const char UStack::fgClassID=0; - -UStack::UStack(UErrorCode &status) : - UVector(status) -{ -} - -UStack::UStack(int32_t initialCapacity, UErrorCode &status) : - UVector(initialCapacity, status) -{ +/** + * Array sort comparator function. + * Used from UVector::sort() + * Conforms to function signature required for uprv_sortArray(). + * This function is essentially just a wrapper, to make a + * UVector style comparator function usable with uprv_sortArray(). + * + * The context pointer to this function is a pointer back + * (with some extra indirection) to the user supplied comparator. + * + */ +static int32_t U_CALLCONV +sortComparator(const void *context, const void *left, const void *right) { + UElementComparator *compare = *static_cast(context); + UElement e1 = *static_cast(left); + UElement e2 = *static_cast(right); + int32_t result = (*compare)(e1, e2); + return result; } -UStack::UStack(UObjectDeleter *d, UKeyComparator *c, UErrorCode &status) : - UVector(d, c, status) -{ -} -UStack::UStack(UObjectDeleter *d, UKeyComparator *c, int32_t initialCapacity, UErrorCode &status) : - UVector(d, c, initialCapacity, status) -{ +/** + * Array sort comparison function for use from UVector::sorti() + * Compares int32_t vector elements. + */ +static int32_t U_CALLCONV +sortiComparator(const void * /*context */, const void *left, const void *right) { + const UElement *e1 = static_cast(left); + const UElement *e2 = static_cast(right); + int32_t result = e1->integer < e2->integer? -1 : + e1->integer == e2->integer? 0 : 1; + return result; } -void* UStack::pop(void) { - int32_t n = size() - 1; - void* result = 0; - if (n >= 0) { - result = elementAt(n); - removeElementAt(n); +/** + * Sort the vector, assuming it constains ints. + * (A more general sort would take a comparison function, but it's + * not clear whether UVector's UElementComparator or + * UComparator from uprv_sortAray would be more appropriate.) + */ +void UVector::sorti(UErrorCode &ec) { + if (U_SUCCESS(ec)) { + uprv_sortArray(elements, count, sizeof(UElement), + sortiComparator, NULL, FALSE, &ec); } - return result; } -int32_t UStack::popi(void) { - int32_t n = size() - 1; - int32_t result = 0; - if (n >= 0) { - result = elementAti(n); - removeElementAt(n); + +/** + * Sort with a user supplied comparator. + * + * The comparator function handling is confusing because the function type + * for UVector (as defined for sortedInsert()) is different from the signature + * required by uprv_sortArray(). This is handled by passing the + * the UVector sort function pointer via the context pointer to a + * sortArray() comparator function, which can then call back to + * the original user functtion. + * + * An additional twist is that it's not safe to pass a pointer-to-function + * as a (void *) data pointer, so instead we pass a (data) pointer to a + * pointer-to-function variable. + */ +void UVector::sort(UElementComparator *compare, UErrorCode &ec) { + if (U_SUCCESS(ec)) { + uprv_sortArray(elements, count, sizeof(UElement), + sortComparator, &compare, FALSE, &ec); } - return result; } -int32_t UStack::search(void* obj) const { - int32_t i = indexOf(obj); - return (i >= 0) ? size() - i : i; + +/** + * Stable sort with a user supplied comparator of type UComparator. + */ +void UVector::sortWithUComparator(UComparator *compare, const void *context, UErrorCode &ec) { + if (U_SUCCESS(ec)) { + uprv_sortArray(elements, count, sizeof(UElement), + compare, context, TRUE, &ec); + } } U_NAMESPACE_END