1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/intl/icu/source/common/uvectr32.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,330 @@
1.4 +/*
1.5 +******************************************************************************
1.6 +* Copyright (C) 1999-2010, International Business Machines Corporation and *
1.7 +* others. All Rights Reserved. *
1.8 +******************************************************************************
1.9 +* Date Name Description
1.10 +* 10/22/99 alan Creation.
1.11 +**********************************************************************
1.12 +*/
1.13 +
1.14 +#include "uvectr32.h"
1.15 +#include "cmemory.h"
1.16 +#include "putilimp.h"
1.17 +
1.18 +U_NAMESPACE_BEGIN
1.19 +
1.20 +#define DEFAULT_CAPACITY 8
1.21 +
1.22 +/*
1.23 + * Constants for hinting whether a key is an integer
1.24 + * or a pointer. If a hint bit is zero, then the associated
1.25 + * token is assumed to be an integer. This is needed for iSeries
1.26 + */
1.27 +
1.28 +UOBJECT_DEFINE_RTTI_IMPLEMENTATION(UVector32)
1.29 +
1.30 +UVector32::UVector32(UErrorCode &status) :
1.31 + count(0),
1.32 + capacity(0),
1.33 + maxCapacity(0),
1.34 + elements(NULL)
1.35 +{
1.36 + _init(DEFAULT_CAPACITY, status);
1.37 +}
1.38 +
1.39 +UVector32::UVector32(int32_t initialCapacity, UErrorCode &status) :
1.40 + count(0),
1.41 + capacity(0),
1.42 + maxCapacity(0),
1.43 + elements(0)
1.44 +{
1.45 + _init(initialCapacity, status);
1.46 +}
1.47 +
1.48 +
1.49 +
1.50 +void UVector32::_init(int32_t initialCapacity, UErrorCode &status) {
1.51 + // Fix bogus initialCapacity values; avoid malloc(0)
1.52 + if (initialCapacity < 1) {
1.53 + initialCapacity = DEFAULT_CAPACITY;
1.54 + }
1.55 + if (maxCapacity>0 && maxCapacity<initialCapacity) {
1.56 + initialCapacity = maxCapacity;
1.57 + }
1.58 + if (initialCapacity > (int32_t)(INT32_MAX / sizeof(int32_t))) {
1.59 + initialCapacity = uprv_min(DEFAULT_CAPACITY, maxCapacity);
1.60 + }
1.61 + elements = (int32_t *)uprv_malloc(sizeof(int32_t)*initialCapacity);
1.62 + if (elements == 0) {
1.63 + status = U_MEMORY_ALLOCATION_ERROR;
1.64 + } else {
1.65 + capacity = initialCapacity;
1.66 + }
1.67 +}
1.68 +
1.69 +UVector32::~UVector32() {
1.70 + uprv_free(elements);
1.71 + elements = 0;
1.72 +}
1.73 +
1.74 +/**
1.75 + * Assign this object to another (make this a copy of 'other').
1.76 + */
1.77 +void UVector32::assign(const UVector32& other, UErrorCode &ec) {
1.78 + if (ensureCapacity(other.count, ec)) {
1.79 + setSize(other.count);
1.80 + for (int32_t i=0; i<other.count; ++i) {
1.81 + elements[i] = other.elements[i];
1.82 + }
1.83 + }
1.84 +}
1.85 +
1.86 +
1.87 +UBool UVector32::operator==(const UVector32& other) {
1.88 + int32_t i;
1.89 + if (count != other.count) return FALSE;
1.90 + for (i=0; i<count; ++i) {
1.91 + if (elements[i] != other.elements[i]) {
1.92 + return FALSE;
1.93 + }
1.94 + }
1.95 + return TRUE;
1.96 +}
1.97 +
1.98 +
1.99 +void UVector32::setElementAt(int32_t elem, int32_t index) {
1.100 + if (0 <= index && index < count) {
1.101 + elements[index] = elem;
1.102 + }
1.103 + /* else index out of range */
1.104 +}
1.105 +
1.106 +void UVector32::insertElementAt(int32_t elem, int32_t index, UErrorCode &status) {
1.107 + // must have 0 <= index <= count
1.108 + if (0 <= index && index <= count && ensureCapacity(count + 1, status)) {
1.109 + for (int32_t i=count; i>index; --i) {
1.110 + elements[i] = elements[i-1];
1.111 + }
1.112 + elements[index] = elem;
1.113 + ++count;
1.114 + }
1.115 + /* else index out of range */
1.116 +}
1.117 +
1.118 +UBool UVector32::containsAll(const UVector32& other) const {
1.119 + for (int32_t i=0; i<other.size(); ++i) {
1.120 + if (indexOf(other.elements[i]) < 0) {
1.121 + return FALSE;
1.122 + }
1.123 + }
1.124 + return TRUE;
1.125 +}
1.126 +
1.127 +UBool UVector32::containsNone(const UVector32& other) const {
1.128 + for (int32_t i=0; i<other.size(); ++i) {
1.129 + if (indexOf(other.elements[i]) >= 0) {
1.130 + return FALSE;
1.131 + }
1.132 + }
1.133 + return TRUE;
1.134 +}
1.135 +
1.136 +UBool UVector32::removeAll(const UVector32& other) {
1.137 + UBool changed = FALSE;
1.138 + for (int32_t i=0; i<other.size(); ++i) {
1.139 + int32_t j = indexOf(other.elements[i]);
1.140 + if (j >= 0) {
1.141 + removeElementAt(j);
1.142 + changed = TRUE;
1.143 + }
1.144 + }
1.145 + return changed;
1.146 +}
1.147 +
1.148 +UBool UVector32::retainAll(const UVector32& other) {
1.149 + UBool changed = FALSE;
1.150 + for (int32_t j=size()-1; j>=0; --j) {
1.151 + int32_t i = other.indexOf(elements[j]);
1.152 + if (i < 0) {
1.153 + removeElementAt(j);
1.154 + changed = TRUE;
1.155 + }
1.156 + }
1.157 + return changed;
1.158 +}
1.159 +
1.160 +void UVector32::removeElementAt(int32_t index) {
1.161 + if (index >= 0) {
1.162 + for (int32_t i=index; i<count-1; ++i) {
1.163 + elements[i] = elements[i+1];
1.164 + }
1.165 + --count;
1.166 + }
1.167 +}
1.168 +
1.169 +void UVector32::removeAllElements(void) {
1.170 + count = 0;
1.171 +}
1.172 +
1.173 +UBool UVector32::equals(const UVector32 &other) const {
1.174 + int i;
1.175 +
1.176 + if (this->count != other.count) {
1.177 + return FALSE;
1.178 + }
1.179 + for (i=0; i<count; i++) {
1.180 + if (elements[i] != other.elements[i]) {
1.181 + return FALSE;
1.182 + }
1.183 + }
1.184 + return TRUE;
1.185 +}
1.186 +
1.187 +
1.188 +
1.189 +
1.190 +int32_t UVector32::indexOf(int32_t key, int32_t startIndex) const {
1.191 + int32_t i;
1.192 + for (i=startIndex; i<count; ++i) {
1.193 + if (key == elements[i]) {
1.194 + return i;
1.195 + }
1.196 + }
1.197 + return -1;
1.198 +}
1.199 +
1.200 +
1.201 +UBool UVector32::expandCapacity(int32_t minimumCapacity, UErrorCode &status) {
1.202 + if (minimumCapacity < 0) {
1.203 + status = U_ILLEGAL_ARGUMENT_ERROR;
1.204 + return FALSE;
1.205 + }
1.206 + if (capacity >= minimumCapacity) {
1.207 + return TRUE;
1.208 + }
1.209 + if (maxCapacity>0 && minimumCapacity>maxCapacity) {
1.210 + status = U_BUFFER_OVERFLOW_ERROR;
1.211 + return FALSE;
1.212 + }
1.213 + if (capacity > (INT32_MAX - 1) / 2) { // integer overflow check
1.214 + status = U_ILLEGAL_ARGUMENT_ERROR;
1.215 + return FALSE;
1.216 + }
1.217 + int32_t newCap = capacity * 2;
1.218 + if (newCap < minimumCapacity) {
1.219 + newCap = minimumCapacity;
1.220 + }
1.221 + if (maxCapacity > 0 && newCap > maxCapacity) {
1.222 + newCap = maxCapacity;
1.223 + }
1.224 + if (newCap > (int32_t)(INT32_MAX / sizeof(int32_t))) { // integer overflow check
1.225 + // We keep the original memory contents on bad minimumCapacity/maxCapacity.
1.226 + status = U_ILLEGAL_ARGUMENT_ERROR;
1.227 + return FALSE;
1.228 + }
1.229 + int32_t* newElems = (int32_t *)uprv_realloc(elements, sizeof(int32_t)*newCap);
1.230 + if (newElems == NULL) {
1.231 + // We keep the original contents on the memory failure on realloc.
1.232 + status = U_MEMORY_ALLOCATION_ERROR;
1.233 + return FALSE;
1.234 + }
1.235 + elements = newElems;
1.236 + capacity = newCap;
1.237 + return TRUE;
1.238 +}
1.239 +
1.240 +void UVector32::setMaxCapacity(int32_t limit) {
1.241 + U_ASSERT(limit >= 0);
1.242 + if (limit < 0) {
1.243 + limit = 0;
1.244 + }
1.245 + if (limit > (int32_t)(INT32_MAX / sizeof(int32_t))) { // integer overflow check for realloc
1.246 + // Something is very wrong, don't realloc, leave capacity and maxCapacity unchanged
1.247 + return;
1.248 + }
1.249 + maxCapacity = limit;
1.250 + if (capacity <= maxCapacity || maxCapacity == 0) {
1.251 + // Current capacity is within the new limit.
1.252 + return;
1.253 + }
1.254 +
1.255 + // New maximum capacity is smaller than the current size.
1.256 + // Realloc the storage to the new, smaller size.
1.257 + int32_t* newElems = (int32_t *)uprv_realloc(elements, sizeof(int32_t)*maxCapacity);
1.258 + if (newElems == NULL) {
1.259 + // Realloc to smaller failed.
1.260 + // Just keep what we had. No need to call it a failure.
1.261 + return;
1.262 + }
1.263 + elements = newElems;
1.264 + capacity = maxCapacity;
1.265 + if (count > capacity) {
1.266 + count = capacity;
1.267 + }
1.268 +}
1.269 +
1.270 +/**
1.271 + * Change the size of this vector as follows: If newSize is smaller,
1.272 + * then truncate the array, possibly deleting held elements for i >=
1.273 + * newSize. If newSize is larger, grow the array, filling in new
1.274 + * slots with NULL.
1.275 + */
1.276 +void UVector32::setSize(int32_t newSize) {
1.277 + int32_t i;
1.278 + if (newSize < 0) {
1.279 + return;
1.280 + }
1.281 + if (newSize > count) {
1.282 + UErrorCode ec = U_ZERO_ERROR;
1.283 + if (!ensureCapacity(newSize, ec)) {
1.284 + return;
1.285 + }
1.286 + for (i=count; i<newSize; ++i) {
1.287 + elements[i] = 0;
1.288 + }
1.289 + }
1.290 + count = newSize;
1.291 +}
1.292 +
1.293 +
1.294 +
1.295 +
1.296 +/**
1.297 + * Insert the given integer into this vector at its sorted position
1.298 + * as defined by 'compare'. The current elements are assumed to
1.299 + * be sorted already.
1.300 + */
1.301 +void UVector32::sortedInsert(int32_t tok, UErrorCode& ec) {
1.302 + // Perform a binary search for the location to insert tok at. Tok
1.303 + // will be inserted between two elements a and b such that a <=
1.304 + // tok && tok < b, where there is a 'virtual' elements[-1] always
1.305 + // less than tok and a 'virtual' elements[count] always greater
1.306 + // than tok.
1.307 + int32_t min = 0, max = count;
1.308 + while (min != max) {
1.309 + int32_t probe = (min + max) / 2;
1.310 + //int8_t c = (*compare)(elements[probe], tok);
1.311 + //if (c > 0) {
1.312 + if (elements[probe] > tok) {
1.313 + max = probe;
1.314 + } else {
1.315 + // assert(c <= 0);
1.316 + min = probe + 1;
1.317 + }
1.318 + }
1.319 + if (ensureCapacity(count + 1, ec)) {
1.320 + for (int32_t i=count; i>min; --i) {
1.321 + elements[i] = elements[i-1];
1.322 + }
1.323 + elements[min] = tok;
1.324 + ++count;
1.325 + }
1.326 +}
1.327 +
1.328 +
1.329 +
1.330 +
1.331 +
1.332 +U_NAMESPACE_END
1.333 +
