1 /*
2 * Copyright (C) 2007 Claus-Justus Heine
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 2, or (at your option)
7 any later version.
8
9 This program is distributed in the hope that it will be useful, but
10 WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program; see the file COPYING. If not, write to the
16 Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
17
18 Simple doubly linked list implementation. Somewhat inspired from the
19 stuff used in the Linux kernel.
20
21 */
22
23 #ifndef _GV_LIST_H_
24 #define _GV_LIST_H_
25
26 typedef struct dbllistnode
27 {
28 struct dbllistnode *next;
29 struct dbllistnode *prev;
30 } DblListNode;
31
32 /* DblListNode Head = DBLLISTINIT(Head); */
33 #define DBLLISTINIT(name, head) { &name.head, &name.head }
34 #define DBLLIST(name) DblListNode name = { &name, &name }
35
36 /* list is empty if the list head is the only member */
DblListInit(DblListNode * head)37 static inline void DblListInit(DblListNode *head)
38 {
39 head->next = head;
40 head->prev = head;
41 }
42
DblListEmpty(DblListNode * head)43 static inline bool DblListEmpty(DblListNode *head)
44 {
45 return head->next == head;
46 }
47
48 /* add in front, right after head */
DblListAdd(DblListNode * head,DblListNode * node)49 static inline void DblListAdd(DblListNode *head, DblListNode *node)
50 {
51 node->next = head->next;
52 head->next->prev = node;
53 head->next = node;
54 node->prev = head;
55 }
56
57 /* add at the tail, right before head */
DblListAddTail(DblListNode * head,DblListNode * node)58 static inline void DblListAddTail(DblListNode *head, DblListNode *node)
59 {
60 node->prev = head->prev;
61 head->prev->next = node;
62 head->prev = node;
63 node->next = head;
64 }
65
66 /* One nice feature of doubly linked lists is that one does not need a
67 * pointer to the head to do a deletion.
68 */
DblListDelete(DblListNode * node)69 static inline void DblListDelete(DblListNode *node)
70 {
71 node->next->prev = node->prev;
72 node->prev->next = node->next;
73 DblListInit(node);
74 }
75
76 /* Copy an entire DblList, i.e. reparent it, give it a new head.
77 */
DblListMove(DblListNode * fromhead,DblListNode * tohead)78 static inline void DblListMove(DblListNode *fromhead, DblListNode *tohead)
79 {
80 fromhead->next->prev = tohead;
81 fromhead->prev->next = tohead;
82 tohead->next = fromhead->next;
83 tohead->prev = fromhead->prev;
84 }
85
86 /* Given a list-node "node" construct a pointer to the containing
87 * structure of type "ctype" which has a member with name "nodename"
88 * (of type DblListNode).
89 */
90 #define DblListContainer(node, ctype, nodename) \
91 ((ctype *)((char *)(node) - (char *)&((ctype *)0)->nodename))
92
93 /* Iterate over the list; head is the list-head, ctype the type of the
94 * containing structure, nodemember the name of the list-head inside
95 * ctype, pos is the loop variable and must be of type ctype, next is
96 * a temporary helper variable to protect against deletion of list
97 * members.
98 */
99 #define DblListIterate(head, ctype, nodename, pos, nextp) \
100 for (pos = DblListContainer((head)->next, ctype, nodename), \
101 nextp = DblListContainer(pos->nodename.next, ctype, nodename); \
102 pos->nodename.next != (head)->next; \
103 pos = nextp, \
104 nextp = DblListContainer(pos->nodename.next, ctype, nodename))
105
106
107 #define DblListIterateNoDelete(head, ctype, nodename, pos) \
108 for (pos = DblListContainer((head)->next, ctype, nodename); \
109 pos->nodename.next != (head)->next; \
110 pos = DblListContainer(pos->nodename.next, ctype, nodename))
111
112 #endif
113
114 /*
115 * Local Variables: ***
116 * mode: c ***
117 * c-basic-offset: 2 ***
118 * End: ***
119 */
120