• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /**
2  * \file simple_list.h
3  * Simple macros for type-safe, intrusive lists.
4  *
5  *  Intended to work with a list sentinal which is created as an empty
6  *  list.  Insert & delete are O(1).
7  *
8  * \author
9  *  (C) 1997, Keith Whitwell
10  */
11 
12 /*
13  * Mesa 3-D graphics library
14  *
15  * Copyright (C) 1999-2001  Brian Paul   All Rights Reserved.
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining a
18  * copy of this software and associated documentation files (the "Software"),
19  * to deal in the Software without restriction, including without limitation
20  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
21  * and/or sell copies of the Software, and to permit persons to whom the
22  * Software is furnished to do so, subject to the following conditions:
23  *
24  * The above copyright notice and this permission notice shall be included
25  * in all copies or substantial portions of the Software.
26  *
27  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
28  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
29  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
30  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
31  * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
32  * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
33  * OTHER DEALINGS IN THE SOFTWARE.
34  */
35 
36 
37 #ifndef _SIMPLE_LIST_H
38 #define _SIMPLE_LIST_H
39 
40 #ifdef __cplusplus
41 extern "C" {
42 #endif
43 
44 struct simple_node {
45    struct simple_node *next;
46    struct simple_node *prev;
47 };
48 
49 /**
50  * Remove an element from list.
51  *
52  * \param elem element to remove.
53  */
54 #define remove_from_list(elem)			\
55 do {						\
56    (elem)->next->prev = (elem)->prev;		\
57    (elem)->prev->next = (elem)->next;		\
58    make_empty_list(elem);			\
59 } while (0)
60 
61 /**
62  * Insert an element to the list head.
63  *
64  * \param list list.
65  * \param elem element to insert.
66  */
67 #define insert_at_head(list, elem)		\
68 do {						\
69    (elem)->prev = list;				\
70    (elem)->next = (list)->next;			\
71    (list)->next->prev = elem;			\
72    (list)->next = elem;				\
73 } while(0)
74 
75 /**
76  * Insert an element to the list tail.
77  *
78  * \param list list.
79  * \param elem element to insert.
80  */
81 #define insert_at_tail(list, elem)		\
82 do {						\
83    (elem)->next = list;				\
84    (elem)->prev = (list)->prev;			\
85    (list)->prev->next = elem;			\
86    (list)->prev = elem;				\
87 } while(0)
88 
89 /**
90  * Move an element to the list head.
91  *
92  * \param list list.
93  * \param elem element to move.
94  */
95 #define move_to_head(list, elem)		\
96 do {						\
97    remove_from_list(elem);			\
98    insert_at_head(list, elem);			\
99 } while (0)
100 
101 /**
102  * Move an element to the list tail.
103  *
104  * \param list list.
105  * \param elem element to move.
106  */
107 #define move_to_tail(list, elem)		\
108 do {						\
109    remove_from_list(elem);			\
110    insert_at_tail(list, elem);			\
111 } while (0)
112 
113 /**
114  * Make a empty list empty.
115  *
116  * \param sentinal list (sentinal element).
117  */
118 #define make_empty_list(sentinal)		\
119 do {						\
120    (sentinal)->next = sentinal;			\
121    (sentinal)->prev = sentinal;			\
122 } while (0)
123 
124 /**
125  * Get list first element.
126  *
127  * \param list list.
128  *
129  * \return pointer to first element.
130  */
131 #define first_elem(list)       ((list)->next)
132 
133 /**
134  * Get list last element.
135  *
136  * \param list list.
137  *
138  * \return pointer to last element.
139  */
140 #define last_elem(list)        ((list)->prev)
141 
142 /**
143  * Get next element.
144  *
145  * \param elem element.
146  *
147  * \return pointer to next element.
148  */
149 #define next_elem(elem)        ((elem)->next)
150 
151 /**
152  * Get previous element.
153  *
154  * \param elem element.
155  *
156  * \return pointer to previous element.
157  */
158 #define prev_elem(elem)        ((elem)->prev)
159 
160 /**
161  * Test whether element is at end of the list.
162  *
163  * \param list list.
164  * \param elem element.
165  *
166  * \return non-zero if element is at end of list, or zero otherwise.
167  */
168 #define at_end(list, elem)     ((elem) == (list))
169 
170 /**
171  * Test if a list is empty.
172  *
173  * \param list list.
174  *
175  * \return non-zero if list empty, or zero otherwise.
176  */
177 #define is_empty_list(list)    ((list)->next == (list))
178 
179 /**
180  * Walk through the elements of a list.
181  *
182  * \param ptr pointer to the current element.
183  * \param list list.
184  *
185  * \note It should be followed by a { } block or a single statement, as in a \c
186  * for loop.
187  */
188 #define foreach(ptr, list)     \
189         for( ptr=(list)->next ;  ptr!=list ;  ptr=(ptr)->next )
190 
191 /**
192  * Walk through the elements of a list.
193  *
194  * Same as #foreach but lets you unlink the current value during a list
195  * traversal.  Useful for freeing a list, element by element.
196  *
197  * \param ptr pointer to the current element.
198  * \param t temporary pointer.
199  * \param list list.
200  *
201  * \note It should be followed by a { } block or a single statement, as in a \c
202  * for loop.
203  */
204 #define foreach_s(ptr, t, list)   \
205         for(ptr=(list)->next,t=(ptr)->next; list != ptr; ptr=t, t=(t)->next)
206 
207 #ifdef __cplusplus
208 }
209 #endif
210 
211 #endif
212