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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
|
/* Licensed under LGPLv2+ - see LICENSE file for details */
#ifndef CCAN_HTABLE_H
#define CCAN_HTABLE_H
#include <stdint.h>
#include <stdbool.h>
#include <stdlib.h>
/**
* struct htable - private definition of a htable.
*
* It's exposed here so you can put it in your structures and so we can
* supply inline functions.
*/
struct htable {
size_t (*rehash)(const void *elem, void *priv);
void *priv;
unsigned int bits;
size_t elems, deleted, max, max_with_deleted;
/* These are the bits which are the same in all pointers. */
uintptr_t common_mask, common_bits;
uintptr_t perfect_bit;
uintptr_t *table;
};
/**
* HTABLE_INITIALIZER - static initialization for a hash table.
* @name: name of this htable.
* @rehash: hash function to use for rehashing.
* @priv: private argument to @rehash function.
*
* This is useful for setting up static and global hash tables.
*
* Example:
* // For simplicity's sake, say hash value is contents of elem.
* static size_t rehash(const void *elem, void *unused)
* {
* return *(size_t *)elem;
* }
* static struct htable ht = HTABLE_INITIALIZER(ht, rehash, NULL);
*/
#define HTABLE_INITIALIZER(name, rehash, priv) \
{ rehash, priv, 0, 0, 0, 0, 0, -1, 0, 0, &name.perfect_bit }
/**
* htable_init - initialize an empty hash table.
* @ht: the hash table to initialize
* @rehash: hash function to use for rehashing.
* @priv: private argument to @rehash function.
*/
void htable_init(struct htable *ht,
size_t (*rehash)(const void *elem, void *priv), void *priv);
/**
* htable_clear - empty a hash table.
* @ht: the hash table to clear
*
* This doesn't do anything to any pointers left in it.
*/
void htable_clear(struct htable *ht);
/**
* htable_rehash - use a hashtree's rehash function
* @elem: the argument to rehash()
*
*/
size_t htable_rehash(const void *elem);
/**
* htable_add - add a pointer into a hash table.
* @ht: the htable
* @hash: the hash value of the object
* @p: the non-NULL pointer
*
* Also note that this can only fail due to allocation failure. Otherwise, it
* returns true.
*/
bool htable_add(struct htable *ht, size_t hash, const void *p);
/**
* htable_del - remove a pointer from a hash table
* @ht: the htable
* @hash: the hash value of the object
* @p: the pointer
*
* Returns true if the pointer was found (and deleted).
*/
bool htable_del(struct htable *ht, size_t hash, const void *p);
/**
* struct htable_iter - iterator or htable_first or htable_firstval etc.
*
* This refers to a location inside the hashtable.
*/
struct htable_iter {
size_t off;
};
/**
* htable_firstval - find a candidate for a given hash value
* @htable: the hashtable
* @i: the struct htable_iter to initialize
* @hash: the hash value
*
* You'll need to check the value is what you want; returns NULL if none.
* See Also:
* htable_delval()
*/
void *htable_firstval(const struct htable *htable,
struct htable_iter *i, size_t hash);
/**
* htable_nextval - find another candidate for a given hash value
* @htable: the hashtable
* @i: the struct htable_iter to initialize
* @hash: the hash value
*
* You'll need to check the value is what you want; returns NULL if no more.
*/
void *htable_nextval(const struct htable *htable,
struct htable_iter *i, size_t hash);
/**
* htable_get - find an entry in the hash table
* @ht: the hashtable
* @h: the hash value of the entry
* @cmp: the comparison function
* @ptr: the pointer to hand to the comparison function.
*
* Convenient inline wrapper for htable_firstval/htable_nextval loop.
*/
static inline void *htable_get(const struct htable *ht,
size_t h,
bool (*cmp)(const void *candidate, void *ptr),
const void *ptr)
{
struct htable_iter i;
void *c;
for (c = htable_firstval(ht,&i,h); c; c = htable_nextval(ht,&i,h)) {
if (cmp(c, (void *)ptr))
return c;
}
return NULL;
}
/**
* htable_first - find an entry in the hash table
* @ht: the hashtable
* @i: the struct htable_iter to initialize
*
* Get an entry in the hashtable; NULL if empty.
*/
void *htable_first(const struct htable *htable, struct htable_iter *i);
/**
* htable_next - find another entry in the hash table
* @ht: the hashtable
* @i: the struct htable_iter to use
*
* Get another entry in the hashtable; NULL if all done.
* This is usually used after htable_first or prior non-NULL htable_next.
*/
void *htable_next(const struct htable *htable, struct htable_iter *i);
/**
* htable_delval - remove an iterated pointer from a hash table
* @ht: the htable
* @i: the htable_iter
*
* Usually used to delete a hash entry after it has been found with
* htable_firstval etc.
*/
void htable_delval(struct htable *ht, struct htable_iter *i);
#endif /* CCAN_HTABLE_H */
|
