doc/README.binarytrees

   1 $Id$
   2
   3 1. Introduction
   4
   5 Binary trees is a well known and popular device in computer science to handle
   6 storage of object based on a search key or identity.
   7 One particular class of binary trees are Red/Black trees which have nice
   8 properties such as being self-balanced.
   9 Such trees are often very fast for accessing data, and may average O(log(n))
  10 for lookups, compared to linked lists that are of order O(n).
  11
  12 Benefits of using binary trees are that they are incredibly fast for
  13 accessing data and they scale very well with good characteristics even to
  14 very large number of objects.
  15
  16 Ethereal provides its own version of red black binary trees designed in
  17 particular to be easy to use and to eliminate most of the memory management
  18 often associated with such trees.
  19
  20 The trees supported by wireshark are currently all created using SEasonal
  21 storage which means that when you load a new trace into ethereal, the SEasonal
  22 memory management will automatically release every single byte of data
  23 associated with the tree.
  24
  25 Please see README.malloc for a description of EmPhereal and SEasonal storage.
  26
  27
  28 2. Basic Usage
  29 For most users it will be sufficiant to only know and use three functions
  30 se_tree_t *se_tree_create(int type, char *name);
  31 void se_tree_insert32(se_tree_t *se_tree, guint32 key, void *data);
  32 void *se_tree_lookup32(se_tree_t *se_tree, guint32 key);
  33
  34
  35 2.1 se_tree_create(int type, char *name);
  36 se_tree_create() is used to initialize a tree that will be automatically
  37 cleared and reset everytime ethereal is resetting all SEasonal storage,
  38 that is every time you load a new capture file into ethereal or when
  39 you rescan the entire capture file from scratch.
  40
  41 Name is just a literal text string and serves no other purpose than making
  42 debugging of the trees easier. Specify a name here that uniquely identifies
  43 both the protocol you create the tree for and its purpose.
  44
  45
  46 This function is most likely called once from your
  47 proto_register_<yourprotocol>() function.
  48
  49 Example (from packet-tcp.c):
  50 #include <epan/emem.h>
  51 ...
  52 static se_tree_t *tcp_pdu_time_table = NULL;
  53 ...
  54 void proto_register_...(void) {
  55    ...
  56    tcp_pdu_time_table=se_tree_create(SE_TREE_TYPE_RED_BLACK, "PROTO_my_tree");
  57    ...
  58 }
  59
  60 That is how easy it is to create a binary tree. You only need to create it once
  61 when ethereal starts and the tree will remain there until you exit ethereal.
  62 Everytime a new capture is loaded, all nodes allocated to the tree is
  63 automatically and the tree is reset without you having to do anything at all.
  64
  65
  66 2.2 se_tree_insert32(se_tree_t *se_tree, guint32 key, void *data);
  67 This function is used to add a new node into the tree.
  68 This function is used for such trees where you always use a guint32 as the
  69 identifier/key for the node. Most trees you want to use are likely in this
  70 category.
  71
  72 As data you should specify a pointer to the data structure you want to be
  73 able to retreive later when you look for that same key.
  74
  75 NOTE: If you insert a node to a key that already exists in the tree
  76 this function will allow you to do that. It will just drop the old pointer
  77 to data and replace it with the new one you just provided.
  78 This should not be a problem as long as the old and the new data blobs
  79 are se_allocated() since you cant free() such memory explicitely anyway
  80 and the old one will be release automatically anyway when the SEasonal
  81 system reclaims all the SE data.
  82
  83 NOTE: It is a good idea to only provide data that point to blobs allocated
  84 bu se_alloc(). By doing that you will have a tree where the tree and all
  85 the data pointed to will be automatically released by the system at the same
  86 time.
  87 This is very neat and makes real difficult to have memory leaks in your code.
  88
  89 NOTE: When you insert items in the tree, it is very likely that you only
  90 want to add any data to the tree during the very first time you process
  91 a particular packet.
  92 Ethereal may reprocess the same packet multiple times afterwards by the user
  93 clicking on the packet or for other reasons.
  94 You probably DO want to protect the insert call within an if statement such
  95 as
  96
  97 Example:
  98     /* only TRUE first time we process this packet*/
  99     if(!pinfo->fd->flags.visited){
 100        ...
 101        data=se_alloc(...);
 102        data->...
 103        ...
 104        se_tree_insert32(se_tree, key, data);
 105        ...
 106     }
 107
 108 Please do think about how and when you want to add items to the tree.
 109 If you dont think you should not use the if statement to protect the insert
 110 please reconsider and think it through one extra time.
 111
 112
 113 2.3 se_tree_lookup32(se_tree_t *se_tree, guint32 key);
 114 This function is used to read back from the tree the data value that is
 115 associated with this key.
 116 If no such node was found the function will return NULL.
 117
 118 Example:
 119     ...
 120     data_structure = se_tree_lookup32(se_tree, key);
 121     if(data_structure){
 122       ...
 123     }
 124
 125 Dont forget to check that the returned pointer is non-NULL before you
 126 dereference it, please.
 127
 128
 129 Simple as that, can it be easier?
 130
 131
 132
 133
 134 3. Advanced Usage
 135 This will list some of the more unconventional and hopefully rarely used
 136 functions.
 137
 138 3.1 se_tree_create_non_persistent(int type, char *name);
 139 Sometimes you dont want a tree that is automatically reset to become an empty
 140 tree. You might want a tree that is completely destroyed once the next
 141 capture file is read and even the pointer to the tree itself becomes invalid.
 142
 143 This would most likely be the case when you do NOT want a global tree
 144 but instead a tree that is held inside some other SE allocated structure.
 145 So that when that encapsulating structure is released the entire tree will
 146 dissapear completely as well.
 147
 148 Maybe you have a normal tree to track all conversations for your protocol
 149 and for each conversation you se_alloc() a structure to maintain some
 150 data about that conversation. Assume you want to add to that structure
 151 another binary tree   a binary tree that is private to that structure/
 152 conversation to hold some other data.
 153 In that case, this is the function you want.
 154
 155
 156 3.2 se_tree_insert32_array / se_tree_lookup32_array
 157 typedef struct _se_tree_key_t {
 158         guint32 length;                 /*length in guint32 words */
 159         guint32 *key;
 160 } se_tree_key_t;
 161 void se_tree_insert32_array(se_tree_t *se_tree, se_tree_key_t *key, void *data);
 162 void *se_tree_lookup32_array(se_tree_t *se_tree, se_tree_key_t *key);
 163
 164 NOTE: the *key parameter taken by these functions WILL be modified by
 165 these functions   so if you want to reuse the key for a second call
 166 you will have to reinitialize key.
 167
 168
 169 These functions are used to insert and lookup a tree where nodes are NOT
 170 indexed by a single guint32 but more like an array of guint32 elements.
 171
 172 These functions take as key an array of guint32 vectors : se_tree_key_t.
 173 The fucntions will use vector by vector to search further down the tree
 174 until an array element where length==0 is found indicating the end of the
 175 array.
 176
 177 NOTE: you MUST terminate the se_tree_key_t array by {0, NULL}
 178 If you forget to do this ethereal will immediately crash.
 179
 180 NOTE: length indicates the number of guint32 values in the vector, not number
 181 of bytes.
 182
 183 If your keys are always of exactly the same length, always, and you are willing
 184 to bet that there can never ever be a key of a different length you can
 185 get away with a simple :
 186   se_tree_key_t key[2];
 187   key[0].length= LEN;
 188   key[0].key= KEY;
 189   key[1].length=0;
 190   key[1].key=NULL;
 191   se_tree_insert32_array(se_tree, &key[0], data);
 192 But IF you would accidentally pass a key with a different number of guint32s
 193 in its vectors to this same se_tree  you will crash.
 194 Dont use key like this. Please.
 195
 196
 197 Instead use this simple workaround to make it all safe :
 198 Specify the first index as 1 guint32 holding the total number of guints in the
 199 rest of the key.
 200 See NFS that does this to handle filehandes that may be of different lengths
 201 in the same tree :
 202   se_tree_key_t fhkey[3];
 203   guint32 tmplen;
 204
 205   tmplen = <length of filehandle/4>;
 206   fhkey[0].length = 1;
 207   fhkey[0].key    = &tmplen;
 208   fhkey[1].length = tmplen;
 209   fhkey[1].key    = <filehandle>;
 210   fhkey[2].length = 0;
 211   fhkey[2].key    = NULL;
 212
 213 ( /4 since we specify the length here in number of guint32 not number of bytes)
 214
 215
 216 3.3 se_tree_insert_string / se_tree_lookup_string
 217 to be added...
 218