1// © 2016 and later: Unicode, Inc. and others.
2// License & terms of use: http://www.unicode.org/copyright.html
3/*
4******************************************************************************
5* Copyright (C) 1999-2015, International Business Machines Corporation and
6* others. All Rights Reserved.
7******************************************************************************
8* Date Name Description
9* 10/22/99 alan Creation.
10**********************************************************************
11*/
12
13#include "uvectr32.h"
14#include "cmemory.h"
15#include "putilimp.h"
16
17U_NAMESPACE_BEGIN
18
19#define DEFAULT_CAPACITY 8
20
21/*
22 * Constants for hinting whether a key is an integer
23 * or a pointer. If a hint bit is zero, then the associated
24 * token is assumed to be an integer. This is needed for iSeries
25 */
26
27UOBJECT_DEFINE_RTTI_IMPLEMENTATION(UVector32)
28
29UVector32::UVector32(UErrorCode &status) :
30 count(0),
31 capacity(0),
32 maxCapacity(0),
33 elements(NULL)
34{
35 _init(DEFAULT_CAPACITY, status);
36}
37
38UVector32::UVector32(int32_t initialCapacity, UErrorCode &status) :
39 count(0),
40 capacity(0),
41 maxCapacity(0),
42 elements(0)
43{
44 _init(initialCapacity, status);
45}
46
47
48
49void UVector32::_init(int32_t initialCapacity, UErrorCode &status) {
50 // Fix bogus initialCapacity values; avoid malloc(0)
51 if (initialCapacity < 1) {
52 initialCapacity = DEFAULT_CAPACITY;
53 }
54 if (maxCapacity>0 && maxCapacity<initialCapacity) {
55 initialCapacity = maxCapacity;
56 }
57 if (initialCapacity > (int32_t)(INT32_MAX / sizeof(int32_t))) {
58 initialCapacity = uprv_min(DEFAULT_CAPACITY, maxCapacity);
59 }
60 elements = (int32_t *)uprv_malloc(sizeof(int32_t)*initialCapacity);
61 if (elements == 0) {
62 status = U_MEMORY_ALLOCATION_ERROR;
63 } else {
64 capacity = initialCapacity;
65 }
66}
67
68UVector32::~UVector32() {
69 uprv_free(elements);
70 elements = 0;
71}
72
73/**
74 * Assign this object to another (make this a copy of 'other').
75 */
76void UVector32::assign(const UVector32& other, UErrorCode &ec) {
77 if (ensureCapacity(other.count, ec)) {
78 setSize(other.count);
79 for (int32_t i=0; i<other.count; ++i) {
80 elements[i] = other.elements[i];
81 }
82 }
83}
84
85
86UBool UVector32::operator==(const UVector32& other) {
87 int32_t i;
88 if (count != other.count) return FALSE;
89 for (i=0; i<count; ++i) {
90 if (elements[i] != other.elements[i]) {
91 return FALSE;
92 }
93 }
94 return TRUE;
95}
96
97
98void UVector32::setElementAt(int32_t elem, int32_t index) {
99 if (0 <= index && index < count) {
100 elements[index] = elem;
101 }
102 /* else index out of range */
103}
104
105void UVector32::insertElementAt(int32_t elem, int32_t index, UErrorCode &status) {
106 // must have 0 <= index <= count
107 if (0 <= index && index <= count && ensureCapacity(count + 1, status)) {
108 for (int32_t i=count; i>index; --i) {
109 elements[i] = elements[i-1];
110 }
111 elements[index] = elem;
112 ++count;
113 }
114 /* else index out of range */
115}
116
117UBool UVector32::containsAll(const UVector32& other) const {
118 for (int32_t i=0; i<other.size(); ++i) {
119 if (indexOf(other.elements[i]) < 0) {
120 return FALSE;
121 }
122 }
123 return TRUE;
124}
125
126UBool UVector32::containsNone(const UVector32& other) const {
127 for (int32_t i=0; i<other.size(); ++i) {
128 if (indexOf(other.elements[i]) >= 0) {
129 return FALSE;
130 }
131 }
132 return TRUE;
133}
134
135UBool UVector32::removeAll(const UVector32& other) {
136 UBool changed = FALSE;
137 for (int32_t i=0; i<other.size(); ++i) {
138 int32_t j = indexOf(other.elements[i]);
139 if (j >= 0) {
140 removeElementAt(j);
141 changed = TRUE;
142 }
143 }
144 return changed;
145}
146
147UBool UVector32::retainAll(const UVector32& other) {
148 UBool changed = FALSE;
149 for (int32_t j=size()-1; j>=0; --j) {
150 int32_t i = other.indexOf(elements[j]);
151 if (i < 0) {
152 removeElementAt(j);
153 changed = TRUE;
154 }
155 }
156 return changed;
157}
158
159void UVector32::removeElementAt(int32_t index) {
160 if (index >= 0) {
161 for (int32_t i=index; i<count-1; ++i) {
162 elements[i] = elements[i+1];
163 }
164 --count;
165 }
166}
167
168void UVector32::removeAllElements(void) {
169 count = 0;
170}
171
172UBool UVector32::equals(const UVector32 &other) const {
173 int i;
174
175 if (this->count != other.count) {
176 return FALSE;
177 }
178 for (i=0; i<count; i++) {
179 if (elements[i] != other.elements[i]) {
180 return FALSE;
181 }
182 }
183 return TRUE;
184}
185
186
187
188
189int32_t UVector32::indexOf(int32_t key, int32_t startIndex) const {
190 int32_t i;
191 for (i=startIndex; i<count; ++i) {
192 if (key == elements[i]) {
193 return i;
194 }
195 }
196 return -1;
197}
198
199
200UBool UVector32::expandCapacity(int32_t minimumCapacity, UErrorCode &status) {
201 if (U_FAILURE(status)) {
202 return FALSE;
203 }
204 if (minimumCapacity < 0) {
205 status = U_ILLEGAL_ARGUMENT_ERROR;
206 return FALSE;
207 }
208 if (capacity >= minimumCapacity) {
209 return TRUE;
210 }
211 if (maxCapacity>0 && minimumCapacity>maxCapacity) {
212 status = U_BUFFER_OVERFLOW_ERROR;
213 return FALSE;
214 }
215 if (capacity > (INT32_MAX - 1) / 2) { // integer overflow check
216 status = U_ILLEGAL_ARGUMENT_ERROR;
217 return FALSE;
218 }
219 int32_t newCap = capacity * 2;
220 if (newCap < minimumCapacity) {
221 newCap = minimumCapacity;
222 }
223 if (maxCapacity > 0 && newCap > maxCapacity) {
224 newCap = maxCapacity;
225 }
226 if (newCap > (int32_t)(INT32_MAX / sizeof(int32_t))) { // integer overflow check
227 // We keep the original memory contents on bad minimumCapacity/maxCapacity.
228 status = U_ILLEGAL_ARGUMENT_ERROR;
229 return FALSE;
230 }
231 int32_t* newElems = (int32_t *)uprv_realloc(elements, sizeof(int32_t)*newCap);
232 if (newElems == NULL) {
233 // We keep the original contents on the memory failure on realloc.
234 status = U_MEMORY_ALLOCATION_ERROR;
235 return FALSE;
236 }
237 elements = newElems;
238 capacity = newCap;
239 return TRUE;
240}
241
242void UVector32::setMaxCapacity(int32_t limit) {
243 U_ASSERT(limit >= 0);
244 if (limit < 0) {
245 limit = 0;
246 }
247 if (limit > (int32_t)(INT32_MAX / sizeof(int32_t))) { // integer overflow check for realloc
248 // Something is very wrong, don't realloc, leave capacity and maxCapacity unchanged
249 return;
250 }
251 maxCapacity = limit;
252 if (capacity <= maxCapacity || maxCapacity == 0) {
253 // Current capacity is within the new limit.
254 return;
255 }
256
257 // New maximum capacity is smaller than the current size.
258 // Realloc the storage to the new, smaller size.
259 int32_t* newElems = (int32_t *)uprv_realloc(elements, sizeof(int32_t)*maxCapacity);
260 if (newElems == NULL) {
261 // Realloc to smaller failed.
262 // Just keep what we had. No need to call it a failure.
263 return;
264 }
265 elements = newElems;
266 capacity = maxCapacity;
267 if (count > capacity) {
268 count = capacity;
269 }
270}
271
272/**
273 * Change the size of this vector as follows: If newSize is smaller,
274 * then truncate the array, possibly deleting held elements for i >=
275 * newSize. If newSize is larger, grow the array, filling in new
276 * slots with NULL.
277 */
278void UVector32::setSize(int32_t newSize) {
279 int32_t i;
280 if (newSize < 0) {
281 return;
282 }
283 if (newSize > count) {
284 UErrorCode ec = U_ZERO_ERROR;
285 if (!ensureCapacity(newSize, ec)) {
286 return;
287 }
288 for (i=count; i<newSize; ++i) {
289 elements[i] = 0;
290 }
291 }
292 count = newSize;
293}
294
295
296
297
298/**
299 * Insert the given integer into this vector at its sorted position
300 * as defined by 'compare'. The current elements are assumed to
301 * be sorted already.
302 */
303void UVector32::sortedInsert(int32_t tok, UErrorCode& ec) {
304 // Perform a binary search for the location to insert tok at. Tok
305 // will be inserted between two elements a and b such that a <=
306 // tok && tok < b, where there is a 'virtual' elements[-1] always
307 // less than tok and a 'virtual' elements[count] always greater
308 // than tok.
309 int32_t min = 0, max = count;
310 while (min != max) {
311 int32_t probe = (min + max) / 2;
312 //int8_t c = (*compare)(elements[probe], tok);
313 //if (c > 0) {
314 if (elements[probe] > tok) {
315 max = probe;
316 } else {
317 // assert(c <= 0);
318 min = probe + 1;
319 }
320 }
321 if (ensureCapacity(count + 1, ec)) {
322 for (int32_t i=count; i>min; --i) {
323 elements[i] = elements[i-1];
324 }
325 elements[min] = tok;
326 ++count;
327 }
328}
329
330
331
332
333
334U_NAMESPACE_END
335
336