1 /****************************************************************************
2 * bfs *
3 * Copyright (C) 2019-2022 Tavian Barnes <tavianator@tavianator.com> *
4 * *
5 * Permission to use, copy, modify, and/or distribute this software for any *
6 * purpose with or without fee is hereby granted. *
7 * *
8 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES *
9 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF *
10 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR *
11 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES *
12 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN *
13 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF *
14 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. *
15 ****************************************************************************/
16
17 #include "darray.h"
18 #include <assert.h>
19 #include <stdlib.h>
20 #include <string.h>
21
22 /**
23 * The darray header.
24 */
25 struct darray {
26 /** The current capacity of the array, as a count of elements. */
27 size_t capacity;
28 /** The current length of the array. */
29 size_t length;
30
31 // The array elements are stored after this header in memory. Not using
32 // a flexible array member to avoid worrying about strict aliasing. We
33 // assume that 2*sizeof(size_t) keeps any memory allocation suitably
34 // aligned for the element type.
35 };
36
37 /** Get the header for a darray. */
darray_header(const void * da)38 static struct darray *darray_header(const void *da) {
39 return (struct darray *)da - 1;
40 }
41
42 /** Get the array from a darray header. */
darray_data(struct darray * header)43 static char *darray_data(struct darray *header) {
44 return (char *)(header + 1);
45 }
46
darray_length(const void * da)47 size_t darray_length(const void *da) {
48 if (da) {
49 return darray_header(da)->length;
50 } else {
51 return 0;
52 }
53 }
54
darray_push(void * da,const void * item,size_t size)55 void *darray_push(void *da, const void *item, size_t size) {
56 struct darray *header;
57 if (da) {
58 header = darray_header(da);
59 } else {
60 header = malloc(sizeof(*header) + size);
61 if (!header) {
62 return NULL;
63 }
64 header->capacity = 1;
65 header->length = 0;
66 }
67
68 size_t capacity = header->capacity;
69 size_t i = header->length++;
70 if (i >= capacity) {
71 capacity *= 2;
72 header = realloc(header, sizeof(*header) + capacity*size);
73 if (!header) {
74 // This failure will be detected by darray_check()
75 return da;
76 }
77 header->capacity = capacity;
78 }
79
80 char *data = darray_data(header);
81 memcpy(data + i*size, item, size);
82 return data;
83 }
84
darray_check(void * da)85 int darray_check(void *da) {
86 if (!da) {
87 return -1;
88 }
89
90 struct darray *header = darray_header(da);
91 if (header->length <= header->capacity) {
92 return 0;
93 } else {
94 // realloc() failed in darray_push(), so reset the length and report the failure
95 header->length = header->capacity;
96 return -1;
97 }
98 }
99
darray_pop(void * da)100 size_t darray_pop(void *da) {
101 assert(da);
102
103 struct darray *header = darray_header(da);
104 assert(header->length > 0);
105 return --header->length;
106 }
107
darray_free(void * da)108 void darray_free(void *da) {
109 if (da) {
110 free(darray_header(da));
111 }
112 }
113