Contiki-NG
dbl-circ-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-circular-list
35  * @{
36  *
37  * \file
38  * Implementation of circular, doubly-linked lists
39  */
40 /*---------------------------------------------------------------------------*/
41 #include "contiki.h"
42 #include "lib/dbl-circ-list.h"
43 
44 #include <stdint.h>
45 #include <stdbool.h>
46 #include <string.h>
47 /*---------------------------------------------------------------------------*/
48 struct dblcl {
49  struct dblcl *next;
50  struct dblcl *previous;
51 };
52 /*---------------------------------------------------------------------------*/
53 void
55 {
56  *dblcl = NULL;
57 }
58 /*---------------------------------------------------------------------------*/
59 void *
61 {
62  return *dblcl;
63 }
64 /*---------------------------------------------------------------------------*/
65 void *
67 {
68  struct dblcl *this;
69 
70  if(*dblcl == NULL) {
71  return NULL;
72  }
73 
74  for(this = *dblcl; this->next != *dblcl; this = this->next);
75 
76  return this;
77 }
78 /*---------------------------------------------------------------------------*/
79 void
81 {
82  struct dblcl *this;
83 
84  if(*dblcl == NULL || element == NULL) {
85  return;
86  }
87 
88  this = *dblcl;
89 
90  do {
91  if(this == element) {
92  this->previous->next = this->next;
93  this->next->previous = this->previous;
94 
95  /* We need to update the head of the list if we removed the head */
96  if(*dblcl == element) {
97  *dblcl = this->next == this ? NULL : this->next;
98  }
99 
100  this->next = NULL;
101  this->previous = NULL;
102 
103  return;
104  }
105 
106  this = this->next;
107  } while(this != *dblcl);
108 }
109 /*---------------------------------------------------------------------------*/
110 void
112 {
113  struct dblcl *head;
114 
115  if(element == NULL) {
116  return;
117  }
118 
119  /* Don't add twice */
120  dbl_circ_list_remove(dblcl, element);
121 
122  head = dbl_circ_list_head(dblcl);
123 
124  if(head == NULL) {
125  /* If the list was empty */
126  ((struct dblcl *)element)->next = element;
127  ((struct dblcl *)element)->previous = element;
128  } else {
129  /* If the list was not empty */
130  ((struct dblcl *)element)->next = head;
131  ((struct dblcl *)element)->previous = head->previous;
132  head->previous->next = element;
133  head->previous = element;
134  }
135 
136  *dblcl = element;
137 }
138 /*---------------------------------------------------------------------------*/
139 void
141 {
142  struct dblcl *tail;
143 
144  if(element == NULL) {
145  return;
146  }
147 
148  /* Don't add twice */
149  dbl_circ_list_remove(dblcl, element);
150 
151  tail = dbl_circ_list_tail(dblcl);
152 
153  if(tail == NULL) {
154  /* If the list was empty */
155  ((struct dblcl *)element)->next = element;
156  ((struct dblcl *)element)->previous = element;
157  *dblcl = element;
158  } else {
159  /* If the list was not empty */
160  ((struct dblcl *)element)->next = *dblcl;
161  ((struct dblcl *)element)->previous = tail;
162  tail->next->previous = element;
163  tail->next = element;
164  }
165 }
166 /*---------------------------------------------------------------------------*/
167 void
168 dbl_circ_list_add_after(dbl_circ_list_t dblcl, void *existing, void *element)
169 {
170  if(element == NULL || existing == NULL) {
171  return;
172  }
173 
174  /* Don't add twice */
175  dbl_circ_list_remove(dblcl, element);
176 
177  ((struct dblcl *)element)->next = ((struct dblcl *)existing)->next;
178  ((struct dblcl *)element)->previous = existing;
179  ((struct dblcl *)existing)->next->previous = element;
180  ((struct dblcl *)existing)->next = element;
181 }
182 /*---------------------------------------------------------------------------*/
183 void
184 dbl_circ_list_add_before(dbl_circ_list_t dblcl, void *existing, void *element)
185 {
186  if(element == NULL || existing == NULL) {
187  return;
188  }
189 
190  /* Don't add twice */
191  dbl_circ_list_remove(dblcl, element);
192 
193  ((struct dblcl *)element)->next = existing;
194  ((struct dblcl *)element)->previous = ((struct dblcl *)existing)->previous;
195  ((struct dblcl *)existing)->previous->next = element;
196  ((struct dblcl *)existing)->previous = element;
197 
198  /* If we added before the list's head, we must update the head */
199  if(*dblcl == existing) {
200  *dblcl = element;
201  }
202 }
203 /*---------------------------------------------------------------------------*/
204 unsigned long
206 {
207  unsigned long len = 1;
208  struct dblcl *this;
209 
210  if(*dblcl == NULL) {
211  return 0;
212  }
213 
214  for(this = *dblcl; this->next != *dblcl; this = this->next) {
215  len++;
216  }
217 
218  return len;
219 }
220 /*---------------------------------------------------------------------------*/
221 bool
223 {
224  return *dblcl == NULL ? true : false;
225 }
226 /*---------------------------------------------------------------------------*/
227 /** @} */
unsigned long dbl_circ_list_length(dbl_circ_list_t dblcl)
Get the length of a circular, doubly-linked list.
void dbl_circ_list_add_after(dbl_circ_list_t dblcl, void *existing, void *element)
Add an element to a circular, doubly linked list after an existing element.
void dbl_circ_list_remove(dbl_circ_list_t dblcl, void *element)
Remove an element from a circular, doubly-linked list.
Definition: dbl-circ-list.c:80
bool dbl_circ_list_is_empty(dbl_circ_list_t dblcl)
Determine whether a circular, doubly-linked list is empty.
void ** dbl_circ_list_t
The doubly-linked list datatype.
Definition: dbl-circ-list.h:86
void dbl_circ_list_add_tail(dbl_circ_list_t dblcl, void *element)
Add an element to the tail of a circular, doubly-linked list.
void dbl_circ_list_init(dbl_circ_list_t dblcl)
Initialise a circular, doubly-linked list.
Definition: dbl-circ-list.c:54
void * dbl_circ_list_head(dbl_circ_list_t dblcl)
Return the tail of a circular, doubly-linked list.
Definition: dbl-circ-list.c:60
void dbl_circ_list_add_before(dbl_circ_list_t dblcl, void *existing, void *element)
Add an element to a circular, doubly linked list before an existing element.
void * dbl_circ_list_tail(dbl_circ_list_t dblcl)
Return the tail of a circular, doubly-linked list.
Definition: dbl-circ-list.c:66
void dbl_circ_list_add_head(dbl_circ_list_t dblcl, void *element)
Add an element to the head of a circular, doubly-linked list.