1 /* This file is part of GNU Dico
2 Copyright (C) 2003-2020 Sergey Poznyakoff
3
4 GNU Dico is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 3, or (at your option)
7 any later version.
8
9 GNU Dico 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
15 along with GNU Dico. If not, see <http://www.gnu.org/licenses/>. */
16
17 #include <config.h>
18 #include <dico.h>
19 #include <sys/types.h>
20 #include <stdlib.h>
21 #include <errno.h>
22
23 struct list_entry {
24 struct list_entry *next, *prev;
25 void *data;
26 };
27
28 struct dico_list {
29 size_t count;
30 struct list_entry *head, *tail;
31 int flags;
32 struct iterator *itr;
33 dico_list_comp_t comp_fun;
34 void *comp_data;
35 dico_list_iterator_t free_item;
36 void *free_data;
37 };
38
39 struct iterator {
40 struct iterator *next;
41 dico_list_t list;
42 struct list_entry *cur;
43 int advanced;
44 size_t pos;
45 };
46
47 static int
cmp_ptr(const void * a,const void * b,void * data)48 cmp_ptr(const void *a, const void *b, void *data)
49 {
50 return a != b;
51 }
52
53 struct dico_list *
dico_list_create(void)54 dico_list_create(void)
55 {
56 struct dico_list *p = malloc(sizeof(*p));
57 if (p) {
58 p->count = 0;
59 p->head = p->tail = NULL;
60 p->flags = 0;
61 p->itr = NULL;
62 p->comp_fun = cmp_ptr;
63 p->comp_data = NULL;
64 p->free_item = NULL;
65 p->free_data = NULL;
66 }
67 return p;
68 }
69
70 int
dico_list_clear(struct dico_list * list)71 dico_list_clear(struct dico_list *list)
72 {
73 struct list_entry *p;
74
75 if (!list) {
76 errno = EINVAL;
77 return 1;
78 }
79
80 p = list->head;
81 list->head = list->tail = NULL;
82 list->count = 0;
83
84 while (p) {
85 struct list_entry *next = p->next;
86 if (list->free_item)
87 list->free_item(p->data, list->free_data);
88 free(p);
89 p = next;
90 }
91 return 0;
92 }
93
94 void
dico_list_destroy(struct dico_list ** plist)95 dico_list_destroy(struct dico_list **plist)
96 {
97 struct dico_list *list;
98
99 if (!plist || !*plist)
100 return;
101
102 list = *plist;
103 *plist = NULL;
104
105 dico_list_clear(list);
106 free(list);
107 }
108
109 void
dico_list_free_item(struct dico_list * list,void * item)110 dico_list_free_item(struct dico_list *list, void *item)
111 {
112 if (list->free_item)
113 list->free_item(item, list->free_data);
114 }
115
116 void *
dico_iterator_current(dico_iterator_t ip)117 dico_iterator_current(dico_iterator_t ip)
118 {
119 if (!ip)
120 return NULL;
121 return ip->cur ? ip->cur->data : NULL;
122 }
123
124 size_t
dico_iterator_position(dico_iterator_t ip)125 dico_iterator_position(dico_iterator_t ip)
126 {
127 if (!ip)
128 return 0;
129 return ip->pos;
130 }
131
132 static void
dico_iterator_attach(dico_iterator_t itr,dico_list_t list)133 dico_iterator_attach(dico_iterator_t itr, dico_list_t list)
134 {
135 itr->list = list;
136 itr->cur = list->head;
137 itr->next = list->itr;
138 itr->advanced = 0;
139 itr->pos = 0;
140 list->itr = itr;
141 }
142
143 static dico_iterator_t
dico_iterator_detach(dico_iterator_t iter)144 dico_iterator_detach(dico_iterator_t iter)
145 {
146 dico_iterator_t cur, prev;
147
148 for (cur = iter->list->itr, prev = NULL;
149 cur;
150 prev = cur, cur = cur->next)
151 if (cur == iter)
152 break;
153
154 if (cur) {
155 if (prev)
156 prev->next = cur->next;
157 else
158 cur->list->itr = cur->next;
159 }
160 return cur;
161 }
162
163 dico_iterator_t
dico_list_iterator(dico_list_t list)164 dico_list_iterator(dico_list_t list)
165 {
166 dico_iterator_t itr;
167
168 if (!list) {
169 errno = EINVAL;
170 return NULL;
171 }
172 itr = malloc(sizeof(*itr));
173 if (itr)
174 dico_iterator_attach(itr, list);
175 return itr;
176 }
177
178 void
dico_iterator_destroy(dico_iterator_t * ip)179 dico_iterator_destroy(dico_iterator_t *ip)
180 {
181 dico_iterator_t itr;
182
183 if (!ip || !*ip)
184 return;
185 itr = dico_iterator_detach(*ip);
186 if (itr)
187 free(itr);
188 *ip = NULL;
189 }
190
191 static void
_iterator_increase_pos(dico_iterator_t ip,size_t after)192 _iterator_increase_pos(dico_iterator_t ip, size_t after)
193 {
194 for (; ip; ip = ip->next) {
195 if (ip->pos > after)
196 ip->pos++;
197 }
198 }
199
200 static void
_iterator_advance(dico_iterator_t ip,struct list_entry * e)201 _iterator_advance(dico_iterator_t ip, struct list_entry *e)
202 {
203 for (; ip; ip = ip->next) {
204 if (ip->cur == e) {
205 ip->cur = e->next;
206 ip->advanced++;
207 }
208 }
209 }
210
211 void *
dico_iterator_first(dico_iterator_t ip)212 dico_iterator_first(dico_iterator_t ip)
213 {
214 if (!ip)
215 return NULL;
216 ip->cur = ip->list->head;
217 ip->advanced = 0;
218 ip->pos = 0;
219 return dico_iterator_current(ip);
220 }
221
222 void *
dico_iterator_next(dico_iterator_t ip)223 dico_iterator_next(dico_iterator_t ip)
224 {
225 if (!ip || !ip->cur)
226 return NULL;
227 if (!ip->advanced) {
228 ip->cur = ip->cur->next;
229 ip->pos++;
230 }
231 ip->advanced = 0;
232 return dico_iterator_current(ip);
233 }
234
235 void *
dico_iterator_prev(dico_iterator_t ip)236 dico_iterator_prev(dico_iterator_t ip)
237 {
238 if (!ip || !ip->cur)
239 return NULL;
240 ip->cur = ip->cur->prev;
241 if (!ip->advanced)
242 ip->pos--;
243 ip->advanced = 0;
244 return dico_iterator_current(ip);
245 }
246
247 void *
dico_iterator_item(dico_iterator_t ip,size_t n)248 dico_iterator_item(dico_iterator_t ip, size_t n)
249 {
250 if (n > ip->pos) {
251 if (!ip->advanced) {
252 ip->cur = ip->cur->next;
253 ip->pos++;
254 }
255 ip->advanced = 0;
256
257 while (ip->cur && ip->pos < n) {
258 ip->cur = ip->cur->next;
259 ip->pos++;
260 }
261 } else if (n < ip->pos) {
262 if (!ip->advanced)
263 ip->pos--;
264 ip->advanced = 0;
265
266 while (ip->cur && ip->pos > n) {
267 ip->cur = ip->cur->prev;
268 ip->pos--;
269 }
270 }
271 return dico_iterator_current(ip);
272 }
273
274 static void _dico_list_remove_item(struct dico_list *list,
275 struct list_entry *p,
276 void **pptr);
277
278 void
dico_iterator_remove_current(dico_iterator_t ip,void ** pptr)279 dico_iterator_remove_current(dico_iterator_t ip, void **pptr)
280 {
281 _dico_list_remove_item(ip->list, ip->cur, pptr);
282 }
283
284 void
dico_iterator_set_data(dico_iterator_t ip,void * data)285 dico_iterator_set_data(dico_iterator_t ip, void *data)
286 {
287 ip->cur->data = data;
288 }
289
290 void *
dico_list_head(struct dico_list * list)291 dico_list_head(struct dico_list *list)
292 {
293 return list->head ? list->head->data : NULL;
294 }
295
296 void *
dico_list_tail(struct dico_list * list)297 dico_list_tail(struct dico_list *list)
298 {
299 return list->tail ? list->tail->data : NULL;
300 }
301
302 void *
dico_list_item(struct dico_list * list,size_t n)303 dico_list_item(struct dico_list *list, size_t n)
304 {
305 struct list_entry *p;
306 if (!list || n >= list->count)
307 return NULL;
308 for (p = list->head; n > 0 && p; p = p->next, n--)
309 ;
310 return p->data;
311 }
312
313 size_t
dico_list_count(struct dico_list * list)314 dico_list_count(struct dico_list *list)
315 {
316 if (!list)
317 return 0;
318 return list->count;
319 }
320
321 int
dico_list_set_free_item(struct dico_list * list,dico_list_iterator_t free_item,void * data)322 dico_list_set_free_item(struct dico_list *list,
323 dico_list_iterator_t free_item, void *data)
324 {
325 if (!list) {
326 errno = EINVAL;
327 return 1;
328 }
329 list->free_item = free_item;
330 list->free_data = data;
331 return 0;
332 }
333
334 int
dico_list_set_comparator(struct dico_list * list,dico_list_comp_t comp,void * data)335 dico_list_set_comparator(struct dico_list *list, dico_list_comp_t comp,
336 void *data)
337 {
338 if (!list) {
339 errno = EINVAL;
340 return -1;
341 }
342 list->comp_fun = comp;
343 list->comp_data = data;
344 return 0;
345 }
346
347 int
dico_list_set_comparator_data(dico_list_t list,void * data)348 dico_list_set_comparator_data(dico_list_t list, void *data)
349 {
350 if (!list) {
351 errno = EINVAL;
352 return -1;
353 }
354 list->comp_data = data;
355 return 0;
356 }
357
358 int
dico_list_set_flags(struct dico_list * list,int flags)359 dico_list_set_flags(struct dico_list *list, int flags)
360 {
361 if (!list) {
362 errno = EINVAL;
363 return 1;
364 }
365 list->flags = flags;
366 return 0;
367 }
368
369 int
dico_list_get_flags(struct dico_list * list)370 dico_list_get_flags(struct dico_list *list)
371 {
372 if (list)
373 return list->flags;
374 return 0;
375 }
376
377 dico_list_comp_t
dico_list_get_comparator(struct dico_list * list)378 dico_list_get_comparator(struct dico_list *list)
379 {
380 if (!list) {
381 errno = EINVAL;
382 return NULL;
383 }
384 return list->comp_fun;
385 }
386
387 void *
dico_list_get_comparator_data(struct dico_list * list)388 dico_list_get_comparator_data(struct dico_list *list)
389 {
390 if (!list) {
391 errno = EINVAL;
392 return NULL;
393 }
394 return list->comp_data;
395 }
396
397 int
_dico_list_append(struct dico_list * list,void * data)398 _dico_list_append(struct dico_list *list, void *data)
399 {
400 struct list_entry *ep = malloc(sizeof(*ep));
401 if (!ep)
402 return 1;
403 ep->next = NULL;
404 ep->prev = list->tail;
405 ep->data = data;
406 if (list->tail)
407 list->tail->next = ep;
408 else
409 list->head = ep;
410 list->tail = ep;
411 list->count++;
412 return 0;
413 }
414
415 int
_dico_list_prepend(struct dico_list * list,void * data)416 _dico_list_prepend(struct dico_list *list, void *data)
417 {
418 struct list_entry *ep = malloc(sizeof(*ep));
419 if (!ep)
420 return 1;
421 ep->data = data;
422 ep->next = list->head;
423 ep->prev = NULL;
424 list->head = ep;
425 if (!list->tail)
426 list->tail = list->head;
427 list->count++;
428 _iterator_increase_pos(list->itr, 0);
429 return 0;
430 }
431
432 int
dico_list_append(struct dico_list * list,void * data)433 dico_list_append(struct dico_list *list, void *data)
434 {
435 if (!list) {
436 errno = EINVAL;
437 return 1;
438 }
439 if ((list->flags & DICO_LIST_COMPARE_TAIL)
440 && list->comp_fun
441 && list->tail
442 && list->comp_fun(list->tail->data, data, list->comp_data) == 0) {
443 errno = EEXIST;
444 return 1;
445 }
446 return _dico_list_append(list, data);
447 }
448
449 int
dico_list_prepend(struct dico_list * list,void * data)450 dico_list_prepend(struct dico_list *list, void *data)
451 {
452 if (!list) {
453 errno = EINVAL;
454 return 1;
455 }
456 if ((list->flags & DICO_LIST_COMPARE_HEAD)
457 && list->comp_fun
458 && list->head
459 && list->comp_fun(list->head->data, data, list->comp_data) == 0) {
460 errno = EEXIST;
461 return 1;
462 }
463 return _dico_list_prepend(list, data);
464 }
465
466 static void
_dico_list_remove_item(struct dico_list * list,struct list_entry * p,void ** pptr)467 _dico_list_remove_item(struct dico_list *list, struct list_entry *p,
468 void **pptr)
469 {
470 struct list_entry *prev;
471
472 _iterator_advance(list->itr, p);
473
474 prev = p->prev;
475 if (prev)
476 prev->next = p->next;
477 else
478 list->head = list->head->next;
479
480 if (p->next)
481 p->next->prev = prev;
482 else
483 list->tail = prev;
484
485 list->count--;
486
487 if (pptr)
488 *pptr = p->data;
489 else if (list->free_item)
490 list->free_item (p->data, list->free_data);
491
492 free(p);
493 }
494
495 int
_dico_list_remove(struct dico_list * list,void * data,dico_list_comp_t cmp,void * cmpdata,void ** pptr)496 _dico_list_remove(struct dico_list *list, void *data,
497 dico_list_comp_t cmp, void *cmpdata,
498 void **pptr)
499 {
500 struct list_entry *p;
501
502 if (!list || !list->head) {
503 errno = ENOENT;
504 return 1;
505 }
506
507 if (!cmp)
508 cmp = cmp_ptr;
509 for (p = list->head; p; p = p->next)
510 if (cmp(p->data, data, cmpdata) == 0)
511 break;
512
513 if (!p) {
514 errno = ENOENT;
515 return 1;
516 }
517
518 _dico_list_remove_item(list, p, pptr);
519
520 return 0;
521 }
522
523 int
dico_list_remove(struct dico_list * list,void * data,void ** pret)524 dico_list_remove(struct dico_list *list, void *data, void **pret)
525 {
526 if (!list) {
527 errno = EINVAL;
528 return 1;
529 }
530 return _dico_list_remove(list, data, list->comp_fun, list->comp_data, pret);
531 }
532
533 void *
dico_list_pop(struct dico_list * list)534 dico_list_pop(struct dico_list *list)
535 {
536 void *p;
537 if (!list->tail)
538 return NULL;
539 _dico_list_remove_item(list, list->tail, &p);
540 return p;
541 }
542
543 /* Note: if modifying this function, make sure it does not allocate any
544 memory! */
545 void
dico_list_iterate(struct dico_list * list,dico_list_iterator_t func,void * data)546 dico_list_iterate(struct dico_list *list, dico_list_iterator_t func,
547 void *data)
548 {
549 struct iterator itr;
550 void *p;
551
552 if (!list)
553 return;
554 dico_iterator_attach(&itr, list);
555 for (p = dico_iterator_first(&itr); p; p = dico_iterator_next(&itr)) {
556 if (func(p, data))
557 break;
558 }
559 dico_iterator_detach(&itr);
560 }
561
562 void *
_dico_list_locate(struct dico_list * list,void * data,dico_list_comp_t cmp,void * cmpdata)563 _dico_list_locate(struct dico_list *list, void *data,
564 dico_list_comp_t cmp, void *cmpdata)
565 {
566 struct list_entry *cur;
567 if (!list)
568 return NULL;
569 if (!cmp)
570 cmp = cmp_ptr;
571 for (cur = list->head; cur; cur = cur->next)
572 if (cmp(cur->data, data, cmpdata) == 0)
573 break;
574 return cur ? cur->data : NULL;
575 }
576
577 void *
dico_list_locate(struct dico_list * list,void * data)578 dico_list_locate(struct dico_list *list, void *data)
579 {
580 if (!list)
581 return NULL;
582 return _dico_list_locate(list, data, list->comp_fun, list->comp_data);
583 }
584
585 int
_dico_list_insert_sorted(struct dico_list * list,void * data,dico_list_comp_t cmp,void * cmpdata)586 _dico_list_insert_sorted(struct dico_list *list, void *data,
587 dico_list_comp_t cmp, void *cmpdata)
588 {
589 int rc;
590 struct list_entry *cur;
591 size_t i;
592
593 if (!list) {
594 errno = EINVAL;
595 return 1;
596 }
597
598 if (!cmp)
599 cmp = cmp_ptr;
600
601 if (!list->head)
602 return _dico_list_append(list, data);
603
604 for (cur = list->head, i = 0; cur; cur = cur->next, i++) {
605 int res = cmp(cur->data, data, cmpdata);
606 if (res > 0)
607 break;
608 else if (res == 0 && list->flags)
609 return EEXIST;
610 }
611
612 if (cur && !cur->prev) {
613 rc = _dico_list_prepend(list, data);
614 } else if (!cur) {
615 rc = _dico_list_append(list, data);
616 } else {
617 struct list_entry *ep = malloc(sizeof(*ep));
618 if (ep) {
619 struct list_entry *prev = cur->prev;
620
621 rc = 0;
622 ep->data = data;
623
624 ep->next = cur;
625 cur->prev = ep;
626
627 ep->prev = prev;
628 prev->next = ep;
629
630 _iterator_increase_pos(list->itr, i - 1);
631
632 list->count++;
633 } else
634 rc = 1;
635 }
636 return rc;
637 }
638
639 int
dico_list_insert_sorted(struct dico_list * list,void * data)640 dico_list_insert_sorted(struct dico_list *list, void *data)
641 {
642 if (!list) {
643 errno = EINVAL;
644 return 1;
645 }
646 return _dico_list_insert_sorted(list, data,
647 list->comp_fun, list->comp_data);
648 }
649
650 /* Computes an intersection of the two lists. The resulting list
651 contains elements from the list A that are also encountered
652 in the list B. Elements are compared using function CMP.
653 The resulting list preserves the ordering of A. */
654 dico_list_t
dico_list_intersect(dico_list_t a,dico_list_t b,dico_list_comp_t cmp,void * cmpdata)655 dico_list_intersect(dico_list_t a, dico_list_t b,
656 dico_list_comp_t cmp, void *cmpdata)
657 {
658 dico_list_t res;
659 dico_iterator_t itr = dico_list_iterator(a);
660 void *p;
661
662 if (!itr)
663 return NULL;
664 res = dico_list_create();
665 if (!res)
666 return NULL;
667 for (p = dico_iterator_first(itr); p; p = dico_iterator_next(itr)) {
668 if (_dico_list_locate(b, p, cmp, cmpdata))
669 _dico_list_append(res, p); /* FIXME: check return, and? */
670 }
671 dico_iterator_destroy (&itr);
672 return res;
673 }
674
675 /* Return true if there exists a non-empty intersection of lists A and B. */
676 int
dico_list_intersect_p(dico_list_t a,dico_list_t b,dico_list_comp_t cmp,void * cmpdata)677 dico_list_intersect_p(dico_list_t a, dico_list_t b,
678 dico_list_comp_t cmp, void *cmpdata)
679 {
680 dico_iterator_t itr = dico_list_iterator(a);
681 void *p;
682 int rc = 0;
683
684 for (p = dico_iterator_first(itr); p; p = dico_iterator_next(itr)) {
685 if (_dico_list_locate(b, p, cmp, cmpdata)) {
686 rc = 1;
687 break;
688 }
689 }
690 dico_iterator_destroy (&itr);
691 return rc;
692 }
693