rewrite of talloc with double linked lists
andreas moroder
claudiamoroder at st-ulrich.suedtirol.net
Sat Sep 1 16:26:28 GMT 2001
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.
More information about the samba-technical
mailing list