set.h 5.29 KB
Newer Older
Götz Lindenmaier's avatar
Götz Lindenmaier committed
1
2
3
4
5
6
7
8
9
10
11
/*
 * Project:     libFIRM
 * File name:   ir/adt/set.h
 * Purpose:     Declarations for set.
 * Author:      Markus Armbruster
 * Modified by:
 * Created:     1999 by getting from fiasco
 * CVS-ID:      $Id$
 * Copyright:   (c) 1995, 1996 Markus Armbruster
 * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
 */
Boris Boesler's avatar
Boris Boesler committed
12

Michael Beck's avatar
Michael Beck committed
13
14
15
16
17
18
/**
 * @file set.h
 *
 * Declarations for set.
 */

Christian Schäfer's avatar
Christian Schäfer committed
19
20
21
22
23
#ifndef _SET_H
#define _SET_H

#include <stddef.h>

Michael Beck's avatar
Michael Beck committed
24
25
26
27
28
29
30
31
/**
 * The abstract type of a set.
 *
 * This sets stores copies of its elements, so there is no need
 * to store the elements after there were added to a set.
 *
 * @see pset
 */
Christian Schäfer's avatar
Christian Schäfer committed
32
33
typedef struct set set;

Michael Beck's avatar
Michael Beck committed
34
/** The entry of a set, representing an element in the set and it's meta-information */
Christian Schäfer's avatar
Christian Schäfer committed
35
typedef struct set_entry {
Michael Beck's avatar
Michael Beck committed
36
37
38
  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
Christian Schäfer's avatar
Christian Schäfer committed
39
40
41
				   alignment than this */
} set_entry;

Michael Beck's avatar
Michael Beck committed
42
43
44
45
46
47
48
49
50
/**
 * 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
51
52
53
54
55
 *
 * @note
 *    Although it is possible to define different meanings for equality of two
 *    elements of a sets, they can be only equal if there sizes are
 *    equal. This is checked before the compare function is called.
Michael Beck's avatar
Michael Beck committed
56
 */
Christian Schäfer's avatar
Christian Schäfer committed
57
58
typedef int (*set_cmp_fun) (const void *elt, const void *key, size_t size);

Michael Beck's avatar
Michael Beck committed
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
/**
 * Creates a new set.
 *
 * @param func    the compare function of this set
 * @param slots   number of slots
 *
 * @returns
 *    created set
 */
set *new_set (set_cmp_fun func, int slots);

/** Deletes a set and all elements of it. */
void del_set (set *set);

/**
 * 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
 *    the address of the found element in the set of NULL if it was not found
 */
void *set_find (set *set, const void *key, size_t size, unsigned hash);
Michael Beck's avatar
Michael Beck committed
85

Michael Beck's avatar
Michael Beck committed
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
/**
 * Inserts an element into a set.
 *
 * @param set   the set to insert in
 * @param key   a pointer to the element to be inserted
 * @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
 *    It is not possible to insert on element more than once. If a element
 *    that should be inserted is already in the set, this functions does
 *    nothing but returning its pointer.
 */
void *set_insert (set *set, const void *key, size_t size, unsigned hash);
Christian Schäfer's avatar
Christian Schäfer committed
102

Michael Beck's avatar
Michael Beck committed
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
/**
 * Inserts an element into a set and returns its set_entry.
 *
 * @param set   the set to insert in
 * @param key   a pointer to the element to be inserted
 * @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
 *    It is not possible to insert on element more than once. If a element
 *    that should be inserted is already in the set, this functions does
 *    nothing but returning its set_entry.
 */
set_entry *set_hinsert (set *set, const void *key, size_t size, unsigned hash);
Christian Schäfer's avatar
Christian Schäfer committed
119

120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
/**
 * Inserts an element into a set, zero-terminate it and returns its set_entry.
 *
 * @param set   the set to insert in
 * @param key   a pointer to the element to be inserted
 * @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
 *    It is not possible to insert on element more than once. If a element
 *    that should be inserted is already in the set, this functions does
 *    nothing but returning its set_entry.
 */
set_entry *set_hinsert0 (set *set, const void *key, size_t size, unsigned hash);

Michael Beck's avatar
Michael Beck committed
137
138
/** Returns the first element of a set. */
void *set_first (set *set);
Michael Beck's avatar
Michael Beck committed
139

Michael Beck's avatar
Michael Beck committed
140
141
/** Returns the next element of a set. */
void *set_next (set *set);
Michael Beck's avatar
Michael Beck committed
142

Michael Beck's avatar
Michael Beck committed
143
144
/** Breaks the iteration of a set. Must be called before the next set_first() call */
void set_break (set *set);
Christian Schäfer's avatar
Christian Schäfer committed
145

Michael Beck's avatar
Michael Beck committed
146
/* implementation specific */
Christian Schäfer's avatar
Christian Schäfer committed
147
148
149
150
151
152
153
#define new_set(cmp, slots) (SET_TRACE (new_set) ((cmp), (slots)))
#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))
154
155
#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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171

#define SET_VRFY(set) (void)0

#ifdef STATS
void set_stats (set *);
#else
# define set_stats(s) ((void)0)
#endif

#ifdef DEBUG
void set_describe (set *);
#endif


/* Private */

172
typedef enum { _set_find, _set_insert, _set_hinsert, _set_hinsert0 } _set_action;
Christian Schäfer's avatar
Christian Schäfer committed
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187

void *_set_search (set *, const void *, size_t, unsigned, _set_action);

#if defined(DEBUG) && defined(HAVE_GNU_MALLOC)
extern const char *set_tag;
# ifdef SET_ID
#   define SET_TRACE set_tag = SET_ID,
# else
#   define SET_TRACE set_tag = __FILE__,
# endif
#else /* !(DEBUG && HAVE_GNU_MALLOC) */
#   define SET_TRACE
#endif /* !(DEBUG && HAVE_GNU_MALLOC) */

#endif