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

Dave Hart davehart at gmail.com
Tue Jul 14 01:41:12 UTC 2009


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

 * LINK_SLIST(listhead, pentry, nextlink)
 *	add entry at head
 *
 * LINK_TAIL_SLIST(listhead, pentry, nextlink, entrytype)
 *	add entry at tail
 *
 * UNLINK_HEAD_SLIST(punlinked, listhead, nextlink)
 *	unlink first entry and point punlinked to it, or set punlinked
 *	to NULL if the list is empty.
 *
 * UNLINK_SLIST(punlinked, listhead, ptounlink, nextlink, entrytype)
 *	unlink entry pointed to by ptounlink.  punlinked is set to NULL
 *	if the entry is not found on the list, otherwise it is set to
 *	ptounlink.
 *
 * UNLINK_EXPR_SLIST(punlinked, listhead, expr, nextlink, entrytype)
 *	unlink entry where expression expr is nonzero.  expr can refer
 *	to the entry being tested using UNLINK_EXPR_SLIST_CURRENT().
 *	See the	implementation of UNLINK_SLIST() below for an example.
 *	punlinked is pointed to the removed entry or NULL if none
 *	satisfy expr.

[...]

The example is:

#define UNLINK_SLIST(punlinked, listhead, ptounlink, nextlink,	\
		     entrytype)					\
	UNLINK_EXPR_SLIST(punlinked, listhead, (ptounlink) ==	\
	    UNLINK_EXPR_SLIST_CURRENT(), nextlink, entrytype)

Scan the patch for other uses of UNLINK_EXPR_SLIST and
UNLINK_EXPR_SLIST_CURRENT()


More information about the hackers mailing list