[ntp:hackers] singly-linked list template macros for NTP

Danny Mayer mayer at ntp.org
Tue Jul 14 03:18:34 UTC 2009

Dave Hart wrote:
> NTP uses several different linked list implementations today.
> ntp_peer.c maintains singly-linked lists for two peer hash tables as
> well as a freelist of peer structures.  There's a good deal of
> duplication, particularly for the peer_hash and assoc_hash arrays of
> lists.  ntp_parser.y and ntp_config.c use FIFO priority queues as
> singly-linked lists.  ntp_io.c and a few other files use ISC's
> doubly-linked list template macros.  In all but one case, the overhead
> of doubly-linked lists is overkill for the way the list is used.
> I've written a set of preprocessor macros to implement singly-linked
> list management, and converted ntp_peer.c and most of ntp_io.c to use
> them.  To avoid merge hassles, I have not changed the use of FIFO
> priority queues for the parse tree, because Max is making changes to
> that code right now.
> Below is a repurposed comment block documenting the interface exposed
> by the proposed include/ntp_lists.h.  See:
> http://bugs.ntp.org/1246
> which has the patch attached to it.
> Comments and suggestions for improvement are welcomed.
> Cheers,
> Dave Hart

I have already stated that this is a waste of time and effort to remove
doubly linked lists. Singly-linked lists are not simpler or faster and
has the amount of memory used by doubly linked lists is negligible.
There is no overkill involved and the task of adding or removing items
from the middle of the list is far easier. Please do not do this
particularly to ntp_io.c or ntp_peer.c which definitely do need and use
the doubly linked lists. You need to be able to add and remove in the
middle and that need will be increasing in the future. All you are doing
is replacing one set of macros for another and at least the ISC ones
have been debugged and been used for many years and are known to be


This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.

More information about the hackers mailing list