summaryrefslogtreecommitdiff
path: root/src/ll.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/ll.c')
-rw-r--r--src/ll.c235
1 files changed, 0 insertions, 235 deletions
diff --git a/src/ll.c b/src/ll.c
deleted file mode 100644
index 908f25f..0000000
--- a/src/ll.c
+++ /dev/null
@@ -1,235 +0,0 @@
1#include "ll.h"
2#include "shared.h"
3
4#include <stdlib.h>
5#include <errno.h>
6#include <error.h>
7
8typedef struct dln {
9 void *data;
10 dll_freecb freecb;
11
12 struct dln *next;
13 struct dln *prev;
14
15} dllnode;
16typedef struct dlinked {
17 int size;
18 dllnode *start;
19 dllnode *end;
20
21} dlinkedlist;
22
23dllnode * dllnode_init(void *data, dll_freecb fcb) {
24 dllnode *n = VALLOC(1, sizeof(*n));
25 if(!n)
26 return NULL;
27
28 n->data = data;
29 n->freecb = fcb;
30 n->prev = NULL;
31 n->next = NULL;
32
33 return n;
34}
35
36dlinkedlist * dlinkedlist_init(void) {
37 dlinkedlist *ll = VALLOC(1, sizeof(*ll));
38 if(!ll)
39 return NULL;
40
41 ll->end = NULL;
42 ll->start = NULL;
43 ll->size = 0;
44
45 return ll;
46}
47
48void dlinkedlist_free(void *dll) {
49 if(!dll)
50 return;
51
52 dlinkedlist *ll = (dlinkedlist *)dll;
53 for(dllnode *current = ll->start, *next; current != NULL; ) {
54 next = current->next;
55
56 // This used to be a function but was causing issues for some inscrutable reason
57 if(current->freecb != NULL)
58 current->freecb(current->data);
59 free(current);
60
61 current = next;
62 }
63 free(ll);
64
65 return;
66}
67
68int dlinkedlist_size(const dlinkedlist * const ll) {
69 if(!ll) ERRRET(EINVAL, -1);
70 return ll->size;
71}
72
73int dlinkedlist_handlefirstnode(dlinkedlist * const ll, void *data, dll_freecb fcb) {
74 if(!ll) ERRRET(EINVAL, 1);
75 if(ll->size > 0)
76 return 1;
77
78 // Need to handle adding the first element differently than other opers, so do it here
79 dllnode *n = dllnode_init(data, fcb);
80 if(!n)
81 return -1;
82 // dllnode_init already sets n.prev and n.next to null, so no need to do so again
83
84 ll->end = n;
85 ll->start = n;
86 ll->size = 1;
87
88 return 0;
89}
90
91int dlinkedlist_xxxend(dlinkedlist * const ll, void *data, dll_freecb fcb, char op) {
92 if(!ll || (op != 'a' && op != 'p')) ERRRET(EINVAL, 1);
93
94 int handleret;
95 if((handleret = dlinkedlist_handlefirstnode(ll, data, fcb)) == 0)
96 return 0;
97
98 dllnode *n = dllnode_init(data, fcb);
99 if(!n || handleret < 0)
100 return -1;
101
102 switch (op) {
103 case 'a':
104 n->prev = (ll->end);
105 (ll->end)->next = n;
106 ll->end = n;
107 break;
108
109 case 'p':
110 n->next = (ll->start);
111 (ll->start)->prev = n;
112 ll->start = n;
113 break;
114
115 default:
116 XALLOC_EXIT("<dlinkedlist_xxxend> got an invalid op token when it shouldn't be possible to recieve one", );
117 // Technically not an alloc, but also there's no reason I can't reuse a perfectly good macro
118 }
119
120 ll->size++;
121 return 0;
122}
123// TODO: Figure out where the memory leak gcc keeps complaining about is & fix it
124
125
126int dlinkedlist_append(dlinkedlist * const ll, void *data, dll_freecb fcb) {
127 return dlinkedlist_xxxend(ll, data, fcb, 'a');
128}
129
130int dlinkedlist_prepend(dlinkedlist * const ll, void *data, dll_freecb fcb) {
131 return dlinkedlist_xxxend(ll, data, fcb, 'p');
132}
133
134dllnode * dlinkedlist_getnode(const dlinkedlist * const ll, int index) {
135 if(!ll) ERRRET(EINVAL, NULL);
136 if(index < 0 || index >= ll->size) ERRRET(EINVAL, NULL);
137
138 if(index == 0)
139 return ll->start;
140 if(index == (ll->size - 1))
141 return ll->end;
142
143 int spoint = (index <= (ll->size / 2));
144 dllnode *p = (spoint) ? ll->start : ll->end;
145 int i = (spoint) ? 0 : ll->size - 1;
146
147 // This should (theoretically) be faster on average
148 for(; p != NULL && ((spoint) ? (i < index) : (i > index)); (spoint) ? i++ : i--, p = (spoint) ? p->next : p->prev);
149
150 return p;
151}
152
153int dlinkedlist_insert(dlinkedlist * const ll, void *data, dll_freecb fcb, int index) {
154 if(!ll) ERRRET(EINVAL, 1);
155 if(index < 0 || index >= ll->size) ERRRET(EINVAL, 1);
156
157 // Handle the special cases of appending or prepending
158 if(index == 0)
159 return dlinkedlist_prepend(ll, data, fcb);
160 if(index == (ll->size - 1))
161 return dlinkedlist_append(ll, data, fcb);
162
163 // Insert between 2 nodes
164 // If you're inserting at index 2, the new node becomes index 2, and the previous node at index 2 moves to index 3
165
166 dllnode *new = dllnode_init(data, fcb);
167 if(!new)
168 return -1;
169 dllnode *current = dlinkedlist_getnode(ll, index);
170 if(!current)
171 XALLOC_EXIT("<dlinkedlist_insert> somehow managed to pull a null node from dlinkedlist_getnode(... , ... , ... , %d)", , (index));
172
173 (current->prev)->next = new;
174 new->prev = (current->prev);
175 new->next = current;
176 current->prev = new;
177
178 ll->size++;
179 return 0;
180}
181
182int dlinkedlist_remove(dlinkedlist * const ll, int index) {
183 if(!ll) ERRRET(EINVAL, 1);
184 if(index < 0 || index >= ll->size) ERRRET(EINVAL, 2);
185
186 dllnode *current = dlinkedlist_getnode(ll, index);
187 if(!current)
188 return -1;
189
190 if(index == 0) {
191 ll->start = current->next;
192 ll->start->prev = NULL;
193 } else if(index == (ll->size - 1)) {
194 ll->end = current->prev;
195 ll->end->next = NULL;
196 } else {
197 current->prev->next = current->next;
198 current->next->prev = current->prev;
199 }
200
201 if(current->freecb != NULL)
202 current->freecb(current->data);
203 free(current);
204
205 ll->size--;
206
207 return 0;
208}
209
210void* dlinkedlist_get(const dlinkedlist * const ll, int index) {
211 dllnode *n = dlinkedlist_getnode(ll, index);
212 if(!n)
213 return NULL;
214
215 return n->data;
216}
217
218int dlinkedlist_foreach(dlinkedlist *ll, int (*callback)(void*)) {
219 if(!ll || callback == NULL) ERRRET(EINVAL, -1);
220
221 for(dllnode *p = ll->start; p != NULL; p = p->next)
222 callback(p->data);
223
224 return 0;
225}
226
227void * dlinkedlist_poplast(dlinkedlist *ll) {
228 if(!ll) ERRRET(EINVAL, NULL);
229 if(dlinkedlist_isempty(ll)) ERRRET(ENODATA, NULL);
230
231 void *data = dlinkedlist_get(ll, ll->size - 1);
232 dlinkedlist_remove(ll, ll->size - 1);
233
234 return data;
235} \ No newline at end of file
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-06 04:52:29 +0000