1 /* Double linked list support
2
3 Copyright (C) 2016 Molnar Karoly
4
5 This file is part of gputils.
6
7 gputils is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
10 any later version.
11
12 gputils is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with gputils; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
21
22 #include "stdhdr.h"
23 #include "libgputils.h"
24
25 #define LIST_INVALID_ID 0
26
27 typedef struct gp_node {
28 GPNodeHeader(struct gp_node);
29 } gp_node_t;
30
31 typedef struct gp_list {
32 GPListHeader(struct gp_node);
33 } gp_list_t;
34
35 static unsigned int list_serial_id = 1;
36
37 /*------------------------------------------------------------------------------------------------*/
38
39 void *
gp_list_node_new(size_t Item_size)40 gp_list_node_new(size_t Item_size)
41 {
42 if (Item_size == 0) {
43 fprintf(stderr, "%s() -- Item_size is 0.\n", __func__);
44 exit(1);
45 }
46
47 return GP_Calloc(1, Item_size);
48 }
49
50 /*------------------------------------------------------------------------------------------------*/
51
52 void
gp_list_node_free(void * List,void * Node)53 gp_list_node_free(void *List, void *Node)
54 {
55 gp_list_t *l;
56
57 if ((List == NULL) || (Node == NULL)) {
58 return;
59 }
60
61 l = (gp_list_t *)List;
62
63 if (l->node_del != NULL) {
64 (*l->node_del)(Node);
65 }
66 else {
67 free(Node);
68 }
69 }
70
71 /*------------------------------------------------------------------------------------------------*/
72
73 void *
gp_list_node_append(void * List,void * Node)74 gp_list_node_append(void *List, void *Node)
75 {
76 gp_list_t *l;
77 gp_node_t *n;
78
79 if ((List == NULL) || (Node == NULL)) {
80 return NULL;
81 }
82
83 l = (gp_list_t *)List;
84
85 if (l->serial_id == LIST_INVALID_ID) {
86 l->serial_id = list_serial_id++;
87 }
88
89 n = (gp_node_t *)Node;
90 n->prev = l->last;
91 n->next = NULL;
92
93 if (l->first == NULL) {
94 /* The list is empty. */
95 l->first = n;
96 l->curr = n;
97 }
98 else {
99 /* Append the new node to the end of the list. */
100 l->last->next = n;
101 }
102
103 l->last = n;
104 n->list_id = l->serial_id;
105 (l->num_nodes)++;
106
107 return Node;
108 }
109
110 /*------------------------------------------------------------------------------------------------*/
111
112 void *
gp_list_node_insert_after(void * List,void * Node,void * Node_new)113 gp_list_node_insert_after(void *List, void *Node, void *Node_new)
114 {
115 gp_list_t *l;
116 gp_node_t *n;
117 gp_node_t *new;
118 gp_node_t *next;
119
120 if ((List == NULL) || (Node == NULL) || (Node_new == NULL)) {
121 return NULL;
122 }
123
124 l = (gp_list_t *)List;
125 n = (gp_node_t *)Node;
126 new = (gp_node_t *)Node_new;
127
128 next = n->next;
129 new->prev = n;
130 new->next = next;
131
132 if (l->last == n) {
133 /* This is last node of the list. */
134 l->last = new;
135 }
136
137 if (next != NULL) {
138 /* The "next" node exists. */
139 next->prev = new;
140 }
141
142 n->next = new;
143 new->list_id = l->serial_id;
144 (l->num_nodes)++;
145
146 return Node_new;
147 }
148
149 /*------------------------------------------------------------------------------------------------*/
150
151 void *
gp_list_node_insert_before(void * List,void * Node,void * Node_new)152 gp_list_node_insert_before(void *List, void *Node, void *Node_new)
153 {
154 gp_list_t *l;
155 gp_node_t *n;
156 gp_node_t *new;
157 gp_node_t *prev;
158
159 if ((List == NULL) || (Node == NULL) || (Node_new == NULL)) {
160 return NULL;
161 }
162
163 l = (gp_list_t *)List;
164 n = (gp_node_t *)Node;
165 new = (gp_node_t *)Node_new;
166
167 prev = n->prev;
168 new->prev = prev;
169 new->next = n;
170
171 if (l->first == n) {
172 /* This is first node of the list. */
173 l->first = new;
174 l->curr = new;
175 }
176
177 if (prev != NULL) {
178 /* The "prev" node exists. */
179 prev->next = new;
180 }
181
182 n->prev = new;
183 new->list_id = l->serial_id;
184 (l->num_nodes)++;
185
186 return Node_new;
187 }
188
189 /*------------------------------------------------------------------------------------------------*/
190
191 void *
gp_list_node_remove(void * List,void * Node)192 gp_list_node_remove(void *List, void *Node)
193 {
194 gp_list_t *l;
195 gp_node_t *n;
196
197 if ((List == NULL) || (Node == NULL)) {
198 return NULL;
199 }
200
201 l = (gp_list_t *)List;
202 n = (gp_node_t *)Node;
203
204 if (n->list_id != l->serial_id) {
205 gp_error("The node{%u} does not belong to this list{%u}.", n->list_id, l->serial_id);
206 assert(0);
207 }
208
209 if (l->first == n) {
210 /* This is first node of the list, the next will be the first. */
211 l->first = n->next;
212 l->curr = n->next;
213 }
214 else {
215 /* The previous node connects to next. */
216 n->prev->next = n->next;
217 }
218
219 if (l->last == n) {
220 /* This is last node of the list, the previous will be the last. */
221 l->last = n->prev;
222 }
223 else {
224 /* The next node connects to previous. */
225 n->next->prev = n->prev;
226 }
227
228 n->prev = NULL;
229 n->next = NULL;
230 n->list_id = 0;
231 (l->num_nodes)--;
232
233 return Node;
234 }
235
236 /*------------------------------------------------------------------------------------------------*/
237
238 void *
gp_list_node_move(void * Dst,void * Src,void * Node)239 gp_list_node_move(void *Dst, void *Src, void *Node)
240 {
241 return gp_list_node_append(Dst, gp_list_node_remove(Src, Node));
242 }
243
244 /*------------------------------------------------------------------------------------------------*/
245
246 void
gp_list_node_delete(void * List,void * Node)247 gp_list_node_delete(void *List, void *Node)
248 {
249 gp_list_node_free(List, gp_list_node_remove(List, Node));
250 }
251
252 /*------------------------------------------------------------------------------------------------*/
253
254 void
gp_list_set_delete_node_func(void * List,gp_node_del_t Function)255 gp_list_set_delete_node_func(void *List, gp_node_del_t Function)
256 {
257 gp_list_t *l;
258
259 if (List == NULL) {
260 return;
261 }
262
263 l = (gp_list_t *)List;
264 l->node_del = Function;
265 }
266
267 /*------------------------------------------------------------------------------------------------*/
268
269 void **
gp_list_make_block(void * List,size_t Num_nodes,size_t Item_size)270 gp_list_make_block(void *List, size_t Num_nodes, size_t Item_size)
271 {
272 gp_list_t *l;
273 gp_node_t **ptr_array;
274 unsigned int id;
275 size_t i;
276
277 if ((List == NULL) || (Num_nodes == 0) || (Item_size == 0)) {
278 return NULL;
279 }
280
281 l = (gp_list_t *)List;
282
283 if (l->first != NULL) {
284 gp_error("%s() -- The block list already exists, can not be created again.", __func__);
285 assert(0);
286 }
287
288 id = list_serial_id++;
289 ptr_array = (gp_node_t **)GP_Malloc(Num_nodes * sizeof(gp_node_t *));
290 l->num_nodes = Num_nodes;
291 l->serial_id = id;
292
293 for (i = 0; i < Num_nodes; i++) {
294 ptr_array[i] = (gp_node_t *)gp_list_node_new(Item_size);
295 ptr_array[i]->list_id = id;
296 }
297
298 /* Do not process the last item. */
299 Num_nodes--;
300
301 /* Initialize the pointers to create the linked list. */
302 for (i = 0; i < Num_nodes; i++) {
303 ptr_array[i + 1]->prev = ptr_array[i];
304 ptr_array[i]->next = ptr_array[i + 1];
305 }
306
307 /* The first->prev and last->next values is already NULL. (calloc) */
308
309 l->first = ptr_array[0];
310 l->curr = ptr_array[0];
311 l->last = ptr_array[Num_nodes];
312
313 return (void **)ptr_array;
314 }
315
316 /*------------------------------------------------------------------------------------------------*/
317
318 static void
_fresh_list_ids(gp_list_t * List,gp_node_t * Start_node)319 _fresh_list_ids(gp_list_t *List, gp_node_t *Start_node)
320 {
321 gp_node_t *node;
322 unsigned int id;
323
324 id = List->serial_id;
325 node = (Start_node != NULL) ? Start_node : List->first;
326 while (node != NULL) {
327 node->list_id = id;
328 node = node->next;
329 }
330 }
331
332 /*------------------------------------------------------------------------------------------------*/
333
334 void
gp_list_move(void * Dst,void * Src)335 gp_list_move(void *Dst, void *Src)
336 {
337 gp_list_t *d;
338 gp_list_t *s;
339
340 if ((Dst == NULL) || (Src == NULL)) {
341 return;
342 }
343
344 d = (gp_list_t *)Dst;
345 s = (gp_list_t *)Src;
346
347 if (s->first != NULL) {
348 /* Append the nodes from the "Src" list to the "Dst". */
349 if (s->num_nodes == 0) {
350 fprintf(stderr, "%s() -- Src->num_nodes: %zu", __func__, s->num_nodes);
351 assert(0);
352 }
353
354 if (d->first == NULL) {
355 if (d->num_nodes > 0) {
356 fprintf(stderr, "%s() -- Dst->num_nodes: %zu", __func__, d->num_nodes);
357 assert(0);
358 }
359
360 d->serial_id = list_serial_id++;
361 d->first = s->first;
362 d->curr = s->first;
363 }
364 else {
365 if (d->num_nodes == 0) {
366 fprintf(stderr, "%s() -- Dst->num_nodes: %zu", __func__, d->num_nodes);
367 assert(0);
368 }
369
370 d->last->next = s->first;
371 s->first->prev = d->last;
372 }
373
374 d->last = s->last;
375 d->num_nodes += s->num_nodes;
376 _fresh_list_ids(d, s->first);
377
378 /* In the "Src" list will not stay reference onto any node. */
379 gp_list_clear(Src);
380 }
381 }
382
383 /*------------------------------------------------------------------------------------------------*/
384
385 void *
gp_list_clone_list(const void * List,int (Cmp_func)(const void *,const void *))386 gp_list_clone_list(const void *List, int (Cmp_func)(const void *, const void *))
387 {
388 const gp_list_t *l;
389 size_t n_nodes;
390 size_t i;
391 gp_node_t *node;
392 gp_node_t **array;
393
394 if ((List == NULL) || (Cmp_func == NULL)) {
395 return NULL;
396 }
397
398 l = (const gp_list_t *)List;
399 n_nodes = l->num_nodes;
400
401 if (n_nodes == 0) {
402 return NULL;
403 }
404
405 array = (gp_node_t **)GP_Malloc(n_nodes * sizeof(gp_node_t *));
406 node = l->first;
407 i = 0;
408 while (node != NULL) {
409 array[i] = node;
410 ++i;
411 assert(i <= n_nodes);
412 node = node->next;
413 }
414
415 if (n_nodes > 1) {
416 qsort(array, n_nodes, sizeof(gp_node_t *), Cmp_func);
417 }
418
419 return array;
420 }
421
422 /*------------------------------------------------------------------------------------------------*/
423
424 void
gp_list_reset(void * List)425 gp_list_reset(void *List)
426 {
427 gp_list_t *l;
428
429 if (List == NULL) {
430 return;
431 }
432
433 l = (gp_list_t *)List;
434 l->curr = l->first;
435 }
436
437 /*------------------------------------------------------------------------------------------------*/
438
439 void
gp_list_set_access_point(void * List,void * Node)440 gp_list_set_access_point(void *List, void *Node)
441 {
442 gp_list_t *l;
443 gp_node_t *n;
444
445 if (List == NULL) {
446 return;
447 }
448
449 l = (gp_list_t *)List;
450 n = (gp_node_t *)Node;
451
452 if (n->list_id != l->serial_id) {
453 gp_error("The node{%u} does not belong to this list{%u}.", n->list_id, l->serial_id);
454 assert(0);
455 }
456
457 l->curr = n;
458 }
459
460 /*------------------------------------------------------------------------------------------------*/
461
462 void
gp_list_clear(void * List)463 gp_list_clear(void *List)
464 {
465 if (List == NULL) {
466 return;
467 }
468
469 memset(List, 0, sizeof(gp_list_t));
470 }
471
472 /*------------------------------------------------------------------------------------------------*/
473
474 void
gp_list_delete(void * List)475 gp_list_delete(void *List)
476 {
477 gp_list_t *l;
478 gp_node_t *node;
479 gp_node_t *next;
480
481 if (List == NULL) {
482 return;
483 }
484
485 l = (gp_list_t *)List;
486
487 node = l->first;
488 while (node != NULL) {
489 next = node->next;
490 gp_list_node_delete(List, node);
491 node = next;
492 }
493
494 gp_list_clear(List);
495 }
496