pset.h 4.34 KB
Newer Older
Götz Lindenmaier's avatar
Götz Lindenmaier committed
1
2
3
4
5
6
7
8
9
10
/*
 * Project:     libFIRM
 * File name:   ir/adt/pset.h
 * Purpose:     Declarations for pset.
 * 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.
Michael Beck's avatar
Michael Beck committed
11
12
 */

Christian Schäfer's avatar
Christian Schäfer committed
13
14
15
16
17
#ifndef _PSET_H
#define _PSET_H

#include <stddef.h>

Michael Beck's avatar
Michael Beck committed
18
19
20
21
22
23
24
25
/**
 * The abstract type of a pset (Set of pointers).
 *
 * This kind of sets stores only pointer to elements, the elements itself
 * must be stored somewere else.
 *
 * @see set
 */
Christian Schäfer's avatar
Christian Schäfer committed
26
27
typedef struct pset pset;

Michael Beck's avatar
Michael Beck committed
28
/** The entry of a pset, representing an element pointer in the set and it's meta-information */
Christian Schäfer's avatar
Christian Schäfer committed
29
30
31
32
33
typedef struct {
  unsigned hash;
  void *dptr;
} pset_entry;

Michael Beck's avatar
Michael Beck committed
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
/**
 * The type of a set compare function.
 *
 * @param elt   pointer to an element
 * @param key   pointer to another element
 *
 * @return
 *    0 if the elements are identically, non-zero else
 */
typedef int (*pset_cmp_fun) (const void *elt, const void *key);

/**
 * Creates a new pset.
 *
 * @param func    the compare function of this pset
 * @param slots   number of slots
 *
 * @returns
 *    created pset
 */
pset *new_pset (pset_cmp_fun func, int slots);

/**
 * Deletes a pset.
 *
 * @note
 *    This does NOT delete the elements of this pset, just it's pointers!
 */
void del_pset (pset *pset);

/**
 * Searches an element pointer in a pset.
 *
 * @param pset  the pset to search in
 * @param key   the element to is searched
 * @param hash  the hash value of key
 *
 * @return
 *    the pointer of the found element in the pset of NULL if it was not found
 */
void *pset_find (pset *pset, const void *key, unsigned hash);

/**
 * Inserts an element pointer into a pset.
 *
 * @param pset  the pset to insert in
 * @param key   a pointer to the element to 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 set_entry.
Christian Schäfer's avatar
Christian Schäfer committed
89

Michael Beck's avatar
Michael Beck committed
90
91
 */
void *pset_insert (pset *pset, const void *key, unsigned hash);
Michael Beck's avatar
Michael Beck committed
92

Michael Beck's avatar
Michael Beck committed
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
/**
 * Inserts an element pointer into a pset and returns its pset_entry.
 *
 * @param pset  the pset to insert in
 * @param key   a pointer to the element to be inserted
 * @param hash  the hash-value of the element
 *
 * @return a pointer to the pset_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 pset, this functions does
 *    nothing but returning its pset_entry.
 */
pset_entry *pset_hinsert (pset *pset, const void *key, unsigned hash);
Christian Schäfer's avatar
Christian Schäfer committed
108

Michael Beck's avatar
Michael Beck committed
109
110
111
112
113
114
115
116
117
118
119
120
121
122
/**
 * Removes an element from a pset.
 *
 * @param pset  the pset to insert in
 * @param key   a pointer to the element to be inserted
 * @param hash  the hash-value of the element
 *
 * @return
 *    the pointer to the removed element
 *
 * @remark
 *    The current implementation did not allow to remove non-existing elements
 */
void *pset_remove (pset *pset, const void *key, unsigned hash);
Christian Schäfer's avatar
Christian Schäfer committed
123

Michael Beck's avatar
Michael Beck committed
124
/** returns the first element of a pset */
Michael Beck's avatar
Michael Beck committed
125
void *pset_first (pset *pset);
Michael Beck's avatar
Michael Beck committed
126
127

/** returns the next element of a pset */
Michael Beck's avatar
Michael Beck committed
128
void *pset_next (pset *pset);
Michael Beck's avatar
Michael Beck committed
129

Michael Beck's avatar
Michael Beck committed
130
131
/** Breaks the iteration of a set. Must be called before the next pset_first() call */
void pset_break (pset *pset);
Christian Schäfer's avatar
Christian Schäfer committed
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172

#define new_pset(cmp, slots) (PSET_TRACE (new_pset) ((cmp), (slots)))
#define pset_find(pset, key, hash) \
  _pset_search ((pset), (key), (hash), _pset_find)
#define pset_insert(pset, key, hash) \
  _pset_search ((pset), (key), (hash), _pset_insert)
#define pset_hinsert(pset, key, hash) \
  ((pset_entry *)_pset_search ((pset), (key), (hash), _pset_hinsert))

#ifdef STATS
void pset_stats (pset *);
#else
# define pset_stats(s) ((void)0)
#endif

#ifdef DEBUG
void pset_describe (pset *);
#endif

/* @@@ NYI */
#define PSET_VRFY(pset) (void)0


/* Private */

typedef enum { _pset_find, _pset_insert, _pset_hinsert } _pset_action;

void *_pset_search (pset *, const void *, unsigned, _pset_action);

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

#endif