summaryrefslogtreecommitdiffhomepage
path: root/ir/adt/cpset.h
blob: 6dae90d9c9a26b3b55662b52df34e348cd28d4c0 (plain)
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
146
147
148
149
150
151
152
153
154
/*
 * This file is part of libFirm.
 * Copyright (C) 2012 University of Karlsruhe.
 */

/**
 * @file
 * @date    16.03.2007
 * @brief   a set of pointers with a custom compare function
 * @author  Matthias Braun
 */
#ifndef FIRM_ADT_CPSET_H
#define FIRM_ADT_CPSET_H

/**
 * @ingroup adt
 * @defgroup Pointer Set (custom Compare)
 * A pointer set with user-definable compare function
 * @{
 */

/**
 * The type of a cpset compare function.
 *
 * @param p1   pointer to an element
 * @param p2   pointer to another element
 *
 * @return  1 if the elements are identically, zero else
 */
typedef int (*cpset_cmp_function) (const void *p1, const void *p2);

/**
 * The type of a cpset hash function.
 */
typedef unsigned (*cpset_hash_function) (const void *obj);

/** @cond PRIVATE */

#define HashSet          cpset_t
#define HashSetIterator  cpset_iterator_t
#define HashSetEntry     cpset_hashset_entry_t
#define ValueType        void*
#define ADDITIONAL_DATA  cpset_cmp_function cmp_function; cpset_hash_function hash_function;
#include "hashset.h"
#undef ADDITIONAL_DATA
#undef ValueType
#undef HashSetEntry
#undef HashSetIterator
#undef HashSet

/** @endcond */

/** a pointer set with custom compare function */
typedef struct cpset_t          cpset_t;
/** iterator over a pointer set with custom compare function
 * @see #cpset_t */
typedef struct cpset_iterator_t cpset_iterator_t;

/**
 * Initializes a cpset
 *
 * @param cpset           Pointer to allocated space for the cpset
 * @param hash_function   The hash function to use
 * @param cmp_function    The compare function to use
 */
void cpset_init(cpset_t *cpset, cpset_hash_function hash_function,
                cpset_cmp_function cmp_function);

/**
 * Initializes a cpset
 *
 * @param cpset              Pointer to allocated space for the cpset
 * @param hash_function      The hash function to use
 * @param cmp_function       The compare function to use
 * @param expected_elements  Number of elements expected in the cpset (roughly)
 */
void cpset_init_size(cpset_t *cpset, cpset_hash_function hash_function,
                     cpset_cmp_function cmp_function,
                     size_t expected_elements);

/**
 * Destroys a cpset and frees the memory allocated for hashtable. The memory of
 * the cpset itself is not freed.
 *
 * @param cpset   Pointer to the cpset
 */
void cpset_destroy(cpset_t *cpset);

/**
 * Inserts an element into a cpset.
 *
 * @param cpset   Pointer to the cpset
 * @param obj     Element to insert into the cpset
 * @returns       The element itself or a pointer to an existing element
 */
void* cpset_insert(cpset_t *cpset, void *obj);

/**
 * Removes an element from a cpset. Does nothing if the cpset doesn't contain the
 * element.
 *
 * @param cpset   Pointer to the cpset
 * @param obj     Pointer to remove from the cpset
 */
void cpset_remove(cpset_t *cpset, const void *obj);

/**
 * Tests whether a cpset contains a pointer
 *
 * @param cpset   Pointer to the cpset
 * @param obj     The pointer to find
 * @returns       An equivalent object to @p obj or NULL
 */
void *cpset_find(const cpset_t *cpset, const void *obj);

/**
 * Returns the number of pointers contained in the cpset
 *
 * @param cpset   Pointer to the cpset
 * @returns       Number of pointers contained in the cpset
 */
size_t cpset_size(const cpset_t *cpset);

/**
 * Initializes a cpset iterator. Sets the iterator before the first element in
 * the cpset.
 *
 * @param iterator   Pointer to already allocated iterator memory
 * @param cpset       Pointer to the cpset
 */
void cpset_iterator_init(cpset_iterator_t *iterator, const cpset_t *cpset);

/**
 * Advances the iterator and returns the current element or NULL if all elements
 * in the cpset have been processed.
 * @attention It is not allowed to use cpset_insert or cpset_remove while
 *            iterating over a cpset.
 *
 * @param iterator  Pointer to the cpset iterator.
 * @returns         Next element in the cpset or NULL
 */
void *cpset_iterator_next(cpset_iterator_t *iterator);

/**
 * Removed the element the iterator currently points to
 *
 * @param cpset     Pointer to the cpset
 * @param iterator  Pointer to the cpset iterator.
 */
void cpset_remove_iterator(cpset_t *cpset, const cpset_iterator_t *iterator);

/** @} */

#endif