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
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
|
/* wmem_map.h
* Definitions for the Wireshark Memory Manager Hash Map
* Copyright 2014, Evan Huus <eapache@gmail.com>
*
* Wireshark - Network traffic analyzer
* By Gerald Combs <gerald@wireshark.org>
* Copyright 1998 Gerald Combs
*
* 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.
*
* 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.
*
* You should have received a copy of the GNU General Public License along
* with this program; if not, write to the Free Software Foundation, Inc.,
* 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*/
#ifndef __WMEM_MAP_H__
#define __WMEM_MAP_H__
#include <glib.h>
#include "wmem_core.h"
#ifdef __cplusplus
extern "C" {
#endif /* __cplusplus */
/** @addtogroup wmem
* @{
* @defgroup wmem-map Hash Map
*
* A hash map implementation on top of wmem. Provides insertion, deletion and
* lookup in expected amortized constant time. Uses universal hashing to map
* keys into buckets, and provides a generic strong hash function that makes
* it secure against algorithmic complexity attacks, and suitable for use
* even with untrusted data.
*
* @{
*/
struct _wmem_map_t;
typedef struct _wmem_map_t wmem_map_t;
/** Creates a map with the given allocator scope. When the scope is emptied,
* the map is fully destroyed. Items stored in it will not be freed unless they
* were allocated from the same scope. For details on the GHashFunc and
* GEqualFunc parameters, see the glib documentation at:
* https://developer.gnome.org/glib/unstable/glib-Hash-Tables.html
*
* If the keys are coming from untrusted data, do *not* use glib's default hash
* functions for strings, int64s or doubles. Wmem provides stronger equivalents
* below. Feel free to use the g_direct_hash, g_int_hash, and any of the
* g_*_equal functions though, as they should be safe.
*
* @param allocator The allocator scope with which to create the map.
* @param hash_func The hash function used to place inserted keys.
* @param eql_func The equality function used to compare inserted keys.
* @return The newly-allocated map.
*/
WS_DLL_PUBLIC
wmem_map_t *
wmem_map_new(wmem_allocator_t *allocator,
GHashFunc hash_func, GEqualFunc eql_func)
G_GNUC_MALLOC;
/** Creates a map with two allocator scopes. The base structure lives in the
* master scope, however the data lives in the slave scope. Every time free_all
* occurs in the slave scope the map is transparently emptied without affecting
* the location of the master structure.
*
* WARNING: None of the map (even the part in the master scope) can be used
* after the slave scope has been *destroyed*.
*
* The primary use for this function is to create maps that reset for each new
* capture file that is loaded. This can be done by specifying wmem_epan_scope()
* as the master and wmem_file_scope() as the slave.
*/
WS_DLL_PUBLIC
wmem_map_t *
wmem_map_new_autoreset(wmem_allocator_t *master, wmem_allocator_t *slave,
GHashFunc hash_func, GEqualFunc eql_func)
G_GNUC_MALLOC;
/** Inserts a value into the map.
*
* @param map The map to insert into.
* @param key The key to insert by.
* @param value The value to insert.
* @return The previous value stored at this key if any, or NULL.
*/
WS_DLL_PUBLIC
void *
wmem_map_insert(wmem_map_t *map, const void *key, void *value);
/** Check if a value is in the map.
*
* @param map The map to search in.
* @param key The key to lookup.
* @return true if the key is in the map, otherwise false.
*/
WS_DLL_PUBLIC
gboolean
wmem_map_contains(wmem_map_t *map, const void *key);
/** Lookup a value in the map.
*
* @param map The map to search in.
* @param key The key to lookup.
* @return The value stored at the key if any, or NULL.
*/
WS_DLL_PUBLIC
void *
wmem_map_lookup(wmem_map_t *map, const void *key);
/** Lookup a value in the map, returning the key, value, and a boolean which
* is true if the key is found.
*
* @param map The map to search in.
* @param key The key to lookup.
* @param orig_key (optional) The key that was determined to be a match, if any.
* @param value (optional) The value stored at the key, if any.
* @return true if the key is in the map, otherwise false.
*/
WS_DLL_PUBLIC
gboolean
wmem_map_lookup_extended(wmem_map_t *map, const void *key, const void **orig_key, void **value);
/** Remove a value from the map. If no value is stored at that key, nothing
* happens.
*
* @param map The map to remove from.
* @param key The key of the value to remove.
* @return The (removed) value stored at the key if any, or NULL.
*/
WS_DLL_PUBLIC
void *
wmem_map_remove(wmem_map_t *map, const void *key);
/** Remove a key and value from the map but does not destroy (free) them. If no
* value is stored at that key, nothing happens.
*
* @param map The map to remove from.
* @param key The key of the value to remove.
* @return TRUE if key is found FALSE if not.
*/
WS_DLL_PUBLIC
gboolean
wmem_map_steal(wmem_map_t *map, const void *key);
/** Retrieves a list of keys inside the map
*
* @param list_allocator The allocator scope for the returned list.
* @param map The map to extract keys from
* @return list of keys in the map
*/
WS_DLL_PUBLIC
wmem_list_t*
wmem_map_get_keys(wmem_allocator_t *list_allocator, wmem_map_t *map);
/** Run a function against all key/value pairs in the map. The order
* of the calls is unpredictable, since it is based on the internal
* storage of data.
*
* @param map The map to use
* @param foreach_func the function to call for each key/value pair
* @param user_data user data to pass to the function
*/
WS_DLL_PUBLIC
void
wmem_map_foreach(wmem_map_t *map, GHFunc foreach_func, gpointer user_data);
/** Return the number of elements of the map.
*
* @param map The map to use
* @return the number of elements
*/
WS_DLL_PUBLIC
guint
wmem_map_size(wmem_map_t *map);
/** Compute a strong hash value for an arbitrary sequence of bytes. Use of this
* hash value should be secure against algorithmic complexity attacks, even for
* short keys. The computation uses a random seed which is generated on wmem
* initialization, so the same key will hash to different values on different
* runs of the application.
*
* @param buf The buffer of bytes (does not have to be aligned).
* @param len The length of buf to use for the hash computation.
* @return The hash value.
*/
WS_DLL_PUBLIC
guint32
wmem_strong_hash(const guint8 *buf, const size_t len);
/** An implementation of GHashFunc using wmem_strong_hash. Prefer this over
* g_str_hash when the data comes from an untrusted source.
*/
WS_DLL_PUBLIC
guint
wmem_str_hash(gconstpointer key);
/** An implementation of GHashFunc using wmem_strong_hash. Prefer this over
* g_int64_hash when the data comes from an untrusted source.
*/
WS_DLL_PUBLIC
guint
wmem_int64_hash(gconstpointer key);
/** An implementation of GHashFunc using wmem_strong_hash. Prefer this over
* g_double_hash when the data comes from an untrusted source.
*/
WS_DLL_PUBLIC
guint
wmem_double_hash(gconstpointer key);
/** @}
* @} */
#ifdef __cplusplus
}
#endif /* __cplusplus */
#endif /* __WMEM_MAP_H__ */
/*
* Editor modelines - http://www.wireshark.org/tools/modelines.html
*
* Local variables:
* c-basic-offset: 4
* tab-width: 8
* indent-tabs-mode: nil
* End:
*
* vi: set shiftwidth=4 tabstop=8 expandtab:
* :indentSize=4:tabSize=8:noTabs=true:
*/
|
