| Wireshark 4.7.0 The Wireshark network protocol analyzer

Loading...
Searching...
No Matches
Classes | Macros | Typedefs | Functions
Red/Black Tree
Wireshark Memory Manager

## Classes
struct | _wmem_tree_key_t
| Represents a key used in a wmem tree. More...

## Macros
#define | WMEM_TREE_STRING_NOCASE 0x00000001

## Typedefs
typedef struct _wmem_tree_t | wmem_tree_t
| Opaque type representing a red-black tree in the wmem system.
typedef struct _wmem_tree_key_t | wmem_tree_key_t
| Represents a key used in a wmem tree.
typedef bool(* | wmem_foreach_func) (const void *key, void *value, void *userdata)
| Function type for processing one node of a tree during a traversal.
typedef void(* | wmem_printer_func) (const void *data)
| Function type to print key/data of nodes in wmem_print_tree_verbose.

## Functions
WS_DLL_PUBLIC wmem_tree_t * | wmem_tree_new (wmem_allocator_t *allocator)
| Creates a tree with the given allocator scope. When the scope is emptied, the tree is fully destroyed.
WS_DLL_PUBLIC wmem_tree_t * | wmem_tree_new_autoreset (wmem_allocator_t *metadata_scope, wmem_allocator_t *data_scope)
| Creates a tree with two allocator scopes.
WS_DLL_PUBLIC void | wmem_tree_destroy (wmem_tree_t *tree, bool free_keys, bool free_values)
| Cleanup memory used by tree.
WS_DLL_PUBLIC bool | wmem_tree_is_empty (const wmem_tree_t *tree)
| Returns true if the tree is empty (has no nodes).
WS_DLL_PUBLIC unsigned | wmem_tree_count (const wmem_tree_t *tree)
| Returns number of nodes in tree.
WS_DLL_PUBLIC void | wmem_tree_insert32 (wmem_tree_t *tree, uint32_t key, void *data)
| Insert a node indexed by a uint32_t key value.
WS_DLL_PUBLIC bool | wmem_tree_contains32 (const wmem_tree_t *tree, uint32_t key)
| Look up a node in the tree indexed by a uint32_t integer value.
WS_DLL_PUBLIC void * | wmem_tree_lookup32 (const wmem_tree_t *tree, uint32_t key)
| Look up a node in the tree indexed by a uint32_t integer value.
WS_DLL_PUBLIC void * | wmem_tree_lookup32_le (const wmem_tree_t *tree, uint32_t key)
| Look up a node in the tree indexed by a uint32_t integer value.
WS_DLL_PUBLIC void * | wmem_tree_lookup32_le_full (const wmem_tree_t *tree, uint32_t key, uint32_t *orig_key)
| Look up a node in the tree indexed by a uint32_t integer value.
WS_DLL_PUBLIC void * | wmem_tree_lookup32_ge (const wmem_tree_t *tree, uint32_t key)
| Look up a node in the tree indexed by a uint32_t integer value.
WS_DLL_PUBLIC void * | wmem_tree_lookup32_ge_full (const wmem_tree_t *tree, uint32_t key, uint32_t *orig_key)
| Look up a node in the tree indexed by a uint32_t integer value.
WS_DLL_PUBLIC void * | wmem_tree_remove32 (wmem_tree_t *tree, uint32_t key)
| Remove a node in the tree indexed by a uint32_t integer value.
WS_DLL_PUBLIC void | wmem_tree_insert_string (wmem_tree_t *tree, const char *key, void *data, uint32_t flags)
| Insert a new value under a string key.
WS_DLL_PUBLIC void * | wmem_tree_lookup_string (const wmem_tree_t *tree, const char *key, uint32_t flags)
| Lookup the value under a string key.
WS_DLL_PUBLIC void * | wmem_tree_remove_string (wmem_tree_t *tree, const char *key, uint32_t flags)
| Remove the value under a string key.
WS_DLL_PUBLIC void | wmem_tree_insert32_array (wmem_tree_t *tree, wmem_tree_key_t *key, void *data)
| Insert a node indexed by a sequence of uint32_t key values.
WS_DLL_PUBLIC void * | wmem_tree_lookup32_array (const wmem_tree_t *tree, wmem_tree_key_t *key)
| Look up a node in the tree indexed by a sequence of uint32_t integer values.
WS_DLL_PUBLIC void * | wmem_tree_lookup32_array_le (const wmem_tree_t *tree, wmem_tree_key_t *key)
| Look up a node in the tree indexed by a multi-part tree value.
WS_DLL_PUBLIC bool | wmem_tree_foreach (const wmem_tree_t *tree, wmem_foreach_func callback, void *user_data)
| Inorder traversal (left/parent/right) of the tree.
WS_DLL_PUBLIC wmem_allocator_t * | wmem_tree_get_data_scope (const wmem_tree_t *tree)
| return the memory scope used by the data of the tree
WS_DLL_PUBLIC void | wmem_print_tree (const wmem_tree_t *tree, wmem_printer_func key_printer, wmem_printer_func data_printer)
| Print the contents of a tree using optional key and data printer callbacks.

