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
UOBJECT_DEFINE_RTTI_IMPLEMENTATION(UVector32)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
UVector32(int32_t initialCapacity,UErrorCode & status)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
_init(int32_t initialCapacity,UErrorCode & status)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
~UVector32()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 */
assign(const UVector32 & other,UErrorCode & ec)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
operator ==(const UVector32 & other)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
setElementAt(int32_t elem,int32_t index)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
insertElementAt(int32_t elem,int32_t index,UErrorCode & status)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
containsAll(const UVector32 & other) const115 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
containsNone(const UVector32 & other) const124 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
removeAll(const UVector32 & other)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
retainAll(const UVector32 & other)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
removeElementAt(int32_t index)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
removeAllElements(void)166 void UVector32::removeAllElements(void) {
167 count = 0;
168 }
169
equals(const UVector32 & other) const170 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
indexOf(int32_t key,int32_t startIndex) const187 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
expandCapacity(int32_t minimumCapacity,UErrorCode & status)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
setMaxCapacity(int32_t limit)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 */
setSize(int32_t newSize)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 */
sortedInsert(int32_t tok,UErrorCode & ec)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
331