]> git.saurik.com Git - apple/icu.git/blob - icuSources/common/uvector.cpp
ICU-400.38.tar.gz
[apple/icu.git] / icuSources / common / uvector.cpp
1 /*
2 ******************************************************************************
3 * Copyright (C) 1999-2004, 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 "uvector.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 #define HINT_KEY_POINTER (1)
24 #define HINT_KEY_INTEGER (0)
25
26 UOBJECT_DEFINE_RTTI_IMPLEMENTATION(UVector)
27
28 UVector::UVector(UErrorCode &status) :
29 count(0),
30 capacity(0),
31 elements(0),
32 deleter(0),
33 comparer(0)
34 {
35 _init(DEFUALT_CAPACITY, status);
36 }
37
38 UVector::UVector(int32_t initialCapacity, UErrorCode &status) :
39 count(0),
40 capacity(0),
41 elements(0),
42 deleter(0),
43 comparer(0)
44 {
45 _init(initialCapacity, status);
46 }
47
48 UVector::UVector(UObjectDeleter *d, UKeyComparator *c, UErrorCode &status) :
49 count(0),
50 capacity(0),
51 elements(0),
52 deleter(d),
53 comparer(c)
54 {
55 _init(DEFUALT_CAPACITY, status);
56 }
57
58 UVector::UVector(UObjectDeleter *d, UKeyComparator *c, int32_t initialCapacity, UErrorCode &status) :
59 count(0),
60 capacity(0),
61 elements(0),
62 deleter(d),
63 comparer(c)
64 {
65 _init(initialCapacity, status);
66 }
67
68 void UVector::_init(int32_t initialCapacity, UErrorCode &status) {
69 if (U_FAILURE(status)) {
70 return;
71 }
72 // Fix bogus initialCapacity values; avoid malloc(0)
73 if (initialCapacity < 1) {
74 initialCapacity = DEFUALT_CAPACITY;
75 }
76 elements = (UHashTok *)uprv_malloc(sizeof(UHashTok)*initialCapacity);
77 if (elements == 0) {
78 status = U_MEMORY_ALLOCATION_ERROR;
79 } else {
80 capacity = initialCapacity;
81 }
82 }
83
84 UVector::~UVector() {
85 removeAllElements();
86 uprv_free(elements);
87 elements = 0;
88 }
89
90 /**
91 * Assign this object to another (make this a copy of 'other').
92 * Use the 'assign' function to assign each element.
93 */
94 void UVector::assign(const UVector& other, UTokenAssigner *assign, UErrorCode &ec) {
95 if (ensureCapacity(other.count, ec)) {
96 setSize(other.count, ec);
97 if (U_SUCCESS(ec)) {
98 for (int32_t i=0; i<other.count; ++i) {
99 if (elements[i].pointer != 0 && deleter != 0) {
100 (*deleter)(elements[i].pointer);
101 }
102 (*assign)(&elements[i], &other.elements[i]);
103 }
104 }
105 }
106 }
107
108 // This only does something sensible if this object has a non-null comparer
109 UBool UVector::operator==(const UVector& other) {
110 int32_t i;
111 if (count != other.count) return FALSE;
112 if (comparer != NULL) {
113 // Compare using this object's comparer
114 for (i=0; i<count; ++i) {
115 if (!(*comparer)(elements[i], other.elements[i])) {
116 return FALSE;
117 }
118 }
119 }
120 return TRUE;
121 }
122
123 void UVector::addElement(void* obj, UErrorCode &status) {
124 if (ensureCapacity(count + 1, status)) {
125 elements[count++].pointer = obj;
126 }
127 }
128
129 void UVector::addElement(int32_t elem, UErrorCode &status) {
130 if (ensureCapacity(count + 1, status)) {
131 elements[count].pointer = NULL; // Pointers may be bigger than ints.
132 elements[count].integer = elem;
133 count++;
134 }
135 }
136
137 void UVector::setElementAt(void* obj, int32_t index) {
138 if (0 <= index && index < count) {
139 if (elements[index].pointer != 0 && deleter != 0) {
140 (*deleter)(elements[index].pointer);
141 }
142 elements[index].pointer = obj;
143 }
144 /* else index out of range */
145 }
146
147 void UVector::setElementAt(int32_t elem, int32_t index) {
148 if (0 <= index && index < count) {
149 if (elements[index].pointer != 0 && deleter != 0) {
150 // TODO: this should be an error. mixing up ints and pointers.
151 (*deleter)(elements[index].pointer);
152 }
153 elements[index].pointer = NULL;
154 elements[index].integer = elem;
155 }
156 /* else index out of range */
157 }
158
159 void UVector::insertElementAt(void* obj, int32_t index, UErrorCode &status) {
160 // must have 0 <= index <= count
161 if (0 <= index && index <= count && ensureCapacity(count + 1, status)) {
162 for (int32_t i=count; i>index; --i) {
163 elements[i] = elements[i-1];
164 }
165 elements[index].pointer = obj;
166 ++count;
167 }
168 /* else index out of range */
169 }
170
171 void UVector::insertElementAt(int32_t elem, int32_t index, UErrorCode &status) {
172 // must have 0 <= index <= count
173 if (0 <= index && index <= count && ensureCapacity(count + 1, status)) {
174 for (int32_t i=count; i>index; --i) {
175 elements[i] = elements[i-1];
176 }
177 elements[index].pointer = NULL;
178 elements[index].integer = elem;
179 ++count;
180 }
181 /* else index out of range */
182 }
183
184 void* UVector::elementAt(int32_t index) const {
185 return (0 <= index && index < count) ? elements[index].pointer : 0;
186 }
187
188 int32_t UVector::elementAti(int32_t index) const {
189 return (0 <= index && index < count) ? elements[index].integer : 0;
190 }
191
192 UBool UVector::containsAll(const UVector& other) const {
193 for (int32_t i=0; i<other.size(); ++i) {
194 if (indexOf(other.elements[i]) < 0) {
195 return FALSE;
196 }
197 }
198 return TRUE;
199 }
200
201 UBool UVector::containsNone(const UVector& other) const {
202 for (int32_t i=0; i<other.size(); ++i) {
203 if (indexOf(other.elements[i]) >= 0) {
204 return FALSE;
205 }
206 }
207 return TRUE;
208 }
209
210 UBool UVector::removeAll(const UVector& other) {
211 UBool changed = FALSE;
212 for (int32_t i=0; i<other.size(); ++i) {
213 int32_t j = indexOf(other.elements[i]);
214 if (j >= 0) {
215 removeElementAt(j);
216 changed = TRUE;
217 }
218 }
219 return changed;
220 }
221
222 UBool UVector::retainAll(const UVector& other) {
223 UBool changed = FALSE;
224 for (int32_t j=size()-1; j>=0; --j) {
225 int32_t i = other.indexOf(elements[j]);
226 if (i < 0) {
227 removeElementAt(j);
228 changed = TRUE;
229 }
230 }
231 return changed;
232 }
233
234 void UVector::removeElementAt(int32_t index) {
235 void* e = orphanElementAt(index);
236 if (e != 0 && deleter != 0) {
237 (*deleter)(e);
238 }
239 }
240
241 UBool UVector::removeElement(void* obj) {
242 int32_t i = indexOf(obj);
243 if (i >= 0) {
244 removeElementAt(i);
245 return TRUE;
246 }
247 return FALSE;
248 }
249
250 void UVector::removeAllElements(void) {
251 if (deleter != 0) {
252 for (int32_t i=0; i<count; ++i) {
253 if (elements[i].pointer != 0) {
254 (*deleter)(elements[i].pointer);
255 }
256 }
257 }
258 count = 0;
259 }
260
261 UBool UVector::equals(const UVector &other) const {
262 int i;
263
264 if (this->count != other.count) {
265 return FALSE;
266 }
267 if (comparer == 0) {
268 for (i=0; i<count; i++) {
269 if (elements[i].pointer != other.elements[i].pointer) {
270 return FALSE;
271 }
272 }
273 } else {
274 UHashTok key;
275 for (i=0; i<count; i++) {
276 key.pointer = &other.elements[i];
277 if (!(*comparer)(key, elements[i])) {
278 return FALSE;
279 }
280 }
281 }
282 return TRUE;
283 }
284
285
286
287 int32_t UVector::indexOf(void* obj, int32_t startIndex) const {
288 UHashTok key;
289 key.pointer = obj;
290 return indexOf(key, startIndex, HINT_KEY_POINTER);
291 }
292
293 int32_t UVector::indexOf(int32_t obj, int32_t startIndex) const {
294 UHashTok key;
295 key.integer = obj;
296 return indexOf(key, startIndex, HINT_KEY_INTEGER);
297 }
298
299 // This only works if this object has a non-null comparer
300 int32_t UVector::indexOf(UHashTok key, int32_t startIndex, int8_t hint) const {
301 int32_t i;
302 if (comparer != 0) {
303 for (i=startIndex; i<count; ++i) {
304 if ((*comparer)(key, elements[i])) {
305 return i;
306 }
307 }
308 } else {
309 for (i=startIndex; i<count; ++i) {
310 /* Pointers are not always the same size as ints so to perform
311 * a valid comparision we need to know whether we are being
312 * provided an int or a pointer. */
313 if (hint & HINT_KEY_POINTER) {
314 if (key.pointer == elements[i].pointer) {
315 return i;
316 }
317 } else {
318 if (key.integer == elements[i].integer) {
319 return i;
320 }
321 }
322 }
323 }
324 return -1;
325 }
326
327 UBool UVector::ensureCapacity(int32_t minimumCapacity, UErrorCode &status) {
328 if (capacity < minimumCapacity) {
329 int32_t newCap = capacity * 2;
330 if (newCap < minimumCapacity) {
331 newCap = minimumCapacity;
332 }
333 UHashTok* newElems = (UHashTok *)uprv_realloc(elements, sizeof(UHashTok)*newCap);
334 if (newElems == NULL) {
335 // We keep the original contents on the memory failure on realloc.
336 status = U_MEMORY_ALLOCATION_ERROR;
337 return FALSE;
338 }
339 elements = newElems;
340 capacity = newCap;
341 }
342 return TRUE;
343 }
344
345 /**
346 * Change the size of this vector as follows: If newSize is smaller,
347 * then truncate the array, possibly deleting held elements for i >=
348 * newSize. If newSize is larger, grow the array, filling in new
349 * slots with NULL.
350 */
351 void UVector::setSize(int32_t newSize, UErrorCode &status) {
352 int32_t i;
353 if (newSize < 0) {
354 return;
355 }
356 if (newSize > count) {
357 if (!ensureCapacity(newSize, status)) {
358 return;
359 }
360 UHashTok empty;
361 empty.pointer = NULL;
362 empty.integer = 0;
363 for (i=count; i<newSize; ++i) {
364 elements[i] = empty;
365 }
366 } else {
367 /* Most efficient to count down */
368 for (i=count-1; i>=newSize; --i) {
369 removeElementAt(i);
370 }
371 }
372 count = newSize;
373 }
374
375 /**
376 * Fill in the given array with all elements of this vector.
377 */
378 void** UVector::toArray(void** result) const {
379 void** a = result;
380 for (int i=0; i<count; ++i) {
381 *a++ = elements[i].pointer;
382 }
383 return result;
384 }
385
386 UObjectDeleter *UVector::setDeleter(UObjectDeleter *d) {
387 UObjectDeleter *old = deleter;
388 deleter = d;
389 return old;
390 }
391
392 UKeyComparator *UVector::setComparer(UKeyComparator *d) {
393 UKeyComparator *old = comparer;
394 comparer = d;
395 return old;
396 }
397
398 /**
399 * Removes the element at the given index from this vector and
400 * transfer ownership of it to the caller. After this call, the
401 * caller owns the result and must delete it and the vector entry
402 * at 'index' is removed, shifting all subsequent entries back by
403 * one index and shortening the size of the vector by one. If the
404 * index is out of range or if there is no item at the given index
405 * then 0 is returned and the vector is unchanged.
406 */
407 void* UVector::orphanElementAt(int32_t index) {
408 void* e = 0;
409 if (0 <= index && index < count) {
410 e = elements[index].pointer;
411 for (int32_t i=index; i<count-1; ++i) {
412 elements[i] = elements[i+1];
413 }
414 --count;
415 }
416 /* else index out of range */
417 return e;
418 }
419
420 /**
421 * Insert the given object into this vector at its sorted position
422 * as defined by 'compare'. The current elements are assumed to
423 * be sorted already.
424 */
425 void UVector::sortedInsert(void* obj, USortComparator *compare, UErrorCode& ec) {
426 UHashTok tok;
427 tok.pointer = obj;
428 sortedInsert(tok, compare, ec);
429 }
430
431 /**
432 * Insert the given integer into this vector at its sorted position
433 * as defined by 'compare'. The current elements are assumed to
434 * be sorted already.
435 */
436 void UVector::sortedInsert(int32_t obj, USortComparator *compare, UErrorCode& ec) {
437 UHashTok tok;
438 tok.integer = obj;
439 sortedInsert(tok, compare, ec);
440 }
441
442 // ASSUME elements[] IS CURRENTLY SORTED
443 void UVector::sortedInsert(UHashTok tok, USortComparator *compare, UErrorCode& ec) {
444 // Perform a binary search for the location to insert tok at. Tok
445 // will be inserted between two elements a and b such that a <=
446 // tok && tok < b, where there is a 'virtual' elements[-1] always
447 // less than tok and a 'virtual' elements[count] always greater
448 // than tok.
449 int32_t min = 0, max = count;
450 while (min != max) {
451 int32_t probe = (min + max) / 2;
452 int8_t c = (*compare)(elements[probe], tok);
453 if (c > 0) {
454 max = probe;
455 } else {
456 // assert(c <= 0);
457 min = probe + 1;
458 }
459 }
460 if (ensureCapacity(count + 1, ec)) {
461 for (int32_t i=count; i>min; --i) {
462 elements[i] = elements[i-1];
463 }
464 elements[min] = tok;
465 ++count;
466 }
467 }
468
469 U_NAMESPACE_END
470