Contiki-NG
dbl-list.c
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2017, George Oikonomou - http://www.spd.gr
3  * Copyright (c) 2017, James Pope
4  * All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
9  *
10  * 1. Redistributions of source code must retain the above copyright
11  * notice, this list of conditions and the following disclaimer.
12  * 2. Redistributions in binary form must reproduce the above copyright
13  * notice, this list of conditions and the following disclaimer in the
14  * documentation and/or other materials provided with the distribution.
15  * 3. Neither the name of the copyright holder nor the names of its
16  * contributors may be used to endorse or promote products derived
17  * from this software without specific prior written permission.
18  *
19  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
22  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
23  * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
24  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
25  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
26  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
28  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
29  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
30  * OF THE POSSIBILITY OF SUCH DAMAGE.
31  */
32 /*---------------------------------------------------------------------------*/
33 /**
34  * \addtogroup doubly-linked-list
35  * @{
36  *
37  * \file
38  * Implementation of doubly-linked lists
39  */
40 /*---------------------------------------------------------------------------*/
41 #include "contiki.h"
42 #include "lib/dbl-list.h"
43 
44 #include <stdint.h>
45 #include <stdbool.h>
46 #include <string.h>
47 /*---------------------------------------------------------------------------*/
48 struct dll {
49  struct dll *next;
50  struct dll *previous;
51 };
52 /*---------------------------------------------------------------------------*/
53 void
55 {
56  *dll = NULL;
57 }
58 /*---------------------------------------------------------------------------*/
59 void *
61 {
62  return *dll;
63 }
64 /*---------------------------------------------------------------------------*/
65 void *
67 {
68  struct dll *this;
69 
70  if(*dll == NULL) {
71  return NULL;
72  }
73 
74  for(this = *dll; this->next != NULL; this = this->next);
75 
76  return this;
77 }
78 /*---------------------------------------------------------------------------*/
79 void
80 dbl_list_remove(dbl_list_t dll, void *element)
81 {
82  struct dll *this, *previous, *next;
83 
84  if(*dll == NULL || element == NULL) {
85  return;
86  }
87 
88  for(this = *dll; this != NULL; this = this->next) {
89  if(this == element) {
90  previous = this->previous;
91  next = this->next;
92 
93  if(previous) {
94  previous->next = this->next;
95  }
96 
97  if(next) {
98  next->previous = this->previous;
99  }
100 
101  if(*dll == this) {
102  *dll = next;
103  }
104 
105  return;
106  }
107  }
108 }
109 /*---------------------------------------------------------------------------*/
110 void
111 dbl_list_add_head(dbl_list_t dll, void *element)
112 {
113  struct dll *head;
114 
115  if(element == NULL) {
116  return;
117  }
118 
119  /* Don't add twice */
120  dbl_list_remove(dll, element);
121 
122  head = dbl_list_head(dll);
123 
124  ((struct dll *)element)->previous = NULL;
125  ((struct dll *)element)->next = head;
126 
127  if(head) {
128  /* If the list was not empty, update ->previous on the old head */
129  head->previous = element;
130  }
131 
132  *dll = element;
133 }
134 /*---------------------------------------------------------------------------*/
135 void
136 dbl_list_add_tail(dbl_list_t dll, void *element)
137 {
138  struct dll *tail;
139 
140  if(element == NULL) {
141  return;
142  }
143 
144  /* Don't add twice */
145  dbl_list_remove(dll, element);
146 
147  tail = dbl_list_tail(dll);
148 
149  if(tail == NULL) {
150  /* The list was empty */
151  *dll = element;
152  } else {
153  tail->next = element;
154  }
155 
156  ((struct dll *)element)->previous = tail;
157  ((struct dll *)element)->next = NULL;
158 }
159 /*---------------------------------------------------------------------------*/
160 void
161 dbl_list_add_after(dbl_list_t dll, void *existing, void *element)
162 {
163  if(element == NULL || existing == NULL) {
164  return;
165  }
166 
167  /* Don't add twice */
168  dbl_list_remove(dll, element);
169 
170  ((struct dll *)element)->next = ((struct dll *)existing)->next;
171  ((struct dll *)element)->previous = existing;
172 
173  if(((struct dll *)existing)->next) {
174  ((struct dll *)existing)->next->previous = element;
175  }
176  ((struct dll *)existing)->next = element;
177 }
178 /*---------------------------------------------------------------------------*/
179 void
180 dbl_list_add_before(dbl_list_t dll, void *existing, void *element)
181 {
182  if(element == NULL || existing == NULL) {
183  return;
184  }
185 
186  /* Don't add twice */
187  dbl_list_remove(dll, element);
188 
189  ((struct dll *)element)->next = existing;
190  ((struct dll *)element)->previous = ((struct dll *)existing)->previous;
191 
192  if(((struct dll *)existing)->previous) {
193  ((struct dll *)existing)->previous->next = element;
194  }
195  ((struct dll *)existing)->previous = element;
196 
197  /* If we added before the list's head, we must update the head */
198  if(*dll == existing) {
199  *dll = element;
200  }
201 }
202 /*---------------------------------------------------------------------------*/
203 unsigned long
205 {
206  unsigned long len = 0;
207  struct dll *this;
208 
209  if(*dll == NULL) {
210  return 0;
211  }
212 
213  for(this = *dll; this != NULL; this = this->next) {
214  len++;
215  }
216 
217  return len;
218 }
219 /*---------------------------------------------------------------------------*/
220 bool
222 {
223  return *dll == NULL ? true : false;
224 }
225 /*---------------------------------------------------------------------------*/
226 /** @} */
unsigned long dbl_list_length(dbl_list_t dll)
Get the length of a doubly-linked list.
Definition: dbl-list.c:204
void dbl_list_init(dbl_list_t dll)
Initialise a doubly-linked list.
Definition: dbl-list.c:54
void dbl_list_add_tail(dbl_list_t dll, void *element)
Add an element to the tail of a doubly-linked list.
Definition: dbl-list.c:136
void dbl_list_add_before(dbl_list_t dll, void *existing, void *element)
Add an element to a doubly linked list before an existing element.
Definition: dbl-list.c:180
void dbl_list_remove(dbl_list_t dll, void *element)
Remove an element from a doubly-linked list.
Definition: dbl-list.c:80
void dbl_list_add_head(dbl_list_t dll, void *element)
Add an element to the head of a doubly-linked list.
Definition: dbl-list.c:111
void * dbl_list_tail(dbl_list_t dll)
Return the tail of a doubly-linked list.
Definition: dbl-list.c:66
void ** dbl_list_t
The doubly-linked list datatype.
Definition: dbl-list.h:86
void dbl_list_add_after(dbl_list_t dll, void *existing, void *element)
Add an element to a doubly linked list after an existing element.
Definition: dbl-list.c:161
bool dbl_list_is_empty(dbl_list_t dll)
Determine whether a doubly-linked list is empty.
Definition: dbl-list.c:221
void * dbl_list_head(dbl_list_t dll)
Return the tail of a doubly-linked list.
Definition: dbl-list.c:60