Contiki-NG
dbl-circ-list.h
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 /** \addtogroup data
34  * @{
35  *
36  * \defgroup doubly-linked-circular-list Circular, doubly-linked list
37  *
38  * This library provides functions for the creation and manipulation of
39  * circular, doubly-linked lists.
40  *
41  * A circular, doubly-linked list is declared using the DBL_CIRC_LIST macro.
42  * Elements must be allocated by the calling code and must be of a C struct
43  * datatype. In this struct, the first field must be a pointer called \e next.
44  * The second field must be a pointer called \e previous.
45  * These fields will be used by the library to maintain the list. Application
46  * code must not modify these fields directly.
47  *
48  * Functions that modify the list (add / remove) will, in the general case,
49  * update the list's head and item order. If you call one of these functions
50  * as part of a list traversal, it is advised to stop / restart traversing
51  * after the respective function returns.
52  *
53  * This library is not safe to be used within an interrupt context.
54  * @{
55  */
56 /*---------------------------------------------------------------------------*/
57 #ifndef DBL_CIRC_LIST_H_
58 #define DBL_CIRC_LIST_H_
59 /*---------------------------------------------------------------------------*/
60 #include "contiki.h"
61 
62 #include <stdint.h>
63 #include <stdbool.h>
64 #include <string.h>
65 /*---------------------------------------------------------------------------*/
66 /**
67  * \brief Define a circular, doubly-linked list.
68  *
69  * This macro defines a circular, doubly-linked list.
70  *
71  * The datatype for elements must be a C struct.
72  * The struct's first member must be a pointer called \e next.
73  * The second field must be a pointer called \e previous.
74  * These fields will be used by the library to maintain the list. Application
75  * code must not modify these fields directly.
76  *
77  * \param name The name of the circular, doubly-linked list.
78  */
79 #define DBL_CIRC_LIST(name) \
80  static void *name##_dbl_circ_list = NULL; \
81  static dbl_list_t name = (dbl_circ_list_t)&name##_dbl_circ_list
82 /*---------------------------------------------------------------------------*/
83 /**
84  * \brief The doubly-linked list datatype
85  */
86 typedef void **dbl_circ_list_t;
87 /*---------------------------------------------------------------------------*/
88 /**
89  * \brief Initialise a circular, doubly-linked list.
90  * \param dblcl The circular, doubly-linked list.
91  */
93 
94 /**
95  * \brief Return the tail of a circular, doubly-linked list.
96  * \param dblcl The circular, doubly-linked list.
97  * \return A pointer to the list's head, or NULL if the list is empty
98  */
100 
101 /**
102  * \brief Return the tail of a circular, doubly-linked list.
103  * \param dblcl The circular, doubly-linked list.
104  * \return A pointer to the list's tail, or NULL if the list is empty
105  */
107 
108 /**
109  * \brief Add an element to the head of a circular, doubly-linked list.
110  * \param dblcl The circular, doubly-linked list.
111  * \param element A pointer to the element to be added.
112  *
113  * Calling this function will update the list's head and item order. If you
114  * call this function as part of a list traversal, it is advised to stop
115  * traversing after this function returns.
116  */
117 void dbl_circ_list_add_head(dbl_circ_list_t dblcl, void *element);
118 
119 /**
120  * \brief Add an element to the tail of a circular, doubly-linked list.
121  * \param dblcl The circular, doubly-linked list.
122  * \param element A pointer to the element to be added.
123  *
124  * Calling this function will update the list's head and item order. If you
125  * call this function as part of a list traversal, it is advised to stop
126  * traversing after this function returns.
127  */
128 void dbl_circ_list_add_tail(dbl_circ_list_t dblcl, void *element);
129 
130 /**
131  * \brief Add an element to a circular, doubly linked list after an existing element.
132  * \param dblcl The circular, doubly-linked list.
133  * \param existing A pointer to the existing element.
134  * \param element A pointer to the element to be added.
135  *
136  * This function will add \e element after \e existing
137  *
138  * The function will not verify that \e existing is already part of the list.
139  *
140  * Calling this function will update the list's head and item order. If you
141  * call this function as part of a list traversal, it is advised to stop
142  * traversing after this function returns.
143  */
144 void dbl_circ_list_add_after(dbl_circ_list_t dblcl, void *existing,
145  void *element);
146 
147 /**
148  * \brief Add an element to a circular, doubly linked list before an existing element.
149  * \param dblcl The circular, doubly-linked list.
150  * \param existing A pointer to the existing element.
151  * \param element A pointer to the element to be added.
152  *
153  * This function will add \e element before \e existing
154  *
155  * The function will not verify that \e existing is already part of the list.
156  *
157  * Calling this function will update the list's head and item order. If you
158  * call this function as part of a list traversal, it is advised to stop
159  * traversing after this function returns.
160  */
161 void dbl_circ_list_add_before(dbl_circ_list_t dblcl, void *existing,
162  void *element);
163 
164 /**
165  * \brief Remove an element from a circular, doubly-linked list.
166  * \param dblcl The circular, doubly-linked list.
167  * \param element A pointer to the element to be removed.
168  *
169  * Calling this function will update the list's head and item order. If you
170  * call this function as part of a list traversal, it is advised to stop
171  * traversing after this function returns.
172  */
173 void dbl_circ_list_remove(dbl_circ_list_t dblcl, void *element);
174 
175 /**
176  * \brief Get the length of a circular, doubly-linked list.
177  * \param dblcl The circular, doubly-linked list.
178  * \return The number of elements in the list
179  */
180 unsigned long dbl_circ_list_length(dbl_circ_list_t dblcl);
181 
182 /**
183  * \brief Determine whether a circular, doubly-linked list is empty.
184  * \param dblcl The circular, doubly-linked list.
185  * \retval true The list is empty
186  * \retval false The list is not empty
187  */
189 /*---------------------------------------------------------------------------*/
190 #endif /* DBL_CIRC_LIST_H_ */
191 /*---------------------------------------------------------------------------*/
192 /**
193  * @}
194  * @}
195  */
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.