Using BSD queue.h for linked lists

[ghudson@MIT.EDU]

MIT krb5 makes limited use of linked data structures, generally
preferring to use arrays for short collections (like pa-data,
authdata, enctype lists, etc.).  We do have a dozen or so uses of
linked lists, but mostly they are singly-linked lists with limited
modification operations (like the list of availale ccache types).
These are very easy to get right.

In the rare cases where we need more complicated structures, it's much
easier to mess up.  For the improved lookaside cache, for example, we
need each cache entry to be part of two lists (a hash bucket for fast
lookup and an insertion-ordered queue for fast expiration of stale
entries), and we need to be able to find an entry in one list and
remove it from both, so each list needs to be doubly-linked.

Tom suggested that we use a standard implementation and further
suggested the *BSD <sys/queue.h> as a candidate.  queue.h has the
properties that:

* It supports six kinds of lists.
* Pointers are embedded in list entries, so you don't need to
  separately allocate entry containers.
* It has no dependencies to speak of.  It's just a header file with no
  library support code, and the header relies on nothing other than
  that NULL be defined.
* It does involve macro expansion to multiple lines of code, usually
  2-4 lines for the simpler structures.  The macro expansions do only
  pointer manipulation, no memory allocation.

If we were to go in this direction, we'd probably make a copy of the
latest NetBSD version of the header in include/k5-queue.h, and
recommend that it be used for even simple lists.  For illustration,
here are some fragments showing how it could be used in the lookaside
cache:

    struct entry {
        LIST_ENTRY(entry) bucket_links;
        TAILQ_ENTRY(entry) expire_links;
        int num_hits;
	[... other field ...]
    };

    LIST_HEAD(entry_list, entry);
    TAILQ_HEAD(entry_queue, entry);
    static struct entry_list hash_table[LOOKASIDE_HASH_SIZE];
    static struct entry_queue expiration_queue;

    [discarding a list entry]
        LIST_REMOVE(entry, bucket_links);
        TAILQ_REMOVE(&expiration_queue, entry, expire_links);
        [... free the actual entry structure ...]

    [purging entries from the expiration queue]
        TAILQ_FOREACH_SAFE(e, &expiration_queue, expire_links, next) {
            if (!STALE(e, timenow))
                break;
            discard_entry(kdc_context, e);
        }

    [adding an entry]
        TAILQ_INSERT_TAIL(&expiration_queue, e, expire_links);
        LIST_INSERT_HEAD(&hash_table[hash], e, bucket_links);

Does this seem like a reasonable direction?