From Reinhard Speyerer:
[obnox/wireshark/wip.git] / doc / README.binarytrees
1 $Id$
2
3 1. Introduction
4
5 Binary trees are 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 numbers of objects.
15
16 Wireshark 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 wireshark, 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 EPhemeral and SEasonal storage.
26
27
28 2. Basic Usage
29 For most users it will be sufficient to only know and use three functions
30 emem_tree_t *se_tree_create(int type, char *name);
31 void se_tree_insert32(emem_tree_t *se_tree, guint32 key, void *data);
32 void *se_tree_lookup32(emem_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 wireshark is resetting all SEasonal storage.
38 That is every time you load a new capture file into wireshark 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 emem_tree_t *tcp_pdu_time_table = NULL;
53 ...
54 void proto_register_...(void) {
55    ...
56    tcp_pdu_time_table=se_tree_create(EMEM_TREE_TYPE_RED_BLACK, "PROTO_mytree");
57    ...
58 }
59
60 That is how easy it is to create a binary tree. You only need to create it
61 once when wireshark starts and the tree will remain there until you exit
62 wireshark.  Everytime a new capture is loaded, all nodes allocated to the
63 tree are freed automatically and the tree is reset without you having to do
64 anything at all.
65
66
67 2.2 se_tree_insert32(emem_tree_t *se_tree, guint32 key, void *data);
68 This function is used to add a new node into the tree. 
69 This function is used for such trees where you always use a guint32 as the 
70 identifier/key for the node. Most trees you want to use are likely in this 
71 category.
72
73 As data you should specify a pointer to the data structure you want to be
74 able to retrieve later when you look for that same key.
75
76 NOTE: If you insert a node to a key that already exists in the tree
77 this function will allow you to do that. It will just drop the old pointer
78 to data and replace it with the new one you just provided.
79 This should not be a problem as long as the old and the new data blobs
80 are se_allocated() since you cant free() such memory explicitly anyway
81 and the old one will be release automatically anyway when the SEasonal
82 system reclaims all the SE data.
83
84 NOTE: It is a good idea to only provide data that point to blobs allocated
85 by se_alloc(). By doing that you will have a tree where the tree and all
86 the data pointed to will be automatically released by the system at the
87 same time.  This is very neat and makes it real difficult to have memory
88 leaks in your code.
89
90 NOTE: When you insert items in the tree, it is very likely that you only
91 want to add any data to the tree during the very first time you process
92 a particular packet.
93 Wireshark may reprocess the same packet multiple times afterwards by the user
94 clicking on the packet or for other reasons. 
95 You probably DO want to protect the insert call within an if statement such
96 as
97
98 Example:
99     /* only TRUE first time we process this packet*/
100     if(!pinfo->fd->flags.visited){ 
101        ...
102        data=se_alloc(...);
103        data->...
104        ...
105        se_tree_insert32(se_tree, key, data);
106        ...
107     }
108
109 Please do think about how and when you want to add items to the tree.
110 If you don't think you should use the if statement to protect the insert
111 please reconsider and think it through one extra time.
112
113
114 2.3 se_tree_lookup32(emem_tree_t *se_tree, guint32 key);
115 This function is used to read back from the tree the data value that is 
116 associated with this key.
117 If no such node was found the function will return NULL.
118
119 Example:
120     ...
121     data_structure = se_tree_lookup32(se_tree, key);
122     if(data_structure){
123       ...
124     }
125
126 Don't forget to check that the returned pointer is non-NULL before you 
127 dereference it, please.
128
129
130 Simple as that, can it be easier?
131
132
133
134
135 3. Advanced Usage
136 This will list some of the more unconventional and hopefully rarely used 
137 functions.
138
139 3.1 se_tree_create_non_persistent(int type, char *name);
140 Sometimes you don't want a tree that is automatically reset to become an empty
141 tree. You might want a tree that is completely destroyed once the next
142 capture file is read and even the pointer to the tree itself becomes invalid.
143
144 This would most likely be the case when you do NOT want a global tree
145 but instead a tree that is held inside some other SE allocated structure.
146 So that when that encapsulating structure is released the entire tree will
147 disappear completely as well.
148
149 Maybe you have a normal tree to track all conversations for your protocol
150 and for each conversation you se_alloc() a structure to maintain some 
151 data about that conversation. Assume you want to add to that structure
152 another binary tree   a binary tree that is private to that structure/
153 conversation to hold some other data.
154 In that case, this is the function you want.
155
156
157 3.2 se_tree_insert32_array / se_tree_lookup32_array
158 typedef struct _emem_tree_key_t {
159         guint32 length;                 /*length in guint32 words */
160         guint32 *key;
161 } emem_tree_key_t;
162 void se_tree_insert32_array(emem_tree_t *se_tree, emem_tree_key_t *key, void *data);
163 void *se_tree_lookup32_array(emem_tree_t *se_tree, emem_tree_key_t *key);
164
165 NOTE: the *key parameter taken by these functions WILL be modified by these
166 functions so if you want to reuse the key for a second call you will have
167 to reinitialize key.
168
169
170 These functions are used to insert and lookup a tree where nodes are NOT 
171 indexed by a single guint32 but more like an array of guint32 elements.
172
173 These functions take as key an array of guint32 vectors : emem_tree_key_t.
174 The functions will use vector by vector to search further down the tree 
175 until an array element where length==0 is found indicating the end of the 
176 array.
177
178 NOTE: you MUST terminate the emem_tree_key_t array by {0, NULL}
179 If you forget to do this wireshark will immediately crash.
180
181 NOTE: length indicates the number of guint32 values in the vector, not the
182 number of bytes.
183
184 If your keys are always of exactly the same length, always, and you are willing
185 to bet that there can never ever be a key of a different length you can
186 get away with a simple :
187   emem_tree_key_t key[2];
188   key[0].length= LEN;
189   key[0].key= KEY;
190   key[1].length=0;
191   key[1].key=NULL;
192   se_tree_insert32_array(se_tree, &key[0], data);
193 But IF you would accidentally pass a key with a different number of guint32s
194 in its vectors to this same se_tree  you will crash.
195 Don't use key like this. Please.
196
197
198 Instead use this simple workaround to make it all safe :
199 Specify the first index as 1 guint32 holding the total number of guints in the
200 rest of the key.
201 See NFS that does this to handle filehandles that may be of different lengths
202 in the same tree :
203   emem_tree_key_t fhkey[3];
204   guint32 tmplen;
205
206   tmplen = <length of filehandle/4>;
207   fhkey[0].length = 1;
208   fhkey[0].key    = &tmplen;
209   fhkey[1].length = tmplen;
210   fhkey[1].key    = <filehandle>;
211   fhkey[2].length = 0;
212   fhkey[2].key    = NULL;
213
214 ( /4 since we specify the length here in number of guint32 not number of bytes)
215
216
217 3.3 se_tree_insert_string / se_tree_lookup_string
218 void emem_tree_insert_string(emem_tree_t* h, const gchar* k, void* v, guint32 flags);
219 void* emem_tree_lookup_string(emem_tree_t* h, const gchar* k, guint32 flags);
220 These functions are essentially wrappers for se_tree_insert32_array and
221 se_tree_lookup32_array, tailored to text strings. They extend the text string
222 into an array key and use that to key the se_tree_insert32_array and
223 se_tree_lookup32_array functions.
224 In order to support text string in a case insensitive way add the
225 EMEM_TREE_STRING_NOCASE flag. This will uppercase all string data before using
226 it as key data.
227