## Detailed Description

Binary trees are a well-known and popular device in computer science to handle storage of objects based on a search key or identity. The particular binary tree style implemented here is the red/black tree, which has the nice property of being self-balancing. This guarantees O(log(n)) time for lookups, compared to linked lists that are O(n). This means red/black trees scale very well when many objects are being stored.

## Macro Definition Documentation

## ◆ WMEM_TREE_STRING_NOCASE

#define WMEM_TREE_STRING_NOCASE 0x00000001

case insensitive strings as keys

## Typedef Documentation

## ◆ wmem_foreach_func

typedef bool(* wmem_foreach_func) (const void *key, void *value, void *userdata)

Function type for processing one node of a tree during a traversal.

This function is called for each node during a tree traversal. If the function returns true, the traversal will end prematurely.

Parameters

  key | Pointer to the key of the current node.
  value | Pointer to the value of the current node.
  userdata | Pointer to user-defined data passed to the traversal function.

Returns
  True to stop traversal early, false to continue.

## ◆ wmem_printer_func

typedef void(* wmem_printer_func) (const void *data)

Function type to print key/data of nodes in wmem_print_tree_verbose.

Parameters

  data | Pointer to the data to be printed.

## ◆ wmem_tree_key_t

typedef struct _wmem_tree_key_t wmem_tree_key_t

Represents a key used in a wmem tree.

This structure defines a variable-length key used for indexing and lookup in a `wmem_tree_t`. Keys are composed of one or more 32-bit words, allowing for hierarchical or compound key structures.

## ◆ wmem_tree_t

wmem_tree_t

Opaque type representing a red-black tree in the wmem system.

`wmem_tree_t` provides efficient key-based storage using a self-balancing red-black tree. It guarantees O(log n) lookup, insertion, and deletion times, making it suitable for high-performance, scoped memory operations.

Use API functions such as `wmem_tree_insert32()`, `wmem_tree_lookup32()`, and `wmem_tree_insert32_array()` to interact with this structure.

## Function Documentation

## ◆ wmem_print_tree()

WS_DLL_PUBLIC void wmem_print_tree | ( | const wmem_tree_t * | tree,
|  | wmem_printer_func | key_printer,
|  | wmem_printer_func | data_printer
| ) |  |

Print the contents of a tree using optional key and data printer callbacks.

Accepts callbacks to print the key and/or data of each node. Either or both printer functions may be NULL, in which case the corresponding output will be skipped.

Parameters

  tree | Pointer to the tree to print.
  key_printer | Callback function to print the key of each node (may be NULL).
  data_printer | Callback function to print the data of each node (may be NULL).

## ◆ wmem_tree_contains32()

WS_DLL_PUBLIC bool wmem_tree_contains32 | ( | const wmem_tree_t * | tree,
|  | uint32_t | key
| ) |  |

Look up a node in the tree indexed by a uint32_t integer value.

Parameters

  tree | Pointer to the tree to search.
  key | The uint32_t key to look up.

Returns
  True if a node with the given key exists, false otherwise.

## ◆ wmem_tree_count()

WS_DLL_PUBLIC unsigned wmem_tree_count | ( | const wmem_tree_t * | tree | ) |

