Re: prerequisite scaling (was: strcache scaling issue)

[Dave Hart]

Ralf Wildenhues <Ralf.Wildenhues <at> gmx.de> writes:
> A doubly-linked list would be overkill (and memory-intensive), but I
> think storing an end pointer to the dep chain in 'struct file' might
> be prudent.  That requires some changes throughout the code though,
> and warrants some data structure change to avoid the obvious error
> (of updating only ->deps but not ->deps_end).  Maybe a
> 
>   struct dep_list {
>     struct dep *deps;       /* all dependencies, including duplicates */
>     struct dep *last_dep;   /* last dependency in the deps list */
>   };
> 
> (the second one could be a double pointer if removal is ever needed)

Hi Ralf,

All of this is ground well tread before.  BSDs refer to these as
STAILQs, or singly-linked tail queue.  I notice a subset of of the BSD
sys/queue.h macros is present on Debian stable, not including STAILQs,
but perhaps you could pick up that implementation.  [1]

I don't care for the API of BSD's sys/queue.h, so when I needed
similar stuff in ntpd, I adapted it.  I used the identier FIFO.  The
ntp_lists.h header has the implementation [2] while most of the code
using the FIFOs is in ntp_config.c [3] with a healthy chunk in
ntp_parser.y [4].

The BSD STAILQ macros require the elements to be structs and take the
struct tag as a parameter.  NTP's FIFO macros allow the elements to be
any type and take the complete type name as a parameter.  BSD STAILQ
has a more complete set of macros, aligned with the other list
alternatives in sys/queue.h, but I felt it was too heavyweight for the
relatively simple FIFO case.  I didn't provide an iterator macro, for
example, following a singly-linked list is easy enough code to get
right by hand.  BSD's STAILQ stores the address of its distinct head
structure's next pointer in the indirect tail pointer of an empty
STAILQ, NTP's uses NULL for both pointers in an empty FIFO.

I didn't reply on-list as I'm not on the GNU make bugs list, but don't
consider this reply private, forward/repost as you like.

[1]  http://fxr.watson.org/fxr/source/sys/queue.h
[2]  http://ntp.bkbits.net:8080/ntp-dev/include/ntp_lists.h
[3]  http://ntp.bkbits.net:8080/ntp-dev/ntpd/ntp_config.c
[4]  http://ntp.bkbits.net:8080/ntp-dev/ntpd/ntp_parser.y

Cheers,
Dave Hart