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
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
|
/*
* Copyright (c) 2009 Petri Lehtinen <petri@digip.org>
*
* This library is free software; you can redistribute it and/or modify
* it under the terms of the MIT license. See LICENSE for details.
*/
#ifndef HASHTABLE_H
#define HASHTABLE_H
typedef unsigned int (*key_hash_fn)(const void *key);
typedef int (*key_cmp_fn)(const void *key1, const void *key2);
typedef void (*free_fn)(void *key);
struct hashtable_list {
struct hashtable_list *prev;
struct hashtable_list *next;
};
struct hashtable_pair {
void *key;
void *value;
unsigned int hash;
struct hashtable_list list;
};
struct hashtable_bucket {
struct hashtable_list *first;
struct hashtable_list *last;
};
typedef struct hashtable {
unsigned int size;
struct hashtable_bucket *buckets;
unsigned int num_buckets; /* index to primes[] */
struct hashtable_list list;
key_hash_fn hash_key;
key_cmp_fn cmp_keys; /* returns non-zero for equal keys */
free_fn free_key;
free_fn free_value;
} hashtable_t;
/**
* hashtable_create - Create a hashtable object
*
* @hash_key: The key hashing function
* @cmp_keys: The key compare function. Returns non-zero for equal and
* zero for unequal unequal keys
* @free_key: If non-NULL, called for a key that is no longer referenced.
* @free_value: If non-NULL, called for a value that is no longer referenced.
*
* Returns a new hashtable object that should be freed with
* hashtable_destroy when it's no longer used, or NULL on failure (out
* of memory).
*/
hashtable_t *hashtable_create(key_hash_fn hash_key, key_cmp_fn cmp_keys,
free_fn free_key, free_fn free_value);
/**
* hashtable_destroy - Destroy a hashtable object
*
* @hashtable: The hashtable
*
* Destroys a hashtable created with hashtable_create().
*/
void hashtable_destroy(hashtable_t *hashtable);
/**
* hashtable_init - Initialize a hashtable object
*
* @hashtable: The (statically allocated) hashtable object
* @hash_key: The key hashing function
* @cmp_keys: The key compare function. Returns non-zero for equal and
* zero for unequal unequal keys
* @free_key: If non-NULL, called for a key that is no longer referenced.
* @free_value: If non-NULL, called for a value that is no longer referenced.
*
* Initializes a statically allocated hashtable object. The object
* should be cleared with hashtable_close when it's no longer used.
*
* Returns 0 on success, -1 on error (out of memory).
*/
int hashtable_init(hashtable_t *hashtable,
key_hash_fn hash_key, key_cmp_fn cmp_keys,
free_fn free_key, free_fn free_value);
/**
* hashtable_close - Release all resources used by a hashtable object
*
* @hashtable: The hashtable
*
* Destroys a statically allocated hashtable object.
*/
void hashtable_close(hashtable_t *hashtable);
/**
* hashtable_set - Add/modify value in hashtable
*
* @hashtable: The hashtable object
* @key: The key
* @value: The value
*
* If a value with the given key already exists, its value is replaced
* with the new value.
*
* Key and value are "stealed" in the sense that hashtable frees them
* automatically when they are no longer used. The freeing is
* accomplished by calling free_key and free_value functions that were
* supplied to hashtable_new. In case one or both of the free
* functions is NULL, the corresponding item is not "stealed".
*
* Returns 0 on success, -1 on failure (out of memory).
*/
int hashtable_set(hashtable_t *hashtable, void *key, void *value);
/**
* hashtable_get - Get a value associated with a key
*
* @hashtable: The hashtable object
* @key: The key
*
* Returns value if it is found, or NULL otherwise.
*/
void *hashtable_get(hashtable_t *hashtable, const void *key);
/**
* hashtable_del - Remove a value from the hashtable
*
* @hashtable: The hashtable object
* @key: The key
*
* Returns 0 on success, or -1 if the key was not found.
*/
int hashtable_del(hashtable_t *hashtable, const void *key);
/**
* hashtable_clear - Clear hashtable
*
* @hashtable: The hashtable object
*
* Removes all items from the hashtable.
*/
void hashtable_clear(hashtable_t *hashtable);
/**
* hashtable_iter - Iterate over hashtable
*
* @hashtable: The hashtable object
*
* Returns an opaque iterator to the first element in the hashtable.
* The iterator should be passed to hashtable_iter_* functions.
* The hashtable items are not iterated over in any particular order.
*
* There's no need to free the iterator in any way. The iterator is
* valid as long as the item that is referenced by the iterator is not
* deleted. Other values may be added or deleted. In particular,
* hashtable_iter_next() may be called on an iterator, and after that
* the key/value pair pointed by the old iterator may be deleted.
*/
void *hashtable_iter(hashtable_t *hashtable);
/**
* hashtable_iter - Return an iterator at a specific key
*
* @hashtable: The hashtable object
* @key: The key that the iterator should point to
*
* Like hashtable_iter() but returns an iterator pointing to a
* specific key.
*/
void *hashtable_iter_at(hashtable_t *hashtable, const void *key);
/**
* hashtable_iter_next - Advance an iterator
*
* @hashtable: The hashtable object
* @iter: The iterator
*
* Returns a new iterator pointing to the next element in the
* hashtable or NULL if the whole hastable has been iterated over.
*/
void *hashtable_iter_next(hashtable_t *hashtable, void *iter);
/**
* hashtable_iter_key - Retrieve the key pointed by an iterator
*
* @iter: The iterator
*/
void *hashtable_iter_key(void *iter);
/**
* hashtable_iter_value - Retrieve the value pointed by an iterator
*
* @iter: The iterator
*/
void *hashtable_iter_value(void *iter);
/**
* hashtable_iter_set - Set the value pointed by an iterator
*
* @iter: The iterator
* @value: The value to set
*/
void hashtable_iter_set(hashtable_t *hashtable, void *iter, void *value);
#endif
|