Returns number of nodes in tree.

Parameters

  tree | Pointer to the tree whose nodes are to be counted.

Returns
  The total number of nodes in the tree.

## ◆ wmem_tree_destroy()

WS_DLL_PUBLIC void wmem_tree_destroy | ( | wmem_tree_t * | tree,
|  | bool | free_keys,
|  | bool | free_values
| ) |  |

Cleanup memory used by tree.

Intended for trees allocated with a NULL scope.

Parameters

  tree | Pointer to the tree to be destroyed.
  free_keys | If true, frees memory associated with keys.
  free_values | If true, frees memory associated with values.

## ◆ wmem_tree_foreach()

WS_DLL_PUBLIC bool wmem_tree_foreach | ( | const wmem_tree_t * | tree,
|  | wmem_foreach_func | callback,
|  | void * | user_data
| ) |  |

Inorder traversal (left/parent/right) of the tree.

Calls the provided callback function for each value found during traversal. Traversal stops early if the callback returns true.

Parameters

  tree | Pointer to the tree to traverse.
  callback | Function to call for each node's value.
  user_data | Pointer to user-defined data passed to the callback.

Returns
  True if traversal was ended prematurely by the callback, false otherwise.

## ◆ wmem_tree_get_data_scope()

WS_DLL_PUBLIC wmem_allocator_t * wmem_tree_get_data_scope | ( | const wmem_tree_t * | tree | ) |

return the memory scope used by the data of the tree

This is intended to help abstract memory use for tree items by having using the knowledge of the tree's data memory scope to allocate items that will go into the tree

Parameters

  tree | Pointer to the tree that has scope.

## ◆ wmem_tree_insert32()

WS_DLL_PUBLIC void wmem_tree_insert32 | ( | wmem_tree_t * | tree,
|  | uint32_t | key,
|  | void * | data
| ) |  |

Insert a node indexed by a uint32_t key value.

Data is a pointer to the structure you want to be able to retrieve by searching for the same key later.

NOTE: If you insert a node to a key that already exists in the tree this function will simply overwrite the old value. If the structures you are storing are allocated in a wmem pool this is not a problem as they will still be freed with the pool. If you are managing them manually however, you must either ensure the key is unique, or do a lookup before each insert.

Parameters

  tree | Pointer to the tree where the node will be inserted.
  key | The uint32_t key used to index the node.
  data | Pointer to the data to associate with the key.

## ◆ wmem_tree_insert32_array()

WS_DLL_PUBLIC void wmem_tree_insert32_array | ( | wmem_tree_t * | tree,
|  | wmem_tree_key_t * | key,
|  | void * | data
| ) |  |

Insert a node indexed by a sequence of uint32_t key values.

Takes as key an array of uint32_t vectors of type wmem_tree_key_t. It will iterate through each key to search further down the tree until it reaches an element where length==0, indicating the end of the array. You MUST terminate the key array by {0, NULL} or this will crash.

NOTE: length indicates the number of uint32_t values in the vector, not the number of bytes.

NOTE: all the "key" members of the "key" argument MUST be aligned on 32-bit boundaries; otherwise, this code will crash on platforms such as SPARC that require aligned pointers.

If you use ...32_array() calls you MUST make sure that every single node you add to a specific tree always has a key of exactly the same number of keylen words or it will crash. Or at least that every single item that sits behind the same top level node always has exactly the same number of words.

One way to guarantee this is the way that NFS does this for the nfs_name_snoop_known tree which holds filehandles for both v2 and v3. v2 filehandles are always 32 bytes (8 words) while v3 filehandles can have any length (though 32 bytes are most common). The NFS dissector handles this by providing a uint32_t containing the length as the very first item in this vector :

                     wmem_tree_key_t fhkey[3];

                     fhlen=nns->fh_length;
                     fhkey[0].length=1;
                     fhkey[0].key=&fhlen;
                     fhkey[1].length=fhlen/4;
                     fhkey[1].key=nns->fh;
                     fhkey[2].length=0;

Parameters

  tree | Pointer to the tree where the node will be inserted.
  key | Array of wmem_tree_key_t structures representing the key sequence.
  data | Pointer to the data to associate with the key.

