wsutil/wmem/wmem_multimap.h

   1 /** @file
   2  *
   3  * Definitions for the Wireshark Memory Manager Hash Multimap
   4  * Copyright 2021, John Thacker <johnthacker@gmail.com>
   5  * Copyright 2014, Evan Huus <eapache@gmail.com>
   6  *
   7  * Wireshark - Network traffic analyzer
   8  * By Gerald Combs <gerald@wireshark.org>
   9  * Copyright 1998 Gerald Combs
  10  *
  11  * SPDX-License-Identifier: GPL-2.0-or-later
  12  */
  13
  14 #ifndef __WMEM_MULTIMAP_H__
  15 #define __WMEM_MULTIMAP_H__
  16
  17 #include <glib.h>
  18
  19 #include "wmem_core.h"
  20 #include "wmem_list.h"
  21
  22 #ifdef __cplusplus
  23 extern "C" {
  24 #endif /* __cplusplus */
  25
  26 /** @addtogroup wmem
  27  *  @{
  28  *    @defgroup wmem-multimap Hash Multimap
  29  *
  30  *    A hash multimap implementation on top of wmem_map and wmem_tree, storing
  31  *    multiple values at each hash key in a tree indexed by a 32 bit integer.
  32  *
  33  *    The primary use case is a protocol with an ID used as the hash lookup
  34  *    key that can be reused in a capture, and the frame number used as the
  35  *    tree key. We often want to find the most recent frame that had a certain
  36  *    ID, e.g. for request/response matching, and wmem_multimap_lookup32_le()
  37  *    serves that purpose.
  38  *
  39  *    Since the tree implementation is a self-balancing red-black tree, lookup
  40  *    time is still O(log(n)) even though elements with equivalent hash keys
  41  *    are usually added in increasing order of frame number.
  42  *
  43  *    NOTE: The multimap does not yet support inserting items without
  44  *    specifying the tree key, because the total capacity of individual trees
  45  *    (including deleted nodes) is not tracked.
  46  *
  47  *    @{
  48  */
  49
  50 typedef struct _wmem_multimap_t wmem_multimap_t;
  51
  52 /** Creates a multimap with the given allocator scope. When the scope is emptied,
  53  * the map is fully destroyed. Items stored in it will not be freed unless they
  54  * were allocated from the same scope.
  55  *
  56  * @param allocator The allocator scope with which to create the map.
  57  * @param hash_func The hash function used to place inserted keys.
  58  * @param eql_func  The equality function used to compare inserted keys.
  59  * @return The newly-allocated map.
  60  */
  61 WS_DLL_PUBLIC
  62 wmem_multimap_t *
  63 wmem_multimap_new(wmem_allocator_t *allocator,
  64         GHashFunc hash_func, GEqualFunc eql_func)
  65 G_GNUC_MALLOC;
  66
  67 /** Creates a multimap with two allocator scopes. The base structure lives in the
  68  * metadata scope, and the map data lives in the data scope. Every time free_all
  69  * occurs in the data scope the map is transparently emptied without affecting
  70  * the location of the base / metadata structure.
  71  *
  72  * WARNING: None of the map (even the part in the metadata scope) can be used
  73  * after the data scope has been *destroyed*.
  74  *
  75  * The primary use for this function is to create maps that reset for each new
  76  * capture file that is loaded. This can be done by specifying wmem_epan_scope()
  77  * as the metadata scope and wmem_file_scope() as the data scope.
  78  */
  79 WS_DLL_PUBLIC
  80 wmem_multimap_t *
  81 wmem_multimap_new_autoreset(wmem_allocator_t *metadata_scope, wmem_allocator_t *data_scope,
  82         GHashFunc hash_func, GEqualFunc eql_func)
  83 G_GNUC_MALLOC;
  84
  85 /** Retrieves a list of the keys inside the multimap
  86  *
  87  * @param list_allocator The allocator scope for the returned list.
  88  * @param map The multimap to extract keys from
  89  * @return list of keys in the multimap
  90  */
  91 WS_DLL_PUBLIC
  92 wmem_list_t*
  93 wmem_multimap_get_keys(wmem_allocator_t *list_allocator, wmem_multimap_t *map);
  94
  95 /** Return the total number of elements in the multimap.
  96  *
  97  * @param map The multimap to use
  98  * @return the number of elements
  99 */
 100 WS_DLL_PUBLIC
 101 unsigned
 102 wmem_multimap_size(wmem_multimap_t *map);
 103
 104 /** Returns the number of values in the multimap with a certain hash key.
 105  * (Note: This is the number of current elements, so this can only be used to
 106  * safely generate unique tree keys prior to insertion if no values have been
 107  * removed, due to how the tree implementation works.)
 108  *
 109  * @param map The multimap to search in.
 110  * @param key The primary key to lookup in the map.
 111  * @return The number of values in the tree stored at map key, or zero if no
 112  * tree exists at that key.
 113  */
 114 WS_DLL_PUBLIC
 115 unsigned
 116 wmem_multimap_count(wmem_multimap_t *map, const void *key);
 117
 118 /** Insert a value in the multimap.
 119  *
 120  * @param map The multimap to insert into.
 121  * @param key The key to insert by in the map.
 122  * @param frame_num The key to insert by in the tree.
 123  * @param value The value to insert.
 124  * @return true if there was already a tree mapped at key, in which case the
 125  * caller may safely free key. (This is not necessary if key is allocated with
 126  * a wmem pool.)
 127  *
 128  * Note: as with wmem_tree, if there is already a node with the same pair
 129  * of keys, then the existing value will simply be overwritten. This is not
 130  * a problem if the value is wmem allocated, but if it is manually managed,
 131  * then you must ensure that the pair is unique or do a lookup before inserting.
 132  */
 133 WS_DLL_PUBLIC
 134 bool
 135 wmem_multimap_insert32(wmem_multimap_t *map, const void *key, uint32_t frame_num, void *value);
 136
 137 /** Lookup a value in the multimap combination with an exact match.
 138  *
 139  * @param map The multimap to search in.
 140  * @param key The primary key to lookup in the map.
 141  * @param frame_num The secondary key to lookup in the tree.
 142  * @return The value stored at the keys if any, or NULL.
 143  */
 144 WS_DLL_PUBLIC
 145 void *
 146 wmem_multimap_lookup32(wmem_multimap_t *map, const void *key, const uint32_t frame_num);
 147
 148 /** Lookup a value in the multimap with an exact match for the map key
 149  * and the largest value less than or equal to the tree key. This is
 150  * useful for request/response matching where IDs can be reused.
 151  *
 152  * @param map The multimap to search in.
 153  * @param key The primary key to lookup in the map.
 154  * @param frame_num The secondary key to lookup in the tree.
 155  * @return The value stored at the primary key in the map and with the largest
 156  * key in the tree that is less than or equal to the second key if any, or NULL.
 157  */
 158 WS_DLL_PUBLIC
 159 void *
 160 wmem_multimap_lookup32_le(wmem_multimap_t *map, const void *key, const uint32_t frame_num);
 161
 162 /** Remove a value from the multimap. If no value is stored at that key pair,
 163  * nothing happens. As with wmem_tree, this is not really a remove, but the
 164  * value is set to NULL so that wmem_multimap_lookup32 not will find it.
 165  *
 166  * @param map The multimap to remove from.
 167  * @param key The map key of the value to remove.
 168  * @param frame_num The tree key of the value to remove.
 169  * @return The (removed) value stored at the key if any, or NULL.
 170  */
 171 WS_DLL_PUBLIC
 172 void *
 173 wmem_multimap_remove32(wmem_multimap_t *map, const void *key, const uint32_t frame_num);
 174
 175 /**   @}
 176  *  @} */
 177
 178 #ifdef __cplusplus
 179 }
 180 #endif /* __cplusplus */
 181
 182 #endif /* __WMEM_MULTIMAP_H__ */
 183
 184 /*
 185  * Editor modelines  -  https://www.wireshark.org/tools/modelines.html
 186  *
 187  * Local variables:
 188  * c-basic-offset: 4
 189  * tab-width: 8
 190  * indent-tabs-mode: nil
 191  * End:
 192  *
 193  * vi: set shiftwidth=4 tabstop=8 expandtab:
 194  * :indentSize=4:tabSize=8:noTabs=true:
 195  */