Line data Source code
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 <malloc.h>
24 : #include <string.h>
25 : #include <stdio.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 : /****************************************************/
45 1052555 : static int ref_array_grow(struct ref_array *ra)
46 : {
47 1052555 : int error = EOK;
48 1052555 : 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 1052555 : newbuf = realloc(ra->storage, (ra->size + ra->grow_by) * ra->elsize);
57 1052555 : if (newbuf == NULL) {
58 : TRACE_ERROR_NUMBER("Failed to allocate memory.", ENOMEM);
59 0 : return ENOMEM;
60 : }
61 :
62 1052555 : ra->storage = newbuf;
63 1052555 : ra->size += ra->grow_by;
64 :
65 : TRACE_INFO_NUMBER("Final size: ", ra->size);
66 : TRACE_FLOW_RETURN(error);
67 1052555 : return error;
68 :
69 : }
70 :
71 :
72 : /****************************************************/
73 : /* PUBLIC FUNCTIONS */
74 : /****************************************************/
75 :
76 : /* Create referenced array */
77 300248 : 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 300248 : struct ref_array *new_ra = NULL;
84 :
85 : TRACE_FLOW_ENTRY();
86 :
87 300248 : if (!ra) {
88 : TRACE_ERROR_NUMBER("Uninitialized argument.", EINVAL);
89 0 : return EINVAL;
90 : }
91 :
92 300248 : if ((!elemsz) || (!grow_by)) {
93 : TRACE_ERROR_NUMBER("Invalid argument.", EINVAL);
94 0 : return EINVAL;
95 : }
96 :
97 300248 : new_ra = (struct ref_array *)malloc(sizeof(struct ref_array));
98 :
99 300248 : if (!new_ra) {
100 : TRACE_ERROR_NUMBER("Failed to allocate memory.", ENOMEM);
101 0 : return ENOMEM;
102 : }
103 :
104 300248 : new_ra->storage = NULL;
105 300248 : new_ra->elsize = elemsz;
106 300248 : new_ra->size = 0;
107 300248 : new_ra->grow_by = grow_by;
108 300248 : new_ra->len = 0;
109 300248 : new_ra->refcount = 1;
110 300248 : new_ra->cb = cb;
111 300248 : new_ra->cb_data = data;
112 :
113 300248 : *ra = new_ra;
114 :
115 : TRACE_FLOW_EXIT();
116 300248 : return EOK;
117 : }
118 :
119 : /* Get new reference to an array */
120 1 : struct ref_array *ref_array_getref(struct ref_array *ra)
121 : {
122 : TRACE_FLOW_ENTRY();
123 :
124 : /* Check if array is not NULL */
125 1 : if (ra) {
126 : TRACE_INFO_NUMBER("Increasing reference count. Current: ", ra->refcount);
127 : /* Increase reference count */
128 1 : 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 1 : return ra;
138 : }
139 :
140 : /* Delete the array */
141 331892 : 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 331892 : if (!ra) {
149 : TRACE_INFO_STRING("Uninitialized array.", "Might be Ok...");
150 332384 : return;
151 : }
152 :
153 : TRACE_INFO_NUMBER("Current reference count: ", ra->refcount);
154 331400 : if (ra->refcount) {
155 : /* Decrease reference count */
156 331400 : ra->refcount--;
157 331400 : if (ra->refcount == 0) {
158 : TRACE_INFO_NUMBER("It is time to delete array. Count:", ra->refcount);
159 331399 : if (ra->cb) {
160 941506 : for (idx = 0; idx < ra->len; idx++) {
161 744391 : ra->cb((unsigned char *)(ra->storage) + idx * ra->elsize,
162 : REF_ARRAY_DESTROY, ra->cb_data);
163 : }
164 : }
165 331399 : free(ra->storage);
166 331399 : 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 */
181 1794802 : int ref_array_append(struct ref_array *ra, void *element)
182 : {
183 1794802 : int error = EOK;
184 :
185 : TRACE_FLOW_ENTRY();
186 :
187 1794802 : if ((!ra) || (!element)) {
188 : TRACE_ERROR_NUMBER("Uninitialized argument.", EINVAL);
189 0 : return EINVAL;
190 : }
191 :
192 : /* Do we have enough room for a new element? */
193 1794802 : if (ra->size == ra->len) {
194 1052540 : error = ref_array_grow(ra);
195 1052540 : if (error) {
196 : TRACE_ERROR_NUMBER("Failed to grow array.", error);
197 0 : return error;
198 : }
199 : }
200 :
201 : /* Copy element */
202 1794802 : memcpy((unsigned char *)(ra->storage) + ra->len * ra->elsize,
203 : element,
204 : ra->elsize);
205 :
206 1794802 : ra->len++;
207 :
208 : TRACE_INFO_NUMBER("Length after append: ", ra->len);
209 :
210 : TRACE_FLOW_EXIT();
211 1794802 : return error;
212 : }
213 :
214 : /* Get element */
215 1593574 : void *ref_array_get(struct ref_array *ra, uint32_t idx, void *acptr)
216 : {
217 : TRACE_FLOW_ENTRY();
218 :
219 1593574 : if (!ra) {
220 : TRACE_ERROR_STRING("Uninitialized argument.", "");
221 0 : return NULL;
222 : }
223 :
224 1593574 : if (idx >= ra->len) {
225 : TRACE_INFO_NUMBER("Invalid idx.", idx);
226 67760 : return NULL;
227 : }
228 :
229 : TRACE_INFO_NUMBER("Index: ", idx);
230 :
231 1525814 : if (acptr) {
232 :
233 : TRACE_INFO_STRING("Copying data.", "");
234 2338320 : memcpy(acptr,
235 1558880 : (unsigned char *)(ra->storage) + idx * ra->elsize,
236 : ra->elsize);
237 :
238 : }
239 :
240 : TRACE_FLOW_EXIT();
241 1525814 : return (unsigned char *)(ra->storage) + idx * ra->elsize;
242 : }
243 :
244 :
245 : /* Get length */
246 31283 : int ref_array_getlen(struct ref_array *ra, uint32_t *len)
247 : {
248 : TRACE_FLOW_ENTRY();
249 :
250 31283 : if ((!ra) || (!len)) {
251 : TRACE_ERROR_STRING("Uninitialized argument.", "");
252 0 : return EINVAL;
253 : }
254 :
255 31283 : *len = ra->len;
256 :
257 : TRACE_FLOW_EXIT();
258 31283 : return EOK;
259 : }
260 :
261 : /* Alternative function to get length */
262 250649 : uint32_t ref_array_len(struct ref_array *ra)
263 : {
264 : TRACE_FLOW_ENTRY();
265 :
266 250649 : if (!ra) {
267 : TRACE_ERROR_STRING("Uninitialized argument.", "");
268 0 : errno = EINVAL;
269 0 : return 0;
270 : }
271 :
272 : TRACE_FLOW_EXIT();
273 250649 : return ra->len;
274 : }
275 :
276 :
277 : /* Insert a new element into the array */
278 18 : int ref_array_insert(struct ref_array *ra,
279 : uint32_t idx,
280 : void *element)
281 : {
282 18 : int error = EOK;
283 : uint32_t i;
284 :
285 : TRACE_FLOW_ENTRY();
286 :
287 18 : if ((!ra) || (!element)) {
288 : TRACE_ERROR_NUMBER("Uninitialized argument.", EINVAL);
289 0 : return EINVAL;
290 : }
291 :
292 18 : if (idx > ra->len) {
293 : TRACE_ERROR_NUMBER("Index is out of range", ERANGE);
294 1 : return ERANGE;
295 : }
296 :
297 : /* Do we have enough room for a new element? */
298 17 : if (ra->size == ra->len) {
299 15 : error = ref_array_grow(ra);
300 15 : if (error) {
301 : TRACE_ERROR_NUMBER("Failed to grow array.", error);
302 0 : return error;
303 : }
304 : }
305 :
306 : /* Shift elements right */
307 52 : for (i = ra->len; i >= (idx + 1); i--) {
308 105 : memcpy((unsigned char *)(ra->storage) + i * ra->elsize,
309 70 : (unsigned char *)(ra->storage) + (i - 1) * ra->elsize,
310 : ra->elsize);
311 : }
312 :
313 : /* Overwrite element */
314 17 : memcpy((unsigned char *)(ra->storage) + idx * ra->elsize,
315 : element,
316 : ra->elsize);
317 :
318 17 : ra->len++;
319 :
320 : TRACE_FLOW_EXIT();
321 17 : return error;
322 :
323 : }
324 :
325 :
326 : /* Replace element in the array */
327 150 : int ref_array_replace(struct ref_array *ra,
328 : uint32_t idx,
329 : void *element)
330 : {
331 150 : int error = EOK;
332 :
333 : TRACE_FLOW_ENTRY();
334 :
335 150 : if ((!ra) || (!element)) {
336 : TRACE_ERROR_NUMBER("Uninitialized argument.", EINVAL);
337 0 : return EINVAL;
338 : }
339 :
340 150 : if (idx > ra->len) {
341 : TRACE_ERROR_NUMBER("Index is out of range", ERANGE);
342 1 : return ERANGE;
343 : }
344 :
345 : /* Clear old element */
346 149 : if (ra->cb)
347 92 : ra->cb((unsigned char *)(ra->storage) + idx * ra->elsize,
348 : REF_ARRAY_DELETE, ra->cb_data);
349 :
350 : /* Overwrite element */
351 149 : memcpy((unsigned char *)(ra->storage) + idx * ra->elsize,
352 : element,
353 : ra->elsize);
354 :
355 :
356 : TRACE_FLOW_EXIT();
357 149 : return error;
358 : }
359 :
360 :
361 : /* Remove element from the array */
362 7 : int ref_array_remove(struct ref_array *ra,
363 : uint32_t idx)
364 : {
365 7 : int error = EOK;
366 : uint32_t i;
367 :
368 : TRACE_FLOW_ENTRY();
369 :
370 7 : if (!ra) {
371 : TRACE_ERROR_NUMBER("Uninitialized argument.", EINVAL);
372 0 : return EINVAL;
373 : }
374 :
375 7 : if (idx >= ra->len) {
376 : TRACE_ERROR_NUMBER("Index is out of range", ERANGE);
377 1 : return ERANGE;
378 : }
379 :
380 : /* Clear old element */
381 6 : if (ra->cb)
382 6 : ra->cb((unsigned char *)(ra->storage) + idx * ra->elsize,
383 : REF_ARRAY_DELETE, ra->cb_data);
384 :
385 : /* Shift elements left */
386 36 : for (i = idx + 1; i < ra->len; i++) {
387 90 : memcpy((unsigned char *)(ra->storage) + (i - 1) * ra->elsize,
388 60 : (unsigned char *)(ra->storage) + i * ra->elsize,
389 : ra->elsize);
390 : }
391 :
392 6 : ra->len--;
393 :
394 : TRACE_FLOW_EXIT();
395 6 : return error;
396 : }
397 :
398 : /* Reset array */
399 264715 : 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 264715 : if (!ra) {
407 : TRACE_ERROR_STRING("Uninitialized array.", "Coding error???");
408 264715 : return;
409 : }
410 :
411 264715 : if (ra->cb) {
412 334333 : for (idx = 0; idx < ra->len; idx++) {
413 201975 : ra->cb((unsigned char *)(ra->storage) + idx * ra->elsize,
414 : REF_ARRAY_DESTROY, ra->cb_data);
415 : }
416 : }
417 :
418 264715 : free(ra->storage);
419 264715 : ra->storage = NULL;
420 264715 : ra->size = 0;
421 264715 : ra->len = 0;
422 :
423 : TRACE_FLOW_EXIT();
424 : }
425 :
426 : /* Swap two elements in the array */
427 7 : int ref_array_swap(struct ref_array *ra,
428 : uint32_t idx1,
429 : uint32_t idx2)
430 : {
431 7 : int error = EOK;
432 7 : void *temp = NULL;
433 :
434 : TRACE_FLOW_ENTRY();
435 :
436 7 : if (!ra) {
437 : TRACE_ERROR_NUMBER("Uninitialized argument.", EINVAL);
438 0 : return EINVAL;
439 : }
440 :
441 14 : if ((idx1 >= ra->len) ||
442 7 : (idx2 >= ra->len)) {
443 : TRACE_ERROR_NUMBER("Index is out of range", ERANGE);
444 0 : return ERANGE;
445 : }
446 :
447 7 : if (idx1 == idx2) {
448 : TRACE_FLOW_STRING("ref_array_swap", "Noop return");
449 0 : return EOK;
450 : }
451 :
452 7 : temp = malloc(ra->elsize);
453 7 : if (!temp) {
454 : TRACE_FLOW_STRING("Failed to allocate memory for temp storage.", "");
455 0 : return ENOMEM;
456 : }
457 :
458 21 : memcpy(temp,
459 14 : (unsigned char *)(ra->storage) + idx2 * ra->elsize,
460 : ra->elsize);
461 21 : memcpy((unsigned char *)(ra->storage) + idx2 * ra->elsize,
462 14 : (unsigned char *)(ra->storage) + idx1 * ra->elsize,
463 : ra->elsize);
464 7 : memcpy((unsigned char *)(ra->storage) + idx1 * ra->elsize,
465 : temp,
466 : ra->elsize);
467 :
468 7 : free(temp);
469 :
470 : TRACE_FLOW_EXIT();
471 7 : return error;
472 : }
473 :
474 : /* Copy array */
475 31151 : 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 31151 : int error = EOK;
482 : int idx;
483 31151 : 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 31151 : if ((!ra) || (!copy_ra)) {
491 : TRACE_ERROR_NUMBER("Invalid argument.", EINVAL);
492 0 : return EINVAL;
493 : }
494 :
495 31151 : new_ra = (struct ref_array *)malloc(sizeof(struct ref_array));
496 31151 : if (!new_ra) {
497 : TRACE_ERROR_NUMBER("Failed to allocate memory.", ENOMEM);
498 0 : return ENOMEM;
499 : }
500 :
501 31151 : new_ra->storage = calloc(ra->size, ra->elsize);
502 31151 : if (!(new_ra->storage)) {
503 : TRACE_ERROR_NUMBER("Failed to allocate memory.", ENOMEM);
504 0 : free(new_ra);
505 0 : return ENOMEM;
506 : }
507 :
508 31151 : new_ra->elsize = ra->elsize;
509 31151 : new_ra->size = ra->size;
510 31151 : new_ra->grow_by = ra->grow_by;
511 31151 : new_ra->len = 0;
512 31151 : new_ra->refcount = 1;
513 31151 : new_ra->cb = cb;
514 31151 : new_ra->cb_data = data;
515 :
516 63480 : for (idx = 0; idx < ra->len; idx++) {
517 32329 : if (copy_cb) {
518 32324 : src = (void *)((unsigned char *)(ra->storage) + idx * ra->elsize);
519 64648 : dst = (void *)((unsigned char *)(new_ra->storage) +
520 32324 : idx * new_ra->elsize);
521 :
522 32324 : error = copy_cb(src, (void *)(dst));
523 32324 : if (error) {
524 : TRACE_ERROR_NUMBER("Failed to copy data.", error);
525 0 : ref_array_destroy(new_ra);
526 0 : return error;
527 : }
528 : }
529 : else {
530 15 : memcpy((unsigned char *)(new_ra->storage) + idx * new_ra->elsize,
531 10 : (unsigned char *)(ra->storage) + idx * ra->elsize,
532 : new_ra->elsize);
533 : }
534 32329 : (new_ra->len)++;
535 : }
536 :
537 :
538 31151 : *copy_ra = new_ra;
539 :
540 : TRACE_FLOW_EXIT();
541 31151 : return error;
542 : }
543 :
544 :
545 :
546 : /* Debug function */
547 0 : void ref_array_debug(struct ref_array *ra, int num)
548 : {
549 : int i,j;
550 :
551 0 : printf("\nARRAY DUMP START\n");
552 0 : printf("Length = %u\n", ra->len);
553 0 : printf("Size = %u\n", ra->size);
554 0 : printf("Element = %u\n", (unsigned int)(ra->elsize));
555 0 : printf("Grow by = %u\n", ra->grow_by);
556 0 : printf("Count = %u\n", ra->refcount);
557 0 : printf("ARRAY:\n");
558 0 : for (i = 0; i < ra->len; i++) {
559 0 : for (j = 0; j < ra->elsize; j++) {
560 0 : printf("%02x", *((unsigned char *)(ra->storage) + i * ra->elsize + j));
561 : }
562 0 : if (num == 0) {
563 0 : printf("\n%s\n", *((char **)((unsigned char *)(ra->storage) + i * ra->elsize)));
564 : }
565 0 : else if (num > 0) {
566 0 : printf("\n%d\n", *((uint32_t *)((unsigned char *)(ra->storage) + i * ra->elsize)));
567 : }
568 : else {
569 0 : printf("\nIt is an object.\n");
570 : }
571 : }
572 0 : printf("\nARRAY DUMP END\n\n");
573 0 : }
|
