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>