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