Contiki-NG
list.h
Go to the documentation of this file.
1/*
2 * Copyright (c) 2004, Swedish Institute of Computer Science.
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. Neither the name of the Institute nor the names of its contributors
14 * may be used to endorse or promote products derived from this software
15 * without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27 * SUCH DAMAGE.
28 *
29 * This file is part of the Contiki operating system.
30 *
31 * Author: Adam Dunkels <adam@sics.se>
32 *
33 */
34
35/**
36 * \file
37 * Linked list manipulation routines.
38 * \author Adam Dunkels <adam@sics.se>
39 *
40 */
41
42/** \addtogroup data
43 @{ */
44/**
45 * \defgroup list Linked list library
46 *
47 * The linked list library provides a set of functions for
48 * manipulating linked lists.
49 *
50 * A linked list is made up of elements where the first element \b
51 * must be a pointer. This pointer is used by the linked list library
52 * to form lists of the elements.
53 *
54 * Lists are declared with the LIST() macro. The declaration specifies
55 * the name of the list that later is used with all list functions.
56 *
57 * Lists can be manipulated by inserting or removing elements from
58 * either sides of the list (list_push(), list_add(), list_pop(),
59 * list_chop()). A specified element can also be removed from inside a
60 * list with list_remove(). The head and tail of a list can be
61 * extracted using list_head() and list_tail(), respectively.
62 *
63 * This library is not safe to be used within an interrupt context.
64 * @{
65 */
66
67#ifndef LIST_H_
68#define LIST_H_
69
70#include <stdbool.h>
71
72#define LIST_CONCAT2(s1, s2) s1##s2
73#define LIST_CONCAT(s1, s2) LIST_CONCAT2(s1, s2)
74
75/**
76 * Declare a linked list.
77 *
78 * This macro declares a linked list with the specified \c type. The
79 * type \b must be a structure (\c struct) with its first element
80 * being a pointer. This pointer is used by the linked list library to
81 * form the linked lists.
82 *
83 * The list variable is declared as static to make it easy to use in a
84 * single C module without unnecessarily exporting the name to other
85 * modules.
86 *
87 * \param name The name of the list.
88 */
89#define LIST(name) \
90 static void *LIST_CONCAT(name,_list) = NULL; \
91 static list_t name = (list_t)&LIST_CONCAT(name,_list)
92
93/**
94 * Declare a linked list inside a structure declaraction.
95 *
96 * This macro declares a linked list with the specified \c type. The
97 * type \b must be a structure (\c struct) with its first element
98 * being a pointer. This pointer is used by the linked list library to
99 * form the linked lists.
100 *
101 * Internally, the list is defined as two items: the list itself and a
102 * pointer to the list. The pointer has the name of the parameter to
103 * the macro and the name of the list is a concatenation of the name
104 * and the suffix "_list". The pointer must point to the list for the
105 * list to work. Thus the list must be initialized before using.
106 *
107 * The list is initialized with the LIST_STRUCT_INIT() macro.
108 *
109 * \param name The name of the list.
110 */
111#define LIST_STRUCT(name) \
112 void *LIST_CONCAT(name,_list); \
113 list_t name
114
115/**
116 * Initialize a linked list that is part of a structure.
117 *
118 * This macro sets up the internal pointers in a list that has been
119 * defined as part of a struct. This macro must be called before using
120 * the list.
121 *
122 * \param struct_ptr A pointer to the struct
123 * \param name The name of the list.
124 */
125#define LIST_STRUCT_INIT(struct_ptr, name) \
126 do { \
127 (struct_ptr)->name = &((struct_ptr)->LIST_CONCAT(name,_list)); \
128 (struct_ptr)->LIST_CONCAT(name,_list) = NULL; \
129 list_init((struct_ptr)->name); \
130 } while(0)
131
132/**
133 * The linked list type.
134 */
135typedef void ** list_t;
136
137/**
138 * The non-modifiable linked list type.
139 */
140typedef void *const *const_list_t;
141
142/**
143 * Initialize a list.
144 *
145 * This function initalizes a list. The list will be empty after this
146 * function has been called.
147 *
148 * \param list The list to be initialized.
149 */
150void list_init(list_t list);
151
152/**
153 * Get a pointer to the first element of a list.
154 *
155 * This function returns a pointer to the first element of the
156 * list. The element will \b not be removed from the list.
157 *
158 * \param list The list.
159 * \return A pointer to the first element on the list.
160 *
161 * \sa list_tail()
162 */
163void * list_head(const_list_t list);
164
165/**
166 * Get the tail of a list.
167 *
168 * This function returns a pointer to the elements following the first
169 * element of a list. No elements are removed by this function.
170 *
171 * \param list The list
172 * \return A pointer to the element after the first element on the list.
173 *
174 * \sa list_head()
175 */
176void * list_tail(const_list_t list);
177
178/**
179 * Remove the first object on a list.
180 *
181 * This function removes the first object on the list and returns a
182 * pointer to it.
183 *
184 * \param list The list.
185 * \return Pointer to the removed element of list.
186 */
187void * list_pop (list_t list);
188
189/**
190 * Add an item to the start of the list.
191 */
192void list_push(list_t list, void *item);
193
194/**
195 * Remove the last object on the list.
196 *
197 * This function removes the last object on the list and returns it.
198 *
199 * \param list The list
200 * \return The removed object
201 *
202 */
203void * list_chop(list_t list);
204
205/**
206 * Add an item at the end of a list.
207 *
208 * This function adds an item to the end of the list.
209 *
210 * \param list The list.
211 * \param item A pointer to the item to be added.
212 *
213 * \sa list_push()
214 *
215 */
216void list_add(list_t list, void *item);
217
218/**
219 * Remove a specific element from a list.
220 *
221 * This function removes a specified element from the list.
222 *
223 * \param list The list.
224 * \param item The item that is to be removed from the list.
225 *
226 */
227void list_remove(list_t list, const void *item);
228
229/**
230 * Get the length of a list.
231 *
232 * This function counts the number of elements on a specified list.
233 *
234 * \param list The list.
235 * \return The length of the list.
236 */
237int list_length(const_list_t list);
238
239/**
240 * Duplicate a list.
241 *
242 * This function duplicates a list by copying the list reference, but
243 * not the elements.
244 *
245 * \note This function does \b not copy the elements of the list, but
246 * merely duplicates the pointer to the first element of the list.
247 *
248 * \param dest The destination list.
249 * \param src The source list.
250 */
251void list_copy(list_t dest, const_list_t src);
252
253/**
254 * \brief Insert an item after a specified item on the list
255 * \param list The list
256 * \param previtem The item after which the new item should be inserted
257 * \param newitem The new item that is to be inserted
258 * \author Adam Dunkels
259 *
260 * This function inserts an item right after a specified
261 * item on the list. This function is useful when using
262 * the list module to ordered lists.
263 *
264 * If previtem is NULL, the new item is placed at the
265 * start of the list.
266 *
267 */
268void list_insert(list_t list, void *previtem, void *newitem);
269
270/**
271 * \brief Get the next item following this item
272 * \param item A list item
273 * \returns A next item on the list
274 *
275 * This function takes a list item and returns the next
276 * item on the list, or NULL if there are no more items on
277 * the list. This function is used when iterating through
278 * lists.
279 */
280void * list_item_next(const void *item);
281
282/**
283 * \brief Check if the list contains an item
284 * \param list The list that is checked
285 * \param item An item to look for in the list
286 * \returns 0 if the list does not contains the item, and 1 otherwise
287 *
288 * This function searches for an item in the list and returns
289 * 0 if the list does not contain the item, and 1 if the item
290 * is present in the list.
291 */
292bool list_contains(const_list_t list, const void *item);
293
294#endif /* LIST_H_ */
295
296/** @} */
297/** @} */
void list_init(list_t list)
Initialize a list.
Definition: list.c:57
void * list_chop(list_t list)
Remove the last object on the list.
Definition: list.c:118
int list_length(const_list_t list)
Get the length of a list.
Definition: list.c:178
void list_add(list_t list, void *item)
Add an item at the end of a list.
Definition: list.c:89
void list_remove(list_t list, const void *item)
Remove a specific element from a list.
Definition: list.c:152
void * list_pop(list_t list)
Remove the first object on a list.
Definition: list.c:140
void * list_item_next(const void *item)
Get the next item following this item.
Definition: list.c:203
void ** list_t
The linked list type.
Definition: list.h:135
void list_push(list_t list, void *item)
Add an item to the start of the list.
Definition: list.c:108
void * list_head(const_list_t list)
Get a pointer to the first element of a list.
Definition: list.c:63
bool list_contains(const_list_t list, const void *item)
Check if the list contains an item.
Definition: list.c:209
void *const * const_list_t
The non-modifiable linked list type.
Definition: list.h:140
void list_copy(list_t dest, const_list_t src)
Duplicate a list.
Definition: list.c:69
void * list_tail(const_list_t list)
Get the tail of a list.
Definition: list.c:75
void list_insert(list_t list, void *previtem, void *newitem)
Insert an item after a specified item on the list.
Definition: list.c:191