intl/icu/source/common/uvector.cpp@fc2d59ddac77
intl/icu/source/common/uvector.cpp
Wed, 31 Dec 2014 07:22:50 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Wed, 31 Dec 2014 07:22:50 +0100
- branch
- TOR_BUG_3246
- changeset 4
- fc2d59ddac77
- permissions
- -rw-r--r--
Correct previous dual key logic pending first delivery installment.
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 */
11 #include "uvector.h"
12 #include "cmemory.h"
13 #include "uarrsort.h"
14 #include "uelement.h"
16 U_NAMESPACE_BEGIN
18 #define DEFAULT_CAPACITY 8
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)
28 UOBJECT_DEFINE_RTTI_IMPLEMENTATION(UVector)
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 }
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 }
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 }
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 }
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 }
86 UVector::~UVector() {
87 removeAllElements();
88 uprv_free(elements);
89 elements = 0;
90 }
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 }
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 }
125 void UVector::addElement(void* obj, UErrorCode &status) {
126 if (ensureCapacity(count + 1, status)) {
127 elements[count++].pointer = obj;
128 }
129 }
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 }
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 }
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 }
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 }
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 }
186 void* UVector::elementAt(int32_t index) const {
187 return (0 <= index && index < count) ? elements[index].pointer : 0;
188 }
190 int32_t UVector::elementAti(int32_t index) const {
191 return (0 <= index && index < count) ? elements[index].integer : 0;
192 }
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 }
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 }
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 }
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 }
236 void UVector::removeElementAt(int32_t index) {
237 void* e = orphanElementAt(index);
238 if (e != 0 && deleter != 0) {
239 (*deleter)(e);
240 }
241 }
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 }
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 }
263 UBool UVector::equals(const UVector &other) const {
264 int i;
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 }
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 }
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 }
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 }
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 }
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 }
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 }
401 UObjectDeleter *UVector::setDeleter(UObjectDeleter *d) {
402 UObjectDeleter *old = deleter;
403 deleter = d;
404 return old;
405 }
407 UElementsAreEqual *UVector::setComparer(UElementsAreEqual *d) {
408 UElementsAreEqual *old = comparer;
409 comparer = d;
410 return old;
411 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
564 U_NAMESPACE_END
