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