1 /*
2 linkedlist: generic c linked list routines
3 Copyright (c) 2004-2016 Adrian M. Gin
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License v2 as published by
7 the Free Software Foundation;
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License along
15 with this program; if not, write to the Free Software Foundation, Inc.,
16 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
17
18 The above copyright notice and this permission notice shall be
19 included in all copies or substantial portions of the Software.
20
21 */
22
23
24 #include <stdint.h>
25 #include <stdlib.h>
26 #include "linkedlist.h"
27
28
LL_DeleteList(LINKED_LIST_t * linkedList)29 void LL_DeleteList(LINKED_LIST_t* linkedList)
30 {
31 LIST_NODE_t* node;
32 node = linkedList->first;
33
34 while(node)
35 {
36 LL_Remove(linkedList, node);
37 node = linkedList->first;
38 }
39 }
40
41
42
LL_DeleteListAndData(LINKED_LIST_t * linkedList)43 void LL_DeleteListAndData(LINKED_LIST_t* linkedList)
44 {
45 LIST_NODE_t* node;
46 node = linkedList->first;
47
48 while(node)
49 {
50 LL_Free(node->data);
51 LL_Remove(linkedList, node);
52 node = linkedList->first;
53 }
54 }
55
56
LL_NewNode(void * data)57 LIST_NODE_t* LL_NewNode(void* data)
58 {
59 LIST_NODE_t* newNode;
60
61 newNode = (LIST_NODE_t*)LL_Malloc(sizeof(LIST_NODE_t));
62
63 // while( newNode == NULL )
64 // {
65 // newNode = (LIST_NODE_t*)malloc(sizeof(LIST_NODE_t));
66 // }
67
68 newNode->next = NULL;
69 newNode->prev = NULL;
70 newNode->data = data;
71 return (LIST_NODE_t*)newNode;
72 }
73
LL_PopData(LINKED_LIST_t * linkedList)74 void* LL_PopData(LINKED_LIST_t* linkedList)
75 {
76 LIST_NODE_t* retNode;
77 void* data = NULL;
78 retNode = linkedList->first;
79 if( retNode )
80 {
81 data = retNode->data;
82 }
83
84 LL_Remove(linkedList, retNode);
85 return data;
86 }
87
LL_AppendData(LINKED_LIST_t * linkedList,void * data)88 void LL_AppendData(LINKED_LIST_t* linkedList, void* data)
89 {
90 LIST_NODE_t* newNode = LL_NewNode(data);
91 LL_InsertEnd(linkedList, newNode);
92 }
93
94
LL_InsertAfter(LINKED_LIST_t * linkedList,LIST_NODE_t * node,LIST_NODE_t * newNode)95 void LL_InsertAfter(LINKED_LIST_t* linkedList, LIST_NODE_t* node, LIST_NODE_t* newNode)
96 {
97 newNode->prev = (struct LIST_NODE_t*)node;
98 newNode->next = node->next;
99 if( node->next == NULL)
100 {
101 linkedList->last = newNode;
102 }
103 else
104 {
105 LIST_NODE_t* tmp;
106 tmp = (LIST_NODE_t*)node->next;
107 tmp->prev = (struct LIST_NODE_t*)newNode;
108 }
109 node->next = (struct LIST_NODE_t*)newNode;
110 }
111
LL_InsertBefore(LINKED_LIST_t * linkedList,LIST_NODE_t * node,LIST_NODE_t * newNode)112 void LL_InsertBefore(LINKED_LIST_t* linkedList, LIST_NODE_t* node, LIST_NODE_t* newNode)
113 {
114 newNode->prev = node->prev;
115 newNode->next = (struct LIST_NODE_t*)node;
116 if( node->prev == NULL )
117 {
118 linkedList->first = newNode;
119 }
120 else
121 {
122 LIST_NODE_t* tmp;
123 tmp = (LIST_NODE_t*)node->prev;
124 tmp->next = (struct LIST_NODE_t*)newNode;
125 }
126 node->prev = (struct LIST_NODE_t*)newNode;
127 }
128
LL_InsertBeginning(LINKED_LIST_t * linkedList,LIST_NODE_t * newNode)129 void LL_InsertBeginning(LINKED_LIST_t* linkedList, LIST_NODE_t* newNode)
130 {
131 if(linkedList->first == NULL)
132 {
133 linkedList->first = newNode;
134 linkedList->last = newNode;
135 newNode->prev = NULL;
136 newNode->next = NULL;
137 }
138 else
139 {
140 LL_InsertBefore(linkedList, linkedList->first, newNode);
141 }
142 }
143
LL_InsertEnd(LINKED_LIST_t * linkedList,LIST_NODE_t * newNode)144 void LL_InsertEnd(LINKED_LIST_t* linkedList, LIST_NODE_t* newNode)
145 {
146 if( linkedList->last == NULL )
147 {
148 LL_InsertBeginning(linkedList, newNode);
149 }
150 else
151 {
152 LL_InsertAfter(linkedList, linkedList->last, newNode);
153 }
154 }
155
156
LL_Remove(LINKED_LIST_t * linkedList,LIST_NODE_t * node)157 void LL_Remove(LINKED_LIST_t* linkedList, LIST_NODE_t* node)
158 {
159
160 if( node == NULL)
161 {
162 return;
163 }
164 //If we are removing the head
165 if( node->prev == NULL )
166 {
167 linkedList->first = (LIST_NODE_t*)node->next;
168 if( node->next )
169 {
170 node->prev = NULL;
171 }
172 }
173 else
174 {
175 LIST_NODE_t* tmp;
176 tmp = (LIST_NODE_t*)node->prev;
177 tmp->next = (struct LIST_NODE_t*)node->next;
178 }
179
180 //If we are removing the tail
181 if( node->next == NULL)
182 {
183 linkedList->last = (LIST_NODE_t*)node->prev;
184 if( node->prev )
185 {
186 node->next = NULL;
187 }
188 }
189 else
190 {
191 LIST_NODE_t* tmp;
192 tmp = (LIST_NODE_t*)node->next;
193 tmp->prev = (struct LIST_NODE_t*)node->prev;
194 }
195 if( node != NULL)
196 {
197 LL_Free(node);
198 }
199 node = NULL;
200 }
201
202
LL_Count(LINKED_LIST_t * linkedList)203 uint16_t LL_Count(LINKED_LIST_t* linkedList)
204 {
205 LIST_NODE_t* tmp;
206 uint16_t count = 0;
207
208 tmp = linkedList->first;
209 while(tmp != NULL)
210 {
211 count++;
212 tmp = tmp->next;
213 }
214
215 return count;
216 }
217
218
LL_ReturnNodeFromIndex(LINKED_LIST_t * linkedList,uint16_t item)219 LIST_NODE_t* LL_ReturnNodeFromIndex(LINKED_LIST_t* linkedList, uint16_t item)
220 {
221 LIST_NODE_t* tmp;
222 uint16_t count = LL_Count(linkedList);
223
224 if(item >= count)
225 {
226 return NULL;
227 }
228
229
230 tmp = linkedList->first;
231 while( (tmp != NULL) && (item) )
232 {
233 item--;
234 tmp = tmp->next;
235 }
236
237 return tmp;
238 }
239
240
241
LL_ReturnNodeDataFromIndex(LINKED_LIST_t * linkedList,uint16_t item)242 void* LL_ReturnNodeDataFromIndex(LINKED_LIST_t* linkedList, uint16_t item)
243 {
244 LIST_NODE_t* tmp;
245
246 tmp = LL_ReturnNodeFromIndex(linkedList, item);
247
248 if( tmp != NULL )
249 {
250 return tmp->data;
251 }
252 return NULL;
253 }
254
255
256
257