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
|
/*
* Copyright (C) 2008-2012 Tobias Brunner
* Hochschule fuer Technik Rapperswil
*
* This program is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License as published by the
* Free Software Foundation; either version 2 of the License, or (at your
* option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
*
* This program is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
* or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* for more details.
*/
/**
* @defgroup hashtable hashtable
* @{ @ingroup collections
*/
#ifndef HASHTABLE_H_
#define HASHTABLE_H_
#include <collections/enumerator.h>
typedef struct hashtable_t hashtable_t;
/**
* Prototype for a function that computes the hash code from the given key.
*
* @param key key to hash
* @return hash code
*/
typedef u_int (*hashtable_hash_t)(const void *key);
/**
* Hashtable hash function calculation the hash solely based on the key pointer.
*
* @param key key to hash
* @return hash of key
*/
u_int hashtable_hash_ptr(const void *key);
/**
* Hashtable hash function calculation the hash for char* keys.
*
* @param key key to hash, a char*
* @return hash of key
*/
u_int hashtable_hash_str(const void *key);
/**
* Prototype for a function that compares the two keys for equality.
*
* @param key first key (the one we are looking for)
* @param other_key second key
* @return TRUE if the keys are equal
*/
typedef bool (*hashtable_equals_t)(const void *key, const void *other_key);
/**
* Hashtable equals function comparing pointers.
*
* @param key key to compare
* @param other_key other key to compare
* @return TRUE if key == other_key
*/
bool hashtable_equals_ptr(const void *key, const void *other_key);
/**
* Hashtable equals function comparing char* keys.
*
* @param key key to compare
* @param other_key other key to compare
* @return TRUE if streq(key, other_key)
*/
bool hashtable_equals_str(const void *key, const void *other_key);
/**
* Class implementing a hash table.
*
* General purpose hash table. This hash table is not synchronized.
*/
struct hashtable_t {
/**
* Create an enumerator over the hash table key/value pairs.
*
* @return enumerator over (void *key, void *value)
*/
enumerator_t *(*create_enumerator) (hashtable_t *this);
/**
* Adds the given value with the given key to the hash table, if there
* exists no entry with that key. NULL is returned in this case.
* Otherwise the existing value is replaced and the function returns the
* old value.
*
* @param key the key to store
* @param value the value to store
* @return NULL if no item was replaced, the old value otherwise
*/
void *(*put) (hashtable_t *this, const void *key, void *value);
/**
* Returns the value with the given key, if the hash table contains such an
* entry, otherwise NULL is returned.
*
* @param key the key of the requested value
* @return the value, NULL if not found
*/
void *(*get) (hashtable_t *this, const void *key);
/**
* Returns the value with a matching key, if the hash table contains such an
* entry, otherwise NULL is returned.
*
* Compared to get() the given match function is used to compare the keys
* for equality. The hash function does have to be deviced properly in
* order to make this work if the match function compares keys differently
* than the equals function provided to the constructor. This basically
* allows to enumerate all entries with the same hash value.
*
* @param key the key to match against
* @param match match function to be used when comparing keys
* @return the value, NULL if not found
*/
void *(*get_match) (hashtable_t *this, const void *key,
hashtable_equals_t match);
/**
* Removes the value with the given key from the hash table and returns the
* removed value (or NULL if no such value existed).
*
* @param key the key of the value to remove
* @return the removed value, NULL if not found
*/
void *(*remove) (hashtable_t *this, const void *key);
/**
* Removes the key and value pair from the hash table at which the given
* enumerator currently points.
*
* @param enumerator enumerator, from create_enumerator
*/
void (*remove_at) (hashtable_t *this, enumerator_t *enumerator);
/**
* Gets the number of items in the hash table.
*
* @return number of items
*/
u_int (*get_count) (hashtable_t *this);
/**
* Destroys a hash table object.
*/
void (*destroy) (hashtable_t *this);
/**
* Destroys a hash table object and calls the given function for each
* item and its key in the hash table.
*
* @param function function to call on each item and key
*/
void (*destroy_function)(hashtable_t *this,
void (*)(void *val, const void *key));
};
/**
* Creates an empty hash table object.
*
* @param hash hash function
* @param equals equals function
* @param capacity initial capacity
* @return hashtable_t object.
*/
hashtable_t *hashtable_create(hashtable_hash_t hash, hashtable_equals_t equals,
u_int capacity);
#endif /** HASHTABLE_H_ @}*/
|
