1 /**************************************************************************
2 *
3 * Copyright 2010 Luca Barbieri
4 *
5 * Permission is hereby granted, free of charge, to any person obtaining
6 * a copy of this software and associated documentation files (the
7 * "Software"), to deal in the Software without restriction, including
8 * without limitation the rights to use, copy, modify, merge, publish,
9 * distribute, sublicense, and/or sell copies of the Software, and to
10 * permit persons to whom the Software is furnished to do so, subject to
11 * the following conditions:
12 *
13 * The above copyright notice and this permission notice (including the
14 * next paragraph) shall be included in all copies or substantial
15 * portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18 * EXPRESS 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 COPYRIGHT OWNER(S) AND/OR ITS SUPPLIERS BE
21 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
22 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
23 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
24 *
25 **************************************************************************/
26
27 #ifndef U_DYNARRAY_H
28 #define U_DYNARRAY_H
29
30 #include <stdlib.h>
31 #include <string.h>
32 #include "ralloc.h"
33
34 #ifdef __cplusplus
35 extern "C" {
36 #endif
37
38 /* A zero-initialized version of this is guaranteed to represent an
39 * empty array.
40 *
41 * Also, size <= capacity and data != 0 if and only if capacity != 0
42 * capacity will always be the allocation size of data
43 */
44 struct util_dynarray
45 {
46 void *mem_ctx;
47 void *data;
48 unsigned size;
49 unsigned capacity;
50 };
51
52 static inline void
util_dynarray_init(struct util_dynarray * buf,void * mem_ctx)53 util_dynarray_init(struct util_dynarray *buf, void *mem_ctx)
54 {
55 memset(buf, 0, sizeof(*buf));
56 buf->mem_ctx = mem_ctx;
57 }
58
59 static inline void
util_dynarray_fini(struct util_dynarray * buf)60 util_dynarray_fini(struct util_dynarray *buf)
61 {
62 if (buf->data) {
63 if (buf->mem_ctx) {
64 ralloc_free(buf->data);
65 } else {
66 free(buf->data);
67 }
68 util_dynarray_init(buf, buf->mem_ctx);
69 }
70 }
71
72 static inline void
util_dynarray_clear(struct util_dynarray * buf)73 util_dynarray_clear(struct util_dynarray *buf)
74 {
75 buf->size = 0;
76 }
77
78 #define DYN_ARRAY_INITIAL_SIZE 64
79
80 /* use util_dynarray_trim to reduce the allocated storage */
81 static inline void *
util_dynarray_resize(struct util_dynarray * buf,unsigned newsize)82 util_dynarray_resize(struct util_dynarray *buf, unsigned newsize)
83 {
84 void *p;
85 if (newsize > buf->capacity) {
86 if (buf->capacity == 0)
87 buf->capacity = DYN_ARRAY_INITIAL_SIZE;
88
89 while (newsize > buf->capacity)
90 buf->capacity *= 2;
91
92 if (buf->mem_ctx) {
93 buf->data = reralloc_size(buf->mem_ctx, buf->data, buf->capacity);
94 } else {
95 buf->data = realloc(buf->data, buf->capacity);
96 }
97 }
98
99 p = (void *)((char *)buf->data + buf->size);
100 buf->size = newsize;
101
102 return p;
103 }
104
105 static inline void *
util_dynarray_grow(struct util_dynarray * buf,int diff)106 util_dynarray_grow(struct util_dynarray *buf, int diff)
107 {
108 return util_dynarray_resize(buf, buf->size + diff);
109 }
110
111 static inline void
util_dynarray_trim(struct util_dynarray * buf)112 util_dynarray_trim(struct util_dynarray *buf)
113 {
114 if (buf->size != buf->capacity) {
115 if (buf->size) {
116 if (buf->mem_ctx) {
117 buf->data = reralloc_size(buf->mem_ctx, buf->data, buf->size);
118 } else {
119 buf->data = realloc(buf->data, buf->size);
120 }
121 buf->capacity = buf->size;
122 } else {
123 if (buf->mem_ctx) {
124 ralloc_free(buf->data);
125 } else {
126 free(buf->data);
127 }
128 buf->data = 0;
129 buf->capacity = 0;
130 }
131 }
132 }
133
134 #define util_dynarray_append(buf, type, v) do {type __v = (v); memcpy(util_dynarray_grow((buf), sizeof(type)), &__v, sizeof(type));} while(0)
135 #define util_dynarray_top_ptr(buf, type) (type*)((char*)(buf)->data + (buf)->size - sizeof(type))
136 #define util_dynarray_top(buf, type) *util_dynarray_top_ptr(buf, type)
137 #define util_dynarray_pop_ptr(buf, type) (type*)((char*)(buf)->data + ((buf)->size -= sizeof(type)))
138 #define util_dynarray_pop(buf, type) *util_dynarray_pop_ptr(buf, type)
139 #define util_dynarray_contains(buf, type) ((buf)->size >= sizeof(type))
140 #define util_dynarray_element(buf, type, idx) ((type*)(buf)->data + (idx))
141 #define util_dynarray_begin(buf) ((buf)->data)
142 #define util_dynarray_end(buf) ((void*)util_dynarray_element((buf), char, (buf)->size))
143
144 #define util_dynarray_foreach(buf, type, elem) \
145 for (type *elem = (type *)(buf)->data; \
146 elem < (type *)((char *)(buf)->data + (buf)->size); elem++)
147
148 #define util_dynarray_delete_unordered(buf, type, v) \
149 do { \
150 unsigned num_elements = (buf)->size / sizeof(type); \
151 unsigned i; \
152 for (i = 0; i < num_elements; i++) { \
153 type __v = *util_dynarray_element((buf), type, (i)); \
154 if (v == __v) { \
155 memcpy(util_dynarray_element((buf), type, (i)), \
156 util_dynarray_pop_ptr((buf), type), sizeof(type)); \
157 break; \
158 } \
159 } \
160 } while (0)
161
162 #ifdef __cplusplus
163 }
164 #endif
165
166 #endif /* U_DYNARRAY_H */
167
168