Contiki-NG
Loading...
Searching...
No Matches
dbl-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-list Doubly-linked list
37 *
38 * This library provides functions for the creation and manipulation of
39 * doubly-linked lists.
40 *
41 * A doubly-linked list is declared using the DBL_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_LIST_H_
58#define DBL_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 doubly-linked list.
68 *
69 * This macro defines a 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 doubly-linked list.
78 */
79#define DBL_LIST(name) \
80 static void *name##_dbl_list = NULL; \
81 static dbl_list_t name = (dbl_list_t)&name##_dbl_list
82/*---------------------------------------------------------------------------*/
83/**
84 * The doubly-linked list datatype.
85 */
86typedef void **dbl_list_t;
87
88/**
89 * The non-modifiable doubly-linked list type.
90 */
91typedef void *const *const_dbl_list_t;
92
93/*---------------------------------------------------------------------------*/
94/**
95 * \brief Initialise a doubly-linked list.
96 * \param dll The doubly-linked list.
97 */
99
100/**
101 * \brief Return the tail of a doubly-linked list.
102 * \param dll The doubly-linked list.
103 * \return A pointer to the list's head, or NULL if the list is empty
104 */
106
107/**
108 * \brief Return the tail of a doubly-linked list.
109 * \param dll The doubly-linked list.
110 * \return A pointer to the list's tail, or NULL if the list is empty
111 */
113
114/**
115 * \brief Add an element to the head of a doubly-linked list.
116 * \param dll The doubly-linked list.
117 * \param element A pointer to the element to be added.
118 *
119 * Calling this function will update the list's head and item order. If you
120 * call this function as part of a list traversal, it is advised to stop
121 * traversing after this function returns.
122 */
123void dbl_list_add_head(dbl_list_t dll, void *element);
124
125/**
126 * \brief Add an element to the tail of a doubly-linked list.
127 * \param dll The doubly-linked list.
128 * \param element A pointer to the element to be added.
129 *
130 * Calling this function will update the list's head and item order. If you
131 * call this function as part of a list traversal, it is advised to stop
132 * traversing after this function returns.
133 */
134void dbl_list_add_tail(dbl_list_t dll, void *element);
135
136/**
137 * \brief Add an element to a doubly linked list after an existing element.
138 * \param dll The doubly-linked list.
139 * \param existing A pointer to the existing element.
140 * \param element A pointer to the element to be added.
141 *
142 * This function will add \e element after \e existing
143 *
144 * The function will not verify that \e existing is already part of the list.
145 *
146 * Calling this function will update the list's head and item order. If you
147 * call this function as part of a list traversal, it is advised to stop
148 * traversing after this function returns.
149 */
150void dbl_list_add_after(dbl_list_t dll, void *existing, void *element);
151
152/**
153 * \brief Add an element to a doubly linked list before an existing element.
154 * \param dll The doubly-linked list.
155 * \param existing A pointer to the existing element.
156 * \param element A pointer to the element to be added.
157 *
158 * This function will add \e element before \e existing
159 *
160 * The function will not verify that \e existing is already part of the list.
161 *
162 * Calling this function will update the list's head and item order. If you
163 * call this function as part of a list traversal, it is advised to stop
164 * traversing after this function returns.
165 */
166void dbl_list_add_before(dbl_list_t dll, void *existing, void *element);
167
168/**
169 * \brief Remove an element from a doubly-linked list.
170 * \param dll The doubly-linked list.
171 * \param element A pointer to the element to be removed.
172 *
173 * Calling this function will update the list's head and item order. If you
174 * call this function as part of a list traversal, it is advised to stop
175 * traversing after this function returns.
176 */
177void dbl_list_remove(dbl_list_t dll, const void *element);
178
179/**
180 * \brief Get the length of a doubly-linked list.
181 * \param dll The doubly-linked list.
182 * \return The number of elements in the list
183 */
184unsigned long dbl_list_length(const_dbl_list_t dll);
185
186/**
187 * \brief Determine whether a doubly-linked list is empty.
188 * \param dll The doubly-linked list.
189 * \retval true The list is empty
190 * \retval false The list is not empty
191 */
193/*---------------------------------------------------------------------------*/
194#endif /* DBL_LIST_H_ */
195/*---------------------------------------------------------------------------*/
196/**
197 * @}
198 * @}
199 */
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
unsigned long dbl_list_length(const_dbl_list_t dll)
Get the length of a doubly-linked list.
Definition dbl-list.c:204
void * dbl_list_tail(const_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_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_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_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_head(const_dbl_list_t dll)
Return the tail of a doubly-linked list.
Definition dbl-list.c:60
void dbl_list_remove(dbl_list_t dll, const void *element)
Remove an element from a doubly-linked list.
Definition dbl-list.c:80
void dbl_list_init(dbl_list_t dll)
Initialise a doubly-linked list.
Definition dbl-list.c:54
void *const * const_dbl_list_t
The non-modifiable doubly-linked list type.
Definition dbl-list.h:91
bool dbl_list_is_empty(const_dbl_list_t dll)
Determine whether a doubly-linked list is empty.
Definition dbl-list.c:221