Home | History | Annotate | Download | only in common
      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 
     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 
     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 
     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 
     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 
     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 
     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  */
     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
    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 
    125 void UVector::addElement(void* obj, UErrorCode &status) {
    126     if (ensureCapacity(count + 1, status)) {
    127         elements[count++].pointer = obj;
    128     }
    129 }
    130 
    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 
    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 
    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 
    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 
    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 
    186 void* UVector::elementAt(int32_t index) const {
    187     return (0 <= index && index < count) ? elements[index].pointer : 0;
    188 }
    189 
    190 int32_t UVector::elementAti(int32_t index) const {
    191     return (0 <= index && index < count) ? elements[index].integer : 0;
    192 }
    193 
    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 }
    202 
    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 }
    211 
    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 
    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 
    236 void UVector::removeElementAt(int32_t index) {
    237     void* e = orphanElementAt(index);
    238     if (e != 0 && deleter != 0) {
    239         (*deleter)(e);
    240     }
    241 }
    242 
    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 
    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 
    263 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 
    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 }
    294 
    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 }
    300 
    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 }
    328 
    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  */
    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  */
    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 }
    400 
    401 UObjectDeleter *UVector::setDeleter(UObjectDeleter *d) {
    402     UObjectDeleter *old = deleter;
    403     deleter = d;
    404     return old;
    405 }
    406 
    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  */
    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  */
    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  */
    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
    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
    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
    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   */
    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  */
    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  */
    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