Coverage Report

Created: 2024-04-24 06:23

/src/icu/source/common/uvector.cpp
Line
Count
Source (jump to first uncovered line)
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-2013, 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 "uvector.h"
14
#include "cmemory.h"
15
#include "uarrsort.h"
16
#include "uelement.h"
17
18
U_NAMESPACE_BEGIN
19
20
constexpr int32_t DEFAULT_CAPACITY = 8;
21
22
/*
23
 * Constants for hinting whether a key is an integer
24
 * or a pointer.  If a hint bit is zero, then the associated
25
 * token is assumed to be an integer. This is needed for iSeries
26
 */
27
constexpr int8_t HINT_KEY_POINTER = 1;
28
constexpr int8_t HINT_KEY_INTEGER = 0;
29
 
30
UOBJECT_DEFINE_RTTI_IMPLEMENTATION(UVector)
31
32
UVector::UVector(UErrorCode &status) :
33
0
        UVector(nullptr, nullptr, DEFAULT_CAPACITY, status) {
34
0
}
35
36
UVector::UVector(int32_t initialCapacity, UErrorCode &status) :
37
0
        UVector(nullptr, nullptr, initialCapacity, status) {
38
0
}
39
40
UVector::UVector(UObjectDeleter *d, UElementsAreEqual *c, UErrorCode &status) :
41
0
        UVector(d, c, DEFAULT_CAPACITY, status) {
42
0
}
43
44
UVector::UVector(UObjectDeleter *d, UElementsAreEqual *c, int32_t initialCapacity, UErrorCode &status) :
45
    deleter(d),
46
    comparer(c)
47
0
{
48
0
    if (U_FAILURE(status)) {
49
0
        return;
50
0
    }
51
    // Fix bogus initialCapacity values; avoid malloc(0) and integer overflow
52
0
    if ((initialCapacity < 1) || (initialCapacity > (int32_t)(INT32_MAX / sizeof(UElement)))) {
53
0
        initialCapacity = DEFAULT_CAPACITY;
54
0
    }
55
0
    elements = (UElement *)uprv_malloc(sizeof(UElement)*initialCapacity);
56
0
    if (elements == nullptr) {
57
0
        status = U_MEMORY_ALLOCATION_ERROR;
58
0
    } else {
59
0
        capacity = initialCapacity;
60
0
    }
61
0
}
62
63
0
UVector::~UVector() {
64
0
    removeAllElements();
65
0
    uprv_free(elements);
66
0
    elements = nullptr;
67
0
}
68
69
/**
70
 * Assign this object to another (make this a copy of 'other').
71
 * Use the 'assign' function to assign each element.
72
 */
