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
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
30UOBJECT_DEFINE_RTTI_IMPLEMENTATION(UVector)
31
32UVector::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
42UVector::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
52UVector::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
62UVector::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
72void 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
88UVector::~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 */
98void 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
113UBool 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
127void UVector::addElement(void* obj, UErrorCode &status) {
128 if (ensureCapacity(count + 1, status)) {
129 elements[count++].pointer = obj;
130 }
131}
132
133void 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
141void 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
151void 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
163void 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
175void 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
188void* UVector::elementAt(int32_t index) const {
189 return (0 <= index && index < count) ? elements[index].pointer : 0;
190}
191
192int32_t UVector::elementAti(int32_t index) const {
193 return (0 <= index && index < count) ? elements[index].integer : 0;
194}
195
196UBool 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
205UBool 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
214UBool 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
226UBool 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
238void UVector::removeElementAt(int32_t index) {
239 void* e = orphanElementAt(index);
240 if (e != 0 && deleter != 0) {
241 (*deleter)(e);
242 }
243}
244
245UBool 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
254void 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
265UBool 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
291int32_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
297int32_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
304int32_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
331UBool 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 */
368void 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 */
395void** 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
403UObjectDeleter *UVector::setDeleter(UObjectDeleter *d) {
404 UObjectDeleter *old = deleter;
405 deleter = d;
406 return old;
407}
408
409UElementsAreEqual *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 */
424void* 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 */
442void 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 */
453void 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
460void 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 */
497static int32_t U_CALLCONV
498sortComparator(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 */
511static int32_t U_CALLCONV
512sortiComparator(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 */
526void 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 */
548void 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 */
559void 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
566U_NAMESPACE_END
567
568