1 /* ptrarray.c -- an expanding array of pointers
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: Greg Banks
43 * Start Date: 2011/01/11
44 */
45
46 #include "ptrarray.h"
47 #include <memory.h>
48 #include "xmalloc.h"
49
ptrarray_new(void)50 EXPORTED ptrarray_t *ptrarray_new(void)
51 {
52 return xzmalloc(sizeof(ptrarray_t));
53 }
54
ptrarray_fini(ptrarray_t * pa)55 EXPORTED void ptrarray_fini(ptrarray_t *pa)
56 {
57 if (!pa)
58 return;
59 memset(pa->data, 0, sizeof(void *) * pa->count);
60 free(pa->data);
61 pa->data = NULL;
62 pa->count = 0;
63 pa->alloc = 0;
64 }
65
ptrarray_free(ptrarray_t * pa)66 EXPORTED void ptrarray_free(ptrarray_t *pa)
67 {
68 if (!pa)
69 return;
70 ptrarray_fini(pa);
71 free(pa);
72 }
73
74 /*
75 * Ensure the index @idx exists in the array, if necessary expanding the
76 * array, and if necessary NULL-filling all the intervening elements.
77 * Note that we always ensure an empty slot past the last reported
78 * index, so that we can pass data[] to execve() or other routines that
79 * assume a NULL terminator.
80 */
81 #define QUANTUM 16
ensure_alloc(ptrarray_t * pa,int newalloc)82 static void ensure_alloc(ptrarray_t *pa, int newalloc)
83 {
84 if (newalloc)
85 newalloc++;
86 if (newalloc <= pa->alloc)
87 return;
88 newalloc = ((newalloc + QUANTUM-1) / QUANTUM) * QUANTUM;
89 pa->data = xrealloc(pa->data, sizeof(void *) * newalloc);
90 memset(pa->data+pa->alloc, 0, sizeof(void *) * (newalloc-pa->alloc));
91 pa->alloc = newalloc;
92 }
93
adjust_index_ro(const ptrarray_t * pa,int idx)94 static inline int adjust_index_ro(const ptrarray_t *pa, int idx)
95 {
96 if (idx >= pa->count)
97 return -1;
98 else if (idx < 0)
99 idx += pa->count;
100 return idx;
101 }
102
adjust_index_rw(ptrarray_t * pa,int idx,int len)103 static inline int adjust_index_rw(ptrarray_t *pa, int idx, int len)
104 {
105 if (idx >= pa->count) {
106 ensure_alloc(pa, idx+len);
107 } else if (idx < 0) {
108 idx += pa->count;
109 if (idx >= 0 && len)
110 ensure_alloc(pa, pa->count+len);
111 } else if (len) {
112 ensure_alloc(pa, pa->count+len);
113 }
114 return idx;
115 }
116
ptrarray_add(ptrarray_t * pa,void * p)117 EXPORTED void ptrarray_add(ptrarray_t *pa, void *p)
118 {
119 if (ptrarray_find(pa, p, 0) < 0)
120 ptrarray_append(pa, p);
121 }
122
ptrarray_append(ptrarray_t * pa,void * p)123 EXPORTED void ptrarray_append(ptrarray_t *pa, void *p)
124 {
125 ensure_alloc(pa, pa->count+1);
126 pa->data[pa->count++] = p;
127 }
128
ptrarray_set(ptrarray_t * pa,int idx,void * p)129 EXPORTED void ptrarray_set(ptrarray_t *pa, int idx, void *p)
130 {
131 if ((idx = adjust_index_rw(pa, idx, 0)) < 0)
132 return;
133 pa->data[idx] = p;
134 }
135
_ptrarray_insert(ptrarray_t * pa,int idx,void * p)136 static inline void _ptrarray_insert(ptrarray_t *pa, int idx, void *p)
137 {
138 if (idx < pa->count)
139 memmove(pa->data+idx+1, pa->data+idx,
140 sizeof(void *) * (pa->count-idx));
141 pa->data[idx] = p;
142 pa->count++;
143 }
144
ptrarray_insert(ptrarray_t * pa,int idx,void * p)145 EXPORTED void ptrarray_insert(ptrarray_t *pa, int idx, void *p)
146 {
147 if ((idx = adjust_index_rw(pa, idx, 1)) < 0)
148 return;
149 _ptrarray_insert(pa, idx, p);
150 }
151
ptrarray_remove(ptrarray_t * pa,int idx)152 EXPORTED void *ptrarray_remove(ptrarray_t *pa, int idx)
153 {
154 void *p;
155 if ((idx = adjust_index_ro(pa, idx)) < 0)
156 return NULL;
157 p = pa->data[idx];
158 pa->count--;
159 if (idx < pa->count)
160 memmove(pa->data+idx, pa->data+idx+1,
161 sizeof(void *) * (pa->count-idx));
162 return p;
163 }
164
ptrarray_truncate(ptrarray_t * pa,int newlen)165 EXPORTED void ptrarray_truncate(ptrarray_t *pa, int newlen)
166 {
167 int i;
168
169 if (newlen == pa->count)
170 return;
171
172 if (newlen > pa->count) {
173 ensure_alloc(pa, newlen);
174 } else {
175 for (i = newlen ; i < pa->count ; i++) {
176 pa->data[i] = NULL;
177 }
178 }
179 pa->count = newlen;
180 }
181
ptrarray_nth(const ptrarray_t * pa,int idx)182 EXPORTED void *ptrarray_nth(const ptrarray_t *pa, int idx)
183 {
184 if ((idx = adjust_index_ro(pa, idx)) < 0)
185 return NULL;
186 return pa->data[idx];
187 }
188
ptrarray_takevf(ptrarray_t * pa)189 EXPORTED void **ptrarray_takevf(ptrarray_t *pa)
190 {
191 void **d = pa->data;
192 pa->data = NULL;
193 pa->count = pa->alloc = 0;
194 ptrarray_free(pa);
195 return d;
196 }
197
ptrarray_find(const ptrarray_t * pa,void * match,int starting)198 EXPORTED int ptrarray_find(const ptrarray_t *pa, void *match, int starting)
199 {
200 int i;
201
202 for (i = starting ; i < pa->count ; i++)
203 if (match == pa->data[i])
204 return i;
205 return -1;
206 }
207
ptrarray_sort(ptrarray_t * pa,int (* compare)(const void **,const void **))208 EXPORTED void ptrarray_sort(ptrarray_t *pa,
209 int (*compare)(const void **, const void **))
210 {
211 qsort(pa->data, pa->count, sizeof(void*),
212 (int (*)(const void *, const void *))compare);
213 }
214
ptrarray_size(const ptrarray_t * pa)215 EXPORTED int ptrarray_size(const ptrarray_t *pa)
216 {
217 return pa->count;
218 }
219