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