| Wireshark 4.7.0 The Wireshark network protocol analyzer

Loading...
Searching...
No Matches
Typedefs | Functions
Hash Multimap
Wireshark Memory Manager

## Typedefs
typedef struct _wmem_multimap_t | wmem_multimap_t
| Opaque type representing a hash multimap in the wmem system.

## Functions
WS_DLL_PUBLIC wmem_multimap_t * | wmem_multimap_new (wmem_allocator_t *allocator, GHashFunc hash_func, GEqualFunc eql_func) G_GNUC_MALLOC
| Creates a multimap with the given allocator scope.
WS_DLL_PUBLIC wmem_multimap_t * | wmem_multimap_new_autoreset (wmem_allocator_t *metadata_scope, wmem_allocator_t *data_scope, GHashFunc hash_func, GEqualFunc eql_func) G_GNUC_MALLOC
| Creates a multimap with two allocator scopes.
WS_DLL_PUBLIC wmem_list_t * | wmem_multimap_get_keys (wmem_allocator_t *list_allocator, const wmem_multimap_t *map)
| Retrieves a list of the keys inside the multimap.
WS_DLL_PUBLIC unsigned | wmem_multimap_size (const wmem_multimap_t *map)
| Return the total number of elements in the multimap.
WS_DLL_PUBLIC unsigned | wmem_multimap_count (const wmem_multimap_t *map, const void *key)
| Returns the number of values in the multimap with a certain hash key.
WS_DLL_PUBLIC bool | wmem_multimap_insert32 (wmem_multimap_t *map, const void *key, uint32_t frame_num, void *value)
| Insert a value in the multimap.
WS_DLL_PUBLIC void * | wmem_multimap_lookup32 (const wmem_multimap_t *map, const void *key, const uint32_t frame_num)
| Lookup a value in the multimap combination with an exact match.
WS_DLL_PUBLIC void * | wmem_multimap_lookup32_le (const wmem_multimap_t *map, const void *key, const uint32_t frame_num)
| Lookup a value in the multimap with an exact match for the map key and the largest value less than or equal to the tree key.
WS_DLL_PUBLIC void * | wmem_multimap_remove32 (wmem_multimap_t *map, const void *key, const uint32_t frame_num)
| Remove a value from the multimap.

## Detailed Description

A hash multimap implementation on top of wmem_map and wmem_tree, storing multiple values at each hash key in a tree indexed by a 32 bit integer.

The primary use case is a protocol with an ID used as the hash lookup key that can be reused in a capture, and the frame number used as the tree key. We often want to find the most recent frame that had a certain ID, e.g. for request/response matching, and wmem_multimap_lookup32_le() serves that purpose.

Since the tree implementation is a self-balancing red-black tree, lookup time is still O(log(n)) even though elements with equivalent hash keys are usually added in increasing order of frame number.

NOTE: The multimap does not yet support inserting items without specifying the tree key, because the total capacity of individual trees (including deleted nodes) is not tracked.

## Typedef Documentation

## ◆ wmem_multimap_t

wmem_multimap_t

Opaque type representing a hash multimap in the wmem system.

`wmem_multimap_t` stores multiple values per hash key using a red-black tree indexed by 32-bit integers. It is optimized for use cases like request/response matching, where the same protocol ID may appear multiple times in a capture, and frame numbers are used to distinguish and order entries.

Use functions such as `wmem_multimap_insert32()` and `wmem_multimap_lookup32_le()` to interact with this structure.

## Function Documentation

## ◆ wmem_multimap_count()

WS_DLL_PUBLIC unsigned wmem_multimap_count | ( | const wmem_multimap_t * | map,
|  | const void * | key
| ) |  |

Returns the number of values in the multimap with a certain hash key.

Note: This is the number of current elements, so this can only be used to safely generate unique tree keys prior to insertion if no values have been removed, due to how the tree implementation works.

Parameters

  map | The multimap to search in.
  key | The primary key to lookup in the map.

Returns
  The number of values in the tree stored at map key, or zero if no tree exists at that key.

## ◆ wmem_multimap_get_keys()

WS_DLL_PUBLIC wmem_list_t * wmem_multimap_get_keys | ( | wmem_allocator_t * | list_allocator,
|  | const wmem_multimap_t * | map
| ) |  |

Retrieves a list of the keys inside the multimap.

Parameters

  list_allocator | The allocator scope for the returned list.
  map | The multimap to extract keys from

