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  *
135  */
136 typedef void ** list_t;
137 
138 void list_init(list_t list);
139 void * list_head(list_t list);
140 void * list_tail(list_t list);
141 void * list_pop (list_t list);
142 void list_push(list_t list, void *item);
143 
144 void * list_chop(list_t list);
145 
146 void list_add(list_t list, void *item);
147 void list_remove(list_t list, void *item);
148 
149 int list_length(list_t list);
150 
151 void list_copy(list_t dest, list_t src);
152 
153 void list_insert(list_t list, void *previtem, void *newitem);
154 
155 void * list_item_next(void *item);
156 
157 bool list_contains(list_t list, void *item);
158 
159 #endif /* LIST_H_ */
160 
161 /** @} */
162 /** @} */
void list_push(list_t list, void *item)
Add an item to the start of the list.
Definition: list.c:164
void list_copy(list_t dest, list_t src)
Duplicate a list.
Definition: list.c:100
void list_insert(list_t list, void *previtem, void *newitem)
Insert an item after a specified item on the list.
Definition: list.c:300
bool list_contains(list_t list, void *item)
Check if the list contains an item.
Definition: list.c:338
void ** list_t
The linked list type.
Definition: list.h:136
void * list_tail(list_t list)
Get the tail of a list.
Definition: list.c:117
void * list_chop(list_t list)
Remove the last object on the list.
Definition: list.c:183
void * list_head(list_t list)
Get a pointer to the first element of a list.
Definition: list.c:82
void list_add(list_t list, void *item)
Add an item at the end of a list.
Definition: list.c:142
void list_init(list_t list)
Initialize a list.
Definition: list.c:65
void * list_pop(list_t list)
Remove the first object on a list.
Definition: list.c:215
void list_remove(list_t list, void *item)
Remove a specific element from a list.
Definition: list.c:237
void * list_item_next(void *item)
Get the next item following this item.
Definition: list.c:322
int list_length(list_t list)
Get the length of a list.
Definition: list.c:272