1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/intl/icu/source/common/uvector.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,565 @@
1.4 +/*
1.5 +******************************************************************************
1.6 +* Copyright (C) 1999-2013, International Business Machines Corporation and
1.7 +* others. All Rights Reserved.
1.8 +******************************************************************************
1.9 +* Date Name Description
1.10 +* 10/22/99 alan Creation.
1.11 +**********************************************************************
1.12 +*/
1.13 +
1.14 +#include "uvector.h"
1.15 +#include "cmemory.h"
1.16 +#include "uarrsort.h"
1.17 +#include "uelement.h"
1.18 +
1.19 +U_NAMESPACE_BEGIN
1.20 +
1.21 +#define DEFAULT_CAPACITY 8
1.22 +
1.23 +/*
1.24 + * Constants for hinting whether a key is an integer
1.25 + * or a pointer. If a hint bit is zero, then the associated
1.26 + * token is assumed to be an integer. This is needed for iSeries
1.27 + */
1.28 +#define HINT_KEY_POINTER (1)
1.29 +#define HINT_KEY_INTEGER (0)
1.30 +
1.31 +UOBJECT_DEFINE_RTTI_IMPLEMENTATION(UVector)
1.32 +
1.33 +UVector::UVector(UErrorCode &status) :
1.34 + count(0),
1.35 + capacity(0),
1.36 + elements(0),
1.37 + deleter(0),
1.38 + comparer(0)
1.39 +{
1.40 + _init(DEFAULT_CAPACITY, status);
1.41 +}
1.42 +
1.43 +UVector::UVector(int32_t initialCapacity, UErrorCode &status) :
1.44 + count(0),
1.45 + capacity(0),
1.46 + elements(0),
1.47 + deleter(0),
1.48 + comparer(0)
1.49 +{
1.50 + _init(initialCapacity, status);
1.51 +}
1.52 +
1.53 +UVector::UVector(UObjectDeleter *d, UElementsAreEqual *c, UErrorCode &status) :
1.54 + count(0),
1.55 + capacity(0),
1.56 + elements(0),
1.57 + deleter(d),
1.58 + comparer(c)
1.59 +{
1.60 + _init(DEFAULT_CAPACITY, status);
1.61 +}
1.62 +
1.63 +UVector::UVector(UObjectDeleter *d, UElementsAreEqual *c, int32_t initialCapacity, UErrorCode &status) :
1.64 + count(0),
1.65 + capacity(0),
1.66 + elements(0),
1.67 + deleter(d),
1.68 + comparer(c)
1.69 +{
1.70 + _init(initialCapacity, status);
1.71 +}
1.72 +
1.73 +void UVector::_init(int32_t initialCapacity, UErrorCode &status) {
1.74 + if (U_FAILURE(status)) {
1.75 + return;
1.76 + }
1.77 + // Fix bogus initialCapacity values; avoid malloc(0) and integer overflow
1.78 + if ((initialCapacity < 1) || (initialCapacity > (int32_t)(INT32_MAX / sizeof(UElement)))) {
1.79 + initialCapacity = DEFAULT_CAPACITY;
1.80 + }
1.81 + elements = (UElement *)uprv_malloc(sizeof(UElement)*initialCapacity);
1.82 + if (elements == 0) {
1.83 + status = U_MEMORY_ALLOCATION_ERROR;
1.84 + } else {
1.85 + capacity = initialCapacity;
1.86 + }
1.87 +}
1.88 +
1.89 +UVector::~UVector() {
1.90 + removeAllElements();
1.91 + uprv_free(elements);
1.92 + elements = 0;
1.93 +}
1.94 +
1.95 +/**
1.96 + * Assign this object to another (make this a copy of 'other').
1.97 + * Use the 'assign' function to assign each element.
1.98 + */
1.99 +void UVector::assign(const UVector& other, UElementAssigner *assign, UErrorCode &ec) {
1.100 + if (ensureCapacity(other.count, ec)) {
1.101 + setSize(other.count, ec);
1.102 + if (U_SUCCESS(ec)) {
1.103 + for (int32_t i=0; i<other.count; ++i) {
1.104 + if (elements[i].pointer != 0 && deleter != 0) {
1.105 + (*deleter)(elements[i].pointer);
1.106 + }
1.107 + (*assign)(&elements[i], &other.elements[i]);
1.108 + }
1.109 + }
1.110 + }
1.111 +}
1.112 +
1.113 +// This only does something sensible if this object has a non-null comparer
1.114 +UBool UVector::operator==(const UVector& other) {
1.115 + int32_t i;
1.116 + if (count != other.count) return FALSE;
1.117 + if (comparer != NULL) {
1.118 + // Compare using this object's comparer
1.119 + for (i=0; i<count; ++i) {
1.120 + if (!(*comparer)(elements[i], other.elements[i])) {
1.121 + return FALSE;
1.122 + }
1.123 + }
1.124 + }
1.125 + return TRUE;
1.126 +}
1.127 +
1.128 +void UVector::addElement(void* obj, UErrorCode &status) {
1.129 + if (ensureCapacity(count + 1, status)) {
1.130 + elements[count++].pointer = obj;
1.131 + }
1.132 +}
1.133 +
1.134 +void UVector::addElement(int32_t elem, UErrorCode &status) {
1.135 + if (ensureCapacity(count + 1, status)) {
1.136 + elements[count].pointer = NULL; // Pointers may be bigger than ints.
1.137 + elements[count].integer = elem;
1.138 + count++;
1.139 + }
1.140 +}
1.141 +
1.142 +void UVector::setElementAt(void* obj, int32_t index) {
1.143 + if (0 <= index && index < count) {
1.144 + if (elements[index].pointer != 0 && deleter != 0) {
1.145 + (*deleter)(elements[index].pointer);
1.146 + }
1.147 + elements[index].pointer = obj;
1.148 + }
1.149 + /* else index out of range */
1.150 +}
1.151 +
1.152 +void UVector::setElementAt(int32_t elem, int32_t index) {
1.153 + if (0 <= index && index < count) {
1.154 + if (elements[index].pointer != 0 && deleter != 0) {
1.155 + // TODO: this should be an error. mixing up ints and pointers.
1.156 + (*deleter)(elements[index].pointer);
1.157 + }
1.158 + elements[index].pointer = NULL;
1.159 + elements[index].integer = elem;
1.160 + }
1.161 + /* else index out of range */
1.162 +}
1.163 +
1.164 +void UVector::insertElementAt(void* obj, int32_t index, UErrorCode &status) {
1.165 + // must have 0 <= index <= count
1.166 + if (0 <= index && index <= count && ensureCapacity(count + 1, status)) {
1.167 + for (int32_t i=count; i>index; --i) {
1.168 + elements[i] = elements[i-1];
1.169 + }
1.170 + elements[index].pointer = obj;
1.171 + ++count;
1.172 + }
1.173 + /* else index out of range */
1.174 +}
1.175 +
1.176 +void UVector::insertElementAt(int32_t elem, int32_t index, UErrorCode &status) {
1.177 + // must have 0 <= index <= count
1.178 + if (0 <= index && index <= count && ensureCapacity(count + 1, status)) {
1.179 + for (int32_t i=count; i>index; --i) {
1.180 + elements[i] = elements[i-1];
1.181 + }
1.182 + elements[index].pointer = NULL;
1.183 + elements[index].integer = elem;
1.184 + ++count;
1.185 + }
1.186 + /* else index out of range */
1.187 +}
1.188 +
1.189 +void* UVector::elementAt(int32_t index) const {
1.190 + return (0 <= index && index < count) ? elements[index].pointer : 0;
1.191 +}
1.192 +
1.193 +int32_t UVector::elementAti(int32_t index) const {
1.194 + return (0 <= index && index < count) ? elements[index].integer : 0;
1.195 +}
1.196 +
1.197 +UBool UVector::containsAll(const UVector& other) const {
1.198 + for (int32_t i=0; i<other.size(); ++i) {
1.199 + if (indexOf(other.elements[i]) < 0) {
1.200 + return FALSE;
1.201 + }
1.202 + }
1.203 + return TRUE;
1.204 +}
1.205 +
1.206 +UBool UVector::containsNone(const UVector& other) const {
1.207 + for (int32_t i=0; i<other.size(); ++i) {
1.208 + if (indexOf(other.elements[i]) >= 0) {
1.209 + return FALSE;
1.210 + }
1.211 + }
1.212 + return TRUE;
1.213 +}
1.214 +
1.215 +UBool UVector::removeAll(const UVector& other) {
1.216 + UBool changed = FALSE;
1.217 + for (int32_t i=0; i<other.size(); ++i) {
1.218 + int32_t j = indexOf(other.elements[i]);
1.219 + if (j >= 0) {
1.220 + removeElementAt(j);
1.221 + changed = TRUE;
1.222 + }
1.223 + }
1.224 + return changed;
1.225 +}
1.226 +
1.227 +UBool UVector::retainAll(const UVector& other) {
1.228 + UBool changed = FALSE;
1.229 + for (int32_t j=size()-1; j>=0; --j) {
1.230 + int32_t i = other.indexOf(elements[j]);
1.231 + if (i < 0) {
1.232 + removeElementAt(j);
1.233 + changed = TRUE;
1.234 + }
1.235 + }
1.236 + return changed;
1.237 +}
1.238 +
1.239 +void UVector::removeElementAt(int32_t index) {
1.240 + void* e = orphanElementAt(index);
1.241 + if (e != 0 && deleter != 0) {
1.242 + (*deleter)(e);
1.243 + }
1.244 +}
1.245 +
1.246 +UBool UVector::removeElement(void* obj) {
1.247 + int32_t i = indexOf(obj);
1.248 + if (i >= 0) {
1.249 + removeElementAt(i);
1.250 + return TRUE;
1.251 + }
1.252 + return FALSE;
1.253 +}
1.254 +
1.255 +void UVector::removeAllElements(void) {
1.256 + if (deleter != 0) {
1.257 + for (int32_t i=0; i<count; ++i) {
1.258 + if (elements[i].pointer != 0) {
1.259 + (*deleter)(elements[i].pointer);
1.260 + }
1.261 + }
1.262 + }
1.263 + count = 0;
1.264 +}
1.265 +
1.266 +UBool UVector::equals(const UVector &other) const {
1.267 + int i;
1.268 +
1.269 + if (this->count != other.count) {
1.270 + return FALSE;
1.271 + }
1.272 + if (comparer == 0) {
1.273 + for (i=0; i<count; i++) {
1.274 + if (elements[i].pointer != other.elements[i].pointer) {
1.275 + return FALSE;
1.276 + }
1.277 + }
1.278 + } else {
1.279 + UElement key;
1.280 + for (i=0; i<count; i++) {
1.281 + key.pointer = &other.elements[i];
1.282 + if (!(*comparer)(key, elements[i])) {
1.283 + return FALSE;
1.284 + }
1.285 + }
1.286 + }
1.287 + return TRUE;
1.288 +}
1.289 +
1.290 +
1.291 +
1.292 +int32_t UVector::indexOf(void* obj, int32_t startIndex) const {
1.293 + UElement key;
1.294 + key.pointer = obj;
1.295 + return indexOf(key, startIndex, HINT_KEY_POINTER);
1.296 +}
1.297 +
1.298 +int32_t UVector::indexOf(int32_t obj, int32_t startIndex) const {
1.299 + UElement key;
1.300 + key.integer = obj;
1.301 + return indexOf(key, startIndex, HINT_KEY_INTEGER);
1.302 +}
1.303 +
1.304 +// This only works if this object has a non-null comparer
1.305 +int32_t UVector::indexOf(UElement key, int32_t startIndex, int8_t hint) const {
1.306 + int32_t i;
1.307 + if (comparer != 0) {
1.308 + for (i=startIndex; i<count; ++i) {
1.309 + if ((*comparer)(key, elements[i])) {
1.310 + return i;
1.311 + }
1.312 + }
1.313 + } else {
1.314 + for (i=startIndex; i<count; ++i) {
1.315 + /* Pointers are not always the same size as ints so to perform
1.316 + * a valid comparision we need to know whether we are being
1.317 + * provided an int or a pointer. */
1.318 + if (hint & HINT_KEY_POINTER) {
1.319 + if (key.pointer == elements[i].pointer) {
1.320 + return i;
1.321 + }
1.322 + } else {
1.323 + if (key.integer == elements[i].integer) {
1.324 + return i;
1.325 + }
1.326 + }
1.327 + }
1.328 + }
1.329 + return -1;
1.330 +}
1.331 +
1.332 +UBool UVector::ensureCapacity(int32_t minimumCapacity, UErrorCode &status) {
1.333 + if (minimumCapacity < 0) {
1.334 + status = U_ILLEGAL_ARGUMENT_ERROR;
1.335 + return FALSE;
1.336 + }
1.337 + if (capacity < minimumCapacity) {
1.338 + if (capacity > (INT32_MAX - 1) / 2) { // integer overflow check
1.339 + status = U_ILLEGAL_ARGUMENT_ERROR;
1.340 + return FALSE;
1.341 + }
1.342 + int32_t newCap = capacity * 2;
1.343 + if (newCap < minimumCapacity) {
1.344 + newCap = minimumCapacity;
1.345 + }
1.346 + if (newCap > (int32_t)(INT32_MAX / sizeof(UElement))) { // integer overflow check
1.347 + // We keep the original memory contents on bad minimumCapacity.
1.348 + status = U_ILLEGAL_ARGUMENT_ERROR;
1.349 + return FALSE;
1.350 + }
1.351 + UElement* newElems = (UElement *)uprv_realloc(elements, sizeof(UElement)*newCap);
1.352 + if (newElems == NULL) {
1.353 + // We keep the original contents on the memory failure on realloc or bad minimumCapacity.
1.354 + status = U_MEMORY_ALLOCATION_ERROR;
1.355 + return FALSE;
1.356 + }
1.357 + elements = newElems;
1.358 + capacity = newCap;
1.359 + }
1.360 + return TRUE;
1.361 +}
1.362 +
1.363 +/**
1.364 + * Change the size of this vector as follows: If newSize is smaller,
1.365 + * then truncate the array, possibly deleting held elements for i >=
1.366 + * newSize. If newSize is larger, grow the array, filling in new
1.367 + * slots with NULL.
1.368 + */
1.369 +void UVector::setSize(int32_t newSize, UErrorCode &status) {
1.370 + int32_t i;
1.371 + if (newSize < 0) {
1.372 + return;
1.373 + }
1.374 + if (newSize > count) {
1.375 + if (!ensureCapacity(newSize, status)) {
1.376 + return;
1.377 + }
1.378 + UElement empty;
1.379 + empty.pointer = NULL;
1.380 + empty.integer = 0;
1.381 + for (i=count; i<newSize; ++i) {
1.382 + elements[i] = empty;
1.383 + }
1.384 + } else {
1.385 + /* Most efficient to count down */
1.386 + for (i=count-1; i>=newSize; --i) {
1.387 + removeElementAt(i);
1.388 + }
1.389 + }
1.390 + count = newSize;
1.391 +}
1.392 +
1.393 +/**
1.394 + * Fill in the given array with all elements of this vector.
1.395 + */
1.396 +void** UVector::toArray(void** result) const {
1.397 + void** a = result;
1.398 + for (int i=0; i<count; ++i) {
1.399 + *a++ = elements[i].pointer;
1.400 + }
1.401 + return result;
1.402 +}
1.403 +
1.404 +UObjectDeleter *UVector::setDeleter(UObjectDeleter *d) {
1.405 + UObjectDeleter *old = deleter;
1.406 + deleter = d;
1.407 + return old;
1.408 +}
1.409 +
1.410 +UElementsAreEqual *UVector::setComparer(UElementsAreEqual *d) {
1.411 + UElementsAreEqual *old = comparer;
1.412 + comparer = d;
1.413 + return old;
1.414 +}
1.415 +
1.416 +/**
1.417 + * Removes the element at the given index from this vector and
1.418 + * transfer ownership of it to the caller. After this call, the
1.419 + * caller owns the result and must delete it and the vector entry
1.420 + * at 'index' is removed, shifting all subsequent entries back by
1.421 + * one index and shortening the size of the vector by one. If the
1.422 + * index is out of range or if there is no item at the given index
1.423 + * then 0 is returned and the vector is unchanged.
1.424 + */
1.425 +void* UVector::orphanElementAt(int32_t index) {
1.426 + void* e = 0;
1.427 + if (0 <= index && index < count) {
1.428 + e = elements[index].pointer;
1.429 + for (int32_t i=index; i<count-1; ++i) {
1.430 + elements[i] = elements[i+1];
1.431 + }
1.432 + --count;
1.433 + }
1.434 + /* else index out of range */
1.435 + return e;
1.436 +}
1.437 +
1.438 +/**
1.439 + * Insert the given object into this vector at its sorted position
1.440 + * as defined by 'compare'. The current elements are assumed to
1.441 + * be sorted already.
1.442 + */
1.443 +void UVector::sortedInsert(void* obj, UElementComparator *compare, UErrorCode& ec) {
1.444 + UElement e;
1.445 + e.pointer = obj;
1.446 + sortedInsert(e, compare, ec);
1.447 +}
1.448 +
1.449 +/**
1.450 + * Insert the given integer into this vector at its sorted position
1.451 + * as defined by 'compare'. The current elements are assumed to
1.452 + * be sorted already.
1.453 + */
1.454 +void UVector::sortedInsert(int32_t obj, UElementComparator *compare, UErrorCode& ec) {
1.455 + UElement e;
1.456 + e.integer = obj;
1.457 + sortedInsert(e, compare, ec);
1.458 +}
1.459 +
1.460 +// ASSUME elements[] IS CURRENTLY SORTED
1.461 +void UVector::sortedInsert(UElement e, UElementComparator *compare, UErrorCode& ec) {
1.462 + // Perform a binary search for the location to insert tok at. Tok
1.463 + // will be inserted between two elements a and b such that a <=
1.464 + // tok && tok < b, where there is a 'virtual' elements[-1] always
1.465 + // less than tok and a 'virtual' elements[count] always greater
1.466 + // than tok.
1.467 + int32_t min = 0, max = count;
1.468 + while (min != max) {
1.469 + int32_t probe = (min + max) / 2;
1.470 + int8_t c = (*compare)(elements[probe], e);
1.471 + if (c > 0) {
1.472 + max = probe;
1.473 + } else {
1.474 + // assert(c <= 0);
1.475 + min = probe + 1;
1.476 + }
1.477 + }
1.478 + if (ensureCapacity(count + 1, ec)) {
1.479 + for (int32_t i=count; i>min; --i) {
1.480 + elements[i] = elements[i-1];
1.481 + }
1.482 + elements[min] = e;
1.483 + ++count;
1.484 + }
1.485 +}
1.486 +
1.487 +/**
1.488 + * Array sort comparator function.
1.489 + * Used from UVector::sort()
1.490 + * Conforms to function signature required for uprv_sortArray().
1.491 + * This function is essentially just a wrapper, to make a
1.492 + * UVector style comparator function usable with uprv_sortArray().
1.493 + *
1.494 + * The context pointer to this function is a pointer back
1.495 + * (with some extra indirection) to the user supplied comparator.
1.496 + *
1.497 + */
1.498 +static int32_t U_CALLCONV
1.499 +sortComparator(const void *context, const void *left, const void *right) {
1.500 + UElementComparator *compare = *static_cast<UElementComparator * const *>(context);
1.501 + UElement e1 = *static_cast<const UElement *>(left);
1.502 + UElement e2 = *static_cast<const UElement *>(right);
1.503 + int32_t result = (*compare)(e1, e2);
1.504 + return result;
1.505 +}
1.506 +
1.507 +
1.508 +/**
1.509 + * Array sort comparison function for use from UVector::sorti()
1.510 + * Compares int32_t vector elements.
1.511 + */
1.512 +static int32_t U_CALLCONV
1.513 +sortiComparator(const void * /*context */, const void *left, const void *right) {
1.514 + const UElement *e1 = static_cast<const UElement *>(left);
1.515 + const UElement *e2 = static_cast<const UElement *>(right);
1.516 + int32_t result = e1->integer < e2->integer? -1 :
1.517 + e1->integer == e2->integer? 0 : 1;
1.518 + return result;
1.519 +}
1.520 +
1.521 +/**
1.522 + * Sort the vector, assuming it constains ints.
1.523 + * (A more general sort would take a comparison function, but it's
1.524 + * not clear whether UVector's UElementComparator or
1.525 + * UComparator from uprv_sortAray would be more appropriate.)
1.526 + */
1.527 +void UVector::sorti(UErrorCode &ec) {
1.528 + if (U_SUCCESS(ec)) {
1.529 + uprv_sortArray(elements, count, sizeof(UElement),
1.530 + sortiComparator, NULL, FALSE, &ec);
1.531 + }
1.532 +}
1.533 +
1.534 +
1.535 +/**
1.536 + * Sort with a user supplied comparator.
1.537 + *
1.538 + * The comparator function handling is confusing because the function type
1.539 + * for UVector (as defined for sortedInsert()) is different from the signature
1.540 + * required by uprv_sortArray(). This is handled by passing the
1.541 + * the UVector sort function pointer via the context pointer to a
1.542 + * sortArray() comparator function, which can then call back to
1.543 + * the original user functtion.
1.544 + *
1.545 + * An additional twist is that it's not safe to pass a pointer-to-function
1.546 + * as a (void *) data pointer, so instead we pass a (data) pointer to a
1.547 + * pointer-to-function variable.
1.548 + */
1.549 +void UVector::sort(UElementComparator *compare, UErrorCode &ec) {
1.550 + if (U_SUCCESS(ec)) {
1.551 + uprv_sortArray(elements, count, sizeof(UElement),
1.552 + sortComparator, &compare, FALSE, &ec);
1.553 + }
1.554 +}
1.555 +
1.556 +
1.557 +/**
1.558 + * Stable sort with a user supplied comparator of type UComparator.
1.559 + */
1.560 +void UVector::sortWithUComparator(UComparator *compare, const void *context, UErrorCode &ec) {
1.561 + if (U_SUCCESS(ec)) {
1.562 + uprv_sortArray(elements, count, sizeof(UElement),
1.563 + compare, context, TRUE, &ec);
1.564 + }
1.565 +}
1.566 +
1.567 +U_NAMESPACE_END
1.568 +
