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 #if __STDC_VERSION__ >= 201112L
16 union
17 {
18 #endif
19 struct SLnode sl;
20 #if __STDC_VERSION__ >= 201112L
21 struct
22 {
23 void* item;
24 void* next;
25 };
26 };
27 #endif
28 struct DLnode* prev;
29} DLnode;
30
31typedef struct LinkedList
32{
33 void* head; /*SLnode if doubly_linked is false, otherwise DLnode*/
34 void* tail;
35 size_t length;
36 bool doubly_linked;
37 bool circularly_linked;
38} LinkedList;
39
40LinkedList* new_ll(bool doubly_linked, bool circularly_linked);
41void delete_ll(LinkedList* ll, void(*rmv) (void*));
42
43void* llnode_at(const LinkedList* ll, size_t index);
44HEDLEY_INLINE
45static void* ll_at(const LinkedList* ll, size_t index)
46{
47 return ((SLnode*)llnode_at(ll, index))->item;
48}
49#define ll_pop(ll) ll_pop_at(ll, ll->length-1)
50void* ll_pop_at(LinkedList* ll, size_t index);
51
52#define ll_push(ll, item) ll_insert(ll, ll->length, item)
53bool sll_insert(LinkedList* ll, size_t index, void* item);
54bool dll_insert(LinkedList* ll, size_t index, void* item);
55HEDLEY_INLINE
56static bool ll_insert(LinkedList* ll, size_t index, void* item)
57{
58 if(ll->doubly_linked)
59 return dll_insert(ll, index, item);
60 else
61 return sll_insert(ll, index, item);
62}
63
64void sll_remove(LinkedList* ll, size_t index, void (*rmv)(void*));
65void dll_remove(LinkedList* ll, size_t index, void (*rmv)(void*));
66HEDLEY_INLINE
67static void ll_remove(LinkedList* ll, size_t index, void (*rmv)(void*))
68{
69 if(ll->doubly_linked)
70 dll_remove(ll, index, rmv);
71 else
72 sll_remove(ll, index, rmv);
73}
74void sll_remove_range(LinkedList* ll, size_t index, size_t length, void (*rmv)(void*));
75void dll_remove_range(LinkedList* ll, size_t index, size_t length, void (*rmv)(void*));
76HEDLEY_INLINE
77static void ll_remove_range(LinkedList* ll, size_t index, size_t length, void (*rmv)(void*))
78{
79 if(ll->doubly_linked)
80 dll_remove_range(ll, index, length, rmv);
81 else
82 sll_remove_range(ll, index, length, rmv);
83}
84
85size_t* ll_find(const LinkedList* haystack, const void* needle, int (*cmp)(const void*, const void*));
86
87void sll_swap(LinkedList* ll, size_t item1, size_t item2);
88void dll_swap(LinkedList* ll, size_t item1, size_t item2);
89HEDLEY_INLINE
90static void ll_swap(LinkedList* ll, size_t item1, size_t item2)
91{
92 if(ll->doubly_linked)
93 dll_swap(ll, item1, item2);
94 else
95 sll_swap(ll, item1, item2);
96}
97
98
99#endif /* CUTILS_LINKED_LIST_H */
100