Line | Count | Source (jump to first uncovered line) |
1 | | // SPDX-License-Identifier: GPL-2.0-or-later |
2 | | /* |
3 | | * June 23 2023, Christian Hopps <chopps@labn.net> |
4 | | * |
5 | | * Copyright (c) 2023, LabN Consulting, L.L.C. |
6 | | * |
7 | | */ |
8 | | #include <zebra.h> |
9 | | #include "darr.h" |
10 | | |
11 | | void __dar_resize(void **a, uint count, size_t esize); |
12 | | |
13 | | static uint _msb(uint count) |
14 | 0 | { |
15 | 0 | uint bit = 0; |
16 | 0 | int msb = 0; |
17 | |
|
18 | 0 | while (count) { |
19 | 0 | if (count & 1) |
20 | 0 | msb = bit; |
21 | 0 | count >>= 1; |
22 | 0 | bit += 1; |
23 | 0 | } |
24 | 0 | return msb; |
25 | 0 | } |
26 | | |
27 | | static uint darr_next_count(uint count, size_t esize) |
28 | 0 | { |
29 | 0 | uint ncount; |
30 | |
|
31 | 0 | if (esize > sizeof(long long) && count == 1) |
32 | | /* treat like a pointer */ |
33 | 0 | ncount = 1; |
34 | 0 | else { |
35 | 0 | uint msb = _msb(count); |
36 | |
|
37 | 0 | ncount = 1ull << msb; |
38 | | /* if the users count wasn't a pow2 make it the next pow2. */ |
39 | 0 | if (ncount != count) { |
40 | 0 | assert(ncount < count); |
41 | 0 | ncount <<= 1; |
42 | 0 | if (esize < sizeof(long long) && ncount < 8) |
43 | 0 | ncount = 8; |
44 | 0 | } |
45 | 0 | } |
46 | 0 | return ncount; |
47 | 0 | } |
48 | | |
49 | | static size_t darr_size(uint count, size_t esize) |
50 | 0 | { |
51 | 0 | return count * esize + sizeof(struct darr_metadata); |
52 | 0 | } |
53 | | |
54 | | void *__darr_resize(void *a, uint count, size_t esize) |
55 | 0 | { |
56 | 0 | uint ncount = darr_next_count(count, esize); |
57 | 0 | size_t osz = (a == NULL) ? 0 : darr_size(darr_cap(a), esize); |
58 | 0 | size_t sz = darr_size(ncount, esize); |
59 | 0 | struct darr_metadata *dm = realloc(a ? _darr_meta(a) : NULL, sz); |
60 | | /* do *not* use a */ |
61 | |
|
62 | 0 | assert(dm); |
63 | 0 | if (sz > osz) |
64 | 0 | memset((char *)dm + osz, 0, sz - osz); |
65 | |
|
66 | 0 | dm->cap = ncount; |
67 | |
|
68 | 0 | return (void *)(dm + 1); |
69 | 0 | } |
70 | | |
71 | | |
72 | | void *__darr_insert_n(void *a, uint at, uint count, size_t esize, bool zero) |
73 | 0 | { |
74 | |
|
75 | 0 | struct darr_metadata *dm; |
76 | 0 | uint olen, nlen; |
77 | |
|
78 | 0 | if (!a) |
79 | 0 | a = __darr_resize(NULL, at + count, esize); |
80 | 0 | dm = (struct darr_metadata *)a - 1; |
81 | 0 | olen = dm->len; |
82 | | |
83 | | // at == 1 |
84 | | // count == 100 |
85 | | // olen == 2 |
86 | | |
87 | | /* see if the user is expanding first using `at` */ |
88 | 0 | if (at >= olen) |
89 | 0 | nlen = at + count; |
90 | 0 | else |
91 | 0 | nlen = olen + count; |
92 | |
|
93 | 0 | if (nlen > dm->cap) { |
94 | 0 | a = __darr_resize(a, nlen, esize); |
95 | 0 | dm = (struct darr_metadata *)a - 1; |
96 | 0 | } |
97 | |
|
98 | 0 | #define _a_at(i) ((char *)a + ((i)*esize)) |
99 | 0 | if (at < olen) |
100 | 0 | memmove(_a_at(at + count), _a_at(at), esize * (olen - at)); |
101 | |
|
102 | 0 | dm->len = nlen; |
103 | |
|
104 | 0 | if (zero) { |
105 | 0 | if (at >= olen) { |
106 | 0 | at -= olen; |
107 | 0 | count += olen; |
108 | 0 | } |
109 | 0 | memset(_a_at(at), 0, esize * count); |
110 | 0 | } |
111 | |
|
112 | 0 | return (void *)a; |
113 | 0 | #undef _a_at |
114 | 0 | } |