73
0
void UVector::assign(const UVector& other, UElementAssigner *assign, UErrorCode &ec) {
74
0
    if (ensureCapacity(other.count, ec)) {
75
0
        setSize(other.count, ec);
76
0
        if (U_SUCCESS(ec)) {
77
0
            for (int32_t i=0; i<other.count; ++i) {
78
0
                if (elements[i].pointer != nullptr && deleter != nullptr) {
79
0
                    (*deleter)(elements[i].pointer);
80
0
                }
81
0
                (*assign)(&elements[i], &other.elements[i]);
82
0
            }
83
0
        }
84
0
    }
85
0
}
86
87
// This only does something sensible if this object has a non-null comparer
88
0
bool UVector::operator==(const UVector& other) const {
89
0
    U_ASSERT(comparer != nullptr);
90
0
    if (count != other.count) return false;
91
0
    if (comparer != nullptr) {
92
        // Compare using this object's comparer
93
0
        for (int32_t i=0; i<count; ++i) {
94
0
            if (!(*comparer)(elements[i], other.elements[i])) {
95
0
                return false;
96
0
            }
97
0
        }
98
0
    }
99
0
    return true;
100
0
}
101
102
0
void UVector::addElement(void* obj, UErrorCode &status) {
103
0
    U_ASSERT(deleter == nullptr);
104
0
    if (ensureCapacity(count + 1, status)) {
105
0
        elements[count++].pointer = obj;
106
0
    }
107
0
}
108
109
0
void UVector::adoptElement(void* obj, UErrorCode &status) {
110
0
    U_ASSERT(deleter != nullptr);
111
0
    if (ensureCapacity(count + 1, status)) {
112
0
        elements[count++].pointer = obj;
113
0
    } else {
114
0
        (*deleter)(obj);
115
0
    }
116
0
}
117
0
void UVector::addElement(int32_t elem, UErrorCode &status) {
118
0
    U_ASSERT(deleter == nullptr);  // Usage error. Mixing up ints and pointers.
119
0
    if (ensureCapacity(count + 1, status)) {
120
0
        elements[count].pointer = nullptr;     // Pointers may be bigger than ints.
121
0
        elements[count].integer = elem;
122
0
        count++;
123
0
    }
124
0
}
125
126
0
void UVector::setElementAt(void* obj, int32_t index) {
127
0
    if (0 <= index && index < count) {
128
0
        if (elements[index].pointer != nullptr && deleter != nullptr) {
129
0
            (*deleter)(elements[index].pointer);
130
0
        }
131
0
        elements[index].pointer = obj;
132
0
    } else {
133
        /* index out of range */
134
0
        if (deleter != nullptr) {
135
0
            (*deleter)(obj);
136
0
        }
137
0
    }
138
0
}
139
140
0
void UVector::setElementAt(int32_t elem, int32_t index) {
141
0
    U_ASSERT(deleter == nullptr);  // Usage error. Mixing up ints and pointers.
142
0
    if (0 <= index && index < count) {
143
0
        elements[index].pointer = nullptr;
144
0
        elements[index].integer = elem;
145
0
    }
146
    /* else index out of range */
147
0
}
148
149
0
void UVector::insertElementAt(void* obj, int32_t index, UErrorCode &status) {
150
0
    if (ensureCapacity(count + 1, status)) {
151
0
        if (0 <= index && index <= count) {
152
0
            for (int32_t i=count; i>index; --i) {
153
0
                elements[i] = elements[i-1];
154
0
            }
155
0
            elements[index].pointer = obj;
156
0
            ++count;
157
0
        } else {
158
            /* index out of range */
159
0
            status = U_ILLEGAL_ARGUMENT_ERROR;
160
0
        }
161
0
    }
162
0
    if (U_FAILURE(status) && deleter != nullptr) {
163
0
        (*deleter)(obj);
164
0
    }
165
0
}
166
167
0
void UVector::insertElementAt(int32_t elem, int32_t index, UErrorCode &status) {
168
0
    U_ASSERT(deleter == nullptr);  // Usage error. Mixing up ints and pointers.
169
    // must have 0 <= index <= count
170
0
    if (ensureCapacity(count + 1, status)) {
171
0
        if (0 <= index && index <= count) {
172
0
            for (int32_t i=count; i>index; --i) {
173
0
                elements[i] = elements[i-1];
174
0
            }
175
0
            elements[index].pointer = nullptr;
176
0
            elements[index].integer = elem;
177
0
            ++count;
178
0
        } else {
179
            /* index out of range */
180
0
            status = U_ILLEGAL_ARGUMENT_ERROR;
181
0
        }
182
0
    }
183
0
}
184
185
0
void* UVector::elementAt(int32_t index) const {
186
0
    return (0 <= index && index < count) ? elements[index].pointer : 0;
187
0
}
188
189
0
int32_t UVector::elementAti(int32_t index) const {
190
0
    return (0 <= index && index < count) ? elements[index].integer : 0;
191
0
}
192
193
0
UBool UVector::containsAll(const UVector& other) const {
194
0
    for (int32_t i=0; i<other.size(); ++i) {
195
0
        if (indexOf(other.elements[i]) < 0) {
196
0
            return FALSE;
197
0
        }
198
0
    }
199
0
    return TRUE;
200
0
}
201
202
0
UBool UVector::containsNone(const UVector& other) const {
203
0
    for (int32_t i=0; i<other.size(); ++i) {
204
0
        if (indexOf(other.elements[i]) >= 0) {
205
0
            return FALSE;
206
0
        }
207
0
    }
208
0
    return TRUE;
209
0
}
210
211
0
UBool UVector::removeAll(const UVector& other) {
212
0
    UBool changed = FALSE;
213
0
    for (int32_t i=0; i<other.size(); ++i) {
214
0
        int32_t j = indexOf(other.elements[i]);
215
0
        if (j >= 0) {
216
0
            removeElementAt(j);
217
0
            changed = TRUE;
218
0
        }
219
0
    }
220
0
    return changed;
221
0
}
222
223
0
UBool UVector::retainAll(const UVector& other) {
224
0
    UBool changed = FALSE;
225
0
    for (int32_t j=size()-1; j>=0; --j) {
226
0
        int32_t i = other.indexOf(elements[j]);
227
0
        if (i < 0) {
228
0
            removeElementAt(j);
229
0
            changed = TRUE;
230
0
        }
231
0
    }
232
0
    return changed;
233
0
}
234
235
0
void UVector::removeElementAt(int32_t index) {
236
0
    void* e = orphanElementAt(index);
237
0
    if (e != nullptr && deleter != nullptr) {
238
0
        (*deleter)(e);
239
0
    }
240
0
}
241
242
0
UBool UVector::removeElement(void* obj) {
243
0
    int32_t i = indexOf(obj);
244
0
    if (i >= 0) {
245
0
        removeElementAt(i);
246
0
        return TRUE;
247
0
    }
248
0
    return FALSE;
249
0
}
250
251
0
void UVector::removeAllElements(void) {
252
0
    if (deleter != nullptr) {
253
0
        for (int32_t i=0; i<count; ++i) {
254
0
            if (elements[i].pointer != nullptr) {
255
0
                (*deleter)(elements[i].pointer);
256
0
            }
257
0
        }
258
0
    }
259
0
    count = 0;
260
0
}
261
262
0
UBool   UVector::equals(const UVector &other) const {
263
0
    int      i;
264
265
0
    if (this->count != other.count) {
266
0
        return FALSE;
267
0
    }
268
0
    if (comparer == nullptr) {
269
0
        for (i=0; i<count; i++) {
270
0
            if (elements[i].pointer != other.elements[i].pointer) {
271
0
                return FALSE;
272
0
            }
273
0
        }
274
0
    } else {
275
0
        UElement key;
276
0
        for (i=0; i<count; i++) {
277
0
            key.pointer = &other.elements[i];
278
0
            if (!(*comparer)(key, elements[i])) {
279
0
                return FALSE;
280
0
            }
281
0
        }
282
0
    }
283
0
    return TRUE;
284
0
}
285
286
287
288
0
int32_t UVector::indexOf(void* obj, int32_t startIndex) const {
289
0
    UElement key;
290
0
    key.pointer = obj;
291
0
    return indexOf(key, startIndex, HINT_KEY_POINTER);
292
0
}
293
294
0
int32_t UVector::indexOf(int32_t obj, int32_t startIndex) const {
295
0
    UElement key;
296
0
    key.integer = obj;
297
0
    return indexOf(key, startIndex, HINT_KEY_INTEGER);
298
0
}
299
300
0
int32_t UVector::indexOf(UElement key, int32_t startIndex, int8_t hint) const {
301
0
    if (comparer != nullptr) {
302
0
        for (int32_t i=startIndex; i<count; ++i) {
303
0
            if ((*comparer)(key, elements[i])) {
304
0
                return i;
305
0
            }
306
0
        }
307
0
    } else {
308
0
        for (int32_t i=startIndex; i<count; ++i) {
309
            /* Pointers are not always the same size as ints so to perform
310
             * a valid comparison we need to know whether we are being
311
             * provided an int or a pointer. */
312
0
            if (hint & HINT_KEY_POINTER) {
313
0
                if (key.pointer == elements[i].pointer) {
314
0
                    return i;
315
0
                }
316
0
            } else {
317
0
                if (key.integer == elements[i].integer) {
318
0
                    return i;
319
0
                }
320
0
            }
321
0
        }
322
0
    }
323
0
    return -1;
324
0
}
325
326
0
UBool UVector::ensureCapacity(int32_t minimumCapacity, UErrorCode &status) {
327
0
    if (U_FAILURE(status)) {
328
0
        return false;
329
0
    }
330
0
    if (minimumCapacity < 0) {
331
0
        status = U_ILLEGAL_ARGUMENT_ERROR;
332
0
        return false;
333
0
    }
334
0
    if (capacity < minimumCapacity) {
335
0
        if (capacity > (INT32_MAX - 1) / 2) {         // integer overflow check
336
0
            status = U_ILLEGAL_ARGUMENT_ERROR;
337
0
            return false;
338
0
        }
339
0
        int32_t newCap = capacity * 2;
340
0
        if (newCap < minimumCapacity) {
341
0
            newCap = minimumCapacity;
342
0
        }
343
0
        if (newCap > (int32_t)(INT32_MAX / sizeof(UElement))) { // integer overflow check
344
            // We keep the original memory contents on bad minimumCapacity.
345
0
            status = U_ILLEGAL_ARGUMENT_ERROR;
346
0
            return false;
347
0
        }
348
0
        UElement* newElems = (UElement *)uprv_realloc(elements, sizeof(UElement)*newCap);
349
0
        if (newElems == nullptr) {
350
            // We keep the original contents on the memory failure on realloc or bad minimumCapacity.
351
0
            status = U_MEMORY_ALLOCATION_ERROR;
352
0
            return false;
353
0
        }
354
0
        elements = newElems;
355
0
        capacity = newCap;
356
0
    }
357
0
    return true;
358
0
}
359
360
/**
361
 * Change the size of this vector as follows: If newSize is smaller,
362
 * then truncate the array, possibly deleting held elements for i >=
363
 * newSize.  If newSize is larger, grow the array, filling in new
364
 * slots with nullptr.
365
 */
