[PATCH 1/3] darray: Add darray_insert() to insert a value at a specified index

[PATCH 1/3] darray: Add darray_insert() to insert a value at a specified index

[Damien Grassart]

This module currently supports removing but not inserting at a
specified index, so this adds that along with some tests. Inserting a
value moves all existing data beyond index over one element.

Signed-off-by: Damien Grassart <damien@grassart.com>
---
 ccan/darray/darray.h   |  7 +++++++
 ccan/darray/test/run.c | 22 ++++++++++++++++++++--
 2 files changed, 27 insertions(+), 2 deletions(-)

diff --git a/ccan/darray/darray.h b/ccan/darray/darray.h
index 75112419..fca20b8a 100644
--- a/ccan/darray/darray.h
+++ b/ccan/darray/darray.h
@@ -56,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):
@@ -169,6 +170,12 @@ 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__)
 
 
diff --git a/ccan/darray/test/run.c b/ccan/darray/test/run.c
index 3d96fa56..5888af60 100644
--- a/ccan/darray/test/run.c
+++ b/ccan/darray/test/run.c
@@ -38,7 +38,7 @@ int main(void) {
 	trace("Generating amalgams (internal)");
 	generateAmalgams();
 	
-	plan_tests(41);
+	plan_tests(47);
 	
 	testLits();
 	
@@ -70,7 +70,25 @@ int main(void) {
 		ok1(darray_size(arr) == 0);
 	}
 	reset(arr);
-	
+
+	testing(darray_insert);
+	{
+		size_t middle_i;
+
+		for (i=0; i < ARRAY_SIZE(lotsOfNumbers); i++)
+			darray_insert(arr, i, lotsOfNumbers[i]);
+		ok1(darray_size(arr) == ARRAY_SIZE(lotsOfNumbers));
+		ok1(darray_alloc(arr) >= darray_size(arr));
+		ok1(!memcmp(arr.item, lotsOfNumbers, sizeof(lotsOfNumbers)));
+
+		middle_i = ARRAY_SIZE(lotsOfNumbers) / 2;
+		darray_insert(arr, middle_i, 42);
+		ok1(darray_size(arr) == ARRAY_SIZE(lotsOfNumbers) + 1);
+		ok1(arr.item[middle_i] == 42);
+		ok1(arr.item[middle_i + 1] == lotsOfNumbers[middle_i]);
+	}
+	reset(arr);
+
 	testing(darray_from_c, darray_foreach, darray_foreach_reverse);
 	{
 		long   *i;
-- 
2.14.1

_______________________________________________
ccan mailing list
ccan@lists.ozlabs.org
https://lists.ozlabs.org/listinfo/ccan

[PATCH 2/3] darray: Rename identifiers starting with an underscore

[Damien Grassart]

Identifiers starting with underscores are technically reserved for
system use, so rename all of them to end with one instead.

Signed-off-by: Damien Grassart <damien@grassart.com>
---
 ccan/darray/darray.h | 68 ++++++++++++++++++++++++++--------------------------
 1 file changed, 34 insertions(+), 34 deletions(-)

diff --git a/ccan/darray/darray.h b/ccan/darray/darray.h
index fca20b8a..82726c05 100644
--- a/ccan/darray/darray.h
+++ b/ccan/darray/darray.h
@@ -171,10 +171,10 @@ typedef darray(unsigned long)  darray_ulong;
 		(arr).item[0] = (__VA_ARGS__); \
 	} while(0)
 #define darray_insert(arr, index, ...) do { \
-		size_t __index = index; \
+		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__); \
+		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__)
 
