#define U_DYNARRAY_H
#include <stdlib.h>
+#include <string.h>
+#include <limits.h>
+#include "ralloc.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
/* A zero-initialized version of this is guaranteed to represent an
* empty array.
*/
struct util_dynarray
{
+ void *mem_ctx;
void *data;
unsigned size;
unsigned capacity;
};
static inline void
-util_dynarray_init(struct util_dynarray *buf)
+util_dynarray_init(struct util_dynarray *buf, void *mem_ctx)
{
memset(buf, 0, sizeof(*buf));
+ buf->mem_ctx = mem_ctx;
}
static inline void
util_dynarray_fini(struct util_dynarray *buf)
{
if (buf->data) {
- free(buf->data);
- util_dynarray_init(buf);
+ if (buf->mem_ctx) {
+ ralloc_free(buf->data);
+ } else {
+ free(buf->data);
+ }
+ util_dynarray_init(buf, buf->mem_ctx);
}
}
-/* use util_dynarray_trim to reduce the allocated storage */
-static inline void *
-util_dynarray_resize(struct util_dynarray *buf, unsigned newsize)
+static inline void
+util_dynarray_clear(struct util_dynarray *buf)
+{
+ buf->size = 0;
+}
+
+#define DYN_ARRAY_INITIAL_SIZE 64
+
+MUST_CHECK static inline void *
+util_dynarray_ensure_cap(struct util_dynarray *buf, unsigned newcap)
{
- void *p;
- if (newsize > buf->capacity) {
- unsigned newcap = buf->capacity << 1;
- if (newsize > newcap)
- newcap = newsize;
- buf->data = realloc(buf->data, newcap);
- buf->capacity = newcap;
+ if (newcap > buf->capacity) {
+ unsigned capacity = MAX3(DYN_ARRAY_INITIAL_SIZE, buf->capacity * 2, newcap);
+ void *data;
+
+ if (buf->mem_ctx) {
+ data = reralloc_size(buf->mem_ctx, buf->data, capacity);
+ } else {
+ data = realloc(buf->data, capacity);
+ }
+ if (!data)
+ return 0;
+
+ buf->data = data;
+ buf->capacity = capacity;
}
- p = (void *)((char *)buf->data + buf->size);
+ return (void *)((char *)buf->data + buf->size);
+}
+
+/* use util_dynarray_trim to reduce the allocated storage */
+MUST_CHECK static inline void *
+util_dynarray_resize_bytes(struct util_dynarray *buf, unsigned nelts, size_t eltsize)
+{
+ if (unlikely(nelts > UINT_MAX / eltsize))
+ return 0;
+
+ unsigned newsize = nelts * eltsize;
+ void *p = util_dynarray_ensure_cap(buf, newsize);
+ if (!p)
+ return 0;
+
buf->size = newsize;
return p;
}
-static inline void *
-util_dynarray_grow(struct util_dynarray *buf, int diff)
+static inline void
+util_dynarray_clone(struct util_dynarray *buf, void *mem_ctx,
+ struct util_dynarray *from_buf)
{
- return util_dynarray_resize(buf, buf->size + diff);
+ util_dynarray_init(buf, mem_ctx);
+ if (util_dynarray_resize_bytes(buf, from_buf->size, 1))
+ memcpy(buf->data, from_buf->data, from_buf->size);
+}
+
+MUST_CHECK static inline void *
+util_dynarray_grow_bytes(struct util_dynarray *buf, unsigned ngrow, size_t eltsize)
+{
+ unsigned growbytes = ngrow * eltsize;
+
+ if (unlikely(ngrow > (UINT_MAX / eltsize) ||
+ growbytes > UINT_MAX - buf->size))
+ return 0;
+
+ unsigned newsize = buf->size + growbytes;
+ void *p = util_dynarray_ensure_cap(buf, newsize);
+ if (!p)
+ return 0;
+
+ buf->size = newsize;
+
+ return p;
}
static inline void
{
if (buf->size != buf->capacity) {
if (buf->size) {
- buf->data = realloc(buf->data, buf->size);
+ if (buf->mem_ctx) {
+ buf->data = reralloc_size(buf->mem_ctx, buf->data, buf->size);
+ } else {
+ buf->data = realloc(buf->data, buf->size);
+ }
buf->capacity = buf->size;
} else {
- free(buf->data);
- buf->data = 0;
+ if (buf->mem_ctx) {
+ ralloc_free(buf->data);
+ } else {
+ free(buf->data);
+ }
+ buf->data = NULL;
buf->capacity = 0;
}
}
}
-#define util_dynarray_append(buf, type, v) do {type __v = (v); memcpy(util_dynarray_grow((buf), sizeof(type)), &__v, sizeof(type));} while(0)
+#define util_dynarray_append(buf, type, v) do {type __v = (v); memcpy(util_dynarray_grow_bytes((buf), 1, sizeof(type)), &__v, sizeof(type));} while(0)
+/* Returns a pointer to the space of the first new element (in case of growth) or NULL on failure. */
+#define util_dynarray_resize(buf, type, nelts) util_dynarray_resize_bytes(buf, (nelts), sizeof(type))
+#define util_dynarray_grow(buf, type, ngrow) util_dynarray_grow_bytes(buf, (ngrow), sizeof(type))
#define util_dynarray_top_ptr(buf, type) (type*)((char*)(buf)->data + (buf)->size - sizeof(type))
#define util_dynarray_top(buf, type) *util_dynarray_top_ptr(buf, type)
#define util_dynarray_pop_ptr(buf, type) (type*)((char*)(buf)->data + ((buf)->size -= sizeof(type)))
#define util_dynarray_element(buf, type, idx) ((type*)(buf)->data + (idx))
#define util_dynarray_begin(buf) ((buf)->data)
#define util_dynarray_end(buf) ((void*)util_dynarray_element((buf), char, (buf)->size))
+#define util_dynarray_num_elements(buf, type) ((buf)->size / sizeof(type))
+
+#define util_dynarray_foreach(buf, type, elem) \
+ for (type *elem = (type *)(buf)->data; \
+ elem < (type *)((char *)(buf)->data + (buf)->size); elem++)
+
+#define util_dynarray_foreach_reverse(buf, type, elem) \
+ if ((buf)->size > 0) \
+ for (type *elem = util_dynarray_top_ptr(buf, type); \
+ elem; \
+ elem = elem > (type *)(buf)->data ? elem - 1 : NULL)
+
+#define util_dynarray_delete_unordered(buf, type, v) \
+ do { \
+ unsigned num_elements = (buf)->size / sizeof(type); \
+ unsigned i; \
+ for (i = 0; i < num_elements; i++) { \
+ type __v = *util_dynarray_element((buf), type, (i)); \
+ if (v == __v) { \
+ memcpy(util_dynarray_element((buf), type, (i)), \
+ util_dynarray_pop_ptr((buf), type), sizeof(type)); \
+ break; \
+ } \
+ } \
+ } while (0)
+
+#ifdef __cplusplus
+}
+#endif
#endif /* U_DYNARRAY_H */
projects / mesa.git / blobdiff