Line data Source code
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 :
17 : U_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 :
27 0 : UOBJECT_DEFINE_RTTI_IMPLEMENTATION(UVector32)
28 :
29 0 : UVector32::UVector32(UErrorCode &status) :
30 : count(0),
31 : capacity(0),
32 : maxCapacity(0),
33 0 : elements(NULL)
34 : {
35 0 : _init(DEFAULT_CAPACITY, status);
36 0 : }
37 :
38 0 : UVector32::UVector32(int32_t initialCapacity, UErrorCode &status) :
39 : count(0),
40 : capacity(0),
41 : maxCapacity(0),
42 0 : elements(0)
43 : {
44 0 : _init(initialCapacity, status);
45 0 : }
46 :
47 :
48 :
49 0 : void UVector32::_init(int32_t initialCapacity, UErrorCode &status) {
50 : // Fix bogus initialCapacity values; avoid malloc(0)
51 0 : if (initialCapacity < 1) {
52 0 : initialCapacity = DEFAULT_CAPACITY;
53 : }
54 0 : if (maxCapacity>0 && maxCapacity<initialCapacity) {
55 0 : initialCapacity = maxCapacity;
56 : }
57 0 : if (initialCapacity > (int32_t)(INT32_MAX / sizeof(int32_t))) {
58 0 : initialCapacity = uprv_min(DEFAULT_CAPACITY, maxCapacity);
59 : }
60 0 : elements = (int32_t *)uprv_malloc(sizeof(int32_t)*initialCapacity);
61 0 : if (elements == 0) {
62 0 : status = U_MEMORY_ALLOCATION_ERROR;
63 : } else {
64 0 : capacity = initialCapacity;
65 : }
66 0 : }
67 :
68 0 : UVector32::~UVector32() {
69 0 : uprv_free(elements);
70 0 : elements = 0;
71 0 : }
72 :
73 : /**
74 : * Assign this object to another (make this a copy of 'other').
75 : */
76 0 : void UVector32::assign(const UVector32& other, UErrorCode &ec) {
77 0 : if (ensureCapacity(other.count, ec)) {
78 0 : setSize(other.count);
79 0 : for (int32_t i=0; i<other.count; ++i) {
80 0 : elements[i] = other.elements[i];
81 : }
82 : }
83 0 : }
84 :
85 :
86 0 : UBool UVector32::operator==(const UVector32& other) {
87 : int32_t i;
88 0 : if (count != other.count) return FALSE;
89 0 : for (i=0; i<count; ++i) {
90 0 : if (elements[i] != other.elements[i]) {
91 0 : return FALSE;
92 : }
93 : }
94 0 : return TRUE;
95 : }
96 :
97 :
98 0 : void UVector32::setElementAt(int32_t elem, int32_t index) {
99 0 : if (0 <= index && index < count) {
100 0 : elements[index] = elem;
101 : }
102 : /* else index out of range */
103 0 : }
104 :
105 0 : void UVector32::insertElementAt(int32_t elem, int32_t index, UErrorCode &status) {
106 : // must have 0 <= index <= count
107 0 : if (0 <= index && index <= count && ensureCapacity(count + 1, status)) {
108 0 : for (int32_t i=count; i>index; --i) {
109 0 : elements[i] = elements[i-1];
110 : }
111 0 : elements[index] = elem;
112 0 : ++count;
113 : }
114 : /* else index out of range */
115 0 : }
116 :
117 0 : UBool UVector32::containsAll(const UVector32& other) const {
118 0 : for (int32_t i=0; i<other.size(); ++i) {
119 0 : if (indexOf(other.elements[i]) < 0) {
120 0 : return FALSE;
121 : }
122 : }
123 0 : return TRUE;
124 : }
125 :
126 0 : UBool UVector32::containsNone(const UVector32& other) const {
127 0 : for (int32_t i=0; i<other.size(); ++i) {
128 0 : if (indexOf(other.elements[i]) >= 0) {
129 0 : return FALSE;
130 : }
131 : }
132 0 : return TRUE;
133 : }
134 :
135 0 : UBool UVector32::removeAll(const UVector32& other) {
136 0 : UBool changed = FALSE;
137 0 : for (int32_t i=0; i<other.size(); ++i) {
138 0 : int32_t j = indexOf(other.elements[i]);
139 0 : if (j >= 0) {
140 0 : removeElementAt(j);
141 0 : changed = TRUE;
142 : }
143 : }
144 0 : return changed;
145 : }
146 :
147 0 : UBool UVector32::retainAll(const UVector32& other) {
148 0 : UBool changed = FALSE;
149 0 : for (int32_t j=size()-1; j>=0; --j) {
150 0 : int32_t i = other.indexOf(elements[j]);
151 0 : if (i < 0) {
152 0 : removeElementAt(j);
153 0 : changed = TRUE;
154 : }
155 : }
156 0 : return changed;
157 : }
158 :
159 0 : void UVector32::removeElementAt(int32_t index) {
160 0 : if (index >= 0) {
161 0 : for (int32_t i=index; i<count-1; ++i) {
162 0 : elements[i] = elements[i+1];
163 : }
164 0 : --count;
165 : }
166 0 : }
167 :
168 0 : void UVector32::removeAllElements(void) {
169 0 : count = 0;
170 0 : }
171 :
172 0 : UBool UVector32::equals(const UVector32 &other) const {
173 : int i;
174 :
175 0 : if (this->count != other.count) {
176 0 : return FALSE;
177 : }
178 0 : for (i=0; i<count; i++) {
179 0 : if (elements[i] != other.elements[i]) {
180 0 : return FALSE;
181 : }
182 : }
183 0 : return TRUE;
184 : }
185 :
186 :
187 :
188 :
189 0 : int32_t UVector32::indexOf(int32_t key, int32_t startIndex) const {
190 : int32_t i;
191 0 : for (i=startIndex; i<count; ++i) {
192 0 : if (key == elements[i]) {
193 0 : return i;
194 : }
195 : }
196 0 : return -1;
197 : }
198 :
199 :
200 0 : UBool UVector32::expandCapacity(int32_t minimumCapacity, UErrorCode &status) {
201 0 : if (U_FAILURE(status)) {
202 0 : return FALSE;
203 : }
204 0 : if (minimumCapacity < 0) {
205 0 : status = U_ILLEGAL_ARGUMENT_ERROR;
206 0 : return FALSE;
207 : }
208 0 : if (capacity >= minimumCapacity) {
209 0 : return TRUE;
210 : }
211 0 : if (maxCapacity>0 && minimumCapacity>maxCapacity) {
212 0 : status = U_BUFFER_OVERFLOW_ERROR;
213 0 : return FALSE;
214 : }
215 0 : if (capacity > (INT32_MAX - 1) / 2) { // integer overflow check
216 0 : status = U_ILLEGAL_ARGUMENT_ERROR;
217 0 : return FALSE;
218 : }
219 0 : int32_t newCap = capacity * 2;
220 0 : if (newCap < minimumCapacity) {
221 0 : newCap = minimumCapacity;
222 : }
223 0 : if (maxCapacity > 0 && newCap > maxCapacity) {
224 0 : newCap = maxCapacity;
225 : }
226 0 : if (newCap > (int32_t)(INT32_MAX / sizeof(int32_t))) { // integer overflow check
227 : // We keep the original memory contents on bad minimumCapacity/maxCapacity.
228 0 : status = U_ILLEGAL_ARGUMENT_ERROR;
229 0 : return FALSE;
230 : }
231 0 : int32_t* newElems = (int32_t *)uprv_realloc(elements, sizeof(int32_t)*newCap);
232 0 : if (newElems == NULL) {
233 : // We keep the original contents on the memory failure on realloc.
234 0 : status = U_MEMORY_ALLOCATION_ERROR;
235 0 : return FALSE;
236 : }
237 0 : elements = newElems;
238 0 : capacity = newCap;
239 0 : return TRUE;
240 : }
241 :
242 0 : void UVector32::setMaxCapacity(int32_t limit) {
243 0 : U_ASSERT(limit >= 0);
244 0 : if (limit < 0) {
245 0 : limit = 0;
246 : }
247 0 : 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 0 : return;
250 : }
251 0 : maxCapacity = limit;
252 0 : if (capacity <= maxCapacity || maxCapacity == 0) {
253 : // Current capacity is within the new limit.
254 0 : return;
255 : }
256 :
257 : // New maximum capacity is smaller than the current size.
258 : // Realloc the storage to the new, smaller size.
259 0 : int32_t* newElems = (int32_t *)uprv_realloc(elements, sizeof(int32_t)*maxCapacity);
260 0 : if (newElems == NULL) {
261 : // Realloc to smaller failed.
262 : // Just keep what we had. No need to call it a failure.
263 0 : return;
264 : }
265 0 : elements = newElems;
266 0 : capacity = maxCapacity;
267 0 : if (count > capacity) {
268 0 : 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 : */
278 0 : void UVector32::setSize(int32_t newSize) {
279 : int32_t i;
280 0 : if (newSize < 0) {
281 0 : return;
282 : }
283 0 : if (newSize > count) {
284 0 : UErrorCode ec = U_ZERO_ERROR;
285 0 : if (!ensureCapacity(newSize, ec)) {
286 0 : return;
287 : }
288 0 : for (i=count; i<newSize; ++i) {
289 0 : elements[i] = 0;
290 : }
291 : }
292 0 : 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 : */
303 0 : void 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 0 : int32_t min = 0, max = count;
310 0 : while (min != max) {
311 0 : int32_t probe = (min + max) / 2;
312 : //int8_t c = (*compare)(elements[probe], tok);
313 : //if (c > 0) {
314 0 : if (elements[probe] > tok) {
315 0 : max = probe;
316 : } else {
317 : // assert(c <= 0);
318 0 : min = probe + 1;
319 : }
320 : }
321 0 : if (ensureCapacity(count + 1, ec)) {
322 0 : for (int32_t i=count; i>min; --i) {
323 0 : elements[i] = elements[i-1];
324 : }
325 0 : elements[min] = tok;
326 0 : ++count;
327 : }
328 0 : }
329 :
330 :
331 :
332 :
333 :
334 : U_NAMESPACE_END
335 :
|
