1 /*
2 REF ARRAY
3
4 Implementation of the dynamic array with reference count.
5
6 Copyright (C) Dmitri Pal <dpal@redhat.com> 2009
7
8 This program is free software; you can redistribute it and/or modify
9 it under the terms of the GNU Lesser General Public License as published by
10 the Free Software Foundation; either version 3 of the License, or
11 (at your option) any later version.
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16 You should have received a copy of the GNU Lesser General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>.
18 */
19
20 #include "config.h"
21 #include <errno.h> /* for errors */
22 #include <stdint.h>
23 #include <string.h>
24 #include <stdio.h>
25 #include <stdlib.h>
26
27 #include "ref_array.h"
28 #include "trace.h"
29
30 /* The structure used in referenced array */
31 struct ref_array {
32 void *storage; /* The storage buffer */
33 size_t elsize; /* Size of one element in the buffer */
34 uint32_t size; /* Size of the storage in items */
35 uint32_t grow_by; /* What increment use to reallocate memory */
36 uint32_t len; /* Number of the elements in the array */
37 uint32_t refcount; /* Reference count */
38 ref_array_fn cb; /* Cleanup callback */
39 void *cb_data; /* Caller's callback data */
40 };
41
42 /****************************************************/
43 /* INTERNAL FUNCTIONS */
44 /****************************************************/
ref_array_grow(struct ref_array * ra)45 static int ref_array_grow(struct ref_array *ra)
46 {
47 int error = EOK;
48 void *newbuf = NULL;
49
50 TRACE_FLOW_ENTRY();
51
52 TRACE_INFO_NUMBER("Current length: ", ra->len);
53 TRACE_INFO_NUMBER("Current size: ", ra->size);
54
55 /* Grow buffer if needed */
56 newbuf = realloc(ra->storage, (ra->size + ra->grow_by) * ra->elsize);
57 if (newbuf == NULL) {
58 TRACE_ERROR_NUMBER("Failed to allocate memory.", ENOMEM);
59 return ENOMEM;
60 }
61
62 ra->storage = newbuf;
63 ra->size += ra->grow_by;
64
65 TRACE_INFO_NUMBER("Final size: ", ra->size);
66 TRACE_FLOW_RETURN(error);
67 return error;
68
69 }
70
71
72 /****************************************************/
73 /* PUBLIC FUNCTIONS */
74 /****************************************************/
75
76 /* Create referenced array */
ref_array_create(struct ref_array ** ra,size_t elemsz,uint32_t grow_by,ref_array_fn cb,void * data)77 int ref_array_create(struct ref_array **ra,
78 size_t elemsz,
79 uint32_t grow_by,
80 ref_array_fn cb,
81 void *data)
82 {
83 struct ref_array *new_ra = NULL;
84
85 TRACE_FLOW_ENTRY();
86
87 if (!ra) {
88 TRACE_ERROR_NUMBER("Uninitialized argument.", EINVAL);
89 return EINVAL;
90 }
91
92 if ((!elemsz) || (!grow_by)) {
93 TRACE_ERROR_NUMBER("Invalid argument.", EINVAL);
94 return EINVAL;
95 }
96
97 new_ra = (struct ref_array *)malloc(sizeof(struct ref_array));
98
99 if (!new_ra) {
100 TRACE_ERROR_NUMBER("Failed to allocate memory.", ENOMEM);
101 return ENOMEM;
102 }
103
104 new_ra->storage = NULL;
105 new_ra->elsize = elemsz;
106 new_ra->size = 0;
107 new_ra->grow_by = grow_by;
108 new_ra->len = 0;
109 new_ra->refcount = 1;
110 new_ra->cb = cb;
111 new_ra->cb_data = data;
112
113 *ra = new_ra;
114
115 TRACE_FLOW_EXIT();
116 return EOK;
117 }
118
119 /* Get new reference to an array */
ref_array_getref(struct ref_array * ra)120 struct ref_array *ref_array_getref(struct ref_array *ra)
121 {
122 TRACE_FLOW_ENTRY();
123
124 /* Check if array is not NULL */
125 if (ra) {
126 TRACE_INFO_NUMBER("Increasing reference count. Current: ", ra->refcount);
127 /* Increase reference count */
128 ra->refcount++;
129 TRACE_INFO_NUMBER("Increased reference count. New: ", ra->refcount);
130
131 }
132 else {
133 TRACE_ERROR_STRING("Uninitialized array.", "Returning NULL");
134 }
135
136 TRACE_FLOW_EXIT();
137 return ra;
138 }
139
140 /* Delete the array */
ref_array_destroy(struct ref_array * ra)141 void ref_array_destroy(struct ref_array *ra)
142 {
143 int idx;
144
145 TRACE_FLOW_ENTRY();
146
147 /* Check if array is not NULL */
148 if (!ra) {
149 TRACE_INFO_STRING("Uninitialized array.", "Might be Ok...");
150 return;
151 }
152
153 TRACE_INFO_NUMBER("Current reference count: ", ra->refcount);
154 if (ra->refcount) {
155 /* Decrease reference count */
156 ra->refcount--;
157 if (ra->refcount == 0) {
158 TRACE_INFO_NUMBER("It is time to delete array. Count:", ra->refcount);
159 if (ra->cb) {
160 for (idx = 0; idx < ra->len; idx++) {
161 ra->cb((unsigned char *)(ra->storage) + idx * ra->elsize,
162 REF_ARRAY_DESTROY, ra->cb_data);
163 }
164 }
165 free(ra->storage);
166 free(ra);
167 }
168 }
169 else {
170 /* Should never be here...
171 * This can happen if the caller by mistake would try to
172 * destroy the object from within the callback. Brrr....
173 */
174 TRACE_ERROR_STRING("Reference count is 0.", "Coding error???");
175 }
176
177 TRACE_FLOW_EXIT();
178 }
179
180 /* Add new element to the array */
ref_array_append(struct ref_array * ra,void * element)181 int ref_array_append(struct ref_array *ra, void *element)
182 {
183 int error = EOK;
184
185 TRACE_FLOW_ENTRY();
186
187 if ((!ra) || (!element)) {
188 TRACE_ERROR_NUMBER("Uninitialized argument.", EINVAL);
189 return EINVAL;
190 }
191
192 /* Do we have enough room for a new element? */
193 if (ra->size == ra->len) {
194 error = ref_array_grow(ra);
195 if (error) {
196 TRACE_ERROR_NUMBER("Failed to grow array.", error);
197 return error;
198 }
199 }
200
201 /* Copy element */
202 memcpy((unsigned char *)(ra->storage) + ra->len * ra->elsize,
203 element,
204 ra->elsize);
205
206 ra->len++;
207
208 TRACE_INFO_NUMBER("Length after append: ", ra->len);
209
210 TRACE_FLOW_EXIT();
211 return error;
212 }
213
214 /* Get element */
ref_array_get(struct ref_array * ra,uint32_t idx,void * acptr)215 void *ref_array_get(struct ref_array *ra, uint32_t idx, void *acptr)
216 {
217 TRACE_FLOW_ENTRY();
218
219 if (!ra) {
220 TRACE_ERROR_STRING("Uninitialized argument.", "");
221 return NULL;
222 }
223
224 if (idx >= ra->len) {
225 TRACE_INFO_NUMBER("Invalid idx.", idx);
226 return NULL;
227 }
228
229 TRACE_INFO_NUMBER("Index: ", idx);
230
231 if (acptr) {
232
233 TRACE_INFO_STRING("Copying data.", "");
234 memcpy(acptr,
235 (unsigned char *)(ra->storage) + idx * ra->elsize,
236 ra->elsize);
237
238 }
239
240 TRACE_FLOW_EXIT();
241 return (unsigned char *)(ra->storage) + idx * ra->elsize;
242 }
243
244
245 /* Get length */
ref_array_getlen(struct ref_array * ra,uint32_t * len)246 int ref_array_getlen(struct ref_array *ra, uint32_t *len)
247 {
248 TRACE_FLOW_ENTRY();
249
250 if ((!ra) || (!len)) {
251 TRACE_ERROR_STRING("Uninitialized argument.", "");
252 return EINVAL;
253 }
254
255 *len = ra->len;
256
257 TRACE_FLOW_EXIT();
258 return EOK;
259 }
260
261 /* Alternative function to get length */
ref_array_len(struct ref_array * ra)262 uint32_t ref_array_len(struct ref_array *ra)
263 {
264 TRACE_FLOW_ENTRY();
265
266 if (!ra) {
267 TRACE_ERROR_STRING("Uninitialized argument.", "");
268 errno = EINVAL;
269 return 0;
270 }
271
272 TRACE_FLOW_EXIT();
273 return ra->len;
274 }
275
276
277 /* Insert a new element into the array */
ref_array_insert(struct ref_array * ra,uint32_t idx,void * element)278 int ref_array_insert(struct ref_array *ra,
279 uint32_t idx,
280 void *element)
281 {
282 int error = EOK;
283 uint32_t i;
284
285 TRACE_FLOW_ENTRY();
286
287 if ((!ra) || (!element)) {
288 TRACE_ERROR_NUMBER("Uninitialized argument.", EINVAL);
289 return EINVAL;
290 }
291
292 if (idx > ra->len) {
293 TRACE_ERROR_NUMBER("Index is out of range", ERANGE);
294 return ERANGE;
295 }
296
297 /* Do we have enough room for a new element? */
298 if (ra->size == ra->len) {
299 error = ref_array_grow(ra);
300 if (error) {
301 TRACE_ERROR_NUMBER("Failed to grow array.", error);
302 return error;
303 }
304 }
305
306 /* Shift elements right */
307 for (i = ra->len; i >= (idx + 1); i--) {
308 memcpy((unsigned char *)(ra->storage) + i * ra->elsize,
309 (unsigned char *)(ra->storage) + (i - 1) * ra->elsize,
310 ra->elsize);
311 }
312
313 /* Overwrite element */
314 memcpy((unsigned char *)(ra->storage) + idx * ra->elsize,
315 element,
316 ra->elsize);
317
318 ra->len++;
319
320 TRACE_FLOW_EXIT();
321 return error;
322
323 }
324
325
326 /* Replace element in the array */
ref_array_replace(struct ref_array * ra,uint32_t idx,void * element)327 int ref_array_replace(struct ref_array *ra,
328 uint32_t idx,
329 void *element)
330 {
331 int error = EOK;
332
333 TRACE_FLOW_ENTRY();
334
335 if ((!ra) || (!element)) {
336 TRACE_ERROR_NUMBER("Uninitialized argument.", EINVAL);
337 return EINVAL;
338 }
339
340 if (idx > ra->len) {
341 TRACE_ERROR_NUMBER("Index is out of range", ERANGE);
342 return ERANGE;
343 }
344
345 /* Clear old element */
346 if (ra->cb)
347 ra->cb((unsigned char *)(ra->storage) + idx * ra->elsize,
348 REF_ARRAY_DELETE, ra->cb_data);
349
350 /* Overwrite element */
351 memcpy((unsigned char *)(ra->storage) + idx * ra->elsize,
352 element,
353 ra->elsize);
354
355
356 TRACE_FLOW_EXIT();
357 return error;
358 }
359
360
361 /* Remove element from the array */
ref_array_remove(struct ref_array * ra,uint32_t idx)362 int ref_array_remove(struct ref_array *ra,
363 uint32_t idx)
364 {
365 int error = EOK;
366 uint32_t i;
367
368 TRACE_FLOW_ENTRY();
369
370 if (!ra) {
371 TRACE_ERROR_NUMBER("Uninitialized argument.", EINVAL);
372 return EINVAL;
373 }
374
375 if (idx >= ra->len) {
376 TRACE_ERROR_NUMBER("Index is out of range", ERANGE);
377 return ERANGE;
378 }
379
380 /* Clear old element */
381 if (ra->cb)
382 ra->cb((unsigned char *)(ra->storage) + idx * ra->elsize,
383 REF_ARRAY_DELETE, ra->cb_data);
384
385 /* Shift elements left */
386 for (i = idx + 1; i < ra->len; i++) {
387 memcpy((unsigned char *)(ra->storage) + (i - 1) * ra->elsize,
388 (unsigned char *)(ra->storage) + i * ra->elsize,
389 ra->elsize);
390 }
391
392 ra->len--;
393
394 TRACE_FLOW_EXIT();
395 return error;
396 }
397
398 /* Reset array */
ref_array_reset(struct ref_array * ra)399 void ref_array_reset(struct ref_array *ra)
400 {
401 int idx;
402
403 TRACE_FLOW_ENTRY();
404
405 /* Check if array is not NULL */
406 if (!ra) {
407 TRACE_ERROR_STRING("Uninitialized array.", "Coding error???");
408 return;
409 }
410
411 if (ra->cb) {
412 for (idx = 0; idx < ra->len; idx++) {
413 ra->cb((unsigned char *)(ra->storage) + idx * ra->elsize,
414 REF_ARRAY_DESTROY, ra->cb_data);
415 }
416 }
417
418 free(ra->storage);
419 ra->storage = NULL;
420 ra->size = 0;
421 ra->len = 0;
422
423 TRACE_FLOW_EXIT();
424 }
425
426 /* Swap two elements in the array */
ref_array_swap(struct ref_array * ra,uint32_t idx1,uint32_t idx2)427 int ref_array_swap(struct ref_array *ra,
428 uint32_t idx1,
429 uint32_t idx2)
430 {
431 int error = EOK;
432 void *temp = NULL;
433
434 TRACE_FLOW_ENTRY();
435
436 if (!ra) {
437 TRACE_ERROR_NUMBER("Uninitialized argument.", EINVAL);
438 return EINVAL;
439 }
440
441 if ((idx1 >= ra->len) ||
442 (idx2 >= ra->len)) {
443 TRACE_ERROR_NUMBER("Index is out of range", ERANGE);
444 return ERANGE;
445 }
446
447 if (idx1 == idx2) {
448 TRACE_FLOW_STRING("ref_array_swap", "Noop return");
449 return EOK;
450 }
451
452 temp = malloc(ra->elsize);
453 if (!temp) {
454 TRACE_FLOW_STRING("Failed to allocate memory for temp storage.", "");
455 return ENOMEM;
456 }
457
458 memcpy(temp,
459 (unsigned char *)(ra->storage) + idx2 * ra->elsize,
460 ra->elsize);
461 memcpy((unsigned char *)(ra->storage) + idx2 * ra->elsize,
462 (unsigned char *)(ra->storage) + idx1 * ra->elsize,
463 ra->elsize);
464 memcpy((unsigned char *)(ra->storage) + idx1 * ra->elsize,
465 temp,
466 ra->elsize);
467
468 free(temp);
469
470 TRACE_FLOW_EXIT();
471 return error;
472 }
473
474 /* Copy array */
ref_array_copy(struct ref_array * ra,ref_array_copy_cb copy_cb,ref_array_fn cb,void * data,struct ref_array ** copy_ra)475 int ref_array_copy(struct ref_array *ra,
476 ref_array_copy_cb copy_cb,
477 ref_array_fn cb,
478 void *data,
479 struct ref_array **copy_ra)
480 {
481 int error = EOK;
482 int idx;
483 struct ref_array *new_ra = NULL;
484 void *src;
485 void *dst;
486
487 TRACE_FLOW_ENTRY();
488
489 /* Check if array is not NULL */
490 if ((!ra) || (!copy_ra)) {
491 TRACE_ERROR_NUMBER("Invalid argument.", EINVAL);
492 return EINVAL;
493 }
494
495 new_ra = (struct ref_array *)malloc(sizeof(struct ref_array));
496 if (!new_ra) {
497 TRACE_ERROR_NUMBER("Failed to allocate memory.", ENOMEM);
498 return ENOMEM;
499 }
500
501 new_ra->storage = calloc(ra->size, ra->elsize);
502 if (!(new_ra->storage)) {
503 TRACE_ERROR_NUMBER("Failed to allocate memory.", ENOMEM);
504 free(new_ra);
505 return ENOMEM;
506 }
507
508 new_ra->elsize = ra->elsize;
509 new_ra->size = ra->size;
510 new_ra->grow_by = ra->grow_by;
511 new_ra->len = 0;
512 new_ra->refcount = 1;
513 new_ra->cb = cb;
514 new_ra->cb_data = data;
515
516 for (idx = 0; idx < ra->len; idx++) {
517 if (copy_cb) {
518 src = (void *)((unsigned char *)(ra->storage) + idx * ra->elsize);
519 dst = (void *)((unsigned char *)(new_ra->storage) +
520 idx * new_ra->elsize);
521
522 error = copy_cb(src, (void *)(dst));
523 if (error) {
524 TRACE_ERROR_NUMBER("Failed to copy data.", error);
525 ref_array_destroy(new_ra);
526 return error;
527 }
528 }
529 else {
530 memcpy((unsigned char *)(new_ra->storage) + idx * new_ra->elsize,
531 (unsigned char *)(ra->storage) + idx * ra->elsize,
532 new_ra->elsize);
533 }
534 (new_ra->len)++;
535 }
536
537
538 *copy_ra = new_ra;
539
540 TRACE_FLOW_EXIT();
541 return error;
542 }
543
544
545
546 /* Debug function */
ref_array_debug(struct ref_array * ra,int num)547 void ref_array_debug(struct ref_array *ra, int num)
548 {
549 int i,j;
550
551 if (!ra) {
552 printf("\nARRAY is NULL\n");
553 return;
554 }
555
556 printf("\nARRAY DUMP START\n");
557 printf("Length = %u\n", ra->len);
558 printf("Size = %u\n", ra->size);
559 printf("Element = %u\n", (unsigned int)(ra->elsize));
560 printf("Grow by = %u\n", ra->grow_by);
561 printf("Count = %u\n", ra->refcount);
562 printf("ARRAY:\n");
563 for (i = 0; i < ra->len; i++) {
564 for (j = 0; j < ra->elsize; j++) {
565 printf("%02x", *((unsigned char *)(ra->storage) + i * ra->elsize + j));
566 }
567 if (num == 0) {
568 printf("\n%s\n", *((char **)((unsigned char *)(ra->storage) + i * ra->elsize)));
569 }
570 else if (num > 0) {
571 printf("\n%d\n", *((uint32_t *)((unsigned char *)(ra->storage) + i * ra->elsize)));
572 }
573 else {
574 printf("\nIt is an object.\n");
575 }
576 }
577 printf("\nARRAY DUMP END\n\n");
578 }
579