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