tommylist.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  *
8  * 1. Redistributions of source code must retain the above copyright
9  * notice, this list of conditions and the following disclaimer.
10  *
11  * 2. Redistributions in binary form must reproduce the above copyright
12  * notice, this list of conditions and the following disclaimer in the
13  * documentation and/or other materials provided with the distribution.
14  *
15  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
16  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
19  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
20  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
21  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
22  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
23  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
24  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
25  * POSSIBILITY OF SUCH DAMAGE.
26  */
27 
97 #ifndef __TOMMYLIST_H
98 #define __TOMMYLIST_H
99 
100 #include "tommytypes.h"
101 
102 /******************************************************************************/
103 /* list */
104 
109 
114 tommy_inline void tommy_list_init(tommy_list* list)
115 {
116  *list = 0;
117 }
118 
124 {
125  return *list;
126 }
127 
133 {
134  tommy_node* head = tommy_list_head(list);
135 
136  if (!head)
137  return 0;
138 
139  return head->prev;
140 }
141 
147 tommy_inline void tommy_list_insert_first(tommy_list* list, tommy_node* node)
148 {
149  /* one element "circular" prev list */
150  node->prev = node;
151 
152  /* one element "0 terminated" next list */
153  node->next = 0;
154 
155  *list = node;
156 }
157 
164 tommy_inline void tommy_list_insert_head_not_empty(tommy_list* list, tommy_node* node)
165 {
166  tommy_node* head = tommy_list_head(list);
167 
168  /* insert in the "circular" prev list */
169  node->prev = head->prev;
170  head->prev = node;
171 
172  /* insert in the "0 terminated" next list */
173  node->next = head;
174 
175  *list = node;
176 }
177 
184 tommy_inline void tommy_list_insert_tail_not_empty(tommy_node* head, tommy_node* node)
185 {
186  /* insert in the "circular" prev list */
187  node->prev = head->prev;
188  head->prev = node;
189 
190  /* insert in the "0 terminated" next list */
191  node->next = 0;
192  node->prev->next = node;
193 }
194 
200 tommy_inline void tommy_list_insert_head(tommy_list* list, tommy_node* node, void* data)
201 {
202  tommy_node* head = tommy_list_head(list);
203 
204  if (head)
205  tommy_list_insert_head_not_empty(list, node);
206  else
207  tommy_list_insert_first(list, node);
208 
209  node->data = data;
210 }
211 
217 tommy_inline void tommy_list_insert_tail(tommy_list* list, tommy_node* node, void* data)
218 {
219  tommy_node* head = tommy_list_head(list);
220 
221  if (head)
222  tommy_list_insert_tail_not_empty(head, node);
223  else
224  tommy_list_insert_first(list, node);
225 
226  node->data = data;
227 }
228 
237 tommy_inline void* tommy_list_remove_existing(tommy_list* list, tommy_node* node)
238 {
239  tommy_node* head = tommy_list_head(list);
240 
241  /* remove from the "circular" prev list */
242  if (node->next)
243  node->next->prev = node->prev;
244  else
245  head->prev = node->prev; /* the last */
246 
247  /* remove from the "0 terminated" next list */
248  if (head == node)
249  *list = node->next; /* the new head, in case 0 */
250  else
251  node->prev->next = node->next;
252 
253  return node->data;
254 }
255 
263 tommy_inline void tommy_list_concat(tommy_list* first, tommy_list* second)
264 {
265  tommy_node* first_head;
266  tommy_node* first_tail;
267  tommy_node* second_head;
268 
269  /* if the second is empty, nothing to do */
270  second_head = tommy_list_head(second);
271  if (second_head == 0)
272  return;
273 
274  /* if the first is empty, copy the second */
275  first_head = tommy_list_head(first);
276  if (first_head == 0) {
277  *first = *second;
278  return;
279  }
280 
281  /* tail of the first list */
282  first_tail = first_head->prev;
283 
284  /* set the "circular" prev list */
285  first_head->prev = second_head->prev;
286  second_head->prev = first_tail;
287 
288  /* set the "0 terminated" next list */
289  first_tail->next = second_head;
290 }
291 
300 
306 {
307  return tommy_list_head(list) == 0;
308 }
309 
315 {
316  tommy_count_t count = 0;
317  tommy_node* i = tommy_list_head(list);
318 
319  while (i) {
320  ++count;
321  i = i->next;
322  }
323 
324  return count;
325 }
326 
355 tommy_inline void tommy_list_foreach(tommy_list* list, tommy_foreach_func* func)
356 {
357  tommy_node* node = tommy_list_head(list);
358 
359  while (node) {
360  void* data = node->data;
361  node = node->next;
362  func(data);
363  }
364 }
365 
369 tommy_inline void tommy_list_foreach_arg(tommy_list* list, tommy_foreach_arg_func* func, void* arg)
370 {
371  tommy_node* node = tommy_list_head(list);
372 
373  while (node) {
374  void* data = node->data;
375  node = node->next;
376  func(arg, data);
377  }
378 }
379 
380 #endif
381 
void tommy_list_insert_head(tommy_list *list, tommy_node *node, void *data)
Inserts an element at the head of a list.
Definition: tommylist.h:200
tommy_uint32_t tommy_count_t
Generic unsigned integer for counting objects.
Definition: tommytypes.h:67
tommy_count_t tommy_list_count(tommy_list *list)
Gets the number of elements.
Definition: tommylist.h:314
tommy_node * tommy_list
Double linked list type.
Definition: tommylist.h:108
struct tommy_node_struct * next
Next node.
Definition: tommytypes.h:188
struct tommy_node_struct * prev
Previous node.
Definition: tommytypes.h:194
int tommy_compare_func(const void *obj_a, const void *obj_b)
Compare function for elements.
Definition: tommytypes.h:240
void tommy_list_concat(tommy_list *first, tommy_list *second)
Concats two lists.
Definition: tommylist.h:263
void tommy_list_sort(tommy_list *list, tommy_compare_func *cmp)
Sorts a list.
tommy_node * tommy_list_tail(tommy_list *list)
Gets the tail of the list.
Definition: tommylist.h:132
tommy_bool_t tommy_list_empty(tommy_list *list)
Checks if empty.
Definition: tommylist.h:305
Data structure node.
Definition: tommytypes.h:183
void tommy_foreach_func(void *obj)
Foreach function.
Definition: tommytypes.h:289
void tommy_list_init(tommy_list *list)
Initializes the list.
Definition: tommylist.h:114
void * tommy_list_remove_existing(tommy_list *list, tommy_node *node)
Removes an element from the list.
Definition: tommylist.h:237
void * data
Pointer to the object containing the node.
Definition: tommytypes.h:200
void tommy_list_foreach_arg(tommy_list *list, tommy_foreach_arg_func *func, void *arg)
Calls the specified function with an argument for each element in the list.
Definition: tommylist.h:369
Generic types.
int tommy_bool_t
Generic boolean type.
Definition: tommytypes.h:52
void tommy_list_foreach(tommy_list *list, tommy_foreach_func *func)
Calls the specified function for each element in the list.
Definition: tommylist.h:355
void tommy_foreach_arg_func(void *arg, void *obj)
Foreach function with an argument.
Definition: tommytypes.h:296
tommy_node * tommy_list_head(tommy_list *list)
Gets the head of the list.
Definition: tommylist.h:123
void tommy_list_insert_tail(tommy_list *list, tommy_node *node, void *data)
Inserts an element at the tail of a list.
Definition: tommylist.h:217