• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /* MIT License
2  *
3  * Copyright (c) 2023 Brad House
4  *
5  * Permission is hereby granted, free of charge, to any person obtaining a copy
6  * of this software and associated documentation files (the "Software"), to deal
7  * in the Software without restriction, including without limitation the rights
8  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9  * copies of the Software, and to permit persons to whom the Software is
10  * furnished to do so, subject to the following conditions:
11  *
12  * The above copyright notice and this permission notice (including the next
13  * paragraph) shall be included in all copies or substantial portions of the
14  * Software.
15  *
16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22  * SOFTWARE.
23  *
24  * SPDX-License-Identifier: MIT
25  */
26 #ifndef __ARES__LLIST_H
27 #define __ARES__LLIST_H
28 
29 /*! \addtogroup ares__llist LinkedList Data Structure
30  *
31  * This is a doubly-linked list data structure.
32  *
33  * Average time complexity:
34  *  - Insert: O(1)   -- head or tail
35  *  - Search: O(n)
36  *  - Delete: O(1)   -- delete assumes you hold a node pointer
37  *
38  * @{
39  */
40 
41 struct ares__llist;
42 
43 /*! Opaque data structure for linked list */
44 typedef struct ares__llist ares__llist_t;
45 
46 struct ares__llist_node;
47 
48 /*! Opaque data structure for a node in a linked list */
49 typedef struct ares__llist_node ares__llist_node_t;
50 
51 /*! Callback to free user-defined node data
52  *
53  *  \param[in] data  user supplied data
54  */
55 typedef void                    (*ares__llist_destructor_t)(void *data);
56 
57 /*! Create a linked list object
58  *
59  *  \param[in] destruct  Optional. Destructor to call on all removed nodes
60  *  \return linked list object or NULL on out of memory
61  */
62 ares__llist_t      *ares__llist_create(ares__llist_destructor_t destruct);
63 
64 /*! Replace destructor for linked list nodes.  Typically this is used
65  *  when wanting to disable the destructor by using NULL.
66  *
67  *  \param[in] list      Initialized linked list object
68  *  \param[in] destruct  replacement destructor, NULL is allowed
69  */
70 void                ares__llist_replace_destructor(ares__llist_t           *list,
71                                                    ares__llist_destructor_t destruct);
72 
73 /*! Insert value as the first node in the linked list
74  *
75  *  \param[in] list   Initialized linked list object
76  *  \param[in] val    user-supplied value.
77  *  \return node object referencing place in list, or null if out of memory or
78  *   misuse
79  */
80 ares__llist_node_t *ares__llist_insert_first(ares__llist_t *list, void *val);
81 
82 /*! Insert value as the last node in the linked list
83  *
84  *  \param[in] list   Initialized linked list object
85  *  \param[in] val    user-supplied value.
86  *  \return node object referencing place in list, or null if out of memory or
87  *   misuse
88  */
89 ares__llist_node_t *ares__llist_insert_last(ares__llist_t *list, void *val);
90 
91 /*! Insert value before specified node in the linked list
92  *
93  *  \param[in] node  node referenced to insert before
94  *  \param[in] val   user-supplied value.
95  *  \return node object referencing place in list, or null if out of memory or
96  *   misuse
97  */
98 ares__llist_node_t *ares__llist_insert_before(ares__llist_node_t *node,
99                                               void               *val);
100 
101 /*! Insert value after specified node in the linked list
102  *
103  *  \param[in] node  node referenced to insert after
104  *  \param[in] val   user-supplied value.
105  *  \return node object referencing place in list, or null if out of memory or
106  *   misuse
107  */
108 ares__llist_node_t *ares__llist_insert_after(ares__llist_node_t *node,
109                                              void               *val);
110 
111 /*! Obtain first node in list
112  *
113  *  \param[in] list  Initialized list object
114  *  \return first node in list or NULL if none
115  */
116 ares__llist_node_t *ares__llist_node_first(ares__llist_t *list);
117 
118 /*! Obtain last node in list
119  *
120  *  \param[in] list  Initialized list object
121  *  \return last node in list or NULL if none
122  */
123 ares__llist_node_t *ares__llist_node_last(ares__llist_t *list);
124 
125 /*! Obtain next node in respect to specified node
126  *
127  *  \param[in] node  Node referenced
128  *  \return node or NULL if none
129  */
130 ares__llist_node_t *ares__llist_node_next(ares__llist_node_t *node);
131 
132 /*! Obtain previous node in respect to specified node
133  *
134  *  \param[in] node  Node referenced
135  *  \return node or NULL if none
136  */
137 ares__llist_node_t *ares__llist_node_prev(ares__llist_node_t *node);
138 
139 /*! Obtain value from node
140  *
141  *  \param[in] node  Node referenced
142  *  \return user provided value from node
143  */
144 void               *ares__llist_node_val(ares__llist_node_t *node);
145 
146 /*! Obtain the number of entries in the list
147  *
148  *  \param[in] list  Initialized list object
149  *  \return count
150  */
151 size_t              ares__llist_len(const ares__llist_t *list);
152 
153 /*! Obtain list object from referenced node
154  *
155  *  \param[in] node  Node referenced
156  *  \return list object node belongs to
157  */
158 ares__llist_t      *ares__llist_node_parent(ares__llist_node_t *node);
159 
160 /*! Obtain the first user-supplied value in the list
161  *
162  *  \param[in] list Initialized list object
163  *  \return first user supplied value or NULL if none
164  */
165 void               *ares__llist_first_val(ares__llist_t *list);
166 
167 /*! Obtain the last user-supplied value in the list
168  *
169  *  \param[in] list Initialized list object
170  *  \return last user supplied value or NULL if none
171  */
172 void               *ares__llist_last_val(ares__llist_t *list);
173 
174 /*! Take ownership of user-supplied value in list without calling destructor.
175  *  Will unchain entry from list.
176  *
177  *  \param[in] node Node referenced
178  *  \return user supplied value
179  */
180 void               *ares__llist_node_claim(ares__llist_node_t *node);
181 
182 /*! Replace user-supplied value for node
183  *
184  *  \param[in] node Node referenced
185  *  \param[in] val  new user-supplied value
186  */
187 void ares__llist_node_replace(ares__llist_node_t *node, void *val);
188 
189 /*! Destroy the node, removing it from the list and calling destructor.
190  *
191  *  \param[in] node  Node referenced
192  */
193 void ares__llist_node_destroy(ares__llist_node_t *node);
194 
195 /*! Destroy the list object and all nodes in the list.
196  *
197  *  \param[in] list Initialized list object
198  */
199 void ares__llist_destroy(ares__llist_t *list);
200 
201 /*! Detach node from the current list and re-attach it to the new list as the
202  *  last entry.
203  *
204  * \param[in] node   node to move
205  * \param[in] parent new list
206  */
207 void ares__llist_node_move_parent_last(ares__llist_node_t *node,
208                                        ares__llist_t      *new_parent);
209 
210 /*! Detach node from the current list and re-attach it to the new list as the
211  *  first entry.
212  *
213  * \param[in] node   node to move
214  * \param[in] parent new list
215  */
216 void ares__llist_node_move_parent_first(ares__llist_node_t *node,
217                                         ares__llist_t      *new_parent);
218 /*! @} */
219 
220 #endif /* __ARES__LLIST_H */
221