1 /*
2 * shl - Dynamic Array
3 *
4 * Copyright (c) 2011-2013 David Herrmann <dh.herrmann@gmail.com>
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining
7 * a copy of this software and associated documentation files
8 * (the "Software"), to deal in the Software without restriction, including
9 * without limitation the rights to use, copy, modify, merge, publish,
10 * distribute, sublicense, and/or sell copies of the Software, and to
11 * permit persons to whom the Software is furnished to do so, subject to
12 * the following conditions:
13 *
14 * The above copyright notice and this permission notice shall be included
15 * in all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
18 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
19 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
20 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
21 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
22 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
23 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
24 */
25
26 /*
27 * A dynamic array implementation
28 */
29
30 #ifndef SHL_ARRAY_H
31 #define SHL_ARRAY_H
32
33 #include <stdbool.h>
34 #include <stdint.h>
35 #include <stdlib.h>
36
37 struct shl_array {
38 size_t element_size;
39 size_t length;
40 size_t size;
41 void *data;
42 };
43
44 #define SHL_ARRAY_AT(_arr, _type, _pos) \
45 (&((_type*)shl_array_get_array(_arr))[(_pos)])
46
shl_array_new(struct shl_array ** out,size_t element_size,size_t initial_size)47 static inline int shl_array_new(struct shl_array **out, size_t element_size,
48 size_t initial_size)
49 {
50 struct shl_array *arr;
51
52 if (!out || !element_size)
53 return -EINVAL;
54
55 if (!initial_size)
56 initial_size = 4;
57
58 arr = malloc(sizeof(*arr));
59 if (!arr)
60 return -ENOMEM;
61 memset(arr, 0, sizeof(*arr));
62 arr->element_size = element_size;
63 arr->length = 0;
64 arr->size = initial_size;
65
66 arr->data = malloc(arr->element_size * arr->size);
67 if (!arr->data) {
68 free(arr);
69 return -ENOMEM;
70 }
71
72 *out = arr;
73 return 0;
74 }
75
shl_array_free(struct shl_array * arr)76 static inline void shl_array_free(struct shl_array *arr)
77 {
78 if (!arr)
79 return;
80
81 free(arr->data);
82 free(arr);
83 }
84
85 /* Compute next higher power-of-2 of @v. Returns 4 in case v is 0. */
shl_array_pow2(size_t v)86 static inline size_t shl_array_pow2(size_t v)
87 {
88 size_t i;
89
90 if (!v)
91 return 4;
92
93 --v;
94
95 for (i = 1; i < 8 * sizeof(size_t); i *= 2)
96 v |= v >> i;
97
98 return ++v;
99 }
100
101 /* resize to length=size and zero out new array entries */
shl_array_zresize(struct shl_array * arr,size_t size)102 static inline int shl_array_zresize(struct shl_array *arr, size_t size)
103 {
104 void *tmp;
105 size_t newsize;
106
107 if (!arr)
108 return -EINVAL;
109
110 if (size > arr->size) {
111 newsize = shl_array_pow2(size);
112 tmp = realloc(arr->data, arr->element_size * newsize);
113 if (!tmp)
114 return -ENOMEM;
115
116 arr->data = tmp;
117 arr->size = newsize;
118
119 memset(((uint8_t*)arr->data) + arr->element_size * arr->length,
120 0, arr->element_size * (size - arr->length));
121 }
122
123 arr->length = size;
124 return 0;
125 }
126
shl_array_push(struct shl_array * arr,const void * data)127 static inline int shl_array_push(struct shl_array *arr, const void *data)
128 {
129 void *tmp;
130 size_t newsize;
131
132 if (!arr || !data)
133 return -EINVAL;
134
135 if (arr->length >= arr->size) {
136 newsize = arr->size * 2;
137 tmp = realloc(arr->data, arr->element_size * newsize);
138 if (!tmp)
139 return -ENOMEM;
140
141 arr->data = tmp;
142 arr->size = newsize;
143 }
144
145 memcpy(((uint8_t*)arr->data) + arr->element_size * arr->length,
146 data, arr->element_size);
147 ++arr->length;
148
149 return 0;
150 }
151
shl_array_pop(struct shl_array * arr)152 static inline void shl_array_pop(struct shl_array *arr)
153 {
154 if (!arr || !arr->length)
155 return;
156
157 --arr->length;
158 }
159
shl_array_get_array(struct shl_array * arr)160 static inline void *shl_array_get_array(struct shl_array *arr)
161 {
162 if (!arr)
163 return NULL;
164
165 return arr->data;
166 }
167
shl_array_get_length(struct shl_array * arr)168 static inline size_t shl_array_get_length(struct shl_array *arr)
169 {
170 if (!arr)
171 return 0;
172
173 return arr->length;
174 }
175
shl_array_get_bsize(struct shl_array * arr)176 static inline size_t shl_array_get_bsize(struct shl_array *arr)
177 {
178 if (!arr)
179 return 0;
180
181 return arr->length * arr->element_size;
182 }
183
shl_array_get_element_size(struct shl_array * arr)184 static inline size_t shl_array_get_element_size(struct shl_array *arr)
185 {
186 if (!arr)
187 return 0;
188
189 return arr->element_size;
190 }
191
192 #endif /* SHL_ARRAY_H */
193