1 /* 2 ****************************************************************************** 3 * Copyright (C) 1999-2010, 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 15 U_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 27 UOBJECT_DEFINE_RTTI_IMPLEMENTATION(UVector) 28 29 UVector::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 39 UVector::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 49 UVector::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 59 UVector::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 69 void 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 85 UVector::~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 */ 95 void 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 110 UBool 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 124 void UVector::addElement(void* obj, UErrorCode &status) { 125 if (ensureCapacity(count + 1, status)) { 126 elements[count++].pointer = obj; 127 } 128 } 129 130 void 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 138 void 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 148 void 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 160 void 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 172 void 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 185 void* UVector::elementAt(int32_t index) const { 186 return (0 <= index && index < count) ? elements[index].pointer : 0; 187 } 188 189 int32_t UVector::elementAti(int32_t index) const { 190 return (0 <= index && index < count) ? elements[index].integer : 0; 191 } 192 193 UBool 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 202 UBool 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 211 UBool 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 223 UBool 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 235 void UVector::removeElementAt(int32_t index) { 236 void* e = orphanElementAt(index); 237 if (e != 0 && deleter != 0) { 238 (*deleter)(e); 239 } 240 } 241 242 UBool 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 251 void 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 262 UBool 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 288 int32_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 294 int32_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 301 int32_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 328 UBool 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 */ 365 void 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 */ 392 void** 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 400 UObjectDeleter *UVector::setDeleter(UObjectDeleter *d) { 401 UObjectDeleter *old = deleter; 402 deleter = d; 403 return old; 404 } 405 406 UKeyComparator *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 */ 421 void* 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 */ 439 void 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 */ 450 void 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 457 void 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 */ 494 static int32_t U_CALLCONV 495 sortComparator(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 */ 508 static int32_t U_CALLCONV 509 sortiComparator(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 */ 523 void 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 */ 545 void 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 U_NAMESPACE_END 553 554