Mercurial > code

changeset 136:c6d9eb5702e8

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
array: o add ARRAY_FASTREMOVE, use last object when removing, o add ARRAY_CLEARBITS, set to 0 the bytes when removing parray: o add PARRAY_FASTREMOVE, use last object when removing, o add PARRAY_NULLEND, always has a last NULL entry
author David Demelier <markand@malikania.fr>
date Mon, 26 Mar 2012 10:24:49 +0200
parents 07800b7af208
children 97c9c20535e2
files array.c array.h parray.c parray.h
diffstat 4 files changed, 160 insertions(+), 53 deletions(-) [+]
line wrap: on
line diff
--- a/array.c	Tue Mar 20 22:49:37 2012 +0100
+++ b/array.c	Mon Mar 26 10:24:49 2012 +0200
@@ -43,6 +43,9 @@
 	if ((arr->data = arr->malloc(arr->size)) == NULL)
 		return -1;
 
+	if (arr->flags & ARRAY_CLEARBITS)
+		memset(arr->data, 0, arr->size);
+
 	return 0;
 }
 
@@ -51,7 +54,7 @@
  * l -> optional array block size of type int
  * m -> malloc function that must matches void * (*malloc)(size_t)
  * r -> realloc function that must matches void * (*realloc)(void *, size_t)
- * t -> type of array of type int
+ * f -> array flags of type int
  */
 
 void
@@ -72,8 +75,8 @@
 		case 'r':
 			arr->realloc = va_arg(ap, void *(*)(void *, size_t));
 			break;
-		case 't':
-			arr->type = va_arg(ap, int);
+		case 'f':
+			arr->flags = va_arg(ap, int);
 			break;
 		default:
 			break;
@@ -141,11 +144,7 @@
 void
 array_pop(struct array *arr)
 {
-	if (arr->length > 0) {
-		memmove((char *)arr->data, (char *)arr->data + OFFSET(1),
-		    OFFSET(--arr->length));
-		memset((char *)arr->data + OFFSET(arr->length), 0, arr->unit);
-	}
+	array_iremove(arr, 0);
 }
 
 /*
@@ -155,8 +154,7 @@
 void
 array_unqueue(struct array *arr)
 {
-	if (arr->length > 0)
-		memset((char *)arr->data + OFFSET(--arr->length), 0, arr->unit);
+	array_iremove(arr, arr->length - 1);
 }
 
 /*
@@ -167,11 +165,18 @@
 array_iremove(struct array *arr, int index)
 {
 	if (arr->length > 0 && index >= 0 && index < arr->length) {
-		memmove((char *)arr->data + OFFSET(index),
-		    (char *)arr->data + OFFSET(index + 1),
-		    OFFSET(arr->length - index - 1));
-		memset((char *)arr->data + OFFSET(--arr->length), 0, arr->unit);
+		if (arr->flags & ARRAY_FASTREMOVE)
+			memmove((char *)arr->data + OFFSET(index),
+			    (char *)arr->data + OFFSET(--arr->length),
+			    arr->unit);
+		else
+			memmove((char *)arr->data + OFFSET(index),
+			    (char *)arr->data + OFFSET(index + 1),
+			    OFFSET(arr->length-- - index - 1));
 	}
+
+	if (arr->flags & ARRAY_CLEARBITS)
+		memset((char *)arr->data + OFFSET(arr->length), 0, arr->unit);
 }
 
 /*
@@ -188,8 +193,10 @@
 	for (i = 0; i < arr->length; ++i) {
 		elm = (char *)arr->data + OFFSET(i);
 
-		if (memcmp(elm, data, arr->unit) == 0)
+		if (memcmp(elm, data, arr->unit) == 0) {
 			array_iremove(arr, i);
+			break;
+		}
 	}
 }
 
@@ -208,11 +215,6 @@
 	if (i1 >= arr->length || i1 < 0 || i2 >= arr->length || i2 < 0)
 		return -1;
 
-	/*
-	 * Only allocate at this time, the user may do not want to use this
-	 * function.
-	 */
-
 	if ((tmp = arr->malloc(arr->unit)) == NULL)
 		return -1;
 
@@ -226,7 +228,8 @@
 	 * secure data to be left somewhere in the memory.
 	 */
 
-	memset(tmp, 0, arr->unit);
+	if (arr->flags & ARRAY_CLEARBITS)
+		memset(tmp, 0, arr->unit);
 	free(tmp);
 
 	return 0;
@@ -292,6 +295,33 @@
 	return (st) ? i - 1 : -1;
 }
 
+void *
+array_first(const struct array *arr)
+{
+	return arr->data;
+}
+
+void *
+array_last(const struct array *arr)
+{
+	if (arr->length == 0)
+		return array_first(arr);
+
+	return (char *)arr->data + OFFSET(arr->length - 1);
+
+}
+
+void *
+array_index(const struct array *arr, int idx)
+{
+	if (idx < 0)
+		return array_first(arr);
+	if (idx >= arr->length)
+		return array_last(arr);
+
+	return (char *)arr->data + OFFSET(idx);
+}
+
 /*
  * Erase every bytes and set the length to 0.
  */
