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
35extern "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 */
44struct util_dynarray
45{
46   void *mem_ctx;
47   void *data;
48   unsigned size;
49   unsigned capacity;
50};
51
52static inline void
53util_dynarray_init(struct util_dynarray *buf, void *mem_ctx)
54{
55   memset(buf, 0, sizeof(*buf));
56   buf->mem_ctx = mem_ctx;
57}
58
59static inline void
60util_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
72static inline void
73util_dynarray_clear(struct util_dynarray *buf)
74{
75	buf->size = 0;
76}
77
78#define DYN_ARRAY_INITIAL_SIZE 64
79
80static inline void *
81util_dynarray_ensure_cap(struct util_dynarray *buf, unsigned newcap)
82{
83   if (newcap > buf->capacity) {
84      if (buf->capacity == 0)
85         buf->capacity = DYN_ARRAY_INITIAL_SIZE;
86
87      while (newcap > buf->capacity)
88         buf->capacity *= 2;
89
90      if (buf->mem_ctx) {
91         buf->data = reralloc_size(buf->mem_ctx, buf->data, buf->capacity);
92      } else {
93         buf->data = realloc(buf->data, buf->capacity);
94      }
95   }
96
97   return (void *)((char *)buf->data + buf->size);
98}
99
100static inline void *
101util_dynarray_grow_cap(struct util_dynarray *buf, int diff)
102{
103   return util_dynarray_ensure_cap(buf, buf->size + diff);
104}
105
106/* use util_dynarray_trim to reduce the allocated storage */
107static inline void *
108util_dynarray_resize(struct util_dynarray *buf, unsigned newsize)
109{
110   void *p = util_dynarray_ensure_cap(buf, newsize);
111   buf->size = newsize;
112
113   return p;
114}
115
116static inline void
117util_dynarray_clone(struct util_dynarray *buf, void *mem_ctx,
118                    struct util_dynarray *from_buf)
119{
120   util_dynarray_init(buf, mem_ctx);
121   util_dynarray_resize(buf, from_buf->size);
122   memcpy(buf->data, from_buf->data, from_buf->size);
123}
124
125static inline void *
126util_dynarray_grow(struct util_dynarray *buf, int diff)
127{
128   return util_dynarray_resize(buf, buf->size + diff);
129}
130
131static inline void
132util_dynarray_trim(struct util_dynarray *buf)
133{
134   if (buf->size != buf->capacity) {
135      if (buf->size) {
136         if (buf->mem_ctx) {
137            buf->data = reralloc_size(buf->mem_ctx, buf->data, buf->size);
138         } else {
139            buf->data = realloc(buf->data, buf->size);
140         }
141         buf->capacity = buf->size;
142      } else {
143         if (buf->mem_ctx) {
144            ralloc_free(buf->data);
145         } else {
146            free(buf->data);
147         }
148         buf->data = NULL;
149         buf->capacity = 0;
150      }
151   }
152}
153
154#define util_dynarray_append(buf, type, v) do {type __v = (v); memcpy(util_dynarray_grow((buf), sizeof(type)), &__v, sizeof(type));} while(0)
155#define util_dynarray_top_ptr(buf, type) (type*)((char*)(buf)->data + (buf)->size - sizeof(type))
156#define util_dynarray_top(buf, type) *util_dynarray_top_ptr(buf, type)
157#define util_dynarray_pop_ptr(buf, type) (type*)((char*)(buf)->data + ((buf)->size -= sizeof(type)))
158#define util_dynarray_pop(buf, type) *util_dynarray_pop_ptr(buf, type)
159#define util_dynarray_contains(buf, type) ((buf)->size >= sizeof(type))
160#define util_dynarray_element(buf, type, idx) ((type*)(buf)->data + (idx))
161#define util_dynarray_begin(buf) ((buf)->data)
162#define util_dynarray_end(buf) ((void*)util_dynarray_element((buf), char, (buf)->size))
163#define util_dynarray_num_elements(buf, type) ((buf)->size / sizeof(type))
164
165#define util_dynarray_foreach(buf, type, elem) \
166   for (type *elem = (type *)(buf)->data; \
167        elem < (type *)((char *)(buf)->data + (buf)->size); elem++)
168
169#define util_dynarray_foreach_reverse(buf, type, elem)          \
170   if ((buf)->size > 0)                                         \
171      for (type *elem = util_dynarray_top_ptr(buf, type);       \
172           elem;                                                \
173           elem = elem > (type *)(buf)->data ? elem - 1 : NULL)
174
175#define util_dynarray_delete_unordered(buf, type, v)                    \
176   do {                                                                 \
177      unsigned num_elements = (buf)->size / sizeof(type);               \
178      unsigned i;                                                       \
179      for (i = 0; i < num_elements; i++) {                              \
180         type __v = *util_dynarray_element((buf), type, (i));           \
181         if (v == __v) {                                                \
182            memcpy(util_dynarray_element((buf), type, (i)),             \
183                   util_dynarray_pop_ptr((buf), type), sizeof(type));   \
184            break;                                                      \
185         }                                                              \
186      }                                                                 \
187   } while (0)
188
189#ifdef __cplusplus
190}
191#endif
192
193#endif /* U_DYNARRAY_H */
194
195