[patch] dlinklist.h rewrite

[tridge at samba.org]

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.

Cheers, Tridge