## ◆ wmem_tree_insert_string()

WS_DLL_PUBLIC void wmem_tree_insert_string | ( | wmem_tree_t * | tree,
|  | const char * | key,
|  | void * | data,
|  | uint32_t | flags
| ) |  |

Insert a new value under a string key.

Like wmem_tree_insert32 but where the key is a null-terminated string instead of a uint32_t. You may pass WMEM_TREE_STRING_NOCASE to the flags argument in order to make it store the key in a case-insensitive way. (Note that "case-insensitive" refers only to the ASCII letters A-Z and a-z; it is locale-independent. Do not expect it to honor the rules of your language; for example, "I" will always be mapped to "i".)

Parameters

  tree | Pointer to the tree where the node will be inserted.
  key | Null-terminated string key used to index the node.
  data | Pointer to the data to associate with the key.
  flags | Flags to control insertion behavior (e.g., case-insensitive key handling).

## ◆ wmem_tree_is_empty()

WS_DLL_PUBLIC bool wmem_tree_is_empty | ( | const wmem_tree_t * | tree | ) |

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

Parameters

  tree | Pointer to the tree to check.

Returns
  True if the tree has no nodes, false otherwise.

## ◆ wmem_tree_lookup32()

WS_DLL_PUBLIC void * wmem_tree_lookup32 | ( | const wmem_tree_t * | tree,
|  | uint32_t | key
| ) |  |

Look up a node in the tree indexed by a uint32_t integer value.

If no node is found, the function will return NULL.

Parameters

  tree | Pointer to the tree to search.
  key | The uint32_t key to look up.

Returns
  Pointer to the data associated with the key, or NULL if not found.

## ◆ wmem_tree_lookup32_array()

WS_DLL_PUBLIC void * wmem_tree_lookup32_array | ( | const wmem_tree_t * | tree,
|  | wmem_tree_key_t * | key
| ) |  |

Look up a node in the tree indexed by a sequence of uint32_t integer values.

See wmem_tree_insert32_array for details on the key format and usage.

Parameters

  tree | Pointer to the tree to search.
  key | Array of wmem_tree_key_t structures representing the key sequence.

Returns
  Pointer to the data associated with the key, or NULL if not found.

## ◆ wmem_tree_lookup32_array_le()

WS_DLL_PUBLIC void * wmem_tree_lookup32_array_le | ( | const wmem_tree_t * | tree,
|  | wmem_tree_key_t * | key
| ) |  |

Look up a node in the tree indexed by a multi-part tree value.

The function returns the node that has the largest key that is equal to or smaller than the search key, or NULL if no such key was found.

NOTE: The key returned will be "less" in key order. The usefulness of the returned node must be verified prior to use.

See wmem_tree_insert32_array for details on the key.

Parameters

  tree | Pointer to the tree to search.
  key | Array of wmem_tree_key_t structures representing the key sequence.

Returns
  Pointer to the data associated with the closest matching key, or NULL if none found.

## ◆ wmem_tree_lookup32_ge()

WS_DLL_PUBLIC void * wmem_tree_lookup32_ge | ( | const wmem_tree_t * | tree,
|  | uint32_t | key
| ) |  |

Look up a node in the tree indexed by a uint32_t integer value.

Returns the node that has the smallest key that is greater than or equal to the search key, or NULL if no such key exists.

Parameters

  tree | Pointer to the tree to search.
  key | The uint32_t key used as the lower bound for the lookup.

Returns
  Pointer to the data associated with the closest matching key, or NULL if none found.

## ◆ wmem_tree_lookup32_ge_full()

WS_DLL_PUBLIC void * wmem_tree_lookup32_ge_full | ( | const wmem_tree_t * | tree,
|  | uint32_t | key,
|  | uint32_t * | orig_key
| ) |  |

Look up a node in the tree indexed by a uint32_t integer value.

Returns the node that has the smallest key that is greater than or equal to the search key, or NULL if no such key exists. Also returns the least upper bound key if it exists.

Parameters

  tree | Pointer to the tree to search.
  key | The uint32_t key used as the upper bound for the lookup.
  orig_key | Pointer to store the greatest lower bound key, if found.

