libcutils

libcutils/include/cutils/linked-list.h
linked-list.h
⎇
Raw
1#ifndef CUTILS_LINKED_LIST_H
2#define CUTILS_LINKED_LIST_H
3
4#include <cutils/common.h>
5#include <stdlib.h>
6
7typedef struct SLnode
8{
9 void* item;
10 void* next; /*has to be void* so the next field is compatible between the structs*/
11} SLnode;
12
13typedef struct DLnode
14{
15 struct SLnode sl;
16 struct DLnode* prev;
17} DLnode;
18
19typedef struct LinkedList
20{
21 void* head; /*SLnode if doubly_linked is false, otherwise DLnode*/
22 void* tail;
23 size_t length;
24 bool doubly_linked;
25 bool circularly_linked;
26} LinkedList;
27
28LinkedList* new_ll(bool doubly_linked, bool circularly_linked);
29void delete_ll(LinkedList* ll, void(*rmv) (void*));
30
31void* llnode_at(const LinkedList* ll, size_t index);
32HEDLEY_INLINE
33static void* ll_at(const LinkedList* ll, size_t index)
34{
35 return ((SLnode*)llnode_at(ll, index))->item;
36}
37#define ll_pop(ll) ll_pop_at(ll, ll->length-1)
38void* ll_pop_at(LinkedList* ll, size_t index);
39
40#define ll_push(ll, item) ll_insert(ll, ll->length, item)
41bool sll_insert(LinkedList* ll, size_t index, void* item);
42bool dll_insert(LinkedList* ll, size_t index, void* item);
43HEDLEY_INLINE
44static bool ll_insert(LinkedList* ll, size_t index, void* item)
45{
46 if(ll->doubly_linked)
47 return dll_insert(ll, index, item);
48 else
49 return sll_insert(ll, index, item);
50}
51
52void sll_remove(LinkedList* ll, size_t index, void (*rmv)(void*));
53void dll_remove(LinkedList* ll, size_t index, void (*rmv)(void*));
54HEDLEY_INLINE
55static void ll_remove(LinkedList* ll, size_t index, void (*rmv)(void*))
56{
57 if(ll->doubly_linked)
58 dll_remove(ll, index, rmv);
59 else
60 sll_remove(ll, index, rmv);
61}
62void sll_remove_range(LinkedList* ll, size_t index, size_t length, void (*rmv)(void*));
63void dll_remove_range(LinkedList* ll, size_t index, size_t length, void (*rmv)(void*));
64HEDLEY_INLINE
65static void ll_remove_range(LinkedList* ll, size_t index, size_t length, void (*rmv)(void*))
66{
67 if(ll->doubly_linked)
68 dll_remove_range(ll, index, length, rmv);
69 else
70 sll_remove_range(ll, index, length, rmv);
71}
72
73size_t* ll_find(const LinkedList* haystack, const void* needle, int (*cmp)(const void*, const void*));
74
75void sll_swap(LinkedList* ll, size_t item1, size_t item2);
76void dll_swap(LinkedList* ll, size_t item1, size_t item2);
77HEDLEY_INLINE
78static void ll_swap(LinkedList* ll, size_t item1, size_t item2)
79{
80 if(ll->doubly_linked)
81 dll_swap(ll, item1, item2);
82 else
83 sll_swap(ll, item1, item2);
84}
85
86
87#endif /* CUTILS_LINKED_LIST_H */
88