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 */
10 
11 #include "uvector.h"
12 #include "cmemory.h"
13 #include "uarrsort.h"
14 #include "uelement.h"
15 
16 U_NAMESPACE_BEGIN
17 
18 #define DEFAULT_CAPACITY 8
19 
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)
27 
UOBJECT_DEFINE_RTTI_IMPLEMENTATION(UVector)28 UOBJECT_DEFINE_RTTI_IMPLEMENTATION(UVector)
29 
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 }
39 
UVector(int32_t initialCapacity,UErrorCode & status)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 }
49 
UVector(UObjectDeleter * d,UElementsAreEqual * c,UErrorCode & status)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 }
59 
UVector(UObjectDeleter * d,UElementsAreEqual * c,int32_t initialCapacity,UErrorCode & status)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 }
69 
_init(int32_t initialCapacity,UErrorCode & status)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 }
85 
~UVector()86 UVector::~UVector() {
87     removeAllElements();
88     uprv_free(elements);
89     elements = 0;
90 }
91 
92 /**
93  * Assign this object to another (make this a copy of 'other').
94  * Use the 'assign' function to assign each element.
95  */
assign(const UVector & other,UElementAssigner * assign,UErrorCode & ec)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 }
109 
110 // This only does something sensible if this object has a non-null comparer
operator ==(const UVector & other)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 }
124 
addElement(void * obj,UErrorCode & status)125 void UVector::addElement(void* obj, UErrorCode &status) {
126     if (ensureCapacity(count + 1, status)) {
127         elements[count++].pointer = obj;
128     }
129 }
130 
addElement(int32_t elem,UErrorCode & status)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 }
138 
setElementAt(void * obj,int32_t index)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 }
148 
setElementAt(int32_t elem,int32_t index)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 }
160 
insertElementAt(void * obj,int32_t index,UErrorCode & status)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 }
172 
insertElementAt(int32_t elem,int32_t index,UErrorCode & status)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 }
185 
elementAt(int32_t index) const186 void* UVector::elementAt(int32_t index) const {
187     return (0 <= index && index < count) ? elements[index].pointer : 0;
188 }
189 
elementAti(int32_t index) const190 int32_t UVector::elementAti(int32_t index) const {
191     return (0 <= index && index < count) ? elements[index].integer : 0;
192 }
193 
containsAll(const UVector & other) const194 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 }
202 
containsNone(const UVector & other) const203 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 }
211 
removeAll(const UVector & other)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 }
223 
retainAll(const UVector & other)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 }
235 
removeElementAt(int32_t index)236 void UVector::removeElementAt(int32_t index) {
237     void* e = orphanElementAt(index);
238     if (e != 0 && deleter != 0) {
239         (*deleter)(e);
240     }
241 }
242 
removeElement(void * obj)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 }
251 
removeAllElements(void)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 }
262 
equals(const UVector & other) const263 UBool   UVector::equals(const UVector &other) const {
264     int      i;
265 
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 }
286 
287 
288 
indexOf(void * obj,int32_t startIndex) const289 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 }
294 
indexOf(int32_t obj,int32_t startIndex) const295 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 }
300 
301 // This only works if this object has a non-null comparer
indexOf(UElement key,int32_t startIndex,int8_t hint) const302 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 }
328 
ensureCapacity(int32_t minimumCapacity,UErrorCode & status)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 }
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 NULL.
365  */
setSize(int32_t newSize,UErrorCode & status)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 }
389 
390 /**
391  * Fill in the given array with all elements of this vector.
392  */
toArray(void ** result) const393 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 }
400 
setDeleter(UObjectDeleter * d)401 UObjectDeleter *UVector::setDeleter(UObjectDeleter *d) {
402     UObjectDeleter *old = deleter;
403     deleter = d;
404     return old;
405 }
406 
setComparer(UElementsAreEqual * d)407 UElementsAreEqual *UVector::setComparer(UElementsAreEqual *d) {
408     UElementsAreEqual *old = comparer;
409     comparer = d;
410     return old;
411 }
412 
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  */
orphanElementAt(int32_t index)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 }
434 
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  */
sortedInsert(void * obj,UElementComparator * compare,UErrorCode & ec)440 void UVector::sortedInsert(void* obj, UElementComparator *compare, UErrorCode& ec) {
441     UElement e;
442     e.pointer = obj;
443     sortedInsert(e, compare, ec);
444 }
445 
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  */
sortedInsert(int32_t obj,UElementComparator * compare,UErrorCode & ec)451 void UVector::sortedInsert(int32_t obj, UElementComparator *compare, UErrorCode& ec) {
452     UElement e;
453     e.integer = obj;
454     sortedInsert(e, compare, ec);
455 }
456 
457 // ASSUME elements[] IS CURRENTLY SORTED
sortedInsert(UElement e,UElementComparator * compare,UErrorCode & ec)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 }
483 
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
sortComparator(const void * context,const void * left,const void * right)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 }
503 
504 
505 /**
506   *  Array sort comparison function for use from UVector::sorti()
507   *  Compares int32_t vector elements.
508   */
509 static int32_t U_CALLCONV
sortiComparator(const void *,const void * left,const void * right)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 }
517 
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   */
sorti(UErrorCode & ec)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 }
530 
531 
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  */
sort(UElementComparator * compare,UErrorCode & ec)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 }
552 
553 
554 /**
555  *  Stable sort with a user supplied comparator of type UComparator.
556  */
sortWithUComparator(UComparator * compare,const void * context,UErrorCode & ec)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 }
563 
564 U_NAMESPACE_END
565 
566