X-Git-Url: http://git.ozlabs.org/?a=blobdiff_plain;f=ccan%2Fdarray%2Fdarray.h;h=82726c05360ae5746b37e0e97f57b5d033abb5fb;hb=d4779b16fdd44a1a4ccf3c82ecd5af71ba096289;hp=d75f31445957f3ba4046cc9e020c140b453972b4;hpb=6ba4abebd2fdaba81a0dad774de3cd8fc99304dc;p=ccan diff --git a/ccan/darray/darray.h b/ccan/darray/darray.h index d75f3144..82726c05 100644 --- a/ccan/darray/darray.h +++ b/ccan/darray/darray.h @@ -1,29 +1,24 @@ /* - Copyright (c) 2009 Joseph A. Adams - All rights reserved. - - Redistribution and use in source and binary forms, with or without - modification, are permitted provided that the following conditions - are met: - 1. Redistributions of source code must retain the above copyright - notice, this list of conditions and the following disclaimer. - 2. Redistributions in binary form must reproduce the above copyright - notice, this list of conditions and the following disclaimer in the - documentation and/or other materials provided with the distribution. - 3. The name of the author may not be used to endorse or promote products - derived from this software without specific prior written permission. - - THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR - IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES - OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. - IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, - INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT - NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF - THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -*/ + * Copyright (C) 2011 Joseph Adams + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. + */ #ifndef CCAN_DARRAY_H #define CCAN_DARRAY_H @@ -61,6 +56,7 @@ * * void darray_append(darray(T) arr, T item); * void darray_prepend(darray(T) arr, T item); + * void darray_insert(darray(T) arr, size_t index, T item); * void darray_push(darray(T) arr, T item); // same as darray_append * * Insertion (multiple items): @@ -79,6 +75,7 @@ * * T darray_pop(darray(T) arr | darray_size(arr) != 0); * T* darray_pop_check(darray(T*) arr); + * void darray_remove(darray(T) arr, size_t index); * * Replacement: * @@ -111,7 +108,7 @@ * darray_foreach(T *&i, darray(T) arr) {...} * darray_foreach_reverse(T *&i, darray(T) arr) {...} * - * Except for darray_foreach and darray_foreach_reverse, + * Except for darray_foreach, darray_foreach_reverse, and darray_remove, * all macros evaluate their non-darray arguments only once. */ @@ -173,36 +170,42 @@ typedef darray(unsigned long) darray_ulong; memmove((arr).item+1, (arr).item, ((arr).size-1)*sizeof(*(arr).item)); \ (arr).item[0] = (__VA_ARGS__); \ } while(0) +#define darray_insert(arr, index, ...) do { \ + size_t index_ = index; \ + darray_resize(arr, (arr).size+1); \ + memmove((arr).item+index_+1, (arr).item+index_, ((arr).size-index_-1)*sizeof(*(arr).item)); \ + (arr).item[index_] = (__VA_ARGS__); \ + } while(0) #define darray_push(arr, ...) darray_append(arr, __VA_ARGS__) /*** Insertion (multiple items) ***/ #define darray_append_items(arr, items, count) do { \ - size_t __count = (count), __oldSize = (arr).size; \ - darray_resize(arr, __oldSize + __count); \ - memcpy((arr).item + __oldSize, items, __count * sizeof(*(arr).item)); \ + size_t count_ = (count), oldSize_ = (arr).size; \ + darray_resize(arr, oldSize_ + count_); \ + memcpy((arr).item + oldSize_, items, count_ * sizeof(*(arr).item)); \ } while(0) #define darray_prepend_items(arr, items, count) do { \ - size_t __count = (count), __oldSize = (arr).size; \ - darray_resize(arr, __count + __oldSize); \ - memmove((arr).item + __count, (arr).item, __oldSize * sizeof(*(arr).item)); \ - memcpy((arr).item, items, __count * sizeof(*(arr).item)); \ + size_t count_ = (count), oldSize_ = (arr).size; \ + darray_resize(arr, count_ + oldSize_); \ + memmove((arr).item + count_, (arr).item, oldSize_ * sizeof(*(arr).item)); \ + memcpy((arr).item, items, count_ * sizeof(*(arr).item)); \ } while(0) #define darray_append_items_nullterminate(arr, items, count) do { \ - size_t __count = (count), __oldSize = (arr).size; \ - darray_resize(arr, __oldSize + __count + 1); \ - memcpy((arr).item + __oldSize, items, __count * sizeof(*(arr).item)); \ + size_t count_ = (count), oldSize_ = (arr).size; \ + darray_resize(arr, oldSize_ + count_ + 1); \ + memcpy((arr).item + oldSize_, items, count_ * sizeof(*(arr).item)); \ (arr).item[--(arr).size] = 0; \ } while(0) #define darray_prepend_items_nullterminate(arr, items, count) do { \ - size_t __count = (count), __oldSize = (arr).size; \ - darray_resize(arr, __count + __oldSize + 1); \ - memmove((arr).item + __count, (arr).item, __oldSize * sizeof(*(arr).item)); \ - memcpy((arr).item, items, __count * sizeof(*(arr).item)); \ + size_t count_ = (count), oldSize_ = (arr).size; \ + darray_resize(arr, count_ + oldSize_ + 1); \ + memmove((arr).item + count_, (arr).item, oldSize_ * sizeof(*(arr).item)); \ + memcpy((arr).item, items, count_ * sizeof(*(arr).item)); \ (arr).item[--(arr).size] = 0; \ } while(0) @@ -212,12 +215,12 @@ typedef darray(unsigned long) darray_ulong; #endif #define darray_appends_t(arr, type, ...) do { \ - type __src[] = {__VA_ARGS__}; \ - darray_append_items(arr, __src, sizeof(__src)/sizeof(*__src)); \ + type src_[] = {__VA_ARGS__}; \ + darray_append_items(arr, src_, sizeof(src_)/sizeof(*src_)); \ } while(0) #define darray_prepends_t(arr, type, ...) do { \ - type __src[] = {__VA_ARGS__}; \ - darray_prepend_items(arr, __src, sizeof(__src)/sizeof(*__src)); \ + type src_[] = {__VA_ARGS__}; \ + darray_prepend_items(arr, src_, sizeof(src_)/sizeof(*src_)); \ } while(0) @@ -226,27 +229,33 @@ typedef darray(unsigned long) darray_ulong; /* Warning: Do not call darray_pop on an empty darray. */ #define darray_pop(arr) ((arr).item[--(arr).size]) #define darray_pop_check(arr) ((arr).size ? darray_pop(arr) : NULL) +/* Warning, slow: Requires copying all elements after removed item. */ +#define darray_remove(arr, index) do { \ + if (index < arr.size-1) \ + memmove(&(arr).item[index], &(arr).item[index+1], ((arr).size-1-i)*sizeof(*(arr).item)); \ + (arr).size--; \ + } while(0) /*** Replacement ***/ -#define darray_from_items(arr, items, count) do {size_t __count = (count); darray_resize(arr, __count); memcpy((arr).item, items, __count*sizeof(*(arr).item));} while(0) +#define darray_from_items(arr, items, count) do {size_t count_ = (count); darray_resize(arr, count_); memcpy((arr).item, items, count_*sizeof(*(arr).item));} while(0) #define darray_from_c(arr, c_array) darray_from_items(arr, c_array, sizeof(c_array)/sizeof(*(c_array))) /*** String buffer ***/ -#define darray_append_string(arr, str) do {const char *__str = (str); darray_append_items(arr, __str, strlen(__str)+1); (arr).size--;} while(0) +#define darray_append_string(arr, str) do {const char *str_ = (str); darray_append_items(arr, str_, strlen(str_)+1); (arr).size--;} while(0) #define darray_append_lit(arr, stringLiteral) do {darray_append_items(arr, stringLiteral, sizeof(stringLiteral)); (arr).size--;} while(0) #define darray_prepend_string(arr, str) do { \ - const char *__str = (str); \ - darray_prepend_items_nullterminate(arr, __str, strlen(__str)); \ + const char *str_ = (str); \ + darray_prepend_items_nullterminate(arr, str_, strlen(str_)); \ } while(0) #define darray_prepend_lit(arr, stringLiteral) \ darray_prepend_items_nullterminate(arr, stringLiteral, sizeof(stringLiteral) - 1) -#define darray_from_string(arr, str) do {const char *__str = (str); darray_from_items(arr, __str, strlen(__str)+1); (arr).size--;} while(0) +#define darray_from_string(arr, str) do {const char *str_ = (str); darray_from_items(arr, str_, strlen(str_)+1); (arr).size--;} while(0) #define darray_from_lit(arr, stringLiteral) do {darray_from_items(arr, stringLiteral, sizeof(stringLiteral)); (arr).size--;} while(0) @@ -254,11 +263,11 @@ typedef darray(unsigned long) darray_ulong; #define darray_resize(arr, newSize) darray_growalloc(arr, (arr).size = (newSize)) #define darray_resize0(arr, newSize) do { \ - size_t __oldSize = (arr).size, __newSize = (newSize); \ - (arr).size = __newSize; \ - if (__newSize > __oldSize) { \ - darray_growalloc(arr, __newSize); \ - memset(&(arr).item[__oldSize], 0, (__newSize - __oldSize) * sizeof(*(arr).item)); \ + size_t oldSize_ = (arr).size, newSize_ = (newSize); \ + (arr).size = newSize_; \ + if (newSize_ > oldSize_) { \ + darray_growalloc(arr, newSize_); \ + memset(&(arr).item[oldSize_], 0, (newSize_ - oldSize_) * sizeof(*(arr).item)); \ } \ } while(0) @@ -266,9 +275,9 @@ typedef darray(unsigned long) darray_ulong; (arr).item = realloc((arr).item, ((arr).alloc = (newAlloc)) * sizeof(*(arr).item)); \ } while(0) #define darray_growalloc(arr, need) do { \ - size_t __need = (need); \ - if (__need > (arr).alloc) \ - darray_realloc(arr, darray_next_alloc((arr).alloc, __need)); \ + size_t need_ = (need); \ + if (need_ > (arr).alloc) \ + darray_realloc(arr, darray_next_alloc((arr).alloc, need_)); \ } while(0) #if HAVE_STATEMENT_EXPR==1