1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
|
/* $Id: slset.h 4800 2009-10-02 13:36:20Z potyra $
*
* Structure for a single linked set.
*
* Copyright (C) 2008-2009 FAUmachine Team <info@faumachine.org>.
* This program is free software. You can redistribute it and/or modify it
* under the terms of the GNU General Public License, either version 2 of
* the License, or (at your option) any later version. See COPYING.
*/
#ifndef __SLSET_H_INCLUDED
#define __SLSET_H_INCLUDED
#include <stdbool.h>
#include <stdlib.h>
/** entry in a single linked set. */
struct slset_entry {
/** pointer to next element. */
struct slset_entry *next;
/** data object */
void *data;
};
/** single linked set, stores element in ascending order. */
struct slset {
/** pointer to first element */
struct slset_entry *first;
/** comparison operator for data objects (may be NULL)
* @param o1 first object to compare
* @param o2 second object to compare
* @return -1 if o1 < o2, 0 if o1 == o2, 1 otherwise.
*/
int (*compare)(const void *o1, const void *o2);
};
/** create a single linked set.
* @param comparison operator for ordering (may be NULL, then < and == will
* get used). This must be a function without side effects
* (__attribute__((__pure__))).
* @param allocator: function to allocate memory (e.g. malloc).
* @return created single linked set.
*/
extern
struct slset *
slset_create(
int (*compare)(const void *o1, const void *o2),
void *(*allocator)(size_t)
);
/** destroy a single linked set.
* @param s set instance
* @param deallocator deallocator (e.g. free)
*/
extern void
slset_destroy(struct slset *s, void (*deallocator)(void *));
/** destroy a single linked set, calling free for each data entry.
* @param s set instance
* @param deallocator deallocator (e.g. free)
*/
extern void
slset_destroy_data(struct slset *s, void (*deallocator)(void *));
/** add data to the set, in case it doesn't exist yet, otherwise a NOOP.
* @param s set instance.
* @param data data object.
* @param allocator function to allocate memory (e.g. malloc)
*/
extern void
slset_add(
struct slset *s,
void *data,
void *(*allocator)(size_t)
);
/** add all entries from src to dst, assuming the compare functions are
* identical. All entries get removed from src.
* @param src source set instance.
* @param dst destination set instance.
* @param allocator function to allocate memory (e.g. malloc)
* @param deallocator function to free memory (e.g. free)
*/
extern void
slset_move_all(
struct slset *src,
struct slset *dst,
void *(*allocator)(size_t),
void (*deallocator)(void *)
);
/** Check if the set is empty.
* @param s set to check.
* @return true, if the set is empty, false otherwise.
*/
extern bool
slset_empty(const struct slset *s);
/** Check if needle is in haystack.
* @param haystack set to check if needle is an element of.
* @param needle look for needle in haystack.
* @return true, if needle is in haystack.
*/
extern bool
slset_contains(const struct slset *haystack, const void *needle);
/** remove data from stack.
* @param s set instance.
* @param data data to remove from the set
* @param deallocator function to free memory (e.g. free)
*/
extern void
slset_remove(struct slset *s, const void *data, void (*deallocator)(void *));
/** remove all entries from given set
* @param s set to clear.
* @param deallocator function to free memory (e.g. free)
*/
extern void
slset_clear(struct slset *s, void (*deallocator)(void *));
/** remove all elements which are equal or greater than data according to
* the comparison function.
* @param s set instance.
* @param data compare the entries with data, remove everything which
* doesn't return -1 from the comparison function with data
* as second argument.
* @param del_data true, if the truncated data should be freed as well.
*/
extern void
slset_truncate_at(struct slset *s, const void *data, bool del_data);
/** debugging function to print out the set.
* @param s set in question.
* @param print_data function to print the data.
*/
extern void
slset_debug_print(
const struct slset *s,
const char *(*print_data)(const void *)
);
#endif /* __SLSET_H_INCLUDED */
|
