1/*
2******************************************************************************
3* Copyright (C) 1999-2015, 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 (U_FAILURE(status)) {
200        return FALSE;
201    }
202    if (minimumCapacity < 0) {
203        status = U_ILLEGAL_ARGUMENT_ERROR;
204        return FALSE;
205    }
206    if (capacity >= minimumCapacity) {
207        return TRUE;
208    }
209    if (maxCapacity>0 && minimumCapacity>maxCapacity) {
210        status = U_BUFFER_OVERFLOW_ERROR;
211        return FALSE;
212    }
213    if (capacity > (INT32_MAX - 1) / 2) {  // integer overflow check
214        status = U_ILLEGAL_ARGUMENT_ERROR;
215        return FALSE;
216    }
217    int32_t newCap = capacity * 2;
218    if (newCap < minimumCapacity) {
219        newCap = minimumCapacity;
220    }
221    if (maxCapacity > 0 && newCap > maxCapacity) {
222        newCap = maxCapacity;
223    }
224    if (newCap > (int32_t)(INT32_MAX / sizeof(int32_t))) {  // integer overflow check
225        // We keep the original memory contents on bad minimumCapacity/maxCapacity.
226        status = U_ILLEGAL_ARGUMENT_ERROR;
227        return FALSE;
228    }
229    int32_t* newElems = (int32_t *)uprv_realloc(elements, sizeof(int32_t)*newCap);
230    if (newElems == NULL) {
231        // We keep the original contents on the memory failure on realloc.
232        status = U_MEMORY_ALLOCATION_ERROR;
233        return FALSE;
234    }
235    elements = newElems;
236    capacity = newCap;
237    return TRUE;
238}
239
240void UVector32::setMaxCapacity(int32_t limit) {
241    U_ASSERT(limit >= 0);
242    if (limit < 0) {
243        limit = 0;
244    }
245    if (limit > (int32_t)(INT32_MAX / sizeof(int32_t))) {  // integer overflow check for realloc
246        //  Something is very wrong, don't realloc, leave capacity and maxCapacity unchanged
247        return;
248    }
249    maxCapacity = limit;
250    if (capacity <= maxCapacity || maxCapacity == 0) {
251        // Current capacity is within the new limit.
252        return;
253    }
254
255    // New maximum capacity is smaller than the current size.
256    // Realloc the storage to the new, smaller size.
257    int32_t* newElems = (int32_t *)uprv_realloc(elements, sizeof(int32_t)*maxCapacity);
258    if (newElems == NULL) {
259        // Realloc to smaller failed.
260        //   Just keep what we had.  No need to call it a failure.
261        return;
262    }
263    elements = newElems;
264    capacity = maxCapacity;
265    if (count > capacity) {
266        count = capacity;
267    }
268}
269
270/**
271 * Change the size of this vector as follows: If newSize is smaller,
272 * then truncate the array, possibly deleting held elements for i >=
273 * newSize.  If newSize is larger, grow the array, filling in new
274 * slots with NULL.
275 */
276void UVector32::setSize(int32_t newSize) {
277    int32_t i;
278    if (newSize < 0) {
279        return;
280    }
281    if (newSize > count) {
282        UErrorCode ec = U_ZERO_ERROR;
283        if (!ensureCapacity(newSize, ec)) {
284            return;
285        }
286        for (i=count; i<newSize; ++i) {
287            elements[i] = 0;
288        }
289    }
290    count = newSize;
291}
292
293
294
295
296/**
297 * Insert the given integer into this vector at its sorted position
298 * as defined by 'compare'.  The current elements are assumed to
299 * be sorted already.
300 */
301void UVector32::sortedInsert(int32_t tok, UErrorCode& ec) {
302    // Perform a binary search for the location to insert tok at.  Tok
303    // will be inserted between two elements a and b such that a <=
304    // tok && tok < b, where there is a 'virtual' elements[-1] always
305    // less than tok and a 'virtual' elements[count] always greater
306    // than tok.
307    int32_t min = 0, max = count;
308    while (min != max) {
309        int32_t probe = (min + max) / 2;
310        //int8_t c = (*compare)(elements[probe], tok);
311        //if (c > 0) {
312        if (elements[probe] > tok) {
313            max = probe;
314        } else {
315            // assert(c <= 0);
316            min = probe + 1;
317        }
318    }
319    if (ensureCapacity(count + 1, ec)) {
320        for (int32_t i=count; i>min; --i) {
321            elements[i] = elements[i-1];
322        }
323        elements[min] = tok;
324        ++count;
325    }
326}
327
328
329
330
331
332U_NAMESPACE_END
333
334