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
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 (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
237void 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 */
273void 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 */
298void 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
329U_NAMESPACE_END
330
331