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
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   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)		\
68do {						\
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)		\
82do {						\
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)		\
96do {						\
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)		\
108do {						\
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)		\
119do {						\
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