@@ -299,7 +329,9 @@
 void
 array_clear(struct array *arr)
 {
-	memset(arr->data, 0, arr->size);
+	if (arr->flags & ARRAY_CLEARBITS)
+		memset(arr->data, 0, arr->size);
+
 	arr->length = 0;
 }
 
@@ -310,7 +342,11 @@
 void
 array_free(struct array *arr)
 {
+	array_clear(arr);
 	free(arr->data);
+
+	arr->data	= NULL;
+	arr->size	= 0;
 }
 
 /*
@@ -322,13 +358,15 @@
 static int
 grow(struct array *arr)
 {
-	if ((arr->size / arr->unit) > (size_t) arr->length)
+	if ((arr->size / arr->unit) > (size_t)arr->length)
 		return 0;
 
-	if (arr->type == ARRAY_AUTO) {
+	if (!(arr->flags & ARRAY_FIXED)) {
 		if ((arr->data = arr->realloc(arr->data, arr->size +
-		    OFFSET(arr->bsize))) == NULL)
+		    OFFSET(arr->bsize))) == NULL) {
+			arr->size = arr->length = 0;
 			return -1;
+		}
 
 		arr->size += OFFSET(arr->bsize);
 	} else
--- a/array.h	Tue Mar 20 22:49:37 2012 +0100
+++ b/array.h	Mon Mar 26 10:24:49 2012 +0200
@@ -30,12 +30,14 @@
 #endif
 
 enum {
-	ARRAY_AUTO	= 0,
-	ARRAY_FIXED	= 1
+	ARRAY_AUTO		= 0,		/* array grows automatically */
+	ARRAY_FIXED		= (1 << 0),	/* fixed size length */
+	ARRAY_FASTREMOVE	= (1 << 1),	/* use last object when removing */
+	ARRAY_CLEARBITS		= (1 << 2)	/* clear data when inserting/removing */
 };
 
 struct array {
-	int	type;		/* (ro) array's type (default FIXED) */
+	int	flags;		/* (ro) array flags (default AUTO) */
 	void	*data;		/* (rw) array of data */
 	int	length;		/* (ro) number of element inside */
 	size_t	size;		/* (ro) current buffer size (allocated memory) */
@@ -89,16 +91,25 @@
 int
 array_find(const struct array *, array_cmp_fn, void *, void *);
 
+void *
+array_first(const struct array *);
+
+void *
+array_last(const struct array *);
+
+void *
+array_index(const struct array *, int);
+
 void
 array_clear(struct array *);
 
 void
 array_free(struct array *);
-
+	
 #define ARRAY_FOREACH(a, var, i)						\
-	for (i = 0, (var) = (a)->data;						\
+	for (i = 0, (var) = array_first((a));					\
 		i < (a)->length;						\
-		++i, ++(var))
+		(var) = array_index(a, ++i))
 
 #ifdef __cplusplus
 }
--- a/parray.c	Tue Mar 20 22:49:37 2012 +0100
+++ b/parray.c	Mon Mar 26 10:24:49 2012 +0200
@@ -34,12 +34,13 @@
 	arr->malloc	= (arr->malloc == NULL) ? &malloc : arr->malloc;
 	arr->realloc	= (arr->realloc == NULL) ? &realloc : arr->realloc;
 
+	arr->bsize	+= (arr->flags & PARRAY_NULLEND) ? 1 : 0;
 	arr->size	= LENGTH(arr->bsize);
 
 	if ((arr->data = arr->malloc(arr->size)) == NULL)
 		return -1;
 
-	memset(arr->data, 0, LENGTH(arr->bsize));
+	memset(arr->data, 0, arr->size);
 
 	return 0;
 }
@@ -49,7 +50,7 @@
  * l -> optional array block size of type int
  * m -> malloc function that must matches void * (*malloc)(size_t)
  * r -> realloc function that must matches void * (*realloc)(void *, size_t)
- * t -> type of array of type int
+ * f -> parray flags of type int
  */
 
 void
@@ -70,8 +71,8 @@
 		case 'r':
 			arr->realloc = va_arg(ap, void * (*)(void *, size_t));
 			break;
-		case 't':
-			arr->type = va_arg(ap, int);
+		case 'f':
+			arr->flags = va_arg(ap, int);
 			break;
 		default:
 			break;
@@ -93,6 +94,9 @@
 	memmove(&arr->data[1], &arr->data[0], LENGTH(arr->length++));
 	arr->data[0] = data;
 
+	if (arr->flags & PARRAY_NULLEND)
+		arr->data[arr->length] = NULL;
+
 	return 0;
 }
 
@@ -114,6 +118,9 @@
 		LENGTH(arr->length++ - index));
 	arr->data[index] = data;
 
+	if (arr->flags & PARRAY_NULLEND)
+		arr->data[arr->length] = NULL;
+
 	return 0;
 }
 
@@ -129,6 +136,9 @@
 
 	arr->data[arr->length++] = data;
 
