Contiki-NG
list.c
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 library implementation.
38  *
39  * \author Adam Dunkels <adam@sics.se>
40  *
41  */
42 
43 /**
44  * \addtogroup list
45  * @{
46  */
47 #include "contiki.h"
48 #include "lib/list.h"
49 
50 #include <string.h>
51 /*---------------------------------------------------------------------------*/
52 struct list {
53  struct list *next;
54 };
55 /*---------------------------------------------------------------------------*/
56 /**
57  * Initialize a list.
58  *
59  * This function initalizes a list. The list will be empty after this
60  * function has been called.
61  *
62  * \param list The list to be initialized.
63  */
64 void
66 {
67  *list = NULL;
68 }
69 /*---------------------------------------------------------------------------*/
70 /**
71  * Get a pointer to the first element of a list.
72  *
73  * This function returns a pointer to the first element of the
74  * list. The element will \b not be removed from the list.
75  *
76  * \param list The list.
77  * \return A pointer to the first element on the list.
78  *
79  * \sa list_tail()
80  */
81 void *
83 {
84  return *list;
85 }
86 /*---------------------------------------------------------------------------*/
87 /**
88  * Duplicate a list.
89  *
90  * This function duplicates a list by copying the list reference, but
91  * not the elements.
92  *
93  * \note This function does \b not copy the elements of the list, but
94  * merely duplicates the pointer to the first element of the list.
95  *
96  * \param dest The destination list.
97  * \param src The source list.
98  */
99 void
101 {
102  *dest = *src;
103 }
104 /*---------------------------------------------------------------------------*/
105 /**
106  * Get the tail of a list.
107  *
108  * This function returns a pointer to the elements following the first
109  * element of a list. No elements are removed by this function.
110  *
111  * \param list The list
112  * \return A pointer to the element after the first element on the list.
113  *
114  * \sa list_head()
115  */
116 void *
118 {
119  struct list *l;
120 
121  if(*list == NULL) {
122  return NULL;
123  }
124 
125  for(l = *list; l->next != NULL; l = l->next);
126 
127  return l;
128 }
129 /*---------------------------------------------------------------------------*/
130 /**
131  * Add an item at the end of a list.
132  *
133  * This function adds an item to the end of the list.
134  *
135  * \param list The list.
136  * \param item A pointer to the item to be added.
137  *
138  * \sa list_push()
139  *
140  */
141 void
142 list_add(list_t list, void *item)
143 {
144  struct list *l;
145 
146  /* Make sure not to add the same element twice */
147  list_remove(list, item);
148 
149  ((struct list *)item)->next = NULL;
150 
151  l = list_tail(list);
152 
153  if(l == NULL) {
154  *list = item;
155  } else {
156  l->next = item;
157  }
158 }
159 /*---------------------------------------------------------------------------*/
160 /**
161  * Add an item to the start of the list.
162  */
163 void
164 list_push(list_t list, void *item)
165 {
166  /* Make sure not to add the same element twice */
167  list_remove(list, item);
168 
169  ((struct list *)item)->next = *list;
170  *list = item;
171 }
172 /*---------------------------------------------------------------------------*/
173 /**
174  * Remove the last object on the list.
175  *
176  * This function removes the last object on the list and returns it.
177  *
178  * \param list The list
179  * \return The removed object
180  *
181  */
182 void *
184 {
185  struct list *l, *r;
186 
187  if(*list == NULL) {
188  return NULL;
189  }
190  if(((struct list *)*list)->next == NULL) {
191  l = *list;
192  *list = NULL;
193  return l;
194  }
195 
196  for(l = *list; l->next->next != NULL; l = l->next);
197 
198  r = l->next;
199  l->next = NULL;
200 
201  return r;
202 }
203 /*---------------------------------------------------------------------------*/
204 /**
205  * Remove the first object on a list.
206  *
207  * This function removes the first object on the list and returns a
208  * pointer to it.
209  *
210  * \param list The list.
211  * \return Pointer to the removed element of list.
212  */
213 /*---------------------------------------------------------------------------*/
214 void *
216 {
217  struct list *l;
218  l = *list;
219  if(*list != NULL) {
220  *list = ((struct list *)*list)->next;
221  }
222 
223  return l;
224 }
225 /*---------------------------------------------------------------------------*/
226 /**
227  * Remove a specific element from a list.
228  *
229  * This function removes a specified element from the list.
230  *
231  * \param list The list.
232  * \param item The item that is to be removed from the list.
233  *
234  */
235 /*---------------------------------------------------------------------------*/
236 void
237 list_remove(list_t list, void *item)
238 {
239  struct list *l, *r;
240 
241  if(*list == NULL) {
242  return;
243  }
244 
245  r = NULL;
246  for(l = *list; l != NULL; l = l->next) {
247  if(l == item) {
248  if(r == NULL) {
249  /* First on list */
250  *list = l->next;
251  } else {
252  /* Not first on list */
253  r->next = l->next;
254  }
255  l->next = NULL;
256  return;
257  }
258  r = l;
259  }
260 }
261 /*---------------------------------------------------------------------------*/
262 /**
263  * Get the length of a list.
264  *
265  * This function counts the number of elements on a specified list.
266  *
267  * \param list The list.
268  * \return The length of the list.
269  */
270 /*---------------------------------------------------------------------------*/
271 int
273 {
274  struct list *l;
275  int n = 0;
276 
277  for(l = *list; l != NULL; l = l->next) {
278  ++n;
279  }
280 
281  return n;
282 }
283 /*---------------------------------------------------------------------------*/
284 /**
285  * \brief Insert an item after a specified item on the list
286  * \param list The list
287  * \param previtem The item after which the new item should be inserted
288  * \param newitem The new item that is to be inserted
289  * \author Adam Dunkels
290  *
291  * This function inserts an item right after a specified
292  * item on the list. This function is useful when using
293  * the list module to ordered lists.
294  *
295  * If previtem is NULL, the new item is placed at the
296  * start of the list.
297  *
298  */
299 void
300 list_insert(list_t list, void *previtem, void *newitem)
301 {
302  if(previtem == NULL) {
303  list_push(list, newitem);
304  } else {
305  list_remove(list, newitem);
306  ((struct list *)newitem)->next = ((struct list *)previtem)->next;
307  ((struct list *)previtem)->next = newitem;
308  }
309 }
310 /*---------------------------------------------------------------------------*/
311 /**
312  * \brief Get the next item following this item
313  * \param item A list item
314  * \returns A next item on the list
315  *
316  * This function takes a list item and returns the next
317  * item on the list, or NULL if there are no more items on
318  * the list. This function is used when iterating through
319  * lists.
320  */
321 void *
322 list_item_next(void *item)
323 {
324  return item == NULL ? NULL : ((struct list *)item)->next;
325 }
326 /*---------------------------------------------------------------------------*/
327 /**
328  * \brief Check if the list contains an item
329  * \param list The list that is checked
330  * \param item An item to look for in the list
331  * \returns 0 if the list does not contains the item, and 1 otherwise
332  *
333  * This function searches for an item in the list and returns
334  * 0 if the list does not contain the item, and 1 if the item
335  * is present in the list.
336  */
337 bool
338 list_contains(list_t list, void *item)
339 {
340  struct list *l;
341  for(l = *list; l != NULL; l = l->next) {
342  if(item == l) {
343  return true;
344  }
345  }
346  return false;
347 }
348 /*---------------------------------------------------------------------------*/
349 /** @} */
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
Linked list manipulation routines.
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