366
0
void UVector::setSize(int32_t newSize, UErrorCode &status) {
367
0
    if (!ensureCapacity(newSize, status)) {
368
0
        return;
369
0
    }
370
0
    if (newSize > count) {
371
0
        UElement empty;
372
0
        empty.pointer = nullptr;
373
0
        empty.integer = 0;
374
0
        for (int32_t i=count; i<newSize; ++i) {
375
0
            elements[i] = empty;
376
0
        }
377
0
    } else {
378
        /* Most efficient to count down */
379
0
        for (int32_t i=count-1; i>=newSize; --i) {
380
0
            removeElementAt(i);
381
0
        }
382
0
    }
383
0
    count = newSize;
384
0
}
385
386
/**
387
 * Fill in the given array with all elements of this vector.
388
 */
389
0
void** UVector::toArray(void** result) const {
390
0
    void** a = result;
391
0
    for (int i=0; i<count; ++i) {
392
0
        *a++ = elements[i].pointer;
393
0
    }
394
0
    return result;
395
0
}
396
397
0
UObjectDeleter *UVector::setDeleter(UObjectDeleter *d) {
398
0
    UObjectDeleter *old = deleter;
399
0
    deleter = d;
400
0
    return old;
401
0
}
402
403
0
UElementsAreEqual *UVector::setComparer(UElementsAreEqual *d) {
404
0
    UElementsAreEqual *old = comparer;
405
0
    comparer = d;
406
0
    return old;
407
0
}
408
409
/**
410
 * Removes the element at the given index from this vector and
411
 * transfer ownership of it to the caller.  After this call, the
412
 * caller owns the result and must delete it and the vector entry
413
 * at 'index' is removed, shifting all subsequent entries back by
414
 * one index and shortening the size of the vector by one.  If the
415
 * index is out of range or if there is no item at the given index
416
 * then 0 is returned and the vector is unchanged.
417
 */
