epan/wmem/wmem_tree.h

   1 /* wmem_tree.h
   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  * $Id$
   7  *
   8  * Wireshark - Network traffic analyzer
   9  * By Gerald Combs <gerald@wireshark.org>
  10  * Copyright 1998 Gerald Combs
  11  *
  12  * This program is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU General Public License as published by
  14  * the Free Software Foundation; either version 2 of the License, or
  15  * (at your option) any later version.
  16  *
  17  * This program is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  * GNU General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU General Public License along
  23  * with this program; if not, write to the Free Software Foundation, Inc.,
  24  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  25  */
  26
  27 #ifndef __WMEM_TREE_H__
  28 #define __WMEM_TREE_H__
  29
  30 #include "wmem_core.h"
  31
  32 #ifdef __cplusplus
  33 extern "C" {
  34 #endif /* __cplusplus */
  35
  36 /** @addtogroup wmem
  37  *  @{
  38  *    @defgroup wmem-tree Red/Black Tree
  39  *
  40  *    Binary trees are a well-known and popular device in computer science to
  41  *    handle storage of objects based on a search key or identity. The
  42  *    particular binary tree style implemented here is the red/black tree, which
  43  *    has the nice property of being self-balancing. This guarantees O(log(n))
  44  *    time for lookups, compared to linked lists that are O(n). This means
  45  *    red/black trees scale very well when many objects are being stored.
  46  *
  47  *    @{
  48  */
  49
  50 struct _wmem_tree_t;
  51 typedef struct _wmem_tree_t wmem_tree_t;
  52
  53 /** Creates a tree with the given allocator scope. When the scope is emptied,
  54  * the tree is fully destroyed. */
  55 WS_DLL_PUBLIC
  56 wmem_tree_t *
  57 wmem_tree_new(wmem_allocator_t *allocator)
  58 G_GNUC_MALLOC;
  59
  60 /** Creates a tree with two allocator scopes. The base structure lives in the
  61  * master scope, however the data lives in the slave scope. Every time free_all
  62  * occurs in the slave scope the tree is transparently emptied without affecting
  63  * the location of the master structure.
  64  *
  65  * WARNING: None of the tree (even the part in the master scope) can be used
  66  * after the slave scope has been *destroyed*.
  67  *
  68  * The primary use for this function is to create trees that reset for each new
  69  * capture file that is loaded. This can be done by specifying wmem_epan_scope()
  70  * as the master and wmem_file_scope() as the slave.
  71  */
  72 WS_DLL_PUBLIC
  73 wmem_tree_t *
  74 wmem_tree_new_autoreset(wmem_allocator_t *master, wmem_allocator_t *slave)
  75 G_GNUC_MALLOC;
  76
  77 /** Returns true if the tree is empty (has no nodes). */
  78 WS_DLL_PUBLIC
  79 gboolean
  80 wmem_tree_is_empty(wmem_tree_t *tree);
  81
  82 /** Insert a node indexed by a guint32 key value.
  83  *
  84  * Data is a pointer to the structure you want to be able to retrieve by
  85  * searching for the same key later.
  86  *
  87  * NOTE: If you insert a node to a key that already exists in the tree this
  88  * function will simply overwrite the old value. If the structures you are
  89  * storing are allocated in a wmem pool this is not a problem as they will still
  90  * be freed with the pool. If you are managing them manually however, you must
  91  * either ensure the key is unique, or do a lookup before each insert.
  92  */
  93 WS_DLL_PUBLIC
  94 void
  95 wmem_tree_insert32(wmem_tree_t *tree, guint32 key, void *data);
  96
  97 /** Look up a node in the tree indexed by a guint32 integer value. If no node is
  98  * found the function will return NULL.
  99  */
 100 WS_DLL_PUBLIC
 101 void *
 102 wmem_tree_lookup32(wmem_tree_t *tree, guint32 key);
 103
 104 /** Look up a node in the tree indexed by a guint32 integer value.
 105  * Returns the node that has the largest key that is less than or equal
 106  * to the search key, or NULL if no such key exists.
 107  */
 108 WS_DLL_PUBLIC
 109 void *
 110 wmem_tree_lookup32_le(wmem_tree_t *tree, guint32 key);
 111
 112 /** case insensitive strings as keys */
 113 #define WMEM_TREE_STRING_NOCASE                 0x00000001
 114 /** Insert a new value under a string key. Like wmem_tree_insert32 but where the
 115  * key is a null-terminated string instead of a guint32. You may pass
 116  * WMEM_TREE_STRING_NOCASE to the flags argument in order to make it store the
 117  * key in a case-insensitive way. */
 118 WS_DLL_PUBLIC
 119 void
 120 wmem_tree_insert_string(wmem_tree_t *tree, const gchar* key, void *data,
 121         guint32 flags);
 122
 123 /** Lookup the value under a string key, like wmem_tree_lookup32 but where the
 124  * keye is a null-terminated string instead of a guint32. See
 125  * wmem_tree_insert_string for an explanation of flags. */
 126 WS_DLL_PUBLIC
 127 void *
 128 wmem_tree_lookup_string(wmem_tree_t* tree, const gchar* key, guint32 flags);
 129
 130 typedef struct _wmem_tree_key_t {
 131     guint32 length;    /**< length in guint32 words */
 132     guint32 *key;
 133 } wmem_tree_key_t;
 134
 135 /** Insert a node indexed by a sequence of guint32 key values.
 136  *
 137  * Takes as key an array of guint32 vectors of type wmem_tree_key_t. It will
 138  * iterate through each key to search further down the tree until it reaches an
 139  * element where length==0, indicating the end of the array. You MUST terminate
 140  * the key array by {0, NULL} or this will crash.
 141  *
 142  * NOTE: length indicates the number of guint32 values in the vector, not the
 143  * number of bytes.
 144  *
 145  * NOTE: all the "key" members of the "key" argument MUST be aligned on
 146  * 32-bit boundaries; otherwise, this code will crash on platforms such
 147  * as SPARC that require aligned pointers.
 148  *
 149  * If you use ...32_array() calls you MUST make sure that every single node
 150  * you add to a specific tree always has a key of exactly the same number of
 151  * keylen words or it will crash. Or at least that every single item that sits
 152  * behind the same top level node always has exactly the same number of words.
 153  *
 154  * One way to guarantee this is the way that NFS does this for the
 155  * nfs_name_snoop_known tree which holds filehandles for both v2 and v3.
 156  * v2 filehandles are always 32 bytes (8 words) while v3 filehandles can have
 157  * any length (though 32 bytes are most common).
 158  * The NFS dissector handles this by providing a guint32 containing the length
 159  * as the very first item in this vector :
 160  *
 161  *                      wmem_tree_key_t fhkey[3];
 162  *
 163  *                      fhlen=nns->fh_length;
 164  *                      fhkey[0].length=1;
 165  *                      fhkey[0].key=&fhlen;
 166  *                      fhkey[1].length=fhlen/4;
 167  *                      fhkey[1].key=nns->fh;
 168  *                      fhkey[2].length=0;
 169  */
 170 WS_DLL_PUBLIC
 171 void
 172 wmem_tree_insert32_array(wmem_tree_t *tree, wmem_tree_key_t *key, void *data);
 173
 174 /** Look up a node in the tree indexed by a sequence of guint32 integer values.
 175  * See wmem_tree_insert32_array for details on the key.
 176  */
 177 WS_DLL_PUBLIC
 178 void *
 179 wmem_tree_lookup32_array(wmem_tree_t *tree, wmem_tree_key_t *key);
 180
 181 /** Look up a node in the tree indexed by a multi-part tree value.
 182  * The function will return the node that has the largest key that is
 183  * equal to or smaller than the search key, or NULL if no such key was
 184  * found.
 185  *
 186  * NOTE:  The key returned will be "less" in key order.  The usefulness
 187  * of the returned node must be verified prior to use.
 188  *
 189  * See wmem_tree_insert32_array for details on the key.
 190  */
 191 WS_DLL_PUBLIC
 192 void *
 193 wmem_tree_lookup32_array_le(wmem_tree_t *tree, wmem_tree_key_t *key);
 194
 195 /** Function type for processing one node of a tree during a traversal. Value is
 196  * the value of the node, userdata is whatever was passed to the traversal
 197  * function. If the function returns TRUE the traversal will end prematurely.
 198  */
 199 typedef gboolean (*wmem_foreach_func)(void *value, void *userdata);
 200
 201 /** Traverse the tree and call callback(value, userdata) for each value found.
 202  * Returns TRUE if the traversal was ended prematurely by the callback.
 203  */
 204 WS_DLL_PUBLIC
 205 gboolean
 206 wmem_tree_foreach(wmem_tree_t* tree, wmem_foreach_func callback,
 207         void *user_data);
 208
 209 /** Prints the structure of the tree to stdout. Primarily for debugging. */
 210 void
 211 wmem_print_tree(wmem_tree_t *tree);
 212
 213 /**   @}
 214  *  @} */
 215
 216 #ifdef __cplusplus
 217 }
 218 #endif /* __cplusplus */
 219
 220 #endif /* __WMEM_TREE_H__ */
 221
 222 /*
 223  * Editor modelines  -  http://www.wireshark.org/tools/modelines.html
 224  *
 225  * Local variables:
 226  * c-basic-offset: 4
 227  * tab-width: 8
 228  * indent-tabs-mode: nil
 229  * End:
 230  *
 231  * vi: set shiftwidth=4 tabstop=8 expandtab:
 232  * :indentSize=4:tabSize=8:noTabs=true:
 233  */