| Wireshark 4.7.0 The Wireshark network protocol analyzer

Loading...
Searching...
No Matches
Classes | Typedefs | Functions
Interval Tree
Wireshark Memory Manager

## Classes
struct | _wmem_range_t
| Represents a numeric range used in wmem's internal range tree. More...

## Typedefs
typedef struct _wmem_tree_t | wmem_itree_t
| Alias for a wmem interval tree.

## Functions
WS_DLL_PUBLIC wmem_itree_t * | wmem_itree_new (wmem_allocator_t *allocator)
| Create a new interval tree using the specified memory allocator.
WS_DLL_PUBLIC bool | wmem_itree_is_empty (wmem_itree_t *tree)
| Check whether an interval tree is empty.
WS_DLL_PUBLIC void | wmem_itree_insert (wmem_itree_t *tree, const uint64_t low, const uint64_t high, void *data)
| Insert an interval into the interval tree.
WS_DLL_PUBLIC wmem_list_t * | wmem_itree_find_intervals (wmem_itree_t *tree, wmem_allocator_t *allocator, uint64_t low, uint64_t high)
| Find all intervals overlapping a given range in an interval tree.
void | wmem_print_itree (wmem_itree_t *tree)
| Print all intervals stored in the interval tree.

## Detailed Description

http://www.geeksforgeeks.org/interval-tree/ The idea is to augment a self-balancing Binary Search Tree (BST) like Red Black Tree, AVL Tree, etc ... to maintain a set of intervals so that all operations can be done in O(Logn) time.

Following wikipedia's convention this is an augmented tree rather than an interval tree http://www.wikiwand.com/en/Interval_tree

## Typedef Documentation

## ◆ wmem_itree_t

wmem_itree_t

Alias for a wmem interval tree.

`wmem_itree_t` is an alias for `wmem_tree_t`, used when the tree stores interval-based keys (e.g., ranges or spans). It supports efficient lookup and insertion of overlapping intervals, commonly used in range-based indexing.

## Function Documentation

## ◆ wmem_itree_find_intervals()

WS_DLL_PUBLIC wmem_list_t * wmem_itree_find_intervals | ( | wmem_itree_t * | tree,
|  | wmem_allocator_t * | allocator,
|  | uint64_t | low,
|  | uint64_t | high
| ) |  |

Find all intervals overlapping a given range in an interval tree.

Searches the specified `wmem_itree_t` for all intervals that overlap with the range `[low, high]`, and stores the results in a newly allocated `wmem_list_t` using the provided `allocator`. The list is always created, even if no matching intervals are found.

Parameters

  tree | Pointer to the interval tree to search.
  allocator | Memory allocator used to allocate the result list.
  low | Lower bound of the search range (inclusive).
  high | Upper bound of the search range (inclusive).

Returns
  A pointer to a `wmem_list_t` containing all overlapping intervals.

## ◆ wmem_itree_insert()

WS_DLL_PUBLIC void wmem_itree_insert | ( | wmem_itree_t * | tree,
|  | const uint64_t | low,
|  | const uint64_t | high,
|  | void * | data
| ) |  |

Insert an interval into the interval tree.

Inserts a range defined by `[low, high]` into the given `wmem_itree_t` in O(log(n)) time. The interval is indexed by its `low` value, and associated with the provided `data` pointer. If an interval with the same `low` value already exists, it will be overwritten.

Parameters

  tree | Pointer to the interval tree.
  low | Lower bound of the interval (inclusive).
  high | Upper bound of the interval (inclusive).
  data | Pointer to user-defined data associated with the interval.

## ◆ wmem_itree_is_empty()

WS_DLL_PUBLIC bool wmem_itree_is_empty | ( | wmem_itree_t * | tree | ) |

Check whether an interval tree is empty.

Returns true if the tree is empty (has no nodes).

Parameters

  tree | Pointer to the interval tree to check.

Returns
  `true` if the tree has no nodes, `false` otherwise.

## ◆ wmem_itree_new()

WS_DLL_PUBLIC wmem_itree_t * wmem_itree_new | ( | wmem_allocator_t * | allocator | ) |

Create a new interval tree using the specified memory allocator.

Allocates and initializes a new `wmem_itree_t` structure for managing intervals. The tree is created using the provided `wmem_allocator_t`, which controls memory allocation and cleanup.

Parameters

  allocator | Pointer to the memory allocator to use for tree allocation.

Returns
  Pointer to the newly created interval tree.

## ◆ wmem_print_itree()

void wmem_print_itree | ( | wmem_itree_t * | tree | ) |

Print all intervals stored in the interval tree.

Traverses the given `wmem_itree_t` and prints each stored interval range. This is typically used for debugging or inspection purposes to visualize the contents of the tree.

Parameters

  tree | Pointer to the interval tree to print.