rewrite of talloc with double linked lists

[Christopher R. Hertel]

> 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


Andreas,

Thanks for this.  We're all swamped but I did take a quick look.  I have
one comment (which I hope won't be annoying). 

Samba has two standard doubly-linked list utilities built in.  It *looks*
(from my initial once-over) as though your code does its own linked list
handling.  Could you take a look at includes/dlinklist.h and
ubiqx/ubi_dLinkList?  One of these should suit the need.  It's just that
using the same code means that small bugs and such (particularly those
introduced when someone fiddles with the code later on) are easier to
track down. 

...oh, and I understand your complaint about singly-linked lists and such. 
At one time, Samba's WINS server was done entirely with linked lists.  
When the WINS database got large...ouch!  That list now uses a Splay 
Tree, which is just about as fast as a hash table.

I'm not clear on what you did with the doubly-linked lists in Talloc, but 
if you think a splay tree or even a simple binary tree would be faster 
just let me know and I'll show you how that code works.

Chris -)-----

-- 
Christopher R. Hertel -)-----                   University of Minnesota
crh at nts.umn.edu              Networking and Telecommunications Services

    Ideals are like stars; you will not succeed in touching them
    with your hands...you choose them as your guides, and following
    them you will reach your destiny.  --Carl Schultz