Returns
  Pointer to the data associated with the closest matching key, or NULL if none found.

## ◆ wmem_tree_lookup32_le()

WS_DLL_PUBLIC void * wmem_tree_lookup32_le | ( | const wmem_tree_t * | tree,
|  | uint32_t | key
| ) |  |

Look up a node in the tree indexed by a uint32_t integer value.

Returns the node that has the largest key that is less than or equal to the search key, or NULL if no such key exists.

Parameters

  tree | Pointer to the tree to search.
  key | The uint32_t key used as the upper bound for the lookup.

Returns
  Pointer to the data associated with the closest matching key, or NULL if none found.

## ◆ wmem_tree_lookup32_le_full()

WS_DLL_PUBLIC void * wmem_tree_lookup32_le_full | ( | const wmem_tree_t * | tree,
|  | uint32_t | key,
|  | uint32_t * | orig_key
| ) |  |

Look up a node in the tree indexed by a uint32_t integer value.

Returns the node that has the largest key that is less than or equal to the search key, or NULL if no such key exists. Also returns the greatest lower bound key if it exists.

Parameters

  tree | Pointer to the tree to search.
  key | The uint32_t key used as the upper bound for the lookup.
  orig_key | Pointer to store the greatest lower bound key, if found.

Returns
  Pointer to the data associated with the closest matching key, or NULL if none found.

## ◆ wmem_tree_lookup_string()

WS_DLL_PUBLIC void * wmem_tree_lookup_string | ( | const wmem_tree_t * | tree,
|  | const char * | key,
|  | uint32_t | flags
| ) |  |

Lookup the value under a string key.

Similar to wmem_tree_lookup32 but uses a null-terminated string as the key. See wmem_tree_insert_string for an explanation of flags.

Parameters

  tree | Pointer to the tree to search.
  key | Null-terminated string key to look up.
  flags | Flags to control lookup behavior (e.g., case-insensitive matching).

Returns
  Pointer to the data associated with the key, or NULL if not found.

## ◆ wmem_tree_new()

WS_DLL_PUBLIC wmem_tree_t * wmem_tree_new | ( | wmem_allocator_t * | allocator | ) |

Creates a tree with the given allocator scope. When the scope is emptied, the tree is fully destroyed.

Parameters

  allocator | Allocator used for the tree.

Returns
  A pointer to the newly created tree.

## ◆ wmem_tree_new_autoreset()

WS_DLL_PUBLIC wmem_tree_t * wmem_tree_new_autoreset | ( | wmem_allocator_t * | metadata_scope,
|  | wmem_allocator_t * | data_scope
| ) |  |

Creates a tree with two allocator scopes.

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

WARNING: None of the tree (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 trees 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 | Allocator for the base structure and metadata.
  data_scope | Allocator for the tree data that resets on free_all.

Returns
  A pointer to the newly created tree.

## ◆ wmem_tree_remove32()

WS_DLL_PUBLIC void * wmem_tree_remove32 | ( | wmem_tree_t * | tree,
|  | uint32_t | key
| ) |  |

Remove a node in the tree indexed by a uint32_t integer value.

This is a real removal operation. The function returns the value stored at the given key. If the tree memory is managed manually (i.e., with a NULL allocator), it is the caller's responsibility to free the returned value.

Parameters

  tree | Pointer to the tree from which the node will be removed.
  key | The uint32_t key identifying the node to remove.

Returns
  Pointer to the data that was stored at the key, or NULL if no such key exists.

## ◆ wmem_tree_remove_string()

WS_DLL_PUBLIC void * wmem_tree_remove_string | ( | wmem_tree_t * | tree,
|  | const char * | key,
|  | uint32_t | flags
| ) |  |

Remove the value under a string key.

This is not a true removal; instead, the value is set to NULL so that wmem_tree_lookup_string will no longer find it. See wmem_tree_insert_string for an explanation of flags.

Parameters

  tree | Pointer to the tree from which the value will be removed.
  key | Null-terminated string key identifying the value to remove.
  flags | Flags to control removal behavior (e.g., case-insensitive matching).

Returns
  Pointer to the data that was previously associated with the key, or NULL if not found.