rewrite of talloc with double linked lists

[andreas moroder]

Hello,

after my first attempt to rewrite talloc.c that has never appeared in the 
cvs, now I try it a second time. This time I use double linked lists to speed 
up talloc_realloc. 

In the original code if you wanted to realloc memory, talloc_realloc did loop 
through the list to find the memory item you wanted to realloc. Now this loop 
is not necessary and the speed of talloc_realloc does not depend of the size 
of the list.

Here my diff against talloc.c and talloc.h of samba 2.2.1a

--- talloc.c	Sat Sep  1 18:12:54 2001
+++ talloc_dll.c	Sat Sep  1 18:19:01 2001
@@ -1,4 +1,4 @@
-/* 
+/*
    Unix SMB/Netbios implementation.
    Version 3.0
    Samba temporary memory allocation functions
@@ -17,7 +17,7 @@
    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
-*/
+ */
 
 /* this is a very simple temporary memory allocator. To use it do the 
following:
 
@@ -35,6 +35,16 @@
 
 #include "includes.h"
 
+/* If there are systems that must allign on a bigger boundary then  8
+   the constant must be changed */
+
+#define TALLOC_NEW_ALLIGN	8
+
+#define TALLOC_MAGIC 		0x536D4261
+
+#define	TALLOC_OFFSET (((sizeof(struct talloc_chunk)-1) & 
(0x100-TALLOC_NEW_ALLIGN))+TALLOC_NEW_ALLIGN)
+
+
 /* initialise talloc context. */
 TALLOC_CTX *talloc_init(void)
 {
@@ -43,7 +53,8 @@
 	t = (TALLOC_CTX *)malloc(sizeof(*t));
 	if (!t) return NULL;
 
-	t->list = NULL;
+	t->next = (struct talloc_chunk *) t;
+	t->prev = (struct talloc_chunk *) t;
 	t->total_alloc_size = 0;
 
 	return t;
@@ -52,72 +63,128 @@
 /* allocate a bit of memory from the specified pool */
 void *talloc(TALLOC_CTX *t, size_t size)
 {
-	void *p;
+	void *p,*mb;
+	long *magic;
 	struct talloc_chunk *tc;
 
 	if (size == 0) return NULL;
 
-	p = malloc(size);
-	if (!p) return p;
-
-	tc = malloc(sizeof(*tc));
+	tc = malloc(TALLOC_OFFSET+size);
 	if (!tc) {
-		free(p);
 		return NULL;
 	}
 
+	p=(void *)tc;
+	p+=TALLOC_OFFSET;
+
 	tc->ptr = p;
 	tc->size = size;
-	tc->next = t->list;
-	t->list = tc;
+	tc->next = t->next;
+	tc->prev = tc->next->prev;
+
+	tc->next->prev=tc;
+
+	t->next = tc;
 	t->total_alloc_size += size;
 
+	mb=p-4;
+	magic=mb;
+	*magic=TALLOC_MAGIC;
+
 	return p;
 }
 
+BOOL talloc_ismagic(void *ptr)
+{
+	void *tmp;
+	long *magic;
+	
+	if (ptr==NULL)
+		return FALSE;
+	tmp=ptr-4;
+	magic=tmp;
+
+	if (*magic==TALLOC_MAGIC)
+		return TRUE;
+	return FALSE;
+}
+
 /* a talloc version of realloc */
 void *talloc_realloc(TALLOC_CTX *t, void *ptr, size_t size)
 {
-	struct talloc_chunk *tc;
+	struct talloc_chunk *tc, *prev,*next;
+	void *p;
 
-	/* size zero is equivalent to free() */
-	if (size == 0)
+	if (!talloc_ismagic(ptr)) {
+		DEBUG(0,("TALLOC: realloc of not talloc type memory\n"));
+		printf("MEMORY TYPE\n");
 		return NULL;
+	}
 
 	/* realloc(NULL) is equavalent to malloc() */
-	if (ptr == NULL)
-		return talloc(t, size);
 
-	for (tc=t->list; tc; tc=tc->next) {
-		if (tc->ptr == ptr) {
-			ptr = realloc(ptr, size);
-			if (ptr) {
-				t->total_alloc_size += (size - tc->size);
-				tc->size = size;
-				tc->ptr = ptr;
-			}
-			return ptr;
+	if (ptr == NULL) {
+		if(size == 0) {
+			DEBUG(0,("talloc with NULL pointer and 0 size\n"));
+			return NULL;
 		}
+		return talloc(t, size);
+	};
+
+	tc=ptr-TALLOC_OFFSET;
+	prev=tc->prev;
+	next=tc->next;
+
+	/* Now we could even free the single block */
+	/* size zero is equivalent to free() */
+	if (size == 0) {
+		tc->prev->next=next;
+		tc->next->prev=prev;
+		free(tc);
+		return NULL;
 	}
-	return NULL;
+
+	ptr = realloc(tc, size+TALLOC_OFFSET);
+	if (ptr) {
+		tc=ptr;
+		p=(void *)tc;
+		p+=TALLOC_OFFSET;
+		tc->ptr = p;
+		t->total_alloc_size += (size - tc->size);
+		tc->size = size;
+		
+
+		prev->next=tc;
+		next->prev=tc;
+
+		ptr=p;
+	} else {
+		DEBUG(0,("Talloc: reallocation error\n"));
+		free(tc);
+		prev->next=next;
+		next->prev=prev;
+	}
+	return ptr;
 }
 
 /* destroy a whole pool */
 void talloc_destroy_pool(TALLOC_CTX *t)
 {
-	struct talloc_chunk *c;
+	struct talloc_chunk *c,*n;
 	
 	if (!t)
 		return;
+	n=t->next;
+	c=n;
 
-	while (t->list) {
-		c = t->list->next;
-		if (t->list->ptr) free(t->list->ptr);
-		free(t->list);
-		t->list = c;
+	while ((struct talloc_chunk *) t!=c) {
+		n=c->next;
+		free(c);
+		c=n;
 	}
 
-	t->list = NULL;
+	t->next = (struct talloc_chunk *) t;
+	t->prev = (struct talloc_chunk *) t;
 	t->total_alloc_size = 0;
 }
 
@@ -151,11 +218,26 @@
 /* memdup with a talloc. */
 void *talloc_memdup(TALLOC_CTX *t, void *p, size_t size)
 {
-	void *newp = talloc(t,size);
+	struct talloc_chunk *tc;
+	void *newp;
 
-	if (!newp)
+	if (p==NULL) {
+		DEBUG(0,("talloc_memdup ptr is null\n"));
+		return 0;
+	}
+	if ( ! talloc_ismagic(p))
 		return 0;
 
+	tc=p-TALLOC_OFFSET;
+	if (tc->size<size) {
+		size=tc->size;
+		DEBUG(0,("talloc_memdup size error\n"));
+	}
+
+	newp = talloc(t,size);
+
+	if (!newp)
+		return 0;
 	memcpy(newp, p, size);
 
 	return newp;
@@ -166,3 +248,4 @@
 {
 	return talloc_memdup(t, p, strlen(p) + 1);
 }
+




--- talloc.h	Sat Sep  1 18:20:12 2001
+++ talloc.new	Sat Sep  1 18:20:05 2001
@@ -23,12 +23,15 @@
 
 struct talloc_chunk {
 	struct talloc_chunk *next;
+	struct talloc_chunk *prev;
 	size_t size;
 	void *ptr;
+	char dummy[4];
 };
 
 typedef struct {
-	struct talloc_chunk *list;
+	struct talloc_chunk *next;
+	struct talloc_chunk *prev;
 	size_t total_alloc_size;
 } TALLOC_CTX;
 

I hope this version will find the way into the cvs.