Home | History | Annotate | Download | only in util 
      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 "pipe/p_compiler.h"
     31 #include "util/u_memory.h"
     32 
     33 /* A zero-initialized version of this is guaranteed to represent an
     34  * empty array.
     35  *
     36  * Also, size <= capacity and data != 0 if and only if capacity != 0
     37  * capacity will always be the allocation size of data
     38  */
     39 struct util_dynarray
     40 {
     41    void *data;
     42    unsigned size;
     43    unsigned capacity;
     44 };
     45 
     46 static INLINE void
     47 util_dynarray_init(struct util_dynarray *buf)
     48 {
     49    memset(buf, 0, sizeof(*buf));
     50 }
     51 
     52 static INLINE void
     53 util_dynarray_fini(struct util_dynarray *buf)
     54 {
     55    if(buf->data)
     56    {
     57       FREE(buf->data);
     58       util_dynarray_init(buf);
     59    }
     60 }
     61 
     62 /* use util_dynarray_trim to reduce the allocated storage */
     63 static INLINE void *
     64 util_dynarray_resize(struct util_dynarray *buf, unsigned newsize)
     65 {
     66    char *p;
     67    if(newsize > buf->capacity)
     68    {
     69       unsigned newcap = buf->capacity << 1;
     70       if(newsize > newcap)
     71 	      newcap = newsize;
     72       buf->data = REALLOC(buf->data, buf->capacity, newcap);
     73       buf->capacity = newcap;
     74    }
     75 
     76    p = (char *)buf->data + buf->size;
     77    buf->size = newsize;
     78    return p;
     79 }
     80 
     81 static INLINE void *
     82 util_dynarray_grow(struct util_dynarray *buf, int diff)
     83 {
     84    return util_dynarray_resize(buf, buf->size + diff);
     85 }
     86 
     87 static INLINE void
     88 util_dynarray_trim(struct util_dynarray *buf)
     89 {
     90    if (buf->size != buf->capacity) {
     91       if (buf->size) {
     92          buf->data = REALLOC(buf->data, buf->capacity, buf->size);
     93          buf->capacity = buf->size;
     94       }
     95       else {
     96          FREE(buf->data);
     97          buf->data = 0;
     98          buf->capacity = 0;
     99       }
    100    }
    101 }
    102 
    103 #define util_dynarray_append(buf, type, v) do {type __v = (v); memcpy(util_dynarray_grow((buf), sizeof(type)), &__v, sizeof(type));} while(0)
    104 #define util_dynarray_top_ptr(buf, type) (type*)((char*)(buf)->data + (buf)->size - sizeof(type))
    105 #define util_dynarray_top(buf, type) *util_dynarray_top_ptr(buf, type)
    106 #define util_dynarray_pop_ptr(buf, type) (type*)((char*)(buf)->data + ((buf)->size -= sizeof(type)))
    107 #define util_dynarray_pop(buf, type) *util_dynarray_pop_ptr(buf, type)
    108 #define util_dynarray_contains(buf, type) ((buf)->size >= sizeof(type))
    109 #define util_dynarray_element(buf, type, idx) ((type*)(buf)->data + (idx))
    110 #define util_dynarray_begin(buf) ((buf)->data)
    111 #define util_dynarray_end(buf) ((void*)util_dynarray_element((buf), char, (buf)->size))
    112 
    113 #endif /* U_DYNARRAY_H */
    114 
    115