Returns
  list of keys in the multimap

## ◆ wmem_multimap_insert32()

WS_DLL_PUBLIC bool wmem_multimap_insert32 | ( | wmem_multimap_t * | map,
|  | const void * | key,
|  | uint32_t | frame_num,
|  | void * | value
| ) |  |

Insert a value in the multimap.

Note: as with wmem_tree, if there is already a node with the same pair of keys, then the existing value will simply be overwritten. This is not a problem if the value is wmem allocated, but if it is manually managed, then you must ensure that the pair is unique or do a lookup before inserting.

Parameters

  map | The multimap to insert into.
  key | The key to insert by in the map.
  frame_num | The key to insert by in the tree.
  value | The value to insert.

Returns
  true if there was already a tree mapped at key, in which case the caller may safely free key. (This is not necessary if key is allocated with a wmem pool.)

## ◆ wmem_multimap_lookup32()

WS_DLL_PUBLIC void * wmem_multimap_lookup32 | ( | const wmem_multimap_t * | map,
|  | const void * | key,
|  | const uint32_t | frame_num
| ) |  |

Lookup a value in the multimap combination with an exact match.

Parameters

  map | The multimap to search in.
  key | The primary key to lookup in the map.
  frame_num | The secondary key to lookup in the tree.

Returns
  The value stored at the keys if any, or NULL.

## ◆ wmem_multimap_lookup32_le()

WS_DLL_PUBLIC void * wmem_multimap_lookup32_le | ( | const wmem_multimap_t * | map,
|  | const void * | key,
|  | const uint32_t | frame_num
| ) |  |

Lookup a value in the multimap with an exact match for the map key and the largest value less than or equal to the tree key.

This is useful for request/response matching where IDs can be reused.

Parameters

  map | The multimap to search in.
  key | The primary key to lookup in the map.
  frame_num | The secondary key to lookup in the tree.

Returns
  The value stored at the primary key in the map and with the largest key in the tree that is less than or equal to the second key if any, or NULL.

## ◆ wmem_multimap_new()

WS_DLL_PUBLIC wmem_multimap_t * wmem_multimap_new | ( | wmem_allocator_t * | allocator,
|  | GHashFunc | hash_func,
|  | GEqualFunc | eql_func
| ) |  |

Creates a multimap 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.

Parameters

  allocator | The allocator scope with which to create the map.
  hash_func | The hash function used to place inserted keys.
  eql_func | The equality function used to compare inserted keys.

Returns
  The newly-allocated map.

## ◆ wmem_multimap_new_autoreset()

WS_DLL_PUBLIC wmem_multimap_t * wmem_multimap_new_autoreset | ( | wmem_allocator_t * | metadata_scope,
|  | wmem_allocator_t * | data_scope,
|  | GHashFunc | hash_func,
|  | GEqualFunc | eql_func
| ) |  |

Creates a multimap with two allocator scopes.

The base structure lives in the metadata scope, and the map data lives in the data scope. Every time free_all occurs in the data scope the map is transparently emptied without affecting the location of the base / metadata structure.

WARNING: None of the map (even the part in the metadata scope) can be used after the data 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 metadata scope and wmem_file_scope() as the data scope.

Parameters

  metadata_scope | Pointer to the allocator used for the base structure.
  data_scope | Pointer to the allocator used for the map's key-value data.
  hash_func | The hash function used to place inserted keys.
  eql_func | The equality function used to compare inserted keys.

Returns
  The newly-allocated map.

## ◆ wmem_multimap_remove32()

WS_DLL_PUBLIC void * wmem_multimap_remove32 | ( | wmem_multimap_t * | map,
|  | const void * | key,
|  | const uint32_t | frame_num
| ) |  |

Remove a value from the multimap.

If no value is stored at that key pair, nothing happens. As with wmem_tree, this is not really a remove, but the value is set to NULL so that wmem_multimap_lookup32 not will find it.

Parameters

  map | The multimap to remove from.
  key | The map key of the value to remove.
  frame_num | The tree key of the value to remove.

Returns
  The (removed) value stored at the key if any, or NULL.

## ◆ wmem_multimap_size()

WS_DLL_PUBLIC unsigned wmem_multimap_size | ( | const wmem_multimap_t * | map | ) |

Return the total number of elements in the multimap.

Parameters

  map | The multimap to use

Returns
  the number of elements