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#ifndef LIST_H
10#define LIST_H
11
12#include "sql_mem.h"
13#include "sql_hash.h"
14
15typedef struct node {
16 struct sql_hash_e e;
17 struct node *next;
18 void *data;
19} node;
20
21typedef void (*fdestroy) (void *);
22
23typedef struct list {
24 sql_allocator *sa;
25 sql_hash *ht;
26 MT_Lock ht_lock; /* latch protecting ht */
27 fdestroy destroy;
28 node *h;
29 node *t;
30 int cnt;
31 int expected_cnt;
32} list;
33
34typedef int (*traverse_func) (void *clientdata, int seqnr, void *data);
35
36extern list *list_create(fdestroy destroy);
37extern list *sa_list(sql_allocator *sa);
38extern list *list_new(sql_allocator *sa, fdestroy destroy);
39
40extern void list_destroy(list *l);
41extern int list_length(list *l);
42extern int list_empty(list *l);
43
44extern list *list_append(list *l, void *data);
45extern list *list_append_before(list *l, node *n, void *data);
46extern list *list_prepend(list *l, void *data);
47
48extern node *list_remove_node(list *l, node *n);
49extern void list_remove_data(list *l, void *data);
50extern void list_remove_list(list *l, list *data);
51extern void list_move_data(list *l, list *d, void *data);
52
53
54extern int list_traverse(list *l, traverse_func f, void *clientdata);
55
56/* the compare function gets one element from the list and a key from the
57 * as input from the find function
58 * Returns 0 if data and key are equal
59 * */
60typedef int (*fcmp) (void *data, void *key);
61typedef void *(*fcmpvalidate) (void *v1, void *v2, int *cmp);
62typedef void *(*fvalidate) (void *v1, void *v2);
63typedef int (*fcmp2) (void *data, void *v1, void *v2);
64typedef void *(*fdup) (void *data);
65typedef void *(*freduce) (void *v1, void *v2);
66typedef void *(*freduce2) (sql_allocator *sa, void *v1, void *v2);
67typedef void *(*fmap) (void *data, void *clientdata);
68
69extern void *list_traverse_with_validate(list *l, void *data, fvalidate cmp);
70extern void *list_append_with_validate(list *l, void *data, fvalidate cmp);
71extern void *list_append_sorted(list *l, void *data, fcmpvalidate cmp);
72extern node *list_find(list *l, void *key, fcmp cmp);
73extern int list_position(list *l, void *val);
74extern void * list_fetch(list *l, int pos);
75extern list *list_select(list *l, void *key, fcmp cmp, fdup dup);
76extern list *list_order(list *l, fcmp cmp, fdup dup);
77extern list *list_distinct(list *l, fcmp cmp, fdup dup);
78extern void *list_reduce(list *l, freduce red, fdup dup);
79extern void *list_reduce2(list *l, freduce2 red, sql_allocator *sa);
80extern list *list_map(list *l, void *data, fmap f);
81extern int list_cmp(list *l1, list *l2, fcmp cmp);
82/* cmp the lists in link order */
83extern int list_match(list *l1, list *l2, fcmp cmp);
84/* match the lists (in any order) */
85extern list *list_sort(list *l, fkeyvalue key, fdup dup);
86/* The sort function sorts the list using the key function, which
87 * translates the list item values into integer keyvalues. */
88/* sometimes more complex functions are needed to compute a key, then
89 * we can pass the keys via an array, to keysort */
90extern list *list_keysort(list *l, int *key, fdup dup);
91
92extern list *list_dup(list *l, fdup dup);
93extern list *list_merge(list *l, list *data, fdup dup);
94extern list *list_merge_destroy(list *l, list *data, fdup dup);
95
96extern void list_hash_delete(list *l, void *data, fcmp cmp);
97extern void* list_hash_add(list *l, void *data, fcmp cmp);
98extern void list_hash_clear(list *l);
99
100#endif /* LIST_H */
101