418
0
void* UVector::orphanElementAt(int32_t index) {
419
0
    void* e = nullptr;
420
0
    if (0 <= index && index < count) {
421
0
        e = elements[index].pointer;
422
0
        for (int32_t i=index; i<count-1; ++i) {
423
0
            elements[i] = elements[i+1];
424
0
        }
425
0
        --count;
426
0
    }
427
    /* else index out of range */
428
0
    return e;
429
0
}
430
431
/**
432
 * Insert the given object into this vector at its sorted position
433
 * as defined by 'compare'.  The current elements are assumed to
434
 * be sorted already.
435
 */
436
0
void UVector::sortedInsert(void* obj, UElementComparator *compare, UErrorCode& ec) {
437
0
    UElement e;
438
0
    e.pointer = obj;
439
0
    sortedInsert(e, compare, ec);
440
0
}
441
442
/**
443
 * Insert the given integer into this vector at its sorted position
444
 * as defined by 'compare'.  The current elements are assumed to
445
 * be sorted already.
446
 */
447
0
void UVector::sortedInsert(int32_t obj, UElementComparator *compare, UErrorCode& ec) {
448
0
    U_ASSERT(deleter == nullptr);
449
0
    UElement e {};
450
0
    e.integer = obj;
451
0
    sortedInsert(e, compare, ec);
452
0
}
453
454
// ASSUME elements[] IS CURRENTLY SORTED
455
0
void UVector::sortedInsert(UElement e, UElementComparator *compare, UErrorCode& ec) {
456
    // Perform a binary search for the location to insert tok at.  Tok
457
    // will be inserted between two elements a and b such that a <=
458
    // tok && tok < b, where there is a 'virtual' elements[-1] always
459
    // less than tok and a 'virtual' elements[count] always greater
460
    // than tok.
461
0
    if (!ensureCapacity(count + 1, ec)) {
462
0
        if (deleter != nullptr) {
463
0
            (*deleter)(e.pointer);
464
0
        }
465
0
        return;
466
0
    }
467
0
    int32_t min = 0, max = count;
468
0
    while (min != max) {
469
0
        int32_t probe = (min + max) / 2;
470
0
        int32_t c = (*compare)(elements[probe], e);
471
0
        if (c > 0) {
472
0
            max = probe;
473
0
        } else {
474
            // assert(c <= 0);
475
0
            min = probe + 1;
476
0
        }
477
0
    }
478
0
    for (int32_t i=count; i>min; --i) {
479
0
        elements[i] = elements[i-1];
480
0
    }
481
0
    elements[min] = e;
482
0
    ++count;
483
0
}
484
485
/**
486
  *  Array sort comparator function.
487
  *  Used from UVector::sort()
488
  *  Conforms to function signature required for uprv_sortArray().
489
  *  This function is essentially just a wrapper, to make a
490
  *  UVector style comparator function usable with uprv_sortArray().
491
  *
492
  *  The context pointer to this function is a pointer back
493
  *  (with some extra indirection) to the user supplied comparator.
494
  *  
495
  */
