set.h 6.78 KB
Newer Older
Götz Lindenmaier's avatar
Götz Lindenmaier committed
1
/*
2
 * Copyright (C) 1995-2011 University of Karlsruhe.  All right reserved.
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
18
 */
Boris Boesler's avatar
Boris Boesler committed
19

Michael Beck's avatar
Michael Beck committed
20
/**
21
22
23
 * @file
 * @brief       hashset: datastructure containing objects accessible by their key
 * @author      Markus Armbruster
yb9976's avatar
typo    
yb9976 committed
24
 * @version     $Id$
Michael Beck's avatar
Michael Beck committed
25
 */
26
27
#ifndef FIRM_ADT_SET_H
#define FIRM_ADT_SET_H
Christian Schäfer's avatar
Christian Schäfer committed
28
29
30

#include <stddef.h>

31
32
#include "../begin.h"

Michael Beck's avatar
Michael Beck committed
33
34
35
36
/**
 * The abstract type of a set.
 *
 * This sets stores copies of its elements, so there is no need
Götz Lindenmaier's avatar
typos    
Götz Lindenmaier committed
37
 * to store the elements after they were added to a set.
Michael Beck's avatar
Michael Beck committed
38
39
40
 *
 * @see pset
 */
Christian Schäfer's avatar
Christian Schäfer committed
41
42
typedef struct set set;

43
/** The entry of a set, representing an element in the set and its meta-information */
Christian Schäfer's avatar
Christian Schäfer committed
44
typedef struct set_entry {
45
46
47
48
	unsigned hash;  /**< the hash value of the element */
	size_t size;    /**< the size of the element */
	int dptr[1];    /**< the element itself, data copied in must not need more
	                     alignment than this */
Christian Schäfer's avatar
Christian Schäfer committed
49
50
} set_entry;

Michael Beck's avatar
Michael Beck committed
51
52
53
54
55
56
57
58
59
/**
 * The type of a set compare function.
 *
 * @param elt   pointer to an element
 * @param key   pointer to another element
 * @param size  size of the elements
 *
 * @return
 *    0 if the elements are identically, non-zero else
Michael Beck's avatar
Michael Beck committed
60
61
 *
 * @note
Götz Lindenmaier's avatar
comment    
Götz Lindenmaier committed
62
63
64
 *    Although it is possible to define different meanings of equality
 *    of two elements of a set, they can be only equal if their sizes are
 *    are equal. This is checked before the compare function is called.
Michael Beck's avatar
Michael Beck committed
65
 */
Christian Schäfer's avatar
Christian Schäfer committed
66
67
typedef int (*set_cmp_fun) (const void *elt, const void *key, size_t size);

Michael Beck's avatar
Michael Beck committed
68
69
70
/**
 * Creates a new set.
 *
Michael Beck's avatar
Michael Beck committed
71
 * @param func    The compare function of this set.
72
 * @param slots   Initial number of collision chains.  I.e., \#slots
Michael Beck's avatar
Michael Beck committed
73
 *                different keys can be hashed without collisions.
Michael Beck's avatar
Michael Beck committed
74
75
76
77
 *
 * @returns
 *    created set
 */
78
FIRM_API set *new_set(set_cmp_fun func, size_t slots);
Michael Beck's avatar
Michael Beck committed
79

Michael Beck's avatar
Michael Beck committed
80
81
/**
 * Deletes a set and all elements of it.
Michael Beck's avatar
Michael Beck committed
82
83
 *
 * @param set  the set to delete
Michael Beck's avatar
Michael Beck committed
84
 */
Michael Beck's avatar
Michael Beck committed
85
FIRM_API void del_set(set *set);
Michael Beck's avatar
Michael Beck committed
86

Michael Beck's avatar
Michael Beck committed
87
88
89
90
91
/**
 * Returns the number of elements in a set.
 *
 * @param set   the set
 */
92
FIRM_API size_t set_count(set *set);
Michael Beck's avatar
Michael Beck committed
93

Michael Beck's avatar
Michael Beck committed
94
95
96
97
98
99
100
101
102
/**
 * Searches an element in a set.
 *
 * @param set   the set to search in
 * @param key   the element to is searched
 * @param size  the size of key
 * @param hash  the hash value of key
 *
 * @return
Götz Lindenmaier's avatar
comment    
Götz Lindenmaier committed
103
 *    The address of the found element in the set or NULL if it was not found.
Michael Beck's avatar
Michael Beck committed
104
 */
Michael Beck's avatar
Michael Beck committed
105
FIRM_API void *set_find(set *set, const void *key, size_t size, unsigned hash);
Michael Beck's avatar
Michael Beck committed
106

Michael Beck's avatar
Michael Beck committed
107
108
109
110
/**
 * Inserts an element into a set.
 *
 * @param set   the set to insert in
Götz Lindenmaier's avatar
comment    
Götz Lindenmaier committed
111
 * @param key   a pointer to the element to be inserted.  Element is copied!
Michael Beck's avatar
Michael Beck committed
112
113
114
115
116
117
 * @param size  the size of the element that should be inserted
 * @param hash  the hash-value of the element
 *
 * @return a pointer to the inserted element
 *
 * @note
118
 *    It is not possible to insert one element more than once. If an element
Michael Beck's avatar
Michael Beck committed
119
120
121
 *    that should be inserted is already in the set, this functions does
 *    nothing but returning its pointer.
 */
Michael Beck's avatar
Michael Beck committed
122
FIRM_API void *set_insert(set *set, const void *key, size_t size, unsigned hash);
Christian Schäfer's avatar
Christian Schäfer committed
123

