1/*
2 * This Source Code Form is subject to the terms of the Mozilla Public
3 * License, v. 2.0. If a copy of the MPL was not distributed with this
4 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
5 *
6 * Copyright 1997 - July 2008 CWI, August 2008 - 2019 MonetDB B.V.
7 */
8
9#include "monetdb_config.h"
10#include "gdk.h" /* for GDKmalloc() & GDKfree() */
11#include "sql_list.h"
12
13static node *
14node_create(sql_allocator *sa, void *data)
15{
16 node *n = (sa)?SA_NEW(sa, node):MNEW(node);
17
18 if (n == NULL)
19 return NULL;
20 n->next = NULL;
21 n->data = data;
22 return n;
23}
24
25static list *
26list_init(list *l, sql_allocator *sa, fdestroy destroy)
27{
28 if (l) {
29 *l = (list) {
30 .sa = sa,
31 .destroy = destroy,
32 };
33 MT_lock_init(&l->ht_lock, "sa_ht_lock");
34 }
35 return l;
36}
37
38list *
39list_create(fdestroy destroy)
40{
41 return list_init(MNEW(list), NULL, destroy);
42}
43
44list *
45sa_list(sql_allocator *sa)
46{
47 list *l = (sa)?SA_NEW(sa, list):MNEW(list);
48 return list_init(l, sa, NULL);
49}
50
51list *
52list_new(sql_allocator *sa, fdestroy destroy)
53{
54 list *l = (sa)?SA_NEW(sa, list):MNEW(list);
55 return list_init(l, sa, destroy);
56}
57
58static list *
59list_new_(list *l)
60{
61 list *res = NULL;
62 if (l->sa)
63 res = list_new(l->sa, l->destroy);
64 else
65 res = list_create(l->destroy);
66 return res;
67}
68
69int
70list_empty(list *l)
71{
72 if (l)
73 return list_length(l) == 0;
74 return 1;
75}
76
77static void
78node_destroy(list *l, node *n)
79{
80 if (n->data && l->destroy) {
81 l->destroy(n->data);
82 n->data = NULL;
83 }
84 if (!l->sa)
85 _DELETE(n);
86}
87
88void
89list_destroy(list *l)
90{
91 if (l) {
92 node *n = l->h;
93
94 MT_lock_destroy(&l->ht_lock);
95 l->h = NULL;
96 if (l->destroy || l->sa == NULL) {
97 while (n) {
98 node *t = n;
99
100 n = t->next;
101 node_destroy(l, t);
102 }
103 }
104 if (!l->sa)
105 _DELETE(l);
106 }
107}
108
109int
110list_length(list *l)
111{
112 if (l)
113 return l->cnt;
114 return 0;
115}
116
117list *
118list_append(list *l, void *data)
119{
120 node *n = node_create(l->sa, data);
121
122 if (n == NULL)
123 return NULL;
124 if (l->cnt) {
125 l->t->next = n;
126 } else {
127 l->h = n;
128 }
129 l->t = n;
130 l->cnt++;
131 MT_lock_set(&l->ht_lock);
132 if (l->ht) {
133 int key = l->ht->key(data);
134
135 if (hash_add(l->ht, key, data) == NULL) {
136 MT_lock_unset(&l->ht_lock);
137 return NULL;
138 }
139 }
140 MT_lock_unset(&l->ht_lock);
141 return l;
142}
143
144void*
145list_append_with_validate(list *l, void *data, fvalidate cmp)
146{
147 node *n = node_create(l->sa, data), *m;
148 void* err = NULL;
149
150 if (n == NULL)
151 return NULL;
152 if (l->cnt) {
153 for (m = l->h; m; m = m->next) {
154 err = cmp(m->data, data);
155 if(err)
156 return err;
157 }
158 l->t->next = n;
159 } else {
160 l->h = n;
161 }
162 l->t = n;
163 l->cnt++;
164 MT_lock_set(&l->ht_lock);
165 if (l->ht) {
166 int key = l->ht->key(data);
167
168 if (hash_add(l->ht, key, data) == NULL) {
169 MT_lock_unset(&l->ht_lock);
170 return NULL;
171 }
172 }
173 MT_lock_unset(&l->ht_lock);
174 return NULL;
175}
176
177void*
178list_append_sorted(list *l, void *data, fcmpvalidate cmp)
179{
180 node *n = node_create(l->sa, data), *m, *prev = NULL;
181 int first = 1, comp = 0;
182 void* err = NULL;
183
184 if (n == NULL)
185 return NULL;
186 if (l->cnt == 0) {
187 l->h = n;
188 l->t = n;
189 } else {
190 for (m = l->h; m; m = m->next) {
191 err = cmp(m->data, data, &comp);
192 if(err)
193 return err;
194 if(comp < 0)
195 break;
196 first = 0;
197 prev = m;
198 }
199 if(first) {
200 n->next = l->h;
201 l->h = n;
202 } else if(!m) {
203 l->t->next = n;
204 l->t = n;
205 } else {
206 assert(prev);
207 n->next = m;
208 prev->next = n;
209 }
210 }
211 l->cnt++;
212 MT_lock_set(&l->ht_lock);
213 if (l->ht) {
214 int key = l->ht->key(data);
215
216 if (hash_add(l->ht, key, data) == NULL) {
217 MT_lock_unset(&l->ht_lock);
218 return NULL;
219 }
220 }
221 MT_lock_unset(&l->ht_lock);
222 return NULL;
223}
224
225list *
226list_append_before(list *l, node *m, void *data)
227{
228 node *p = l->h;
229 node *n = node_create(l->sa, data);
230
231 if (n == NULL)
232 return NULL;
233 n->next = m;
234 if (p == m){
235 l->h = n;
236 } else {
237 while (p->next && p->next != m)
238 p = p->next;
239 p->next = n;
240 }
241 l->cnt++;
242 MT_lock_set(&l->ht_lock);
243 if (l->ht) {
244 int key = l->ht->key(data);
245
246 if (hash_add(l->ht, key, data) == NULL) {
247 MT_lock_unset(&l->ht_lock);
248 return NULL;
249 }
250 }
251 MT_lock_unset(&l->ht_lock);
252 return l;
253}
254
255list *
256list_prepend(list *l, void *data)
257{
258 node *n = node_create(l->sa, data);
259
260 if (n == NULL)
261 return NULL;
262 if (!l->cnt) {
263 l->t = n;
264 }
265 n->next = l->h;
266 l->h = n;
267 l->cnt++;
268 MT_lock_set(&l->ht_lock);
269 if (l->ht) {
270 int key = l->ht->key(data);
271
272 if (hash_add(l->ht, key, data) == NULL) {
273 MT_lock_unset(&l->ht_lock);
274 return NULL;
275 }
276 }
277 MT_lock_unset(&l->ht_lock);
278 return l;
279}
280
281static void
282hash_delete(sql_hash *h, void *data)
283{
284 int key = h->key(data);
285 sql_hash_e *e, *p = h->buckets[key&(h->size-1)];
286
287 e = p;
288 for (; p && p->value != data ; p = p->chain)
289 e = p;
290 if (p && p->value == data) {
291 if (p == e)
292 h->buckets[key&(h->size-1)] = p->chain;
293 else
294 e->chain = p->chain;
295 }
296}
297
298node *
299list_remove_node(list *l, node *n)
300{
301 void *data = n->data;
302 node *p = l->h;
303
304 if (p != n)
305 while (p && p->next != n)
306 p = p->next;
307 if (p == n) {
308 l->h = n->next;
309 p = NULL;
310 } else if ( p != NULL) {
311 p->next = n->next;
312 }
313 if (n == l->t)
314 l->t = p;
315 MT_lock_set(&l->ht_lock);
316 if (l->ht && data)
317 hash_delete(l->ht, data);
318 MT_lock_unset(&l->ht_lock);
319 node_destroy(l, n);
320 l->cnt--;
321 return p;
322}
323
324void
325list_remove_data(list *s, void *data)
326{
327 node *n;
328
329 /* maybe use compare func */
330 if (s == NULL)
331 return;
332 for (n = s->h; n; n = n->next) {
333 if (n->data == data) {
334 MT_lock_set(&s->ht_lock);
335 if (s->ht && n->data)
336 hash_delete(s->ht, n->data);
337 MT_lock_unset(&s->ht_lock);
338 n->data = NULL;
339 list_remove_node(s, n);
340 break;
341 }
342 }
343}
344
345void
346list_remove_list(list *l, list *data)
347{
348 node *n;
349
350 for (n=data->h; n; n = n->next)
351 list_remove_data(l, n->data);
352}
353
354void
355list_move_data(list *s, list *d, void *data)
356{
357 node *n;
358
359 for (n = s->h; n; n = n->next) {
360 if (n->data == data) {
361 MT_lock_set(&s->ht_lock);
362 if (s->ht && n->data)
363 hash_delete(s->ht, n->data);
364 MT_lock_unset(&s->ht_lock);
365 n->data = NULL; /* make sure data isn't destroyed */
366 list_remove_node(s, n);
367 break;
368 }
369 }
370 list_append(d, data);
371}
372
373int
374list_traverse(list *l, traverse_func f, void *clientdata)
375{
376 int res = 0, seqnr = 0;
377 node *n = l->h;
378
379 while (n && !res) {
380 res = f(clientdata, seqnr++, n->data);
381 n = n->next;
382 }
383 return res;
384}
385
386void *
387list_traverse_with_validate(list *l, void *data, fvalidate cmp)
388{
389 void* err = NULL;
390
391 for (node *n = l->h; n; n = n->next) {
392 err = cmp(n->data, data);
393 if(err)
394 break;
395 }
396 return err;
397}
398
399node *
400list_find(list *l, void *key, fcmp cmp)
401{
402 node *n = NULL;
403
404 if (key) {
405 if (cmp) {
406 for (n = l->h; n; n = n->next) {
407 if (cmp(n->data, key) == 0) {
408 return n;
409 }
410 }
411 } else {
412 for (n = l->h; n; n = n->next) {
413 if (n->data == key)
414 return n;
415 }
416 }
417 }
418 return NULL;
419}
420
421int
422list_cmp(list *l1, list *l2, fcmp cmp)
423{
424 node *n, *m;
425 int res = 0;
426
427 if (l1 == l2)
428 return 0;
429 if (!l1 && l2 && list_empty(l2))
430 return 0;
431 if (!l2 && l1 && list_empty(l1))
432 return 0;
433 if (!l1 || !l2 || (list_length(l1) != list_length(l2)))
434 return -1;
435
436 for (n = l1->h, m = l2->h; res == 0 && n; n = n->next, m = m->next) {
437 res = cmp(n->data, m->data);
438 }
439 return res;
440}
441
442int
443list_match(list *l1, list *l2, fcmp cmp)
444{
445 node *n, *m;
446 ulng chk = 0;
447
448 if (l1 == l2)
449 return 0;
450
451 if (!l1 || !l2 || (list_length(l1) != list_length(l2)))
452 return -1;
453
454 for (n = l1->h; n; n = n->next) {
455 int pos = 0, fnd = 0;
456 for (m = l2->h; m; m = m->next, pos++) {
457 if (!(chk & ((ulng) 1 << pos)) &&
458 cmp(n->data, m->data) == 0) {
459 chk |= (ulng) 1 << pos;
460 fnd = 1;
461 }
462 }
463 if (!fnd)
464 return -1;
465 }
466 return 0;
467}
468
469list *
470list_keysort(list *l, int *keys, fdup dup)
471{
472 list *res;
473 node *n = NULL;
474 int i, cnt = list_length(l);
475 void **data;
476
477 data = GDKmalloc(cnt*sizeof(void *));
478 if (data == NULL) {
479 return NULL;
480 }
481 res = list_new_(l);
482 if (res == NULL) {
483 GDKfree(data);
484 return NULL;
485 }
486 for (n = l->h, i = 0; n; n = n->next, i++) {
487 data[i] = n->data;
488 }
489 /* sort descending */
490 GDKqsort(keys, data, NULL, cnt, sizeof(int), sizeof(void *), TYPE_int, true, true);
491 for(i=0; i<cnt; i++) {
492 list_append(res, dup?dup(data[i]):data[i]);
493 }
494 GDKfree(data);
495 return res;
496}
497
498list *
499list_sort(list *l, fkeyvalue key, fdup dup)
500{
501 list *res;
502 node *n = NULL;
503 int i, *keys, cnt = list_length(l);
504 void **data;
505
506 keys = GDKmalloc(cnt*sizeof(int));
507 data = GDKmalloc(cnt*sizeof(void *));
508 if (keys == NULL || data == NULL) {
509 GDKfree(keys);
510 GDKfree(data);
511 return NULL;
512 }
513 res = list_new_(l);
514 if (res == NULL) {
515 GDKfree(keys);
516 GDKfree(data);
517 return NULL;
518 }
519 for (n = l->h, i = 0; n; n = n->next, i++) {
520 keys[i] = key(n->data);
521 data[i] = n->data;
522 }
523 /* sort descending */
524 GDKqsort(keys, data, NULL, cnt, sizeof(int), sizeof(void *), TYPE_int, true, true);
525 for(i=0; i<cnt; i++) {
526 list_append(res, dup?dup(data[i]):data[i]);
527 }
528 GDKfree(keys);
529 GDKfree(data);
530 return res;
531}
532
533list *
534list_select(list *l, void *key, fcmp cmp, fdup dup)
535{
536 list *res = NULL;
537 node *n = NULL;
538
539 if (key && l) {
540 res = list_new_(l);
541 if(res) {
542 for (n = l->h; n; n = n->next)
543 if (cmp(n->data, key) == 0)
544 list_append(res, dup?dup(n->data):n->data);
545 }
546 }
547 return res;
548}
549
550/* order the list based on the compare function cmp */
551list *
552list_order(list *l, fcmp cmp, fdup dup)
553{
554 list *res = list_new_(l);
555 node *m, *n = NULL;
556
557 /* use simple insert sort */
558 if(res) {
559 for (n = l->h; n; n = n->next) {
560 int append = 1;
561 for (m = res->h; m && append; m = m->next) {
562 if (cmp(n->data, m->data) > 0) {
563 list_append_before(res, m, dup ? dup(n->data) : n->data);
564 append = 0;
565 }
566 }
567 if (append)
568 list_append(res, dup ? dup(n->data) : n->data);
569 }
570 }
571 return res;
572}
573
574list *
575list_distinct(list *l, fcmp cmp, fdup dup)
576{
577 list *res = list_new_(l);
578 node *n = NULL;
579
580 if(res) {
581 for (n = l->h; n; n = n->next) {
582 if (!list_find(res, n->data, cmp)) {
583 list_append(res, dup ? dup(n->data) : n->data);
584 }
585 }
586 }
587 return res;
588}
589
590int
591list_position(list *l, void *val)
592{
593 node *n = NULL;
594 int i;
595
596 for (n = l->h, i=0; n && val != n->data; n = n->next, i++)
597 ;
598 if (n && n->data == val)
599 return i;
600 return -1;
601}
602
603void *
604list_fetch(list *l, int pos)
605{
606 node *n = NULL;
607 int i;
608
609 for (n = l->h, i=0; n && i<pos; n = n->next, i++)
610 ;
611 if (n)
612 return n->data;
613 return NULL;
614}
615
616void *
617list_reduce(list *l, freduce red, fdup dup)
618{
619 void *res = NULL;
620 node *n = l->h;
621
622 if (n) {
623 res = dup?dup(n->data):n->data;
624 for (n = n->next; n; n = n->next) {
625 res = red(res, dup?dup(n->data):n->data);
626 }
627 }
628 return res;
629}
630
631void *
632list_reduce2(list *l, freduce2 red, sql_allocator *sa)
633{
634 void *res = NULL;
635 node *n = l->h;
636
637 if (n) {
638 res = n->data;
639 for (n = n->next; n; n = n->next)
640 res = red(sa, res, n->data);
641 }
642 return res;
643}
644
645
646list *
647list_map(list *l, void *data, fmap map)
648{
649 list *res = list_new_(l);
650
651 node *n = l->h;
652
653 if(res) {
654 while (n) {
655 void *v = map(n->data, data);
656
657 if (v)
658 list_append(res, v);
659 n = n->next;
660 }
661 }
662 return res;
663}
664
665list *
666list_merge(list *l, list *data, fdup dup)
667{
668 if (data) {
669 node *n = data->h;
670
671 while (n) {
672 if (dup && n->data)
673 list_append(l, dup(n->data));
674 else
675 list_append(l, n->data);
676 n = n->next;
677 }
678 }
679 return l;
680}
681
682list *
683list_merge_destroy(list *l, list *data, fdup dup)
684{
685 if (data) {
686 node *n = data->h;
687
688 while (n) {
689 if (dup)
690 list_append(l, dup(n->data));
691 else
692 list_append(l, n->data);
693 n = n->next;
694 }
695 }
696
697 list_destroy(data);
698
699 return l;
700}
701
702list *
703list_dup(list *l, fdup dup)
704{
705 list *res = list_new_(l);
706 return res ? list_merge(res, l, dup) : NULL;
707}
708
709void
710list_hash_delete(list *l, void *data, fcmp cmp)
711{
712 if (l && data) {
713 node *n = list_find(l, data, cmp);
714 if(n) {
715 MT_lock_set(&l->ht_lock);
716 if (l->ht && n->data)
717 hash_delete(l->ht, data);
718 MT_lock_unset(&l->ht_lock);
719 }
720 }
721}
722
723void*
724list_hash_add(list *l, void *data, fcmp cmp)
725{
726 if (l && data) {
727 node *n = list_find(l, data, cmp);
728 if(n) {
729 MT_lock_set(&l->ht_lock);
730 if (l->ht && n->data) {
731 int nkey = l->ht->key(data);
732 if (hash_add(l->ht, nkey, data) == NULL) {
733 MT_lock_unset(&l->ht_lock);
734 return NULL;
735 }
736 }
737 MT_lock_unset(&l->ht_lock);
738 }
739 }
740 return data;
741}
742
743void
744list_hash_clear(list *l)
745{
746 MT_lock_set(&l->ht_lock);
747 l->ht = NULL;
748 MT_lock_unset(&l->ht_lock);
749}
750