source/common/uvectr32.cpp

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