wsutil/wmem/wmem_tree.h

   1 /** @file
   2  * Definitions for the Wireshark Memory Manager Red-Black Tree
   3  * Based on the red-black tree implementation in epan/emem.*
   4  * Copyright 2013, Evan Huus <eapache@gmail.com>
   5  *
   6  * Wireshark - Network traffic analyzer
   7  * By Gerald Combs <gerald@wireshark.org>
   8  * Copyright 1998 Gerald Combs
   9  *
  10  * SPDX-License-Identifier: GPL-2.0-or-later
  11  */
  12
  13 #ifndef __WMEM_TREE_H__
  14 #define __WMEM_TREE_H__
  15
  16 #include "wmem_core.h"
  17
  18 #ifdef __cplusplus
  19 extern "C" {
  20 #endif /* __cplusplus */
  21
  22 /** @addtogroup wmem
  23  *  @{
  24  *    @defgroup wmem-tree Red/Black Tree
  25  *
  26  *    Binary trees are a well-known and popular device in computer science to
  27  *    handle storage of objects based on a search key or identity. The
  28  *    particular binary tree style implemented here is the red/black tree, which
  29  *    has the nice property of being self-balancing. This guarantees O(log(n))
  30  *    time for lookups, compared to linked lists that are O(n). This means
  31  *    red/black trees scale very well when many objects are being stored.
  32  *
  33  *    @{
  34  */
  35
  36 struct _wmem_tree_t;
  37 typedef struct _wmem_tree_t wmem_tree_t;
  38
  39 /** Creates a tree with the given allocator scope. When the scope is emptied,
  40  * the tree is fully destroyed. */
  41 WS_DLL_PUBLIC
  42 wmem_tree_t *
  43 wmem_tree_new(wmem_allocator_t *allocator)
  44 G_GNUC_MALLOC;
  45
  46 /** Creates a tree with two allocator scopes. The base structure lives in the
  47  * metadata scope, and the tree data lives in the data scope. Every time free_all
  48  * occurs in the data scope the tree is transparently emptied without affecting
  49  * the location of the base / metadata structure.
  50  *
  51  * WARNING: None of the tree (even the part in the metadata scope) can be used
  52  * after the data scope has been *destroyed*.
  53  *
  54  * The primary use for this function is to create trees that reset for each new
  55  * capture file that is loaded. This can be done by specifying wmem_epan_scope()
  56  * as the metadata scope and wmem_file_scope() as the data scope.
  57  */
  58 WS_DLL_PUBLIC
  59 wmem_tree_t *
  60 wmem_tree_new_autoreset(wmem_allocator_t *metadata_scope, wmem_allocator_t *data_scope)
  61 G_GNUC_MALLOC;
  62
  63 /** Cleanup memory used by tree.  Intended for NULL scope allocated trees */
  64 WS_DLL_PUBLIC
  65 void
  66 wmem_tree_destroy(wmem_tree_t *tree, bool free_keys, bool free_values);
  67
  68 /** Returns true if the tree is empty (has no nodes). */
  69 WS_DLL_PUBLIC
  70 bool
  71 wmem_tree_is_empty(wmem_tree_t *tree);
  72
  73 /** Returns number of nodes in tree */
  74 WS_DLL_PUBLIC
  75 unsigned
  76 wmem_tree_count(wmem_tree_t* tree);
  77
  78 /** Insert a node indexed by a uint32_t key value.
  79  *
  80  * Data is a pointer to the structure you want to be able to retrieve by
  81  * searching for the same key later.
  82  *
  83  * NOTE: If you insert a node to a key that already exists in the tree this
  84  * function will simply overwrite the old value. If the structures you are
  85  * storing are allocated in a wmem pool this is not a problem as they will still
  86  * be freed with the pool. If you are managing them manually however, you must
  87  * either ensure the key is unique, or do a lookup before each insert.
  88  */
  89 WS_DLL_PUBLIC
  90 void
  91 wmem_tree_insert32(wmem_tree_t *tree, uint32_t key, void *data);
  92
  93 /** Look up a node in the tree indexed by a uint32_t integer value. Return true
  94  * if present.
  95  */
  96 WS_DLL_PUBLIC
  97 bool
  98 wmem_tree_contains32(wmem_tree_t *tree, uint32_t key);
  99
 100 /** Look up a node in the tree indexed by a uint32_t integer value. If no node is
 101  * found the function will return NULL.
 102  */
 103 WS_DLL_PUBLIC
 104 void *
 105 wmem_tree_lookup32(wmem_tree_t *tree, uint32_t key);
 106
 107 /** Look up a node in the tree indexed by a uint32_t integer value.
 108  * Returns the node that has the largest key that is less than or equal
 109  * to the search key, or NULL if no such key exists.
 110  */
 111 WS_DLL_PUBLIC
 112 void *
 113 wmem_tree_lookup32_le(wmem_tree_t *tree, uint32_t key);
 114
 115 /** Look up a node in the tree indexed by a uint32_t integer value.
 116  * Returns the node that has the largest key that is less than or equal
 117  * to the search key, or NULL if no such key exists. Also returns the
 118  * greatest lower bound key if it exists.
 119  */
 120 WS_DLL_PUBLIC
 121 void *
 122 wmem_tree_lookup32_le_full(wmem_tree_t *tree, uint32_t key, uint32_t *orig_key);
 123
 124 /** Look up a node in the tree indexed by a uint32_t integer value.
 125  * Returns the node that has the smallest key that is greater than or equal
 126  * to the search key, or NULL if no such key exists.
 127  */
 128 WS_DLL_PUBLIC
 129 void *
 130 wmem_tree_lookup32_ge(wmem_tree_t *tree, uint32_t key);
 131
 132 /** Look up a node in the tree indexed by a uint32_t integer value.
 133  * Returns the node that has the smallest key that is greater than or equal
 134  * to the search key, or NULL if no such key exists. Also returns the
 135  * least upper bound key if it exists.
 136  */
 137 WS_DLL_PUBLIC
 138 void *
 139 wmem_tree_lookup32_ge_full(wmem_tree_t *tree, uint32_t key, uint32_t *orig_key);
 140
 141 /** Remove a node in the tree indexed by a uint32_t integer value. This
 142  * now is a real remove. This returns the value stored at that key. If
 143  * the tree memory is managed manually (NULL allocator), it is the
 144  * responsibility of the caller to free it.
 145  */
 146 WS_DLL_PUBLIC
 147 void *
 148 wmem_tree_remove32(wmem_tree_t *tree, uint32_t key);
 149
 150 /** case insensitive strings as keys */
 151 #define WMEM_TREE_STRING_NOCASE                 0x00000001
 152 /** Insert a new value under a string key. Like wmem_tree_insert32 but where the
 153  * key is a null-terminated string instead of a uint32_t. You may pass
 154  * WMEM_TREE_STRING_NOCASE to the flags argument in order to make it store the
 155  * key in a case-insensitive way.  (Note that "case-insensitive" refers
 156  * only to the ASCII letters A-Z and a-z; it is locale-independent.
 157  * Do not expect it to honor the rules of your language; for example, "I"
 158  * will always be mapped to "i". */
 159 WS_DLL_PUBLIC
 160 void
 161 wmem_tree_insert_string(wmem_tree_t *tree, const char* key, void *data,
 162         uint32_t flags);
 163
 164 /** Lookup the value under a string key, like wmem_tree_lookup32 but where the
 165  * keye is a null-terminated string instead of a uint32_t. See
 166  * wmem_tree_insert_string for an explanation of flags. */
 167 WS_DLL_PUBLIC
 168 void *
 169 wmem_tree_lookup_string(wmem_tree_t* tree, const char* key, uint32_t flags);
 170
 171 /** Remove the value under a string key.  This is not really a remove, but the
 172  * value is set to NULL so that wmem_tree_lookup_string not will find it.
 173  * See wmem_tree_insert_string for an explanation of flags. */
 174 WS_DLL_PUBLIC
 175 void *
 176 wmem_tree_remove_string(wmem_tree_t* tree, const char* key, uint32_t flags);
 177
 178 typedef struct _wmem_tree_key_t {
 179     uint32_t length;    /**< length in uint32_t words */
 180     uint32_t *key;
 181 } wmem_tree_key_t;
 182
 183 /** Insert a node indexed by a sequence of uint32_t key values.
 184  *
 185  * Takes as key an array of uint32_t vectors of type wmem_tree_key_t. It will
 186  * iterate through each key to search further down the tree until it reaches an
 187  * element where length==0, indicating the end of the array. You MUST terminate
 188  * the key array by {0, NULL} or this will crash.
 189  *
 190  * NOTE: length indicates the number of uint32_t values in the vector, not the
 191  * number of bytes.
 192  *
 193  * NOTE: all the "key" members of the "key" argument MUST be aligned on
 194  * 32-bit boundaries; otherwise, this code will crash on platforms such
 195  * as SPARC that require aligned pointers.
 196  *
 197  * If you use ...32_array() calls you MUST make sure that every single node
 198  * you add to a specific tree always has a key of exactly the same number of
 199  * keylen words or it will crash. Or at least that every single item that sits
 200  * behind the same top level node always has exactly the same number of words.
 201  *
 202  * One way to guarantee this is the way that NFS does this for the
 203  * nfs_name_snoop_known tree which holds filehandles for both v2 and v3.
 204  * v2 filehandles are always 32 bytes (8 words) while v3 filehandles can have
 205  * any length (though 32 bytes are most common).
 206  * The NFS dissector handles this by providing a uint32_t containing the length
 207  * as the very first item in this vector :
 208  *
 209  *                      wmem_tree_key_t fhkey[3];
 210  *
 211  *                      fhlen=nns->fh_length;
 212  *                      fhkey[0].length=1;
 213  *                      fhkey[0].key=&fhlen;
 214  *                      fhkey[1].length=fhlen/4;
 215  *                      fhkey[1].key=nns->fh;
 216  *                      fhkey[2].length=0;
 217  */
 218 WS_DLL_PUBLIC
 219 void
 220 wmem_tree_insert32_array(wmem_tree_t *tree, wmem_tree_key_t *key, void *data);
 221
 222 /** Look up a node in the tree indexed by a sequence of uint32_t integer values.
 223  * See wmem_tree_insert32_array for details on the key.
 224  */
 225 WS_DLL_PUBLIC
 226 void *
 227 wmem_tree_lookup32_array(wmem_tree_t *tree, wmem_tree_key_t *key);
 228
 229 /** Look up a node in the tree indexed by a multi-part tree value.
 230  * The function will return the node that has the largest key that is
 231  * equal to or smaller than the search key, or NULL if no such key was
 232  * found.
 233  *
 234  * NOTE:  The key returned will be "less" in key order.  The usefulness
 235  * of the returned node must be verified prior to use.
 236  *
 237  * See wmem_tree_insert32_array for details on the key.
 238  */
 239 WS_DLL_PUBLIC
 240 void *
 241 wmem_tree_lookup32_array_le(wmem_tree_t *tree, wmem_tree_key_t *key);
 242
 243 /** Function type for processing one node of a tree during a traversal. Value is
 244  * the value of the node, userdata is whatever was passed to the traversal
 245  * function. If the function returns true the traversal will end prematurely.
 246  */
 247 typedef bool (*wmem_foreach_func)(const void *key, void *value, void *userdata);
 248
 249
 250 /** Function type to print key/data of nodes in wmem_print_tree_verbose */
 251 typedef void (*wmem_printer_func)(const void *data);
 252
 253
 254 /** Inorder traversal (left/parent/right) of the tree and call
 255  * callback(value, userdata) for each value found.
 256  *
 257  * Returns true if the traversal was ended prematurely by the callback.
 258  */
 259 WS_DLL_PUBLIC
 260 bool
 261 wmem_tree_foreach(wmem_tree_t* tree, wmem_foreach_func callback,
 262         void *user_data);
 263
 264
 265 /* Accepts callbacks to print the key and/or data (both printers can be null) */
 266 WS_DLL_PUBLIC
 267 void
 268 wmem_print_tree(wmem_tree_t *tree, wmem_printer_func key_printer, wmem_printer_func data_printer);
 269
 270 /**   @}
 271  *  @} */
 272
 273 #ifdef __cplusplus
 274 }
 275 #endif /* __cplusplus */
 276
 277 #endif /* __WMEM_TREE_H__ */
 278
 279 /*
 280  * Editor modelines  -  https://www.wireshark.org/tools/modelines.html
 281  *
 282  * Local variables:
 283  * c-basic-offset: 4
 284  * tab-width: 8
 285  * indent-tabs-mode: nil
 286  * End:
 287  *
 288  * vi: set shiftwidth=4 tabstop=8 expandtab:
 289  * :indentSize=4:tabSize=8:noTabs=true:
 290  */