Line data Source code
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 0 : UOBJECT_DEFINE_RTTI_IMPLEMENTATION(UVector)
31 :
32 0 : UVector::UVector(UErrorCode &status) :
33 : count(0),
34 : capacity(0),
35 : elements(0),
36 : deleter(0),
37 0 : comparer(0)
38 : {
39 0 : _init(DEFAULT_CAPACITY, status);
40 0 : }
41 :
42 0 : UVector::UVector(int32_t initialCapacity, UErrorCode &status) :
43 : count(0),
44 : capacity(0),
45 : elements(0),
46 : deleter(0),
47 0 : comparer(0)
48 : {
49 0 : _init(initialCapacity, status);
50 0 : }
51 :
52 0 : UVector::UVector(UObjectDeleter *d, UElementsAreEqual *c, UErrorCode &status) :
53 : count(0),
54 : capacity(0),
55 : elements(0),
56 : deleter(d),
57 0 : comparer(c)
58 : {
59 0 : _init(DEFAULT_CAPACITY, status);
60 0 : }
61 :
62 0 : UVector::UVector(UObjectDeleter *d, UElementsAreEqual *c, int32_t initialCapacity, UErrorCode &status) :
63 : count(0),
64 : capacity(0),
65 : elements(0),
66 : deleter(d),
67 0 : comparer(c)
68 : {
69 0 : _init(initialCapacity, status);
70 0 : }
71 :
72 0 : void UVector::_init(int32_t initialCapacity, UErrorCode &status) {
73 0 : if (U_FAILURE(status)) {
74 0 : return;
75 : }
76 : // Fix bogus initialCapacity values; avoid malloc(0) and integer overflow
77 0 : if ((initialCapacity < 1) || (initialCapacity > (int32_t)(INT32_MAX / sizeof(UElement)))) {
78 0 : initialCapacity = DEFAULT_CAPACITY;
79 : }
80 0 : elements = (UElement *)uprv_malloc(sizeof(UElement)*initialCapacity);
81 0 : if (elements == 0) {
82 0 : status = U_MEMORY_ALLOCATION_ERROR;
83 : } else {
84 0 : capacity = initialCapacity;
85 : }
86 : }
87 :
88 0 : UVector::~UVector() {
89 0 : removeAllElements();
90 0 : uprv_free(elements);
91 0 : elements = 0;
92 0 : }
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 0 : void UVector::assign(const UVector& other, UElementAssigner *assign, UErrorCode &ec) {
99 0 : if (ensureCapacity(other.count, ec)) {
100 0 : setSize(other.count, ec);
101 0 : if (U_SUCCESS(ec)) {
102 0 : for (int32_t i=0; i<other.count; ++i) {
103 0 : if (elements[i].pointer != 0 && deleter != 0) {
104 0 : (*deleter)(elements[i].pointer);
105 : }
106 0 : (*assign)(&elements[i], &other.elements[i]);
107 : }
108 : }
109 : }
110 0 : }
111 :
112 : // This only does something sensible if this object has a non-null comparer
113 0 : UBool UVector::operator==(const UVector& other) {
114 : int32_t i;
115 0 : if (count != other.count) return FALSE;
116 0 : if (comparer != NULL) {
117 : // Compare using this object's comparer
118 0 : for (i=0; i<count; ++i) {
119 0 : if (!(*comparer)(elements[i], other.elements[i])) {
120 0 : return FALSE;
121 : }
122 : }
123 : }
124 0 : return TRUE;
125 : }
126 :
127 0 : void UVector::addElement(void* obj, UErrorCode &status) {
128 0 : if (ensureCapacity(count + 1, status)) {
129 0 : elements[count++].pointer = obj;
130 : }
131 0 : }
132 :
133 0 : void UVector::addElement(int32_t elem, UErrorCode &status) {
134 0 : if (ensureCapacity(count + 1, status)) {
135 0 : elements[count].pointer = NULL; // Pointers may be bigger than ints.
136 0 : elements[count].integer = elem;
137 0 : count++;
138 : }
139 0 : }
140 :
141 0 : void UVector::setElementAt(void* obj, int32_t index) {
142 0 : if (0 <= index && index < count) {
143 0 : if (elements[index].pointer != 0 && deleter != 0) {
144 0 : (*deleter)(elements[index].pointer);
145 : }
146 0 : elements[index].pointer = obj;
147 : }
148 : /* else index out of range */
149 0 : }
150 :
151 0 : void UVector::setElementAt(int32_t elem, int32_t index) {
152 0 : if (0 <= index && index < count) {
153 0 : if (elements[index].pointer != 0 && deleter != 0) {
154 : // TODO: this should be an error. mixing up ints and pointers.
155 0 : (*deleter)(elements[index].pointer);
156 : }
157 0 : elements[index].pointer = NULL;
158 0 : elements[index].integer = elem;
159 : }
160 : /* else index out of range */
161 0 : }
162 :
163 0 : void UVector::insertElementAt(void* obj, int32_t index, UErrorCode &status) {
164 : // must have 0 <= index <= count
165 0 : if (0 <= index && index <= count && ensureCapacity(count + 1, status)) {
166 0 : for (int32_t i=count; i>index; --i) {
167 0 : elements[i] = elements[i-1];
168 : }
169 0 : elements[index].pointer = obj;
170 0 : ++count;
171 : }
172 : /* else index out of range */
173 0 : }
174 :
175 0 : void UVector::insertElementAt(int32_t elem, int32_t index, UErrorCode &status) {
176 : // must have 0 <= index <= count
177 0 : if (0 <= index && index <= count && ensureCapacity(count + 1, status)) {
178 0 : for (int32_t i=count; i>index; --i) {
179 0 : elements[i] = elements[i-1];
180 : }
181 0 : elements[index].pointer = NULL;
182 0 : elements[index].integer = elem;
183 0 : ++count;
184 : }
185 : /* else index out of range */
186 0 : }
187 :
188 0 : void* UVector::elementAt(int32_t index) const {
189 0 : return (0 <= index && index < count) ? elements[index].pointer : 0;
190 : }
191 :
192 0 : int32_t UVector::elementAti(int32_t index) const {
193 0 : return (0 <= index && index < count) ? elements[index].integer : 0;
194 : }
195 :
196 0 : UBool UVector::containsAll(const UVector& other) const {
197 0 : for (int32_t i=0; i<other.size(); ++i) {
198 0 : if (indexOf(other.elements[i]) < 0) {
199 0 : return FALSE;
200 : }
201 : }
202 0 : return TRUE;
203 : }
204 :
205 0 : UBool UVector::containsNone(const UVector& other) const {
206 0 : for (int32_t i=0; i<other.size(); ++i) {
207 0 : if (indexOf(other.elements[i]) >= 0) {
208 0 : return FALSE;
209 : }
210 : }
211 0 : return TRUE;
212 : }
213 :
214 0 : UBool UVector::removeAll(const UVector& other) {
215 0 : UBool changed = FALSE;
216 0 : for (int32_t i=0; i<other.size(); ++i) {
217 0 : int32_t j = indexOf(other.elements[i]);
218 0 : if (j >= 0) {
219 0 : removeElementAt(j);
220 0 : changed = TRUE;
221 : }
222 : }
223 0 : return changed;
224 : }
225 :
226 0 : UBool UVector::retainAll(const UVector& other) {
227 0 : UBool changed = FALSE;
228 0 : for (int32_t j=size()-1; j>=0; --j) {
229 0 : int32_t i = other.indexOf(elements[j]);
230 0 : if (i < 0) {
231 0 : removeElementAt(j);
232 0 : changed = TRUE;
233 : }
234 : }
235 0 : return changed;
236 : }
237 :
238 0 : void UVector::removeElementAt(int32_t index) {
239 0 : void* e = orphanElementAt(index);
240 0 : if (e != 0 && deleter != 0) {
241 0 : (*deleter)(e);
242 : }
243 0 : }
244 :
245 0 : UBool UVector::removeElement(void* obj) {
246 0 : int32_t i = indexOf(obj);
247 0 : if (i >= 0) {
248 0 : removeElementAt(i);
249 0 : return TRUE;
250 : }
251 0 : return FALSE;
252 : }
253 :
254 0 : void UVector::removeAllElements(void) {
255 0 : if (deleter != 0) {
256 0 : for (int32_t i=0; i<count; ++i) {
257 0 : if (elements[i].pointer != 0) {
258 0 : (*deleter)(elements[i].pointer);
259 : }
260 : }
261 : }
262 0 : count = 0;
263 0 : }
264 :
265 0 : UBool UVector::equals(const UVector &other) const {
266 : int i;
267 :
268 0 : if (this->count != other.count) {
269 0 : return FALSE;
270 : }
271 0 : if (comparer == 0) {
272 0 : for (i=0; i<count; i++) {
273 0 : if (elements[i].pointer != other.elements[i].pointer) {
274 0 : return FALSE;
275 : }
276 : }
277 : } else {
278 : UElement key;
279 0 : for (i=0; i<count; i++) {
280 0 : key.pointer = &other.elements[i];
281 0 : if (!(*comparer)(key, elements[i])) {
282 0 : return FALSE;
283 : }
284 : }
285 : }
286 0 : return TRUE;
287 : }
288 :
289 :
290 :
291 0 : int32_t UVector::indexOf(void* obj, int32_t startIndex) const {
292 : UElement key;
293 0 : key.pointer = obj;
294 0 : return indexOf(key, startIndex, HINT_KEY_POINTER);
295 : }
296 :
297 0 : int32_t UVector::indexOf(int32_t obj, int32_t startIndex) const {
298 : UElement key;
299 0 : key.integer = obj;
300 0 : return indexOf(key, startIndex, HINT_KEY_INTEGER);
301 : }
302 :
303 : // This only works if this object has a non-null comparer
304 0 : int32_t UVector::indexOf(UElement key, int32_t startIndex, int8_t hint) const {
305 : int32_t i;
306 0 : if (comparer != 0) {
307 0 : for (i=startIndex; i<count; ++i) {
308 0 : if ((*comparer)(key, elements[i])) {
309 0 : return i;
310 : }
311 : }
312 : } else {
313 0 : 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 0 : if (hint & HINT_KEY_POINTER) {
318 0 : if (key.pointer == elements[i].pointer) {
319 0 : return i;
320 : }
321 : } else {
322 0 : if (key.integer == elements[i].integer) {
323 0 : return i;
324 : }
325 : }
326 : }
327 : }
328 0 : return -1;
329 : }
330 :
331 0 : UBool UVector::ensureCapacity(int32_t minimumCapacity, UErrorCode &status) {
332 0 : if (minimumCapacity < 0) {
333 0 : status = U_ILLEGAL_ARGUMENT_ERROR;
334 0 : return FALSE;
335 : }
336 0 : if (capacity < minimumCapacity) {
337 0 : if (capacity > (INT32_MAX - 1) / 2) { // integer overflow check
338 0 : status = U_ILLEGAL_ARGUMENT_ERROR;
339 0 : return FALSE;
340 : }
341 0 : int32_t newCap = capacity * 2;
342 0 : if (newCap < minimumCapacity) {
343 0 : newCap = minimumCapacity;
344 : }
345 0 : if (newCap > (int32_t)(INT32_MAX / sizeof(UElement))) { // integer overflow check
346 : // We keep the original memory contents on bad minimumCapacity.
347 0 : status = U_ILLEGAL_ARGUMENT_ERROR;
348 0 : return FALSE;
349 : }
350 0 : UElement* newElems = (UElement *)uprv_realloc(elements, sizeof(UElement)*newCap);
351 0 : if (newElems == NULL) {
352 : // We keep the original contents on the memory failure on realloc or bad minimumCapacity.
353 0 : status = U_MEMORY_ALLOCATION_ERROR;
354 0 : return FALSE;
355 : }
356 0 : elements = newElems;
357 0 : capacity = newCap;
358 : }
359 0 : 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 0 : void UVector::setSize(int32_t newSize, UErrorCode &status) {
369 : int32_t i;
370 0 : if (newSize < 0) {
371 0 : return;
372 : }
373 0 : if (newSize > count) {
374 0 : if (!ensureCapacity(newSize, status)) {
375 0 : return;
376 : }
377 : UElement empty;
378 0 : empty.pointer = NULL;
379 0 : empty.integer = 0;
380 0 : for (i=count; i<newSize; ++i) {
381 0 : elements[i] = empty;
382 : }
383 : } else {
384 : /* Most efficient to count down */
385 0 : for (i=count-1; i>=newSize; --i) {
386 0 : removeElementAt(i);
387 : }
388 : }
389 0 : count = newSize;
390 : }
391 :
392 : /**
393 : * Fill in the given array with all elements of this vector.
394 : */
395 0 : void** UVector::toArray(void** result) const {
396 0 : void** a = result;
397 0 : for (int i=0; i<count; ++i) {
398 0 : *a++ = elements[i].pointer;
399 : }
400 0 : return result;
401 : }
402 :
403 0 : UObjectDeleter *UVector::setDeleter(UObjectDeleter *d) {
404 0 : UObjectDeleter *old = deleter;
405 0 : deleter = d;
406 0 : return old;
407 : }
408 :
409 0 : UElementsAreEqual *UVector::setComparer(UElementsAreEqual *d) {
410 0 : UElementsAreEqual *old = comparer;
411 0 : comparer = d;
412 0 : 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 0 : void* UVector::orphanElementAt(int32_t index) {
425 0 : void* e = 0;
426 0 : if (0 <= index && index < count) {
427 0 : e = elements[index].pointer;
428 0 : for (int32_t i=index; i<count-1; ++i) {
429 0 : elements[i] = elements[i+1];
430 : }
431 0 : --count;
432 : }
433 : /* else index out of range */
434 0 : 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 0 : void UVector::sortedInsert(void* obj, UElementComparator *compare, UErrorCode& ec) {
443 : UElement e;
444 0 : e.pointer = obj;
445 0 : sortedInsert(e, compare, ec);
446 0 : }
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 0 : void UVector::sortedInsert(int32_t obj, UElementComparator *compare, UErrorCode& ec) {
454 : UElement e;
455 0 : e.integer = obj;
456 0 : sortedInsert(e, compare, ec);
457 0 : }
458 :
459 : // ASSUME elements[] IS CURRENTLY SORTED
460 0 : 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 0 : int32_t min = 0, max = count;
467 0 : while (min != max) {
468 0 : int32_t probe = (min + max) / 2;
469 0 : int8_t c = (*compare)(elements[probe], e);
470 0 : if (c > 0) {
471 0 : max = probe;
472 : } else {
473 : // assert(c <= 0);
474 0 : min = probe + 1;
475 : }
476 : }
477 0 : if (ensureCapacity(count + 1, ec)) {
478 0 : for (int32_t i=count; i>min; --i) {
479 0 : elements[i] = elements[i-1];
480 : }
481 0 : elements[min] = e;
482 0 : ++count;
483 : }
484 0 : }
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 0 : sortComparator(const void *context, const void *left, const void *right) {
499 0 : UElementComparator *compare = *static_cast<UElementComparator * const *>(context);
500 0 : UElement e1 = *static_cast<const UElement *>(left);
501 0 : UElement e2 = *static_cast<const UElement *>(right);
502 0 : int32_t result = (*compare)(e1, e2);
503 0 : 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 0 : sortiComparator(const void * /*context */, const void *left, const void *right) {
513 0 : const UElement *e1 = static_cast<const UElement *>(left);
514 0 : const UElement *e2 = static_cast<const UElement *>(right);
515 0 : int32_t result = e1->integer < e2->integer? -1 :
516 0 : e1->integer == e2->integer? 0 : 1;
517 0 : 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 0 : void UVector::sorti(UErrorCode &ec) {
527 0 : if (U_SUCCESS(ec)) {
528 0 : uprv_sortArray(elements, count, sizeof(UElement),
529 0 : sortiComparator, NULL, FALSE, &ec);
530 : }
531 0 : }
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 0 : void UVector::sort(UElementComparator *compare, UErrorCode &ec) {
549 0 : if (U_SUCCESS(ec)) {
550 0 : uprv_sortArray(elements, count, sizeof(UElement),
551 0 : sortComparator, &compare, FALSE, &ec);
552 : }
553 0 : }
554 :
555 :
556 : /**
557 : * Stable sort with a user supplied comparator of type UComparator.
558 : */
559 0 : void UVector::sortWithUComparator(UComparator *compare, const void *context, UErrorCode &ec) {
560 0 : if (U_SUCCESS(ec)) {
561 0 : uprv_sortArray(elements, count, sizeof(UElement),
562 0 : compare, context, TRUE, &ec);
563 : }
564 0 : }
565 :
566 : U_NAMESPACE_END
567 :
|
