Wireshark 2.9.0-477-g68ec514b The Wireshark network protocol analyzer

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

Classes | Macros | Typedefs | Functions
Red/Black Tree
Wireshark Memory Manager

## Classes
struct | _wmem_tree_key_t

## Macros
#define | WMEM_TREE_STRING_NOCASE 0x00000001

## Typedefs
typedef struct _wmem_tree_t | wmem_tree_t
typedef struct _wmem_tree_key_t | wmem_tree_key_t
typedef gboolean(* | wmem_foreach_func) (const void *key, void *value, void *userdata)
typedef void(* | wmem_printer_func) (const void *data)

## Functions
WS_DLL_PUBLIC wmem_tree_t * | wmem_tree_new (wmem_allocator_t *allocator) G_GNUC_MALLOC
WS_DLL_PUBLIC wmem_tree_t * | wmem_tree_new_autoreset (wmem_allocator_t *master, wmem_allocator_t *slave) G_GNUC_MALLOC
WS_DLL_PUBLIC void | wmem_tree_destroy (wmem_tree_t *tree, gboolean free_keys, gboolean free_values)
WS_DLL_PUBLIC gboolean | wmem_tree_is_empty (wmem_tree_t *tree)
WS_DLL_PUBLIC guint | wmem_tree_count (wmem_tree_t *tree)
WS_DLL_PUBLIC void | wmem_tree_insert32 (wmem_tree_t *tree, guint32 key, void *data)
WS_DLL_PUBLIC void * | wmem_tree_lookup32 (wmem_tree_t *tree, guint32 key)
WS_DLL_PUBLIC void * | wmem_tree_lookup32_le (wmem_tree_t *tree, guint32 key)
WS_DLL_PUBLIC void * | wmem_tree_remove32 (wmem_tree_t *tree, guint32 key)
WS_DLL_PUBLIC void | wmem_tree_insert_string (wmem_tree_t *tree, const gchar *key, void *data, guint32 flags)
WS_DLL_PUBLIC void * | wmem_tree_lookup_string (wmem_tree_t *tree, const gchar *key, guint32 flags)
WS_DLL_PUBLIC void * | wmem_tree_remove_string (wmem_tree_t *tree, const gchar *key, guint32 flags)
WS_DLL_PUBLIC void | wmem_tree_insert32_array (wmem_tree_t *tree, wmem_tree_key_t *key, void *data)
WS_DLL_PUBLIC void * | wmem_tree_lookup32_array (wmem_tree_t *tree, wmem_tree_key_t *key)
WS_DLL_PUBLIC void * | wmem_tree_lookup32_array_le (wmem_tree_t *tree, wmem_tree_key_t *key)
WS_DLL_PUBLIC gboolean | wmem_tree_foreach (wmem_tree_t *tree, wmem_foreach_func callback, void *user_data)
void | wmem_print_tree (wmem_tree_t *tree, wmem_printer_func key_printer, wmem_printer_func data_printer)

## 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

#define WMEM_TREE_STRING_NOCASE 0x00000001

case insensitive strings as keys

## Typedef Documentation

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

Function type for processing one node of a tree during a traversal. Value is the value of the node, userdata is whatever was passed to the traversal function. If the function returns TRUE the traversal will end prematurely.

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

Function type to print key/data of nodes in wmem_print_tree_verbose

## Function Documentation

WS_DLL_PUBLIC guint wmem_tree_count | ( | wmem_tree_t * | tree | ) |

Returns number of nodes in tree

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

Cleanup memory used by tree. Intended for NULL scope allocated trees

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

Traverse the tree and call callback(value, userdata) for each value found. Returns TRUE if the traversal was ended prematurely by the callback.

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

Insert a node indexed by a guint32 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.

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 guint32 key values.

Takes as key an array of guint32 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 guint32 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 guint32 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;

WS_DLL_PUBLIC void wmem_tree_insert_string | ( | wmem_tree_t * | tree,
|  | const gchar * | key,
|  | void * | data,
|  | guint32 | 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 guint32. 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".

WS_DLL_PUBLIC gboolean wmem_tree_is_empty | ( | wmem_tree_t * | tree | ) |

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

WS_DLL_PUBLIC void* wmem_tree_lookup32 | ( | wmem_tree_t * | tree,
|  | guint32 | key
| ) |  |

Look up a node in the tree indexed by a guint32 integer value. If no node is found the function will return NULL.

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

Look up a node in the tree indexed by a sequence of guint32 integer values. See wmem_tree_insert32_array for details on the key.

WS_DLL_PUBLIC void* wmem_tree_lookup32_array_le | ( | 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 will return 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.

WS_DLL_PUBLIC void* wmem_tree_lookup32_le | ( | wmem_tree_t * | tree,
|  | guint32 | key
| ) |  |

Look up a node in the tree indexed by a guint32 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.

WS_DLL_PUBLIC void* wmem_tree_lookup_string | ( | wmem_tree_t * | tree,
|  | const gchar * | key,
|  | guint32 | flags
| ) |  |

Lookup the value under a string key, like wmem_tree_lookup32 but where the keye is a null-terminated string instead of a guint32. See wmem_tree_insert_string for an explanation of flags.

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 * | master,
|  | wmem_allocator_t * | slave
| ) |  |

Creates a tree with two allocator scopes. The base structure lives in the master scope, however the data lives in the slave scope. Every time free_all occurs in the slave scope the tree is transparently emptied without affecting the location of the master structure.

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

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

Remove a node in the tree indexed by a guint32 integer value. This is not really a remove, but the value is set to NULL so that wmem_tree_lookup32 not will find it.

WS_DLL_PUBLIC void* wmem_tree_remove_string | ( | wmem_tree_t * | tree,
|  | const gchar * | key,
|  | guint32 | flags
| ) |  |

Remove the value under a string key. This is not really a remove, but the value is set to NULL so that wmem_tree_lookup_string not will find it. See wmem_tree_insert_string for an explanation of flags.