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 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 (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 240void 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 */ 276void 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 */ 301void 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 332U_NAMESPACE_END 333 334