diff options
Diffstat (limited to 'wsutil/wmem/wmem_tree.h')
| -rw-r--r-- | wsutil/wmem/wmem_tree.h | 255 |
1 files changed, 255 insertions, 0 deletions
diff --git a/wsutil/wmem/wmem_tree.h b/wsutil/wmem/wmem_tree.h new file mode 100644 index 0000000000..51f3c9908b --- /dev/null +++ b/wsutil/wmem/wmem_tree.h @@ -0,0 +1,255 @@ +/* wmem_tree.h + * Definitions for the Wireshark Memory Manager Red-Black Tree + * Based on the red-black tree implementation in epan/emem.* + * Copyright 2013, Evan Huus <eapache@gmail.com> + * + * Wireshark - Network traffic analyzer + * By Gerald Combs <gerald@wireshark.org> + * Copyright 1998 Gerald Combs + * + * SPDX-License-Identifier: GPL-2.0-or-later + */ + +#ifndef __WMEM_TREE_H__ +#define __WMEM_TREE_H__ + +#include "wmem_core.h" + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +/** @addtogroup wmem + * @{ + * @defgroup wmem-tree Red/Black Tree + * + * 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. + * + * @{ + */ + +struct _wmem_tree_t; +typedef struct _wmem_tree_t wmem_tree_t; + +/** 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(wmem_allocator_t *allocator) +G_GNUC_MALLOC; + +/** 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. + */ +WS_DLL_PUBLIC +wmem_tree_t * +wmem_tree_new_autoreset(wmem_allocator_t *metadata_scope, wmem_allocator_t *data_scope) +G_GNUC_MALLOC; + +/** Cleanup memory used by tree. Intended for NULL scope allocated trees */ +WS_DLL_PUBLIC +void +wmem_tree_destroy(wmem_tree_t *tree, gboolean free_keys, gboolean free_values); + +/** Returns true if the tree is empty (has no nodes). */ +WS_DLL_PUBLIC +gboolean +wmem_tree_is_empty(wmem_tree_t *tree); + +/** Returns number of nodes in tree */ +WS_DLL_PUBLIC +guint +wmem_tree_count(wmem_tree_t* tree); + +/** 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(wmem_tree_t *tree, guint32 key, void *data); + +/** 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(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_lookup32_le(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_remove32(wmem_tree_t *tree, guint32 key); + +/** case insensitive strings as keys */ +#define WMEM_TREE_STRING_NOCASE 0x00000001 +/** 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 +void +wmem_tree_insert_string(wmem_tree_t *tree, const gchar* key, void *data, + 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 +void * +wmem_tree_lookup_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. */ +WS_DLL_PUBLIC +void * +wmem_tree_remove_string(wmem_tree_t* tree, const gchar* key, guint32 flags); + +typedef struct _wmem_tree_key_t { + guint32 length; /**< length in guint32 words */ + guint32 *key; +} wmem_tree_key_t; + +/** 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_insert32_array(wmem_tree_t *tree, wmem_tree_key_t *key, void *data); + +/** 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(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_array_le(wmem_tree_t *tree, wmem_tree_key_t *key); + +/** 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 gboolean (*wmem_foreach_func)(const void *key, void *value, void *userdata); + + +/** Function type to print key/data of nodes in wmem_print_tree_verbose */ +typedef void (*wmem_printer_func)(const void *data); + + +/** Inorder traversal (left/parent/right) of 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 +gboolean +wmem_tree_foreach(wmem_tree_t* tree, wmem_foreach_func callback, + void *user_data); + + +/* Accepts callbacks to print the key and/or data (both printers can be null) */ +void +wmem_print_tree(wmem_tree_t *tree, wmem_printer_func key_printer, wmem_printer_func data_printer); + +/** @} + * @} */ + +#ifdef __cplusplus +} +#endif /* __cplusplus */ + +#endif /* __WMEM_TREE_H__ */ + +/* + * Editor modelines - https://www.wireshark.org/tools/modelines.html + * + * Local variables: + * c-basic-offset: 4 + * tab-width: 8 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=4 tabstop=8 expandtab: + * :indentSize=4:tabSize=8:noTabs=true: + */ |