| Wireshark 4.7.0 The Wireshark network protocol analyzer

Loading...
Searching...
No Matches
Classes | Typedefs | Enumerations | Functions
wmem_tree-int.h File Reference
`#include "wmem_tree.h"`

Go to the source code of this file.

## Classes
struct | _wmem_tree_node_t
| Internal node structure for a wmem balanced tree. More...
struct | _wmem_tree_t
| Internal representation of a wmem balanced tree. More...

## Typedefs
typedef enum _wmem_node_color_t | wmem_node_color_t
| Enumeration of node colors used in red-black trees.
typedef struct _wmem_tree_node_t | wmem_tree_node_t
| Opaque type representing a node in a red-black tree.
typedef struct _wmem_itree_node_t | wmem_itree_node_t
| Opaque type representing a node in an interval tree.
typedef int(* | compare_func) (const void *a, const void *b)
| Function pointer type for comparing two values.
typedef struct _wmem_range_t | wmem_range_t
| Opaque type representing a 32-bit interval range.

## Enumerations
enum | _wmem_node_color_t { WMEM_NODE_COLOR_RED , WMEM_NODE_COLOR_BLACK }
| Enumeration of node colors used in red-black trees. More...

## Functions
wmem_tree_node_t * | wmem_tree_insert_node (wmem_tree_t *tree, const void *key, void *data, compare_func cmp)
| Insert a key-value pair into a wmem red-black tree and return the new node.
bool | wmem_itree_range_overlap (const wmem_range_t *r1, const wmem_range_t *r2)
| Check whether two 32-bit ranges overlap.

## Detailed Description

Definitions for the Wireshark Memory Manager Red-Black Tree Copyright 2013, Evan Huus eapac.nosp@m.he@g.nosp@m.mail..nosp@m.com

Wireshark - Network traffic analyzer By Gerald Combs geral.nosp@m.d@wi.nosp@m.resha.nosp@m.rk.o.nosp@m.rg Copyright 1998 Gerald Combs

SPDX-License-Identifier: GPL-2.0-or-later

## Typedef Documentation

## ◆ compare_func

compare_func

Function pointer type for comparing two values.

Used to define custom comparison logic for sorting, searching, or ordering operations. The function should return:

- A negative value if `a` is less than `b`
- Zero if `a` is equal to `b`
- A positive value if `a` is greater than `b`

Parameters

  a | Pointer to the first value.
  b | Pointer to the second value.

Returns
  Integer indicating the relative order of `a` and `b`.

## ◆ wmem_itree_node_t

wmem_itree_node_t

Opaque type representing a node in an interval tree.

`wmem_itree_node_t` extends `wmem_tree_node_t` to support range-based indexing, typically used in multimap structures for request/response matching by frame number.

## ◆ wmem_node_color_t

typedef enum _wmem_node_color_t wmem_node_color_t

Enumeration of node colors used in red-black trees.

Red-black trees use node coloring to maintain balance during insertions and deletions. This enum defines the two possible colors for tree nodes.

## ◆ wmem_range_t

wmem_range_t

Opaque type representing a 32-bit interval range.

`wmem_range_t` is used to represent a closed or half-open interval over 32-bit integers, typically for indexing within interval trees.

## ◆ wmem_tree_node_t

wmem_tree_node_t

Opaque type representing a node in a red-black tree.

`wmem_tree_node_t` is used internally by the wmem tree implementation to store key-value pairs and maintain tree structure and balance.

## Enumeration Type Documentation

## ◆ _wmem_node_color_t

enum _wmem_node_color_t

Enumeration of node colors used in red-black trees.

Red-black trees use node coloring to maintain balance during insertions and deletions. This enum defines the two possible colors for tree nodes.

Enumerator
WMEM_NODE_COLOR_RED | Node is colored red.
WMEM_NODE_COLOR_BLACK | Node is colored black.

## Function Documentation

## ◆ wmem_itree_range_overlap()

bool wmem_itree_range_overlap | ( | const wmem_range_t * | r1,
|  | const wmem_range_t * | r2
| ) |  |

Check whether two 32-bit ranges overlap.

Compares two `wmem_range_t` intervals and returns true if they intersect. This is commonly used in interval tree lookups to identify overlapping ranges.

Parameters

  r1 | Pointer to the first range.
  r2 | Pointer to the second range.

Returns
  true if the ranges overlap, false otherwise.

## ◆ wmem_tree_insert_node()

wmem_tree_node_t * wmem_tree_insert_node | ( | wmem_tree_t * | tree,
|  | const void * | key,
|  | void * | data,
|  | compare_func | cmp
| ) |  |

Insert a key-value pair into a wmem red-black tree and return the new node.

Inserts a new node into the specified `wmem_tree_t` using the provided `key` and `data`. If a custom comparison function `cmp` is provided, it overrides the default key comparison. The tree remains balanced after insertion, ensuring O(log n) performance.

Parameters

  tree | Pointer to the red-black tree to insert into.
  key | Pointer to the key used for ordering within the tree.
  data | Pointer to the value associated with the key.
  cmp | Optional comparison function for custom key ordering. If NULL, default ordering is used.

Returns
  Pointer to the newly inserted `wmem_tree_node_t`, or NULL on failure.