uvector.cpp revision b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2
1/* 2****************************************************************************** 3* Copyright (C) 1999-2011, International Business Machines Corporation and * 4* others. All Rights Reserved. * 5****************************************************************************** 6* Date Name Description 7* 10/22/99 alan Creation. 8********************************************************************** 9*/ 10 11#include "uvector.h" 12#include "cmemory.h" 13#include "uarrsort.h" 14 15U_NAMESPACE_BEGIN 16 17#define DEFAULT_CAPACITY 8 18 19/* 20 * Constants for hinting whether a key is an integer 21 * or a pointer. If a hint bit is zero, then the associated 22 * token is assumed to be an integer. This is needed for iSeries 23 */ 24#define HINT_KEY_POINTER (1) 25#define HINT_KEY_INTEGER (0) 26 27UOBJECT_DEFINE_RTTI_IMPLEMENTATION(UVector) 28 29UVector::UVector(UErrorCode &status) : 30 count(0), 31 capacity(0), 32 elements(0), 33 deleter(0), 34 comparer(0) 35{ 36 _init(DEFAULT_CAPACITY, status); 37} 38 39UVector::UVector(int32_t initialCapacity, UErrorCode &status) : 40 count(0), 41 capacity(0), 42 elements(0), 43 deleter(0), 44 comparer(0) 45{ 46 _init(initialCapacity, status); 47} 48 49UVector::UVector(UObjectDeleter *d, UKeyComparator *c, UErrorCode &status) : 50 count(0), 51 capacity(0), 52 elements(0), 53 deleter(d), 54 comparer(c) 55{ 56 _init(DEFAULT_CAPACITY, status); 57} 58 59UVector::UVector(UObjectDeleter *d, UKeyComparator *c, int32_t initialCapacity, UErrorCode &status) : 60 count(0), 61 capacity(0), 62 elements(0), 63 deleter(d), 64 comparer(c) 65{ 66 _init(initialCapacity, status); 67} 68 69void UVector::_init(int32_t initialCapacity, UErrorCode &status) { 70 if (U_FAILURE(status)) { 71 return; 72 } 73 // Fix bogus initialCapacity values; avoid malloc(0) and integer overflow 74 if ((initialCapacity < 1) || (initialCapacity > (int32_t)(INT32_MAX / sizeof(UHashTok)))) { 75 initialCapacity = DEFAULT_CAPACITY; 76 } 77 elements = (UHashTok *)uprv_malloc(sizeof(UHashTok)*initialCapacity); 78 if (elements == 0) { 79 status = U_MEMORY_ALLOCATION_ERROR; 80 } else { 81 capacity = initialCapacity; 82 } 83} 84 85UVector::~UVector() { 86 removeAllElements(); 87 uprv_free(elements); 88 elements = 0; 89} 90 91/** 92 * Assign this object to another (make this a copy of 'other'). 93 * Use the 'assign' function to assign each element. 94 */ 95void UVector::assign(const UVector& other, UTokenAssigner *assign, UErrorCode &ec) { 96 if (ensureCapacity(other.count, ec)) { 97 setSize(other.count, ec); 98 if (U_SUCCESS(ec)) { 99 for (int32_t i=0; i<other.count; ++i) { 100 if (elements[i].pointer != 0 && deleter != 0) { 101 (*deleter)(elements[i].pointer); 102 } 103 (*assign)(&elements[i], &other.elements[i]); 104 } 105 } 106 } 107} 108 109// This only does something sensible if this object has a non-null comparer 110UBool UVector::operator==(const UVector& other) { 111 int32_t i; 112 if (count != other.count) return FALSE; 113 if (comparer != NULL) { 114 // Compare using this object's comparer 115 for (i=0; i<count; ++i) { 116 if (!(*comparer)(elements[i], other.elements[i])) { 117 return FALSE; 118 } 119 } 120 } 121 return TRUE; 122} 123 124void UVector::addElement(void* obj, UErrorCode &status) { 125 if (ensureCapacity(count + 1, status)) { 126 elements[count++].pointer = obj; 127 } 128} 129 130void UVector::addElement(int32_t elem, UErrorCode &status) { 131 if (ensureCapacity(count + 1, status)) { 132 elements[count].pointer = NULL; // Pointers may be bigger than ints. 133 elements[count].integer = elem; 134 count++; 135 } 136} 137 138void UVector::setElementAt(void* obj, int32_t index) { 139 if (0 <= index && index < count) { 140 if (elements[index].pointer != 0 && deleter != 0) { 141 (*deleter)(elements[index].pointer); 142 } 143 elements[index].pointer = obj; 144 } 145 /* else index out of range */ 146} 147 148void UVector::setElementAt(int32_t elem, int32_t index) { 149 if (0 <= index && index < count) { 150 if (elements[index].pointer != 0 && deleter != 0) { 151 // TODO: this should be an error. mixing up ints and pointers. 152 (*deleter)(elements[index].pointer); 153 } 154 elements[index].pointer = NULL; 155 elements[index].integer = elem; 156 } 157 /* else index out of range */ 158} 159 160void UVector::insertElementAt(void* obj, int32_t index, UErrorCode &status) { 161 // must have 0 <= index <= count 162 if (0 <= index && index <= count && ensureCapacity(count + 1, status)) { 163 for (int32_t i=count; i>index; --i) { 164 elements[i] = elements[i-1]; 165 } 166 elements[index].pointer = obj; 167 ++count; 168 } 169 /* else index out of range */ 170} 171 172void UVector::insertElementAt(int32_t elem, int32_t index, UErrorCode &status) { 173 // must have 0 <= index <= count 174 if (0 <= index && index <= count && ensureCapacity(count + 1, status)) { 175 for (int32_t i=count; i>index; --i) { 176 elements[i] = elements[i-1]; 177 } 178 elements[index].pointer = NULL; 179 elements[index].integer = elem; 180 ++count; 181 } 182 /* else index out of range */ 183} 184 185void* UVector::elementAt(int32_t index) const { 186 return (0 <= index && index < count) ? elements[index].pointer : 0; 187} 188 189int32_t UVector::elementAti(int32_t index) const { 190 return (0 <= index && index < count) ? elements[index].integer : 0; 191} 192 193UBool UVector::containsAll(const UVector& other) const { 194 for (int32_t i=0; i<other.size(); ++i) { 195 if (indexOf(other.elements[i]) < 0) { 196 return FALSE; 197 } 198 } 199 return TRUE; 200} 201 202UBool UVector::containsNone(const UVector& other) const { 203 for (int32_t i=0; i<other.size(); ++i) { 204 if (indexOf(other.elements[i]) >= 0) { 205 return FALSE; 206 } 207 } 208 return TRUE; 209} 210 211UBool UVector::removeAll(const UVector& other) { 212 UBool changed = FALSE; 213 for (int32_t i=0; i<other.size(); ++i) { 214 int32_t j = indexOf(other.elements[i]); 215 if (j >= 0) { 216 removeElementAt(j); 217 changed = TRUE; 218 } 219 } 220 return changed; 221} 222 223UBool UVector::retainAll(const UVector& other) { 224 UBool changed = FALSE; 225 for (int32_t j=size()-1; j>=0; --j) { 226 int32_t i = other.indexOf(elements[j]); 227 if (i < 0) { 228 removeElementAt(j); 229 changed = TRUE; 230 } 231 } 232 return changed; 233} 234 235void UVector::removeElementAt(int32_t index) { 236 void* e = orphanElementAt(index); 237 if (e != 0 && deleter != 0) { 238 (*deleter)(e); 239 } 240} 241 242UBool UVector::removeElement(void* obj) { 243 int32_t i = indexOf(obj); 244 if (i >= 0) { 245 removeElementAt(i); 246 return TRUE; 247 } 248 return FALSE; 249} 250 251void UVector::removeAllElements(void) { 252 if (deleter != 0) { 253 for (int32_t i=0; i<count; ++i) { 254 if (elements[i].pointer != 0) { 255 (*deleter)(elements[i].pointer); 256 } 257 } 258 } 259 count = 0; 260} 261 262UBool UVector::equals(const UVector &other) const { 263 int i; 264 265 if (this->count != other.count) { 266 return FALSE; 267 } 268 if (comparer == 0) { 269 for (i=0; i<count; i++) { 270 if (elements[i].pointer != other.elements[i].pointer) { 271 return FALSE; 272 } 273 } 274 } else { 275 UHashTok key; 276 for (i=0; i<count; i++) { 277 key.pointer = &other.elements[i]; 278 if (!(*comparer)(key, elements[i])) { 279 return FALSE; 280 } 281 } 282 } 283 return TRUE; 284} 285 286 287 288int32_t UVector::indexOf(void* obj, int32_t startIndex) const { 289 UHashTok key; 290 key.pointer = obj; 291 return indexOf(key, startIndex, HINT_KEY_POINTER); 292} 293 294int32_t UVector::indexOf(int32_t obj, int32_t startIndex) const { 295 UHashTok key; 296 key.integer = obj; 297 return indexOf(key, startIndex, HINT_KEY_INTEGER); 298} 299 300// This only works if this object has a non-null comparer 301int32_t UVector::indexOf(UHashTok key, int32_t startIndex, int8_t hint) const { 302 int32_t i; 303 if (comparer != 0) { 304 for (i=startIndex; i<count; ++i) { 305 if ((*comparer)(key, elements[i])) { 306 return i; 307 } 308 } 309 } else { 310 for (i=startIndex; i<count; ++i) { 311 /* Pointers are not always the same size as ints so to perform 312 * a valid comparision we need to know whether we are being 313 * provided an int or a pointer. */ 314 if (hint & HINT_KEY_POINTER) { 315 if (key.pointer == elements[i].pointer) { 316 return i; 317 } 318 } else { 319 if (key.integer == elements[i].integer) { 320 return i; 321 } 322 } 323 } 324 } 325 return -1; 326} 327 328UBool UVector::ensureCapacity(int32_t minimumCapacity, UErrorCode &status) { 329 if (minimumCapacity < 0) { 330 status = U_ILLEGAL_ARGUMENT_ERROR; 331 return FALSE; 332 } 333 if (capacity < minimumCapacity) { 334 if (capacity > (INT32_MAX - 1) / 2) { // integer overflow check 335 status = U_ILLEGAL_ARGUMENT_ERROR; 336 return FALSE; 337 } 338 int32_t newCap = capacity * 2; 339 if (newCap < minimumCapacity) { 340 newCap = minimumCapacity; 341 } 342 if (newCap > (int32_t)(INT32_MAX / sizeof(UHashTok))) { // integer overflow check 343 // We keep the original memory contents on bad minimumCapacity. 344 status = U_ILLEGAL_ARGUMENT_ERROR; 345 return FALSE; 346 } 347 UHashTok* newElems = (UHashTok *)uprv_realloc(elements, sizeof(UHashTok)*newCap); 348 if (newElems == NULL) { 349 // We keep the original contents on the memory failure on realloc or bad minimumCapacity. 350 status = U_MEMORY_ALLOCATION_ERROR; 351 return FALSE; 352 } 353 elements = newElems; 354 capacity = newCap; 355 } 356 return TRUE; 357} 358 359/** 360 * Change the size of this vector as follows: If newSize is smaller, 361 * then truncate the array, possibly deleting held elements for i >= 362 * newSize. If newSize is larger, grow the array, filling in new 363 * slots with NULL. 364 */ 365void UVector::setSize(int32_t newSize, UErrorCode &status) { 366 int32_t i; 367 if (newSize < 0) { 368 return; 369 } 370 if (newSize > count) { 371 if (!ensureCapacity(newSize, status)) { 372 return; 373 } 374 UHashTok empty; 375 empty.pointer = NULL; 376 empty.integer = 0; 377 for (i=count; i<newSize; ++i) { 378 elements[i] = empty; 379 } 380 } else { 381 /* Most efficient to count down */ 382 for (i=count-1; i>=newSize; --i) { 383 removeElementAt(i); 384 } 385 } 386 count = newSize; 387} 388 389/** 390 * Fill in the given array with all elements of this vector. 391 */ 392void** UVector::toArray(void** result) const { 393 void** a = result; 394 for (int i=0; i<count; ++i) { 395 *a++ = elements[i].pointer; 396 } 397 return result; 398} 399 400UObjectDeleter *UVector::setDeleter(UObjectDeleter *d) { 401 UObjectDeleter *old = deleter; 402 deleter = d; 403 return old; 404} 405 406UKeyComparator *UVector::setComparer(UKeyComparator *d) { 407 UKeyComparator *old = comparer; 408 comparer = d; 409 return old; 410} 411 412/** 413 * Removes the element at the given index from this vector and 414 * transfer ownership of it to the caller. After this call, the 415 * caller owns the result and must delete it and the vector entry 416 * at 'index' is removed, shifting all subsequent entries back by 417 * one index and shortening the size of the vector by one. If the 418 * index is out of range or if there is no item at the given index 419 * then 0 is returned and the vector is unchanged. 420 */ 421void* UVector::orphanElementAt(int32_t index) { 422 void* e = 0; 423 if (0 <= index && index < count) { 424 e = elements[index].pointer; 425 for (int32_t i=index; i<count-1; ++i) { 426 elements[i] = elements[i+1]; 427 } 428 --count; 429 } 430 /* else index out of range */ 431 return e; 432} 433 434/** 435 * Insert the given object into this vector at its sorted position 436 * as defined by 'compare'. The current elements are assumed to 437 * be sorted already. 438 */ 439void UVector::sortedInsert(void* obj, USortComparator *compare, UErrorCode& ec) { 440 UHashTok tok; 441 tok.pointer = obj; 442 sortedInsert(tok, compare, ec); 443} 444 445/** 446 * Insert the given integer into this vector at its sorted position 447 * as defined by 'compare'. The current elements are assumed to 448 * be sorted already. 449 */ 450void UVector::sortedInsert(int32_t obj, USortComparator *compare, UErrorCode& ec) { 451 UHashTok tok; 452 tok.integer = obj; 453 sortedInsert(tok, compare, ec); 454} 455 456// ASSUME elements[] IS CURRENTLY SORTED 457void UVector::sortedInsert(UHashTok tok, USortComparator *compare, UErrorCode& ec) { 458 // Perform a binary search for the location to insert tok at. Tok 459 // will be inserted between two elements a and b such that a <= 460 // tok && tok < b, where there is a 'virtual' elements[-1] always 461 // less than tok and a 'virtual' elements[count] always greater 462 // than tok. 463 int32_t min = 0, max = count; 464 while (min != max) { 465 int32_t probe = (min + max) / 2; 466 int8_t c = (*compare)(elements[probe], tok); 467 if (c > 0) { 468 max = probe; 469 } else { 470 // assert(c <= 0); 471 min = probe + 1; 472 } 473 } 474 if (ensureCapacity(count + 1, ec)) { 475 for (int32_t i=count; i>min; --i) { 476 elements[i] = elements[i-1]; 477 } 478 elements[min] = tok; 479 ++count; 480 } 481} 482 483/** 484 * Array sort comparator function. 485 * Used from UVector::sort() 486 * Conforms to function signature required for uprv_sortArray(). 487 * This function is essentially just a wrapper, to make a 488 * UVector style comparator function usable with uprv_sortArray(). 489 * 490 * The context pointer to this function is a pointer back 491 * (with some extra indirection) to the user supplied comparator. 492 * 493 */ 494static int32_t U_CALLCONV 495sortComparator(const void *context, const void *left, const void *right) { 496 USortComparator *compare = *static_cast<USortComparator * const *>(context); 497 UHashTok tok1 = *static_cast<const UHashTok *>(left); 498 UHashTok tok2 = *static_cast<const UHashTok *>(right); 499 int32_t result = (*compare)(tok1, tok2); 500 return result; 501} 502 503 504/** 505 * Array sort comparison function for use from UVector::sorti() 506 * Compares int32_t vector elements. 507 */ 508static int32_t U_CALLCONV 509sortiComparator(const void * /*context */, const void *left, const void *right) { 510 const UHashTok *tok1 = static_cast<const UHashTok *>(left); 511 const UHashTok *tok2 = static_cast<const UHashTok *>(right); 512 int32_t result = tok1->integer < tok2->integer? -1 : 513 tok1->integer == tok2->integer? 0 : 1; 514 return result; 515} 516 517/** 518 * Sort the vector, assuming it constains ints. 519 * (A more general sort would take a comparison function, but it's 520 * not clear whether UVector's USortComparator or 521 * UComparator from uprv_sortAray would be more appropriate.) 522 */ 523void UVector::sorti(UErrorCode &ec) { 524 if (U_SUCCESS(ec)) { 525 uprv_sortArray(elements, count, sizeof(UHashTok), 526 sortiComparator, NULL, FALSE, &ec); 527 } 528} 529 530 531/** 532 * Sort with a user supplied comparator. 533 * 534 * The comparator function handling is confusing because the function type 535 * for UVector (as defined for sortedInsert()) is different from the signature 536 * required by uprv_sortArray(). This is handled by passing the 537 * the UVector sort function pointer via the context pointer to a 538 * sortArray() comparator function, which can then call back to 539 * the original user functtion. 540 * 541 * An additional twist is that it's not safe to pass a pointer-to-function 542 * as a (void *) data pointer, so instead we pass a (data) pointer to a 543 * pointer-to-function variable. 544 */ 545void UVector::sort(USortComparator *compare, UErrorCode &ec) { 546 if (U_SUCCESS(ec)) { 547 uprv_sortArray(elements, count, sizeof(UHashTok), 548 sortComparator, &compare, FALSE, &ec); 549 } 550} 551 552 553/** 554 * Sort with a user supplied comparator of type UComparator. 555 */ 556void UVector::sortWithUComparator(UComparator *compare, const void *context, UErrorCode &ec) { 557 if (U_SUCCESS(ec)) { 558 uprv_sortArray(elements, count, sizeof(UHashTok), 559 compare, context, FALSE, &ec); 560 } 561} 562 563U_NAMESPACE_END 564 565