1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
|
#include "ll.h"
#include "shared.h"
#include <stddef.h>
#include <stdlib.h>
#include <errno.h>
typedef struct dll {
void *data;
dlinkedlist_freecallback dfreecb;
struct dll *next;
struct dll *prev;
} dllnode;
typedef struct dlinkedlist {
dllnode *start;
dllnode *end;
size_t size;
} dlinkedlist;
dllnode* dllnode_init(void *data, dlinkedlist_freecallback dfreecb) {
dllnode *n = xcalloc(1, sizeof(*n));
n->next = NULL;
n->prev = NULL;
n->data = data;
n->dfreecb = dfreecb;
return n;
}
int dllnode_free(dllnode **n) {
if(!n) {
errno = EINVAL;
return -1;
}
if(!(*n)) {
errno = EINVAL;
return -1;
}
if((*n)->dfreecb != NULL)
(*n)->dfreecb((*n)->data);
free(*n);
*n = NULL;
return 0;
}
void dlinkedlist_init(dlinkedlist **ll) {
(*ll) = xcalloc(1, sizeof(**ll));
(*ll)->start = NULL;
(*ll)->end = NULL;
(*ll)->size = 0;
return;
}
void dlinkedlist_free(dlinkedlist **ll) {
dllnode *p = (*ll)->start, *n;
while(p != NULL) {
n = p->next;
dllnode_free(&p);
p = n;
}
free(*ll);
(*ll) = NULL;
return;
}
int dlinkedlist_firstitem(dlinkedlist * const ll, void *data, dlinkedlist_freecallback dfreecb) {
if(!ll) {
errno = EINVAL;
return -1;
}
if(ll->size != 0)
return 0;
dllnode *n = dllnode_init(data, dfreecb);
ll->start = n;
ll->end = n;
ll->size = 1;
return 1;
}
int dlinkedlist_insert(dlinkedlist * const ll, void *data, dlinkedlist_freecallback dfreecb) {
if(!ll) {
errno = EINVAL;
return -1;
}
if(dlinkedlist_firstitem(ll, data, dfreecb) > 0)
return 0;
dllnode *n = dllnode_init(data, dfreecb);
n->prev = NULL;
n->next = ll->start;
ll->start->prev = n;
ll->start = n;
ll->size++;
return 0;
}
int dlinkedlist_append(dlinkedlist * const ll, void *data, dlinkedlist_freecallback dfreecb) {
if(!ll) {
errno = EINVAL;
return -1;
}
if(dlinkedlist_firstitem(ll, data, dfreecb) > 0)
return 0;
dllnode *n = dllnode_init(data, dfreecb);
n->prev = ll->end;
n->next = NULL;
ll->end->next = n;
ll->end = n;
ll->size++;
return 0;
}
dllnode *dlinkedlist_getnode(const dlinkedlist * const ll, size_t index) {
if(!ll) {
errno = EINVAL;
return NULL;
}
if(index >= ll->size) {
errno = EINVAL;
return NULL;
}
// No need to loop if the desired indices are either the first or last
if(index == 0)
return ll->start->data;
if(index == (ll->size - 1))
return ll->end->data;
int spoint = (index < (ll->size / 2));
dllnode *p = (spoint) ? ll->start : ll->end;
size_t i = (spoint) ? 0 : ll->size-1;
// This should (theoretically) cut down on fetch times
for(; ((spoint) ? (i < index) : (i > index)) && p != NULL; ((spoint) ? i++ : i--), p = ((spoint) ? p->next : p->prev));
// old imp (above is untested)
// for(size_t i = 0; i < index && p != NULL; i++, p = p->next);
return p;
}
void *dlinkedlist_get(const dlinkedlist * const ll, size_t index) {
dllnode *n = dlinkedlist_getnode(ll, index);
if(!n)
return NULL;
return n->data;
}
void *dlinkedlist_getfirst(const dlinkedlist * const ll) {
return dlinkedlist_get(ll, 0);
}
void *dlinkedlist_getlast(const dlinkedlist * const ll) {
return dlinkedlist_get(ll, ll->size - 1);
}
int dlinkedlist_remove(dlinkedlist * const ll, size_t index) {
if(!ll) {
errno = EINVAL;
return -1;
}
if(index >= ll->size) {
errno = EINVAL;
return -1;
}
dllnode *current = dlinkedlist_getnode(ll, index);
if(!current) {
/* gcc is halucinating an error where there isn't one, claiming that the size of the linked list could, somehow, magically
// grow in the time it takes to grab the desired node, and thus return NULL and cause a NULL Dereference. I am willing to
// be humble and state that the compiler is probably smarter than me, and there is MAYBE an edge case where is COULD occur,
// and thus I should do this check, but I'm unconvinced */
errno = ENOTRECOVERABLE;
return -2;
}
// Handle special cases of removing the start or end
if(index == 0) {
ll->start = current->next;
ll->start->prev = NULL;
} else if(index == (ll->size - 1)) {
ll->end = current->prev;
ll->end->next = NULL;
} else {
// Set the prior's next to the next, set the next's prior to the prior, delete the current one
dllnode *prev = current->prev;
dllnode *next = current->next;
prev->next = next;
next->prev = prev;
}
// Wow, I genuinely can't think of the last time I've needed to use an if-elif-else block
dllnode_free(¤t);
ll->size--;
return 0;
}
|
