[patch] dlinklist.h rewrite

[Jeremy Allison]

On Sat, Feb 06, 2010 at 05:01:15PM +1100, tridge at samba.org wrote:
> Hi Jeremy,
> 
> As we discussed earlier, I have rewritten the dlinklist.h macros to be
> O(1) for operations like DLIST_ADD_END()
> 
> The main patch is here:
> 
>   http://git.samba.org/?p=tridge/samba.git;a=commitdiff;h=3ba777d9b544cb3b781c0aa8d85847ddd959dba9
> 
> The original motivation was to fix a problem with large queues of
> messages in CTDBD, but I would like to apply it to Samba as well. We
> have over 100 places where we use DLIST_ADD_END() and they can all
> benefit a lot from moving to the O(1) system.
> 
> As explained in the new header, the approach is to change the linked
> list to use listhead->prev to point at the list tail. The tail still
> keeps its old value of listtail->next==NULL.
> 
> That means:
> 
>      1) with no entries in the list:
>           list_head == NULL
> 
>      2) with 1 entry in the list:
>           list_head->next == NULL
>           list_head->prev == list_head
> 
>      3) with 2 entries in the list:
>           list_head->next == element2
>           list_head->prev == element2
> 	  element2->prev == list_head
> 	  element2->next == NULL
> 
>      4) with N entries in the list:
>           list_head->next == element2
>           list_head->prev == elementN
> 	  elementN->prev == element{N-1}
> 	  elementN->next == NULL
> 
> This allows us to find the tail of the list by using list_head->prev,
> which means we can add to the end of the list in O(1) time.
> 
> The main change for users of the DLIST macros is that it is no longer
> safe to access el->prev directly. There were a few places in Samba
> that did access ->prev, and I have fixed those up with a series of
> followup patches in my dlist-rewrite branch here:
> 
>   http://git.samba.org/?p=tridge/samba.git;a=shortlog;h=refs/heads/dlist-rewrite
> 
> There was one use case of el->prev in Samba that went from O(1) to
> O(n) with this change, which was the cli_shutdown() code in
> libsmb/clientgen.c. The patch for that is here:
> 
>   http://git.samba.org/?p=tridge/samba.git;a=commitdiff;h=444077f1e9d3f08daf26769dc8f1e3342fefc359
> 
> The reason this was one tricky is that it is removing an element from
> a list without having a pointer to the list head. I added a new
> DLIST_HEAD() macro to make that case a bit easier to follow, but
> DLIST_HEAD() is O(n). I don't think it matters much for this use case
> as we don't expect to have thousands of DFS connections active in our
> client code at once. The benefit to all the other users of the
> DLIST_*() macros is worth this change I think.
> 
> The dlist-rewrite branch passes make test on my box for both Samba4
> and Samba3.

Wow - this looks really nice ! Impressive work !

Getting late here so I'll try and get to reviewing this
either over the weekend or (more likely) on Monday.

Cheers,

	Jeremy.