496
static int32_t U_CALLCONV
497
0
sortComparator(const void *context, const void *left, const void *right) {
498
0
    UElementComparator *compare = *static_cast<UElementComparator * const *>(context);
499
0
    UElement e1 = *static_cast<const UElement *>(left);
500
0
    UElement e2 = *static_cast<const UElement *>(right);
501
0
    int32_t result = (*compare)(e1, e2);
502
0
    return result;
503
0
}
504
505
506
/**
507
  *  Array sort comparison function for use from UVector::sorti()
508
  *  Compares int32_t vector elements.
509
  */
510
static int32_t U_CALLCONV
511
0
sortiComparator(const void * /*context */, const void *left, const void *right) {
512
0
    const UElement *e1 = static_cast<const UElement *>(left);
513
0
    const UElement *e2 = static_cast<const UElement *>(right);
514
0
    int32_t result = e1->integer < e2->integer? -1 :
515
0
                     e1->integer == e2->integer? 0 : 1;
516
0
    return result;
517
0
}
518
519
/**
520
  * Sort the vector, assuming it contains ints.
521
  *     (A more general sort would take a comparison function, but it's
522
  *     not clear whether UVector's UElementComparator or
523
  *     UComparator from uprv_sortAray would be more appropriate.)
524
  */
525
0
void UVector::sorti(UErrorCode &ec) {
526
0
    if (U_SUCCESS(ec)) {
527
0
        uprv_sortArray(elements, count, sizeof(UElement),
528
0
                       sortiComparator, nullptr,  FALSE, &ec);
529
0
    }
530
0
}
531
532
533
/**
534
 *  Sort with a user supplied comparator.
535
 *
536
 *    The comparator function handling is confusing because the function type
537
 *    for UVector  (as defined for sortedInsert()) is different from the signature
538
 *    required by uprv_sortArray().  This is handled by passing the
539
 *    the UVector sort function pointer via the context pointer to a
540
 *    sortArray() comparator function, which can then call back to
541
 *    the original user function.
542
 *
543
 *    An additional twist is that it's not safe to pass a pointer-to-function
544
 *    as  a (void *) data pointer, so instead we pass a (data) pointer to a
545
 *    pointer-to-function variable.
546
 */
547
0
void UVector::sort(UElementComparator *compare, UErrorCode &ec) {
548
0
    if (U_SUCCESS(ec)) {
549
0
        uprv_sortArray(elements, count, sizeof(UElement),
550
0
                       sortComparator, &compare, FALSE, &ec);
551
0
    }
552
0
}
553
554
555
/**
556
 *  Stable sort with a user supplied comparator of type UComparator.
557
 */
558
0
void UVector::sortWithUComparator(UComparator *compare, const void *context, UErrorCode &ec) {
559
0
    if (U_SUCCESS(ec)) {
560
0
        uprv_sortArray(elements, count, sizeof(UElement),
561
0
                       compare, context, TRUE, &ec);
562
0
    }
563
0
}
564
565
U_NAMESPACE_END
566