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