@@ -182,30 +182,30 @@ typedef darray(unsigned long)  darray_ulong;
 /*** 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)
 
@@ -215,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)
 
 
@@ -239,23 +239,23 @@ typedef darray(unsigned long)  darray_ulong;
 
 /*** 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)
 
 
@@ -263,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)
 
@@ -275,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
-- 
2.14.1

_______________________________________________
ccan mailing list
ccan@lists.ozlabs.org
https://lists.ozlabs.org/listinfo/ccan

[PATCH 3/3] darray: Fix bug in the darray_remove() macro

[Damien Grassart]

The memmove() call should be using the index argument to determine the
number of bytes to copy. To be consistent with the rest of the code,
we should also not evaluate the index parameter multiple
times. Calling this with rand() % arr.size would otherwise generally
segfault.

Finally, we want to avoid using "index" as an identifier so as to not
shadow index(3) in the C library.

Signed-off-by: Damien Grassart <damien@grassart.com>
---
 ccan/darray/darray.h | 11 ++++++-----
 1 file changed, 6 insertions(+), 5 deletions(-)

diff --git a/ccan/darray/darray.h b/ccan/darray/darray.h
index 82726c05..58470fde 100644
--- a/ccan/darray/darray.h
+++ b/ccan/darray/darray.h
@@ -170,8 +170,8 @@ 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; \
+#define darray_insert(arr, i, ...) do { \
+		size_t index_ = (i); \
 		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__); \
@@ -230,9 +230,10 @@ typedef darray(unsigned long)  darray_ulong;
 #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)); \
+#define darray_remove(arr, i) do { \
+	size_t index_ = (i); \
+	if (index_ < arr.size-1)    \
+		memmove(&(arr).item[index_], &(arr).item[index_+1], ((arr).size-1-index_)*sizeof(*(arr).item)); \
 	(arr).size--;  \
 	} while(0)
 
-- 
2.14.1

_______________________________________________
ccan mailing list
ccan@lists.ozlabs.org
https://lists.ozlabs.org/listinfo/ccan

Re: [PATCH 1/3] darray: Add darray_insert() to insert a value at a specified index

[David Gibson]

[-- Attachment #1.1: Type: text/plain, Size: 2941 bytes --]

On Tue, Aug 29, 2017 at 12:08:40PM +0200, Damien Grassart wrote:
> This module currently supports removing but not inserting at a
> specified index, so this adds that along with some tests. Inserting a
> value moves all existing data beyond index over one element.
> 
> Signed-off-by: Damien Grassart <damien@grassart.com>

Series applied, thanks.

> ---
>  ccan/darray/darray.h   |  7 +++++++
>  ccan/darray/test/run.c | 22 ++++++++++++++++++++--
>  2 files changed, 27 insertions(+), 2 deletions(-)
> 
> diff --git a/ccan/darray/darray.h b/ccan/darray/darray.h
> index 75112419..fca20b8a 100644
> --- a/ccan/darray/darray.h
> +++ b/ccan/darray/darray.h
> @@ -56,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):
> @@ -169,6 +170,12 @@ 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__)
>  
>  
> diff --git a/ccan/darray/test/run.c b/ccan/darray/test/run.c
> index 3d96fa56..5888af60 100644
> --- a/ccan/darray/test/run.c
> +++ b/ccan/darray/test/run.c
> @@ -38,7 +38,7 @@ int main(void) {
>  	trace("Generating amalgams (internal)");
>  	generateAmalgams();
>  	
> -	plan_tests(41);
> +	plan_tests(47);
>  	
>  	testLits();
>  	
> @@ -70,7 +70,25 @@ int main(void) {
>  		ok1(darray_size(arr) == 0);
>  	}
>  	reset(arr);
> -	
> +
> +	testing(darray_insert);
> +	{
> +		size_t middle_i;
> +
> +		for (i=0; i < ARRAY_SIZE(lotsOfNumbers); i++)
> +			darray_insert(arr, i, lotsOfNumbers[i]);
> +		ok1(darray_size(arr) == ARRAY_SIZE(lotsOfNumbers));
> +		ok1(darray_alloc(arr) >= darray_size(arr));
> +		ok1(!memcmp(arr.item, lotsOfNumbers, sizeof(lotsOfNumbers)));
> +
> +		middle_i = ARRAY_SIZE(lotsOfNumbers) / 2;
> +		darray_insert(arr, middle_i, 42);
> +		ok1(darray_size(arr) == ARRAY_SIZE(lotsOfNumbers) + 1);
> +		ok1(arr.item[middle_i] == 42);
> +		ok1(arr.item[middle_i + 1] == lotsOfNumbers[middle_i]);
> +	}
> +	reset(arr);
> +
>  	testing(darray_from_c, darray_foreach, darray_foreach_reverse);
>  	{
>  		long   *i;

-- 
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/~dgibson

[-- Attachment #1.2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

[-- Attachment #2: Type: text/plain, Size: 127 bytes --]

_______________________________________________
ccan mailing list
ccan@lists.ozlabs.org
https://lists.ozlabs.org/listinfo/ccan