1 /*
2  * This program is free software; you can redistribute it and/or modify
3  * it under the terms of the GNU General Public License as published by
4  * the Free Software Foundation; either version 2 of the License, or
5  * (at your option) any later version.
6  * Please read the file COPYING, README and AUTHORS for more information.
7  *
8  * functions to dynamically allocate arrays.
9  * Copyright (c) 2005 Florian Westphal (westphal@foo.fh-furtwangen.de)
10  *
11  */
12 
13 #include "array.h"
14 
15 static char UNUSED id[] = "$Id: array.c,v 1.15 2007/11/18 15:05:35 alex Exp $";
16 
17 #include <assert.h>
18 
19 #include <stdlib.h>
20 #include <string.h>
21 
22 #include "log.h"
23 
24 /* Enable more Debug messages in alloc / append / memmove code. */
25 /* #define DEBUG_ARRAY */
26 
27 
28 
29 #define array_UNUSABLE(x)	( !(x)->mem || (0 == (x)->allocated) )
30 
31 #define ALIGN_32U(x)            (((x)+(unsigned)31  ) & ~((unsigned)31))
32 #define ALIGN_1024U(x)          (((x)+(unsigned)1023) & ~((unsigned)1023))
33 #define ALIGN_4096U(x)          (((x)+(unsigned)4095) & ~((unsigned)4095))
34 
35 
36 static bool
37 safemult_sizet(size_t a, size_t b, size_t *res)
38 {
39 	size_t tmp = a * b;
40 
41 	if (b && (tmp / b != a))
42 		return false;
43 
44 	*res = tmp;
45 	return true;
46 }
47 
48 
49 void
50 array_init(array *a)
51 {
52 	assert(a != NULL);
53 	a->mem = NULL;
54 	a->allocated = 0;
55 	a->used = 0;
56 }
57 
58 
59 /* if realloc() fails, array_alloc return NULL. otherwise return pointer to elem pos in array */
60 void *
61 array_alloc(array * a, size_t size, size_t pos)
62 {
63 	size_t alloc, pos_plus1 = pos + 1;
64 	size_t aligned = 0;
65 	char *tmp;
66 
67 	assert(size > 0);
68 
69 	if (pos_plus1 == 0 || !safemult_sizet(size, pos_plus1, &alloc))
70 		return NULL;
71 
72 	if (a->allocated < alloc) {
73 		if (alloc < 128) {
74 			aligned = ALIGN_32U(alloc);
75 		} else {
76 			if (alloc < 4096) {
77 				aligned = ALIGN_1024U(alloc);
78 			} else {
79 				aligned = ALIGN_4096U(alloc);
80 			}
81 		}
82 #ifdef DEBUG_ARRAY
83 		Log(LOG_DEBUG, "array_alloc(): rounded %u to %u bytes.", alloc, aligned);
84 #endif
85 
86 		assert(aligned >= alloc);
87 
88 		if (aligned < alloc)	/* rounding overflow */
89 			return NULL;
90 
91 		alloc = aligned;
92 #ifdef DEBUG_ARRAY
93 		Log(LOG_DEBUG, "array_alloc(): changing size from %u to %u bytes.",
94 		    a->allocated, aligned);
95 #endif
96 
97 		tmp = realloc(a->mem, alloc);
98 		if (!tmp)
99 			return NULL;
100 
101 		a->mem = tmp;
102 		a->allocated = alloc;
103 
104 		assert(a->allocated > a->used);
105 
106 		memset(a->mem + a->used, 0, a->allocated - a->used);
107 
108 		a->used = alloc;
109 	}
110 	return a->mem + (pos * size);
111 }
112 
113 
114 /*return number of initialized ELEMS in a. */
115 size_t
116 array_length(const array * const a, size_t membersize)
117 {
118 	assert(a != NULL);
119 	assert(membersize > 0);
120 
121 	if (array_UNUSABLE(a))
122 		return 0;
123 
124 	return membersize ? a->used / membersize : 0;
125 }
126 
127 
128 /* copy array src to array dest */
129 bool
130 array_copy(array * dest, const array * const src)
131 {
132 	if (array_UNUSABLE(src))
133 		return false;
134 
135 	return array_copyb(dest, src->mem, src->used);
136 }
137 
138 
139 /* return false on failure (realloc failure, invalid src/dest array) */
140 bool
141 array_copyb(array * dest, const char *src, size_t len)
142 {
143 	assert(dest != NULL);
144 	assert(src != NULL );
145 
146 	if (!src || !dest)
147 		return false;
148 
149 	array_trunc(dest);
150 	return array_catb(dest, src, len);
151 }
152 
153 
154 /* copy string to dest */
155 bool
156 array_copys(array * dest, const char *src)
157 {
158 	return array_copyb(dest, src, strlen(src));
159 }
160 
161 
162 /* append len bytes from src to the array dest.
163 return false if we could not append all bytes (realloc failure, invalid src/dest array) */
164 bool
165 array_catb(array * dest, const char *src, size_t len)
166 {
167 	size_t tmp;
168 	size_t used;
169 	char *ptr;
170 
171 	assert(dest != NULL);
172 	assert(src != NULL);
173 
174 	if (!len)
175 		return true;
176 
177 	if (!src || !dest)
178 		return false;
179 
180 	used = dest->used;
181 	tmp = used + len;
182 
183 	if (tmp < used || tmp < len)	/* integer overflow */
184 		return false;
185 
186 	if (!array_alloc(dest, 1, tmp))
187 		return false;
188 
189 	ptr = dest->mem;
190 
191 	assert(ptr != NULL);
192 
193 #ifdef DEBUG_ARRAY
194 	Log(LOG_DEBUG,
195 	    "array_catb(): appending %u bytes to array (now %u bytes in array).",
196 	    len, tmp);
197 #endif
198 	memcpy(ptr + used, src, len);
199 	dest->used = tmp;
200 	return true;
201 }
202 
203 
204 /* append string to dest */
205 bool
206 array_cats(array * dest, const char *src)
207 {
208 	return array_catb(dest, src, strlen(src));
209 }
210 
211 
212 /* append trailing NUL byte to array */
213 bool
214 array_cat0(array * a)
215 {
216 	return array_catb(a, "", 1);
217 }
218 
219 
220 /* append trailing NUL byte to array, but do not count it. */
221 bool
222 array_cat0_temporary(array * a)
223 {
224 	char *endpos = array_alloc(a, 1, array_bytes(a));
225 	if (!endpos)
226 		return false;
227 
228 	*endpos = '\0';
229 	return true;
230 }
231 
232 /* add contents of array src to array dest. */
233 bool
234 array_cat(array * dest, const array * const src)
235 {
236 	if (array_UNUSABLE(src))
237 		return false;
238 
239 	return array_catb(dest, src->mem, src->used);
240 }
241 
242 
243 /* return pointer to the element at pos.
244    return NULL if the array is unallocated, or if pos is larger than
245    the number of elements stored int the array. */
246 void *
247 array_get(array * a, size_t membersize, size_t pos)
248 {
249 	size_t totalsize;
250 	size_t posplus1 = pos + 1;
251 
252 	assert(membersize > 0);
253 	assert(a != NULL);
254 
255 	if (!posplus1 || array_UNUSABLE(a))
256 		return NULL;
257 
258 	if (!safemult_sizet(posplus1, membersize, &totalsize))
259 		return NULL;
260 
261 	if (a->allocated < totalsize)
262 		return NULL;
263 
264 	totalsize = pos * membersize;
265 	return a->mem + totalsize;
266 }
267 
268 
269 void
270 array_free(array * a)
271 {
272 	assert(a != NULL);
273 #ifdef DEBUG_ARRAY
274 	Log(LOG_DEBUG,
275 	    "array_free(): %u bytes free'd (%u bytes still used at time of free()).",
276 	    a->allocated, a->used);
277 #endif
278 	free(a->mem);
279 	a->mem = NULL;
280 	a->allocated = 0;
281 	a->used = 0;
282 }
283 
284 void
285 array_free_wipe(array *a)
286 {
287 	size_t bytes = a->allocated;
288 	if (bytes)
289 		memset(a->mem, 0, bytes);
290 	array_free(a);
291 }
292 
293 void *
294 array_start(const array * const a)
295 {
296 	assert(a != NULL);
297 	return a->mem;
298 }
299 
300 
301 void
302 array_trunc(array * a)
303 {
304 	assert(a != NULL);
305 	a->used = 0;
306 }
307 
308 
309 void
310 array_truncate(array * a, size_t membersize, size_t len)
311 {
312 	size_t newlen;
313 	assert(a != NULL);
314 	if (!safemult_sizet(membersize, len, &newlen))
315 		return;
316 
317 	if (newlen <= a->allocated)
318 		a->used = newlen;
319 }
320 
321 
322 /* move elements starting at pos to beginning of array */
323 void
324 array_moveleft(array * a, size_t membersize, size_t pos)
325 {
326 	size_t bytepos;
327 
328 	assert(a != NULL);
329 	assert(membersize > 0);
330 
331 	if (!safemult_sizet(membersize, pos, &bytepos)) {
332 		a->used = 0;
333 		return;
334 	}
335 
336 	if (!bytepos)
337 		return;	/* nothing to do */
338 
339 #ifdef DEBUG_ARRAY
340 	Log(LOG_DEBUG,
341 	    "array_moveleft(): %u bytes used in array, starting at position %u.",
342 	    a->used, bytepos);
343 #endif
344 	if (a->used <= bytepos) {
345 		a->used = 0;
346 		return;
347 	}
348 
349 	a->used -= bytepos;
350 	memmove(a->mem, a->mem + bytepos, a->used);
351 }
352 
353 /* -eof- */