[ntp:hackers] singly-linked list template macros for NTP
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:
which has the patch attached to it.
Comments and suggestions for improvement are welcomed.
* 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
* 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, \
UNLINK_EXPR_SLIST(punlinked, listhead, (ptounlink) == \
UNLINK_EXPR_SLIST_CURRENT(), nextlink, entrytype)
Scan the patch for other uses of UNLINK_EXPR_SLIST and
More information about the hackers