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 15U_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 25UOBJECT_DEFINE_RTTI_IMPLEMENTATION(UVector32) 26 27UVector32::UVector32(UErrorCode &status) : 28 count(0), 29 capacity(0), 30 maxCapacity(0), 31 elements(NULL) 32{ 33 _init(DEFAULT_CAPACITY, status); 34} 35 36UVector32::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 47void 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 66UVector32::~UVector32() { 67 uprv_free(elements); 68 elements = 0; 69} 70 71/** 72 * Assign this object to another (make this a copy of 'other'). 73 */ 74void 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 84UBool 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 96void 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 103void 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 115UBool 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 124UBool 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 133UBool 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 145UBool 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 157void 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 166void UVector32::removeAllElements(void) { 167 count = 0; 168} 169 170UBool 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 187int32_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 198UBool 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 237void 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 */ 273void 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 */ 298void 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 329U_NAMESPACE_END 330 331