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 _______________________________________________ Bug-make mailing list Bug-make@gnu.org http://lists.gnu.org/mailman/listinfo/bug-make