source/common/uvectr32.cpp

   1 /*
   2 ******************************************************************************
   3 * Copyright (C) 1999-2015, 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 "uvectr32.h"
  12 #include "cmemory.h"
  13 #include "putilimp.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
  25 UOBJECT_DEFINE_RTTI_IMPLEMENTATION(UVector32)
  26
  27 UVector32::UVector32(UErrorCode &status) :
  28     count(0),
  29     capacity(0),
  30     maxCapacity(0),
  31     elements(NULL)
  32 {
  33     _init(DEFAULT_CAPACITY, status);
  34 }
  35
  36 UVector32::UVector32(int32_t initialCapacity, UErrorCode &status) :
  37     count(0),
  38     capacity(0),
  39     maxCapacity(0),
  40     elements(0)
  41 {
  42     _init(initialCapacity, status);
  43 }
  44
  45
  46
  47 void UVector32::_init(int32_t initialCapacity, UErrorCode &status) {
  48     // Fix bogus initialCapacity values; avoid malloc(0)
  49     if (initialCapacity < 1) {
  50         initialCapacity = DEFAULT_CAPACITY;
  51     }
  52     if (maxCapacity>0 && maxCapacity<initialCapacity) {
  53         initialCapacity = maxCapacity;
  54     }
  55     if (initialCapacity > (int32_t)(INT32_MAX / sizeof(int32_t))) {
  56         initialCapacity = uprv_min(DEFAULT_CAPACITY, maxCapacity);
  57     }
  58     elements = (int32_t *)uprv_malloc(sizeof(int32_t)*initialCapacity);
  59     if (elements == 0) {
  60         status = U_MEMORY_ALLOCATION_ERROR;
  61     } else {
  62         capacity = initialCapacity;
  63     }
  64 }
  65
  66 UVector32::~UVector32() {
  67     uprv_free(elements);
  68     elements = 0;
  69 }
  70
  71 /**
  72  * Assign this object to another (make this a copy of 'other').
  73  */
  74 void UVector32::assign(const UVector32& other, UErrorCode &ec) {
  75     if (ensureCapacity(other.count, ec)) {
  76         setSize(other.count);
  77         for (int32_t i=0; i<other.count; ++i) {
  78             elements[i] = other.elements[i];
  79         }
  80     }
  81 }
  82
  83
  84 UBool UVector32::operator==(const UVector32& other) {
  85     int32_t i;
  86     if (count != other.count) return FALSE;
  87     for (i=0; i<count; ++i) {
  88         if (elements[i] != other.elements[i]) {
  89             return FALSE;
  90         }
  91     }
  92     return TRUE;
  93 }
  94
  95
  96 void UVector32::setElementAt(int32_t elem, int32_t index) {
  97     if (0 <= index && index < count) {
  98         elements[index] = elem;
  99     }
 100     /* else index out of range */
 101 }
 102
 103 void UVector32::insertElementAt(int32_t elem, int32_t index, UErrorCode &status) {
 104     // must have 0 <= index <= count
 105     if (0 <= index && index <= count && ensureCapacity(count + 1, status)) {
 106         for (int32_t i=count; i>index; --i) {
 107             elements[i] = elements[i-1];
 108         }
 109         elements[index] = elem;
 110         ++count;
 111     }
 112     /* else index out of range */
 113 }
 114
 115 UBool UVector32::containsAll(const UVector32& other) const {
 116     for (int32_t i=0; i<other.size(); ++i) {
 117         if (indexOf(other.elements[i]) < 0) {
 118             return FALSE;
 119         }
 120     }
 121     return TRUE;
 122 }
 123
 124 UBool UVector32::containsNone(const UVector32& other) const {
 125     for (int32_t i=0; i<other.size(); ++i) {
 126         if (indexOf(other.elements[i]) >= 0) {
 127             return FALSE;
 128         }
 129     }
 130     return TRUE;
 131 }
 132
 133 UBool UVector32::removeAll(const UVector32& other) {
 134     UBool changed = FALSE;
 135     for (int32_t i=0; i<other.size(); ++i) {
 136         int32_t j = indexOf(other.elements[i]);
 137         if (j >= 0) {
 138             removeElementAt(j);
 139             changed = TRUE;
 140         }
 141     }
 142     return changed;
 143 }
 144
 145 UBool UVector32::retainAll(const UVector32& other) {
 146     UBool changed = FALSE;
 147     for (int32_t j=size()-1; j>=0; --j) {
 148         int32_t i = other.indexOf(elements[j]);
 149         if (i < 0) {
 150             removeElementAt(j);
 151             changed = TRUE;
 152         }
 153     }
 154     return changed;
 155 }
 156
 157 void UVector32::removeElementAt(int32_t index) {
 158     if (index >= 0) {
 159         for (int32_t i=index; i<count-1; ++i) {
 160             elements[i] = elements[i+1];
 161         }
 162         --count;
 163     }
 164 }
 165
 166 void UVector32::removeAllElements(void) {
 167     count = 0;
 168 }
 169
 170 UBool   UVector32::equals(const UVector32 &other) const {
 171     int      i;
 172
 173     if (this->count != other.count) {
 174         return FALSE;
 175     }
 176     for (i=0; i<count; i++) {
 177         if (elements[i] != other.elements[i]) {
 178             return FALSE;
 179         }
 180     }
 181     return TRUE;
 182 }
 183
 184
 185
 186
 187 int32_t UVector32::indexOf(int32_t key, int32_t startIndex) const {
 188     int32_t i;
 189     for (i=startIndex; i<count; ++i) {
 190         if (key == elements[i]) {
 191             return i;
 192         }
 193     }
 194     return -1;
 195 }
 196
 197
 198 UBool UVector32::expandCapacity(int32_t minimumCapacity, UErrorCode &status) {
 199     if (U_FAILURE(status)) {
 200         return FALSE;
 201     }
 202     if (minimumCapacity < 0) {
 203         status = U_ILLEGAL_ARGUMENT_ERROR;
 204         return FALSE;
 205     }
 206     if (capacity >= minimumCapacity) {
 207         return TRUE;
 208     }
 209     if (maxCapacity>0 && minimumCapacity>maxCapacity) {
 210         status = U_BUFFER_OVERFLOW_ERROR;
 211         return FALSE;
 212     }
 213     if (capacity > (INT32_MAX - 1) / 2) {  // integer overflow check
 214         status = U_ILLEGAL_ARGUMENT_ERROR;
 215         return FALSE;
 216     }
 217     int32_t newCap = capacity * 2;
 218     if (newCap < minimumCapacity) {
 219         newCap = minimumCapacity;
 220     }
 221     if (maxCapacity > 0 && newCap > maxCapacity) {
 222         newCap = maxCapacity;
 223     }
 224     if (newCap > (int32_t)(INT32_MAX / sizeof(int32_t))) {  // integer overflow check
 225         // We keep the original memory contents on bad minimumCapacity/maxCapacity.
 226         status = U_ILLEGAL_ARGUMENT_ERROR;
 227         return FALSE;
 228     }
 229     int32_t* newElems = (int32_t *)uprv_realloc(elements, sizeof(int32_t)*newCap);
 230     if (newElems == NULL) {
 231         // We keep the original contents on the memory failure on realloc.
 232         status = U_MEMORY_ALLOCATION_ERROR;
 233         return FALSE;
 234     }
 235     elements = newElems;
 236     capacity = newCap;
 237     return TRUE;
 238 }
 239
 240 void UVector32::setMaxCapacity(int32_t limit) {
 241     U_ASSERT(limit >= 0);
 242     if (limit < 0) {
 243         limit = 0;
 244     }
 245     if (limit > (int32_t)(INT32_MAX / sizeof(int32_t))) {  // integer overflow check for realloc
 246         //  Something is very wrong, don't realloc, leave capacity and maxCapacity unchanged
 247         return;
 248     }
 249     maxCapacity = limit;
 250     if (capacity <= maxCapacity || maxCapacity == 0) {
 251         // Current capacity is within the new limit.
 252         return;
 253     }
 254
 255     // New maximum capacity is smaller than the current size.
 256     // Realloc the storage to the new, smaller size.
 257     int32_t* newElems = (int32_t *)uprv_realloc(elements, sizeof(int32_t)*maxCapacity);
 258     if (newElems == NULL) {
 259         // Realloc to smaller failed.
 260         //   Just keep what we had.  No need to call it a failure.
 261         return;
 262     }
 263     elements = newElems;
 264     capacity = maxCapacity;
 265     if (count > capacity) {
 266         count = capacity;
 267     }
 268 }
 269
 270 /**
 271  * Change the size of this vector as follows: If newSize is smaller,
 272  * then truncate the array, possibly deleting held elements for i >=
 273  * newSize.  If newSize is larger, grow the array, filling in new
 274  * slots with NULL.
 275  */
 276 void UVector32::setSize(int32_t newSize) {
 277     int32_t i;
 278     if (newSize < 0) {
 279         return;
 280     }
 281     if (newSize > count) {
 282         UErrorCode ec = U_ZERO_ERROR;
 283         if (!ensureCapacity(newSize, ec)) {
 284             return;
 285         }
 286         for (i=count; i<newSize; ++i) {
 287             elements[i] = 0;
 288         }
 289     }
 290     count = newSize;
 291 }
 292
 293
 294
 295
 296 /**
 297  * Insert the given integer into this vector at its sorted position
 298  * as defined by 'compare'.  The current elements are assumed to
 299  * be sorted already.
 300  */
 301 void UVector32::sortedInsert(int32_t tok, UErrorCode& ec) {
 302     // Perform a binary search for the location to insert tok at.  Tok
 303     // will be inserted between two elements a and b such that a <=
 304     // tok && tok < b, where there is a 'virtual' elements[-1] always
 305     // less than tok and a 'virtual' elements[count] always greater
 306     // than tok.
 307     int32_t min = 0, max = count;
 308     while (min != max) {
 309         int32_t probe = (min + max) / 2;
 310         //int8_t c = (*compare)(elements[probe], tok);
 311         //if (c > 0) {
 312         if (elements[probe] > tok) {
 313             max = probe;
 314         } else {
 315             // assert(c <= 0);
 316             min = probe + 1;
 317         }
 318     }
 319     if (ensureCapacity(count + 1, ec)) {
 320         for (int32_t i=count; i>min; --i) {
 321             elements[i] = elements[i-1];
 322         }
 323         elements[min] = tok;
 324         ++count;
 325     }
 326 }
 327
 328
 329
 330
 331
 332 U_NAMESPACE_END
 333