1 /* wmem_map.h 2 * Definitions for the Wireshark Memory Manager Hash Map 3 * Copyright 2014, Evan Huus <eapache@gmail.com> 4 * 5 * Wireshark - Network traffic analyzer 6 * By Gerald Combs <gerald@wireshark.org> 7 * Copyright 1998 Gerald Combs 8 * 9 * SPDX-License-Identifier: GPL-2.0-or-later 10 */ 11 12 #ifndef __WMEM_MAP_H__ 13 #define __WMEM_MAP_H__ 14 15 #include <glib.h> 16 17 #include "wmem_core.h" 18 19 #ifdef __cplusplus 20 extern "C" { 21 #endif /* __cplusplus */ 22 23 /** @addtogroup wmem 24 * @{ 25 * @defgroup wmem-map Hash Map 26 * 27 * A hash map implementation on top of wmem. Provides insertion, deletion and 28 * lookup in expected amortized constant time. Uses universal hashing to map 29 * keys into buckets, and provides a generic strong hash function that makes 30 * it secure against algorithmic complexity attacks, and suitable for use 31 * even with untrusted data. 32 * 33 * @{ 34 */ 35 36 struct _wmem_map_t; 37 typedef struct _wmem_map_t wmem_map_t; 38 39 /** Creates a map with the given allocator scope. When the scope is emptied, 40 * the map is fully destroyed. Items stored in it will not be freed unless they 41 * were allocated from the same scope. For details on the GHashFunc and 42 * GEqualFunc parameters, see the glib documentation at: 43 * https://developer.gnome.org/glib/unstable/glib-Hash-Tables.html 44 * 45 * If the keys are coming from untrusted data, do *not* use glib's default hash 46 * functions for strings, int64s or doubles. Wmem provides stronger equivalents 47 * below. Feel free to use the g_direct_hash, g_int_hash, and any of the 48 * g_*_equal functions though, as they should be safe. 49 * 50 * @param allocator The allocator scope with which to create the map. 51 * @param hash_func The hash function used to place inserted keys. 52 * @param eql_func The equality function used to compare inserted keys. 53 * @return The newly-allocated map. 54 */ 55 WS_DLL_PUBLIC 56 wmem_map_t * 57 wmem_map_new(wmem_allocator_t *allocator, 58 GHashFunc hash_func, GEqualFunc eql_func) 59 G_GNUC_MALLOC; 60 61 /** Creates a map with two allocator scopes. The base structure lives in the 62 * metadata scope, and the map data lives in the data scope. Every time free_all 63 * occurs in the data scope the map is transparently emptied without affecting 64 * the location of the base / metadata structure. 65 * 66 * WARNING: None of the map (even the part in the metadata scope) can be used 67 * after the data scope has been *destroyed*. 68 * 69 * The primary use for this function is to create maps that reset for each new 70 * capture file that is loaded. This can be done by specifying wmem_epan_scope() 71 * as the metadata scope and wmem_file_scope() as the data scope. 72 */ 73 WS_DLL_PUBLIC 74 wmem_map_t * 75 wmem_map_new_autoreset(wmem_allocator_t *metadata_scope, wmem_allocator_t *data_scope, 76 GHashFunc hash_func, GEqualFunc eql_func) 77 G_GNUC_MALLOC; 78 79 /** Inserts a value into the map. 80 * 81 * @param map The map to insert into. 82 * @param key The key to insert by. 83 * @param value The value to insert. 84 * @return The previous value stored at this key if any, or NULL. 85 */ 86 WS_DLL_PUBLIC 87 void * 88 wmem_map_insert(wmem_map_t *map, const void *key, void *value); 89 90 /** Check if a value is in the map. 91 * 92 * @param map The map to search in. 93 * @param key The key to lookup. 94 * @return true if the key is in the map, otherwise false. 95 */ 96 WS_DLL_PUBLIC 97 gboolean 98 wmem_map_contains(wmem_map_t *map, const void *key); 99 100 /** Lookup a value in the map. 101 * 102 * @param map The map to search in. 103 * @param key The key to lookup. 104 * @return The value stored at the key if any, or NULL. 105 */ 106 WS_DLL_PUBLIC 107 void * 108 wmem_map_lookup(wmem_map_t *map, const void *key); 109 110 /** Lookup a value in the map, returning the key, value, and a boolean which 111 * is true if the key is found. 112 * 113 * @param map The map to search in. 114 * @param key The key to lookup. 115 * @param orig_key (optional) The key that was determined to be a match, if any. 116 * @param value (optional) The value stored at the key, if any. 117 * @return true if the key is in the map, otherwise false. 118 */ 119 WS_DLL_PUBLIC 120 gboolean 121 wmem_map_lookup_extended(wmem_map_t *map, const void *key, const void **orig_key, void **value); 122 123 /** Remove a value from the map. If no value is stored at that key, nothing 124 * happens. 125 * 126 * @param map The map to remove from. 127 * @param key The key of the value to remove. 128 * @return The (removed) value stored at the key if any, or NULL. 129 */ 130 WS_DLL_PUBLIC 131 void * 132 wmem_map_remove(wmem_map_t *map, const void *key); 133 134 /** Remove a key and value from the map but does not destroy (free) them. If no 135 * value is stored at that key, nothing happens. 136 * 137 * @param map The map to remove from. 138 * @param key The key of the value to remove. 139 * @return TRUE if key is found FALSE if not. 140 */ 141 WS_DLL_PUBLIC 142 gboolean 143 wmem_map_steal(wmem_map_t *map, const void *key); 144 145 /** Retrieves a list of keys inside the map 146 * 147 * @param list_allocator The allocator scope for the returned list. 148 * @param map The map to extract keys from 149 * @return list of keys in the map 150 */ 151 WS_DLL_PUBLIC 152 wmem_list_t* 153 wmem_map_get_keys(wmem_allocator_t *list_allocator, wmem_map_t *map); 154 155 /** Run a function against all key/value pairs in the map. The order 156 * of the calls is unpredictable, since it is based on the internal 157 * storage of data. 158 * 159 * @param map The map to use 160 * @param foreach_func the function to call for each key/value pair 161 * @param user_data user data to pass to the function 162 */ 163 WS_DLL_PUBLIC 164 void 165 wmem_map_foreach(wmem_map_t *map, GHFunc foreach_func, gpointer user_data); 166 167 /** Return the number of elements of the map. 168 * 169 * @param map The map to use 170 * @return the number of elements 171 */ 172 WS_DLL_PUBLIC 173 guint 174 wmem_map_size(wmem_map_t *map); 175 176 /** Compute a strong hash value for an arbitrary sequence of bytes. Use of this 177 * hash value should be secure against algorithmic complexity attacks, even for 178 * short keys. The computation uses a random seed which is generated on wmem 179 * initialization, so the same key will hash to different values on different 180 * runs of the application. 181 * 182 * @param buf The buffer of bytes (does not have to be aligned). 183 * @param len The length of buf to use for the hash computation. 184 * @return The hash value. 185 */ 186 WS_DLL_PUBLIC 187 guint32 188 wmem_strong_hash(const guint8 *buf, const size_t len); 189 190 /** An implementation of GHashFunc using wmem_strong_hash. Prefer this over 191 * g_str_hash when the data comes from an untrusted source. 192 */ 193 WS_DLL_PUBLIC 194 guint 195 wmem_str_hash(gconstpointer key); 196 197 /** An implementation of GHashFunc using wmem_strong_hash. Prefer this over 198 * g_int64_hash when the data comes from an untrusted source. 199 */ 200 WS_DLL_PUBLIC 201 guint 202 wmem_int64_hash(gconstpointer key); 203 204 /** An implementation of GHashFunc using wmem_strong_hash. Prefer this over 205 * g_double_hash when the data comes from an untrusted source. 206 */ 207 WS_DLL_PUBLIC 208 guint 209 wmem_double_hash(gconstpointer key); 210 211 /** @} 212 * @} */ 213 214 #ifdef __cplusplus 215 } 216 #endif /* __cplusplus */ 217 218 #endif /* __WMEM_MAP_H__ */ 219 220 /* 221 * Editor modelines - https://www.wireshark.org/tools/modelines.html 222 * 223 * Local variables: 224 * c-basic-offset: 4 225 * tab-width: 8 226 * indent-tabs-mode: nil 227 * End: 228 * 229 * vi: set shiftwidth=4 tabstop=8 expandtab: 230 * :indentSize=4:tabSize=8:noTabs=true: 231 */ 232