Michael Beck's avatar
Michael Beck committed
124
125
126
127
/**
 * Inserts an element into a set and returns its set_entry.
 *
 * @param set   the set to insert in
Götz Lindenmaier's avatar
comment    
Götz Lindenmaier committed
128
 * @param key   a pointer to the element to be inserted. Element is copied!
Michael Beck's avatar
Michael Beck committed
129
130
131
132
133
134
 * @param size  the size of the element that should be inserted
 * @param hash  the hash-value of the element
 *
 * @return a pointer to the set_entry of the inserted element
 *
 * @note
135
 *    It is not possible to insert an element more than once. If an element
Michael Beck's avatar
Michael Beck committed
136
137
138
 *    that should be inserted is already in the set, this functions does
 *    nothing but returning its set_entry.
 */
Michael Beck's avatar
Michael Beck committed
139
FIRM_API set_entry *set_hinsert(set *set, const void *key, size_t size, unsigned hash);
Christian Schäfer's avatar
Christian Schäfer committed
140

141
142
143
144
/**
 * Inserts an element into a set, zero-terminate it and returns its set_entry.
 *
 * @param set   the set to insert in
Götz Lindenmaier's avatar
comment    
Götz Lindenmaier committed
145
 * @param key   a pointer to the element to be inserted.  Element is copied!
146
147
148
149
150
151
 * @param size  the size of the element that should be inserted
 * @param hash  the hash-value of the element
 *
 * @return a pointer to the set_entry of the inserted element
 *
 * @note
Götz Lindenmaier's avatar
comment    
Götz Lindenmaier committed
152
 *    It is not possible to insert on element more than once. If an element
153
154
155
 *    that should be inserted is already in the set, this functions does
 *    nothing but returning its set_entry.
 */
Michael Beck's avatar
Michael Beck committed
156
FIRM_API set_entry *set_hinsert0(set *set, const void *key, size_t size, unsigned hash);
157

Michael Beck's avatar
Michael Beck committed
158
159
160
161
162
163
164
/**
 * Returns the first element of a set.
 *
 * @param set  the set to iterate
 *
 * @return a pointer to the element or NULL if the set is empty
 */
Michael Beck's avatar
Michael Beck committed
165
FIRM_API void *set_first(set *set);
Michael Beck's avatar
Michael Beck committed
166

Michael Beck's avatar
Michael Beck committed
167
168
169
170
171
172
173
174
/**
 * Returns the next element of a set.
 *
 * @param set  the set to iterate
 *
 * @return a pointer to the next element or NULL if the
 *         iteration is finished
 */
Michael Beck's avatar
Michael Beck committed
175
FIRM_API void *set_next(set *set);
Michael Beck's avatar
Michael Beck committed
176

Michael Beck's avatar
Michael Beck committed
177
178
/**
 * Breaks the iteration of a set. Must be called before
Michael Beck's avatar
Michael Beck committed
179
 * the next set_first() call if the iteration was NOT
Michael Beck's avatar
Michael Beck committed
180
181
 * finished.
 *
Michael Beck's avatar
Michael Beck committed
182
 * @param set  the set
Michael Beck's avatar
Michael Beck committed
183
 */
Michael Beck's avatar
Michael Beck committed
184
FIRM_API void set_break(set *set);
Christian Schäfer's avatar
Christian Schäfer committed
185

186
187
188
189
190
191
/**
 * Iterates over an set.
 *
 * @param set    the set
 * @param entry  the iterator
 */
192
#define foreach_set(set, type, entry) for (entry = (type) set_first(set); entry; entry = (type) set_next(set))
193

Michael Beck's avatar
Michael Beck committed
194
/* implementation specific */
195
#define new_set(cmp, slots) ((new_set) ((cmp), (slots)))
Christian Schäfer's avatar
Christian Schäfer committed
196
197
198
199
200
201
#define set_find(set, key, size, hash) \
  _set_search ((set), (key), (size), (hash), _set_find)
#define set_insert(set, key, size, hash) \
  _set_search ((set), (key), (size), (hash), _set_insert)
#define set_hinsert(set, key, size, hash) \
  ((set_entry *)_set_search ((set), (key), (size), (hash), _set_hinsert))
202
203
#define set_hinsert0(set, key, size, hash) \
  ((set_entry *)_set_search ((set), (key), (size), (hash), _set_hinsert0))
Christian Schäfer's avatar
Christian Schäfer committed
204
205
206
207

#define SET_VRFY(set) (void)0

#ifdef STATS
Michael Beck's avatar
Michael Beck committed
208
209
210
211
212
213
/**
 * Prints statistics on a set to stdout.
 *
 * @param set  the set
 */
void set_stats (set *set);
Christian Schäfer's avatar
Christian Schäfer committed
214
215
216
217
218
#else
# define set_stats(s) ((void)0)
#endif

#ifdef DEBUG
Michael Beck's avatar
Michael Beck committed
219
220
221
222
223
224
225
226
227
/**
 * Describe a set.
 *
 * Writes a description of a set to stdout. The description includes:
 * - a header telling how many elements (nkey) and segments (nseg) are in use
 * - for every collision chain the number of element with its hash values
 *
 * @param set  the set
 */
228
FIRM_API void set_describe(set *set);
Christian Schäfer's avatar
Christian Schäfer committed
229
230
231
232
233
#endif


/* Private */

234
typedef enum { _set_find, _set_insert, _set_hinsert, _set_hinsert0 } _set_action;
Christian Schäfer's avatar
Christian Schäfer committed
235

Michael Beck's avatar
Michael Beck committed
236
FIRM_API void *_set_search(set *, const void *, size_t, unsigned, _set_action);
Christian Schäfer's avatar
Christian Schäfer committed
237

238
239
#include "../end.h"

Christian Schäfer's avatar
Christian Schäfer committed
240
#endif