15f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri/************************************************************************** 25f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri * 35f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri * Copyright 2010 Luca Barbieri 45f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri * 55f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri * Permission is hereby granted, free of charge, to any person obtaining 65f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri * a copy of this software and associated documentation files (the 75f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri * "Software"), to deal in the Software without restriction, including 85f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri * without limitation the rights to use, copy, modify, merge, publish, 95f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri * distribute, sublicense, and/or sell copies of the Software, and to 105f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri * permit persons to whom the Software is furnished to do so, subject to 115f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri * the following conditions: 125f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri * 135f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri * The above copyright notice and this permission notice (including the 145f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri * next paragraph) shall be included in all copies or substantial 155f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri * portions of the Software. 165f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri * 175f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 185f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 195f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 205f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri * IN NO EVENT SHALL THE COPYRIGHT OWNER(S) AND/OR ITS SUPPLIERS BE 215f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 225f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 235f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 245f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri * 255f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri **************************************************************************/ 265f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri 275f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri#ifndef U_DYNARRAY_H 285f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri#define U_DYNARRAY_H 295f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri 305f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri#include "pipe/p_compiler.h" 315f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri#include "util/u_memory.h" 325f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri 335f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri/* A zero-initialized version of this is guaranteed to represent an 345f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri * empty array. 355f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri * 365f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri * Also, size <= capacity and data != 0 if and only if capacity != 0 375f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri * capacity will always be the allocation size of data 385f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri */ 395f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieristruct util_dynarray 405f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri{ 415f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri void *data; 425f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri unsigned size; 435f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri unsigned capacity; 445f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri}; 455f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri 465f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieristatic INLINE void 475f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieriutil_dynarray_init(struct util_dynarray *buf) 485f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri{ 495f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri memset(buf, 0, sizeof(*buf)); 505f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri} 515f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri 525f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieristatic INLINE void 535f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieriutil_dynarray_fini(struct util_dynarray *buf) 545f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri{ 555f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri if(buf->data) 565f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri { 575f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri FREE(buf->data); 585f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri util_dynarray_init(buf); 595f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri } 605f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri} 615f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri 626c31dd119878378540b6bdbb2f47bc5ab6cc516fLuca Barbieri/* use util_dynarray_trim to reduce the allocated storage */ 635f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieristatic INLINE void * 646c31dd119878378540b6bdbb2f47bc5ab6cc516fLuca Barbieriutil_dynarray_resize(struct util_dynarray *buf, unsigned newsize) 655f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri{ 665f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri char *p; 675f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri if(newsize > buf->capacity) 685f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri { 695f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri unsigned newcap = buf->capacity << 1; 705f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri if(newsize > newcap) 715f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri newcap = newsize; 725f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri buf->data = REALLOC(buf->data, buf->capacity, newcap); 735f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri buf->capacity = newcap; 745f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri } 755f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri 765f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri p = (char *)buf->data + buf->size; 775f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri buf->size = newsize; 785f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri return p; 795f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri} 805f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri 816c31dd119878378540b6bdbb2f47bc5ab6cc516fLuca Barbieristatic INLINE void * 826c31dd119878378540b6bdbb2f47bc5ab6cc516fLuca Barbieriutil_dynarray_grow(struct util_dynarray *buf, int diff) 836c31dd119878378540b6bdbb2f47bc5ab6cc516fLuca Barbieri{ 846c31dd119878378540b6bdbb2f47bc5ab6cc516fLuca Barbieri return util_dynarray_resize(buf, buf->size + diff); 856c31dd119878378540b6bdbb2f47bc5ab6cc516fLuca Barbieri} 866c31dd119878378540b6bdbb2f47bc5ab6cc516fLuca Barbieri 875f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieristatic INLINE void 885f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieriutil_dynarray_trim(struct util_dynarray *buf) 895f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri{ 90ddc42b6380d0380a6f519df268a8b3531ddb81fbMichal Krol if (buf->size != buf->capacity) { 91ddc42b6380d0380a6f519df268a8b3531ddb81fbMichal Krol if (buf->size) { 92ddc42b6380d0380a6f519df268a8b3531ddb81fbMichal Krol buf->data = REALLOC(buf->data, buf->capacity, buf->size); 93ddc42b6380d0380a6f519df268a8b3531ddb81fbMichal Krol buf->capacity = buf->size; 94ddc42b6380d0380a6f519df268a8b3531ddb81fbMichal Krol } 95ddc42b6380d0380a6f519df268a8b3531ddb81fbMichal Krol else { 96ddc42b6380d0380a6f519df268a8b3531ddb81fbMichal Krol FREE(buf->data); 97ddc42b6380d0380a6f519df268a8b3531ddb81fbMichal Krol buf->data = 0; 98ddc42b6380d0380a6f519df268a8b3531ddb81fbMichal Krol buf->capacity = 0; 99ddc42b6380d0380a6f519df268a8b3531ddb81fbMichal Krol } 100c57261981702f78f0df1426c405a7e891ef81639Luca Barbieri } 1015f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri} 1025f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri 1035f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri#define util_dynarray_append(buf, type, v) do {type __v = (v); memcpy(util_dynarray_grow((buf), sizeof(type)), &__v, sizeof(type));} while(0) 1045f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri#define util_dynarray_top_ptr(buf, type) (type*)((char*)(buf)->data + (buf)->size - sizeof(type)) 1055f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri#define util_dynarray_top(buf, type) *util_dynarray_top_ptr(buf, type) 1065f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri#define util_dynarray_pop_ptr(buf, type) (type*)((char*)(buf)->data + ((buf)->size -= sizeof(type))) 1075f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri#define util_dynarray_pop(buf, type) *util_dynarray_pop_ptr(buf, type) 1085f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri#define util_dynarray_contains(buf, type) ((buf)->size >= sizeof(type)) 109bfaa2577c6474222c79341c0d90685ed579f3414Luca Barbieri#define util_dynarray_element(buf, type, idx) ((type*)(buf)->data + (idx)) 110bfaa2577c6474222c79341c0d90685ed579f3414Luca Barbieri#define util_dynarray_begin(buf) ((buf)->data) 111bfaa2577c6474222c79341c0d90685ed579f3414Luca Barbieri#define util_dynarray_end(buf) ((void*)util_dynarray_element((buf), char, (buf)->size)) 1125f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri 1135f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri#endif /* U_DYNARRAY_H */ 1145f968a64dc965c7197c2b85ccf0a596fde366c06Luca Barbieri 115