1760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org/************************************************************************** 2760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org * 3760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org * Copyright 2010 Luca Barbieri 4760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org * 5760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org * Permission is hereby granted, free of charge, to any person obtaining 6760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org * a copy of this software and associated documentation files (the 7760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org * "Software"), to deal in the Software without restriction, including 8760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org * without limitation the rights to use, copy, modify, merge, publish, 9760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org * distribute, sublicense, and/or sell copies of the Software, and to 10760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org * permit persons to whom the Software is furnished to do so, subject to 11760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org * the following conditions: 12760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org * 13760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org * The above copyright notice and this permission notice (including the 14760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org * next paragraph) shall be included in all copies or substantial 15760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org * portions of the Software. 16760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org * 17760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 18760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 19760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 20760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org * IN NO EVENT SHALL THE COPYRIGHT OWNER(S) AND/OR ITS SUPPLIERS BE 21760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 22760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 23760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 24760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org * 25760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org **************************************************************************/ 26760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org 27760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org#ifndef U_DYNARRAY_H 28760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org#define U_DYNARRAY_H 29760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org 30760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org#include "pipe/p_compiler.h" 31760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org#include "util/u_memory.h" 32760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org 33760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org/* A zero-initialized version of this is guaranteed to represent an 34760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org * empty array. 35760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org * 36760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org * Also, size <= capacity and data != 0 if and only if capacity != 0 37760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org * capacity will always be the allocation size of data 38760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org */ 39760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.orgstruct util_dynarray 40760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org{ 41760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org void *data; 42760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org unsigned size; 43760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org unsigned capacity; 44760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org}; 45760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org 46760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.orgstatic INLINE void 47760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.orgutil_dynarray_init(struct util_dynarray *buf) 48760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org{ 49760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org memset(buf, 0, sizeof(*buf)); 50760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org} 51760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org 52760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.orgstatic INLINE void 53760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.orgutil_dynarray_fini(struct util_dynarray *buf) 54760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org{ 55760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org if(buf->data) 56760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org { 57760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org FREE(buf->data); 58760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org util_dynarray_init(buf); 59760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org } 60760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org} 61760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org 62760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org/* use util_dynarray_trim to reduce the allocated storage */ 63760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.orgstatic INLINE void * 64760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.orgutil_dynarray_resize(struct util_dynarray *buf, unsigned newsize) 65760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org{ 66760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org char *p; 67760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org if(newsize > buf->capacity) 68760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org { 69760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org unsigned newcap = buf->capacity << 1; 70760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org if(newsize > newcap) 71760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org newcap = newsize; 72760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org buf->data = REALLOC(buf->data, buf->capacity, newcap); 73760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org buf->capacity = newcap; 74760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org } 75760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org 76760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org p = (char *)buf->data + buf->size; 77760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org buf->size = newsize; 78760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org return p; 79760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org} 80760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org 81760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.orgstatic INLINE void * 82760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.orgutil_dynarray_grow(struct util_dynarray *buf, int diff) 83760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org{ 84760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org return util_dynarray_resize(buf, buf->size + diff); 85760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org} 86760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org 87760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.orgstatic INLINE void 88760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.orgutil_dynarray_trim(struct util_dynarray *buf) 89760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org{ 90760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org if (buf->size != buf->capacity) { 91760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org if (buf->size) { 92760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org buf->data = REALLOC(buf->data, buf->capacity, buf->size); 93760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org buf->capacity = buf->size; 94760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org } 95760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org else { 96760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org FREE(buf->data); 97760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org buf->data = 0; 98760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org buf->capacity = 0; 99760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org } 100760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org } 101760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org} 102760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org 103760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org#define util_dynarray_append(buf, type, v) do {type __v = (v); memcpy(util_dynarray_grow((buf), sizeof(type)), &__v, sizeof(type));} while(0) 104760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org#define util_dynarray_top_ptr(buf, type) (type*)((char*)(buf)->data + (buf)->size - sizeof(type)) 105760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org#define util_dynarray_top(buf, type) *util_dynarray_top_ptr(buf, type) 106760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org#define util_dynarray_pop_ptr(buf, type) (type*)((char*)(buf)->data + ((buf)->size -= sizeof(type))) 107760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org#define util_dynarray_pop(buf, type) *util_dynarray_pop_ptr(buf, type) 108760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org#define util_dynarray_contains(buf, type) ((buf)->size >= sizeof(type)) 109760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org#define util_dynarray_element(buf, type, idx) ((type*)(buf)->data + (idx)) 110760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org#define util_dynarray_begin(buf) ((buf)->data) 111760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org#define util_dynarray_end(buf) ((void*)util_dynarray_element((buf), char, (buf)->size)) 112760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org 113760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org#endif /* U_DYNARRAY_H */ 114760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org 115