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