Skip site navigation (1)Skip section navigation (2) 
Date:      Thu, 4 Jan 2001 17:47:34 -0800 (PST)
From:      Matt Dillon <dillon@earth.backplane.com>
To:        Peter Wemm <peter@netplex.com.au>
Cc:        Tony Finch <dot@dotat.at>, Kirk McKusick <mckusick@mckusick.com>, Alfred Perlstein <bright@wintelcom.net>, Will Andrews <will@physics.purdue.edu>, Stephen McKay <mckay@thehub.com.au>, phk@FreeBSD.ORG, arch@FreeBSD.ORG
Subject:   Re: Reinstatement of CIRCLEQ 
Message-ID:  <200101050147.f051lYr96332@earth.backplane.com>
References:   <200101050113.f051Dtq61858@mobile.wemm.org>
next in thread | previous in thread | raw e-mail | index | archive | help 

    Basically when implementing a doubly linked list the optimization
    tradeoff comes down to whether you want to remove the conditionals
    from the list scanning routines, or whether you want to remove the
    conditionals from the list insertion and removal routines.

    What it comes down to, in a nutshell, is that a circular-list
    implementation can be done that has no more conditionals then a
    non-circular list implementation.  You simply have a LIST_EOF() macro
    which for a circular queue compares the 'next node' or 'previous node'
    against &listhead (which you probably already have in the L1 cache
    anyway or can calculate trivially, so no biggy).

    I use circular queues all over the place.  Sometimes to make things
    easier (when I don't care about performance as much), I embed tests
    against the list head and return a conventional NULL.  Otherwise I
    compare against the address of the list head, which is always at 
    hand anyway and doesn't cost any extra verses comparing against NULL.
    For embedded systems I use these sorts of doubly linked queues all
    over the scheduler, often with at least one embedded 'real' node
    to remove even more conditionals from the code using the list in question.
    e.g. for a software interrupt queue I have a terminator node with a -1
    software interrupt priority, which of course can never run so the 
    scheduler softint dispatcher stops there, without having to check for
    list EOF on top of testing the software interrupt priorities verses the
    current task priority.

    I just typed this in from memory, so there may be type-o's.

    Oh, by the way, I think *ALL* the list macros in sys/queue.h suck rocks.
    (Sorry Kirk!).

					-Matt


    typedef struct Node {
	struct Node	*no_Succ;
	struct Node	*no_Pred;
    } Node;

    typedef struct List {
	Node	li_Node;
    } List;

    #define LIST_EOF(list)	(&(list)->li_Node)

    static __inline void
    initList(List *list)
    {
	list->li_Node.no_Succ = &list->li_Node;
	list->li_Node.no_Pred = &list->li_Node;
    }

    /*
     * caller tests result against LIST_EOF(list) to determine if the
     * list is empty (verses checking against NULL).  It's one conditional
     * either way.
     */
    static __inline void *
    getListHead(List *list)
    {
	return(list->li_Node.no_Succ);
    }

    static __inline void *
    getListTail(List *list)
    {
	return(list->li_Node.no_Pred);
    }

    static __inline void *
    getListSucc(Node *node)
    {
	return(node->no_Succ);
    }

    static __inline void *
    getListPred(Node *node)
    {
	return(node->no_Pred);
    }

    static __inline void
    insertNodeBefore(Node *lnode, Node *node)
    {
	node->no_Succ = lnode;
	node->no_Pred = lnode->no_Pred;
	node->no_Pred->no_Succ = node;
	lnode->no_Pred = node;
    }

    static __inline void
    insertNodeAfter(Node *lnode, Node *node)
    {
	node->no_Pred = lnode;
	node->no_Succ = lnode->no_Succ;
	node->no_Succ->no_Pred = node;
	lnode->no_Succ = node;
    }

    static __inline void
    addListHead(List *list, Node *node)
    {
	insertNodeAfter(&list->li_Node, node);
    }

    static __inline void
    addListTail(List *list, Node *node)
    {
	insertNodeBefore(&list->li_Node, node);
    }

    static __inline void
    removeNode(Node *node)
    {
	node->no_Succ->no_Pred = node->no_Pred;
	node->no_Pred->no_Succ = node->no_Succ;
    }

    /*
     * Compare result against LIST_EOF(list) to check for empty list
     */
    static __inline void *
    removeListHead(List *list)
    {
	Node *node = list->li_Node.no_Succ;
	removeNode(node);
	return(node);
    }

    static __inline void *
    removeListTail(List *list)
    {
	Node *node = list->li_Node.no_Pred;
	removeNode(node);
	return(node);
    }

						-Matt



To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-arch" in the body of the message

Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200101050147.f051lYr96332>