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.