wsutil/wmem/wmem_map.h

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