1 /* arrayu64.c - expanding array of 64 bit unsigned numbers
2 *
3 * Copyright (c) 1994-2011 Carnegie Mellon University. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in
14 * the documentation and/or other materials provided with the
15 * distribution.
16 *
17 * 3. The name "Carnegie Mellon University" must not be used to
18 * endorse or promote products derived from this software without
19 * prior written permission. For permission or any legal
20 * details, please contact
21 * Carnegie Mellon University
22 * Center for Technology Transfer and Enterprise Creation
23 * 4615 Forbes Avenue
24 * Suite 302
25 * Pittsburgh, PA 15213
26 * (412) 268-7393, fax: (412) 268-7395
27 * innovation@andrew.cmu.edu
28 *
29 * 4. Redistributions of any form whatsoever must retain the following
30 * acknowledgment:
31 * "This product includes software developed by Computing Services
32 * at Carnegie Mellon University (http://www.cmu.edu/computing/)."
33 *
34 * CARNEGIE MELLON UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO
35 * THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
36 * AND FITNESS, IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY BE LIABLE
37 * FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
38 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN
39 * AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING
40 * OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
41 *
42 * Author: Bron Gondwana
43 * Start Date: 2013/02/12
44 */
45
46 #include <config.h>
47
48 #include <string.h>
49
50 #include "arrayu64.h"
51 #include "xmalloc.h"
52
arrayu64_new(void)53 EXPORTED arrayu64_t *arrayu64_new(void)
54 {
55 return xzmalloc(sizeof(arrayu64_t));
56 }
57
arrayu64_fini(arrayu64_t * au)58 EXPORTED void arrayu64_fini(arrayu64_t *au)
59 {
60 if (!au)
61 return;
62 free(au->data);
63 au->data = NULL;
64 au->count = 0;
65 au->alloc = 0;
66 }
67
arrayu64_free(arrayu64_t * au)68 EXPORTED void arrayu64_free(arrayu64_t *au)
69 {
70 if (!au)
71 return;
72 arrayu64_fini(au);
73 free(au);
74 }
75
76 #define QUANTUM 16
ensure_alloc(arrayu64_t * au,int newalloc)77 static void ensure_alloc(arrayu64_t *au, int newalloc)
78 {
79 if (newalloc <= au->alloc)
80 return;
81 newalloc = ((newalloc + QUANTUM-1) / QUANTUM) * QUANTUM;
82 au->data = xrealloc(au->data, sizeof(uint64_t) * newalloc);
83 memset(au->data + au->alloc, 0, sizeof(uint64_t) * (newalloc - au->alloc));
84 au->alloc = newalloc;
85 }
86
87 /*
88 * Normalise the index passed by a caller, to a value in the range
89 * 0..count-1, or < 0 for invalid, assuming the function we're
90 * performing does not have the side effect of expanding the array.
91 * Note that doesn't necessarily mean the array is read-only, e.g.
92 * arrayu64_remove() modifies the array but does not expand the array if
93 * given an index outside the array's current bounds. In Perl style,
94 * negative indexes whose absolute value is less than the length of the
95 * array are treated as counting back from the end, e.g. idx=-1 means
96 * the final element.
97 */
adjust_index_ro(const arrayu64_t * au,int idx)98 static inline int adjust_index_ro(const arrayu64_t *au, int idx)
99 {
100 if (idx >= au->count)
101 return -1;
102 else if (idx < 0)
103 idx += au->count;
104 return idx;
105 }
106
107 /*
108 * Like adjust_index_ro(), with extra complication that the function
109 * we're performing will expand the array if either the adjusted index
110 * points outside the current bounds of the array, or @grow tells us
111 * that we're about to need more space in the array.
112 */
adjust_index_rw(arrayu64_t * au,int idx,int grow)113 static inline int adjust_index_rw(arrayu64_t *au, int idx, int grow)
114 {
115 if (idx >= au->count) {
116 /* expanding the array as a side effect @idx pointing
117 * outside the current bounds, plus perhaps @grow */
118 ensure_alloc(au, idx+grow);
119 } else if (idx < 0) {
120 /* adjust Perl-style negative indices */
121 idx += au->count;
122 if (idx >= 0 && grow)
123 ensure_alloc(au, au->count+grow);
124 } else if (grow) {
125 /* expanding the array due to an insert or append */
126 ensure_alloc(au, au->count+grow);
127 }
128 return idx;
129 }
130
arrayu64_dup(const arrayu64_t * au)131 EXPORTED arrayu64_t *arrayu64_dup(const arrayu64_t *au)
132 {
133 arrayu64_t *new = arrayu64_new();
134 int i;
135
136 arrayu64_truncate(new, au->count);
137
138 for (i = 0 ; i < au->count ; i++)
139 new->data[i] = au->data[i];
140
141 return new;
142 }
143
arrayu64_append(arrayu64_t * au,uint64_t val)144 EXPORTED int arrayu64_append(arrayu64_t *au, uint64_t val)
145 {
146 int pos = au->count++;
147 ensure_alloc(au, au->count);
148 au->data[pos] = val;
149 return pos;
150 }
151
arrayu64_add(arrayu64_t * au,uint64_t val)152 EXPORTED int arrayu64_add(arrayu64_t *au, uint64_t val)
153 {
154 int pos = arrayu64_find(au, val, 0);
155 if (pos < 0) pos = arrayu64_append(au, val);
156 return pos;
157 }
158
arrayu64_set(arrayu64_t * au,int idx,uint64_t val)159 EXPORTED void arrayu64_set(arrayu64_t *au, int idx, uint64_t val)
160 {
161 if ((idx = adjust_index_rw(au, idx, 0)) < 0)
162 return;
163 au->data[idx] = val;
164 /* adjust the count if we just sparsely expanded the array */
165 if (idx >= au->count)
166 au->count = idx+1;
167 }
168
169
arrayu64_insert(arrayu64_t * au,int idx,uint64_t val)170 EXPORTED void arrayu64_insert(arrayu64_t *au, int idx, uint64_t val)
171 {
172 if ((idx = adjust_index_rw(au, idx, 1)) < 0)
173 return;
174 if (idx < au->count)
175 memmove(au->data+idx+1, au->data+idx,
176 sizeof(uint64_t) * (au->count-idx));
177 au->data[idx] = val;
178 au->count++;
179 }
180
arrayu64_remove(arrayu64_t * au,int idx)181 EXPORTED uint64_t arrayu64_remove(arrayu64_t *au, int idx)
182 {
183 uint64_t val;
184 if ((idx = adjust_index_ro(au, idx)) < 0)
185 return 0;
186 val = au->data[idx];
187 au->count--;
188 if (idx < au->count)
189 memmove(au->data+idx, au->data+idx+1,
190 sizeof(uint64_t) * (au->count-idx));
191 au->data[au->count] = 0;
192 return val;
193 }
194
arrayu64_remove_all(arrayu64_t * au,uint64_t val)195 EXPORTED int arrayu64_remove_all(arrayu64_t *au, uint64_t val)
196 {
197 int i = 0;
198 int count = 0;
199
200 for (;;) {
201 i = arrayu64_find(au, val, i);
202 if (i < 0)
203 break;
204 count++;
205 arrayu64_remove(au, i);
206 }
207
208 return count;
209 }
210
arrayu64_truncate(arrayu64_t * au,int newlen)211 EXPORTED void arrayu64_truncate(arrayu64_t *au, int newlen)
212 {
213 if (newlen == au->count)
214 return;
215
216 if (newlen > au->count) {
217 ensure_alloc(au, newlen);
218 }
219 else {
220 memset(au->data+newlen, 0, sizeof(uint64_t) * (au->count - newlen));
221 }
222
223 au->count = newlen;
224 }
225
226 /* note: values outside the range are all zero */
arrayu64_nth(const arrayu64_t * au,int idx)227 EXPORTED uint64_t arrayu64_nth(const arrayu64_t *au, int idx)
228 {
229 if ((idx = adjust_index_ro(au, idx)) < 0)
230 return 0;
231 return au->data[idx];
232 }
233
arrayu64_max(const arrayu64_t * au)234 EXPORTED uint64_t arrayu64_max(const arrayu64_t *au)
235 {
236 uint64_t max = 0;
237 int i;
238
239 for (i = 0; i < au->count; i++) {
240 if (au->data[i] > max)
241 max = au->data[i];
242 }
243
244 return max;
245 }
246
_numeric_sort(const void * a,const void * b)247 static int _numeric_sort(const void *a, const void *b)
248 {
249 uint64_t av = *((uint64_t *)a);
250 uint64_t bv = *((uint64_t *)b);
251
252 if (av == bv)
253 return 0;
254 if (av < bv)
255 return -1;
256 return 1;
257 }
258
arrayu64_sort(arrayu64_t * au,arrayu64_cmp_fn_t * cmp)259 EXPORTED void arrayu64_sort(arrayu64_t *au, arrayu64_cmp_fn_t *cmp)
260 {
261 if (!cmp) cmp = _numeric_sort;
262 qsort(au->data, au->count, sizeof(uint64_t), cmp);
263 }
264
arrayu64_uniq(arrayu64_t * au)265 EXPORTED void arrayu64_uniq(arrayu64_t *au)
266 {
267 int i;
268
269 for (i = 1; i < au->count; i++) {
270 if (au->data[i-1] == au->data[i])
271 arrayu64_remove(au, i--);
272 }
273 }
274
arrayu64_find(arrayu64_t * au,uint64_t val,int idx)275 EXPORTED int arrayu64_find(arrayu64_t *au, uint64_t val, int idx)
276 {
277 int i;
278
279 if ((idx = adjust_index_ro(au, idx)) < 0)
280 return -1;
281
282 for (i = idx; i < au->count; i++) {
283 if (au->data[i] == val)
284 return i;
285 }
286
287 return -1;
288 }
289
arrayu64_size(const arrayu64_t * au)290 EXPORTED int arrayu64_size(const arrayu64_t *au)
291 {
292 return au->count;
293 }
294