icuSources/common/uvectr32.cpp

   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 "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 (minimumCapacity < 0) {
 200         status = U_ILLEGAL_ARGUMENT_ERROR;
 201         return FALSE;
 202     }
 203     if (capacity >= minimumCapacity) {
 204         return TRUE;
 205     }
 206     if (maxCapacity>0 && minimumCapacity>maxCapacity) {
 207         status = U_BUFFER_OVERFLOW_ERROR;
 208         return FALSE;
 209     }
 210     if (capacity > (INT32_MAX - 1) / 2) {  // integer overflow check
 211         status = U_ILLEGAL_ARGUMENT_ERROR;
 212         return FALSE;
 213     }
 214     int32_t newCap = capacity * 2;
 215     if (newCap < minimumCapacity) {
 216         newCap = minimumCapacity;
 217     }
 218     if (maxCapacity > 0 && newCap > maxCapacity) {
 219         newCap = maxCapacity;
 220     }
 221     if (newCap > (int32_t)(INT32_MAX / sizeof(int32_t))) {  // integer overflow check
 222         // We keep the original memory contents on bad minimumCapacity/maxCapacity.
 223         status = U_ILLEGAL_ARGUMENT_ERROR;
 224         return FALSE;
 225     }
 226     int32_t* newElems = (int32_t *)uprv_realloc(elements, sizeof(int32_t)*newCap);
 227     if (newElems == NULL) {
 228         // We keep the original contents on the memory failure on realloc.
 229         status = U_MEMORY_ALLOCATION_ERROR;
 230         return FALSE;
 231     }
 232     elements = newElems;
 233     capacity = newCap;
 234     return TRUE;
 235 }
 236
 237 void UVector32::setMaxCapacity(int32_t limit) {
 238     U_ASSERT(limit >= 0);
 239     if (limit < 0) {
 240         limit = 0;
 241     }
 242     if (limit > (int32_t)(INT32_MAX / sizeof(int32_t))) {  // integer overflow check for realloc
 243         //  Something is very wrong, don't realloc, leave capacity and maxCapacity unchanged
 244         return;
 245     }
 246     maxCapacity = limit;
 247     if (capacity <= maxCapacity || maxCapacity == 0) {
 248         // Current capacity is within the new limit.
 249         return;
 250     }
 251
 252     // New maximum capacity is smaller than the current size.
 253     // Realloc the storage to the new, smaller size.
 254     int32_t* newElems = (int32_t *)uprv_realloc(elements, sizeof(int32_t)*maxCapacity);
 255     if (newElems == NULL) {
 256         // Realloc to smaller failed.
 257         //   Just keep what we had.  No need to call it a failure.
 258         return;
 259     }
 260     elements = newElems;
 261     capacity = maxCapacity;
 262     if (count > capacity) {
 263         count = capacity;
 264     }
 265 }
 266
 267 /**
 268  * Change the size of this vector as follows: If newSize is smaller,
 269  * then truncate the array, possibly deleting held elements for i >=
 270  * newSize.  If newSize is larger, grow the array, filling in new
 271  * slots with NULL.
 272  */
 273 void UVector32::setSize(int32_t newSize) {
 274     int32_t i;
 275     if (newSize < 0) {
 276         return;
 277     }
 278     if (newSize > count) {
 279         UErrorCode ec = U_ZERO_ERROR;
 280         if (!ensureCapacity(newSize, ec)) {
 281             return;
 282         }
 283         for (i=count; i<newSize; ++i) {
 284             elements[i] = 0;
 285         }
 286     }
 287     count = newSize;
 288 }
 289
 290
 291
 292
 293 /**
 294  * Insert the given integer into this vector at its sorted position
 295  * as defined by 'compare'.  The current elements are assumed to
 296  * be sorted already.
 297  */
 298 void UVector32::sortedInsert(int32_t tok, UErrorCode& ec) {
 299     // Perform a binary search for the location to insert tok at.  Tok
 300     // will be inserted between two elements a and b such that a <=
 301     // tok && tok < b, where there is a 'virtual' elements[-1] always
 302     // less than tok and a 'virtual' elements[count] always greater
 303     // than tok.
 304     int32_t min = 0, max = count;
 305     while (min != max) {
 306         int32_t probe = (min + max) / 2;
 307         //int8_t c = (*compare)(elements[probe], tok);
 308         //if (c > 0) {
 309         if (elements[probe] > tok) {
 310             max = probe;
 311         } else {
 312             // assert(c <= 0);
 313             min = probe + 1;
 314         }
 315     }
 316     if (ensureCapacity(count + 1, ec)) {
 317         for (int32_t i=count; i>min; --i) {
 318             elements[i] = elements[i-1];
 319         }
 320         elements[min] = tok;
 321         ++count;
 322     }
 323 }
 324
 325
 326
 327
 328
 329 U_NAMESPACE_END
 330