+	if (arr->flags & PARRAY_NULLEND)
+		arr->data[arr->length] = NULL;
+
 	return 0;
 }
 
@@ -139,10 +149,7 @@
 void
 parray_pop(struct parray *arr)
 {
-	if (arr->length > 0) {
-		memmove(&arr->data[0], &arr->data[1], LENGTH(--arr->length));
-		arr->data[arr->length] = NULL;
-	}
+	parray_iremove(arr, 0);
 }
 
 /*
@@ -152,8 +159,7 @@
 void
 parray_unqueue(struct parray *arr)
 {
-	if (arr->length > 0)
-		arr->data[--arr->length] = NULL;
+	parray_iremove(arr, arr->length - 1);
 }
 
 /*
@@ -164,10 +170,14 @@
 parray_iremove(struct parray *arr, int index)
 {
 	if (arr->length > 0 && index >= 0 && index < arr->length) {
-		memmove(&arr->data[index], &arr->data[index + 1],
-		    LENGTH(arr->length - index - 1));
-		arr->data[--arr->length] = NULL;
+		if (arr->flags & PARRAY_FASTREMOVE)
+			arr->data[index] = arr->data[--arr->length];
+		else
+			memmove(&arr->data[index], &arr->data[index + 1],
+			    LENGTH(arr->length-- - index - 1));
 	}
+
+	arr->data[arr->length] = NULL;
 }
 
 /*
@@ -272,6 +282,33 @@
 	return (st) ? i - 1 : -1;
 }
 
+void *
+parray_first(const struct parray *arr)
+{
+	return arr->data[0];
+}
+
+void *
+parray_last(const struct parray *arr)
+{
+	if (arr->length == 0)
+		return parray_first(arr);
+
+	return arr->data[arr->length - 1];
+
+}
+
+void *
+parray_index(const struct parray *arr, int idx)
+{
+	if (idx < 0)
+		return parray_first(arr);
+	if (idx >= arr->length)
+		return parray_last(arr);
+
+	return arr->data[idx];
+}
+
 /*
  * Reset the array by setting each pointer to NULL and the length to 0.
  */
@@ -279,8 +316,8 @@
 void
 parray_clear(struct parray *arr)
 {
-	memset(arr->data, 0, arr->size);
-	arr->length = 0;
+	arr->data[0]	= NULL;
+	arr->length	= 0;
 }
 
 /*
@@ -290,7 +327,11 @@
 void
 parray_free(struct parray *arr)
 {
+	parray_clear(arr);
 	free(arr->data);
+
+	arr->data	= NULL;
+	arr->size	= 0;
 }
 
 /*
@@ -302,13 +343,19 @@
 static int
 grow(struct parray *arr)
 {
-	if ((arr->size / sizeof (void *)) > (size_t) arr->length)
+	int toadd;
+
+	toadd = (arr->flags & PARRAY_NULLEND) ? 2 : 1;
+
+	if ((arr->size / sizeof (void *)) - arr->length >= toadd)
 		return 0;
 
-	if (arr->type == PARRAY_AUTO) {
+	if (!(arr->flags & PARRAY_FIXED)) {
 		if ((arr->data = arr->realloc(arr->data, arr->size +
-		    LENGTH(arr->bsize))) == NULL)
+		    LENGTH(arr->bsize))) == NULL) {
+			arr->size = arr->length = 0;
 			return -1;
+		}
 
 		arr->size += LENGTH(arr->bsize);
 	} else
--- a/parray.h	Tue Mar 20 22:49:37 2012 +0100
+++ b/parray.h	Mon Mar 26 10:24:49 2012 +0200
@@ -1,5 +1,5 @@
 /*
- * array.h -- manipulate dynamic pointer arrays
+ * parray.h -- manipulate dynamic pointer arrays
  *
  * Copyright (c) 2011, 2012, David Demelier <markand@malikania.fr>
  *
@@ -30,12 +30,14 @@
 #endif
 
 enum {
-	PARRAY_AUTO	= 0,
-	PARRAY_FIXED	= 1
+	PARRAY_AUTO		= 0,		/* array grows automatically */
+	PARRAY_FIXED		= (1 << 0),	/* fixed size length */
+	PARRAY_FASTREMOVE	= (1 << 1),	/* use last object when removing */
+	PARRAY_NULLEND		= (1 << 2)	/* always has a NULL pointer at end */
 };
 
 struct parray {
-	int	type;		/* (ro) array type (default FIXED) */
+	int	flags;		/* (ro) array flags (default AUTO) */
 	void	**data;		/* (rw) array of data */
 	int	length;		/* (ro) number of element inside */
 	size_t	size;		/* (ro) current buffer size (allocated memory) */
@@ -88,6 +90,15 @@
 int
 parray_find(const struct parray *, parray_cmp_fn, void *, void *);
 
+void *
+parray_first(const struct parray *);
+
+void *
+parray_last(const struct parray *);
+
+void *
+parray_index(const struct parray *, int);
+
 void
 parray_clear(struct parray *);