1. Introduction
-Binary trees is a well known and popular device in computer science to handle
+Binary trees are a well known and popular device in computer science to handle
storage of object based on a search key or identity.
One particular class of binary trees are Red/Black trees which have nice
properties such as being self-balanced.
Benefits of using binary trees are that they are incredibly fast for
accessing data and they scale very well with good characteristics even to
-very large number of objects.
+very large numbers of objects.
Wireshark provides its own version of red black binary trees designed in
particular to be easy to use and to eliminate most of the memory management
2. Basic Usage
-For most users it will be sufficiant to only know and use three functions
+For most users it will be sufficient to only know and use three functions
emem_tree_t *se_tree_create(int type, char *name);
void se_tree_insert32(emem_tree_t *se_tree, guint32 key, void *data);
void *se_tree_lookup32(emem_tree_t *se_tree, guint32 key);
2.1 se_tree_create(int type, char *name);
se_tree_create() is used to initialize a tree that will be automatically
-cleared and reset everytime wireshark is resetting all SEasonal storage,
-that is every time you load a new capture file into wireshark or when
+cleared and reset every time wireshark is resetting all SEasonal storage.
+That is every time you load a new capture file into wireshark or when
you rescan the entire capture file from scratch.
Name is just a literal text string and serves no other purpose than making
...
void proto_register_...(void) {
...
- tcp_pdu_time_table=se_tree_create(EMEM_TREE_TYPE_RED_BLACK, "PROTO_my_tree");
+ tcp_pdu_time_table=se_tree_create(EMEM_TREE_TYPE_RED_BLACK, "PROTO_mytree");
...
}
-That is how easy it is to create a binary tree. You only need to create it once
-when wireshark starts and the tree will remain there until you exit wireshark.
-Everytime a new capture is loaded, all nodes allocated to the tree is
-automatically and the tree is reset without you having to do anything at all.
+That is how easy it is to create a binary tree. You only need to create it
+once when wireshark starts and the tree will remain there until you exit
+wireshark. Every time a new capture is loaded, all nodes allocated to the
+tree are freed automatically and the tree is reset without you having to do
+anything at all.
2.2 se_tree_insert32(emem_tree_t *se_tree, guint32 key, void *data);
category.
As data you should specify a pointer to the data structure you want to be
-able to retreive later when you look for that same key.
+able to retrieve later when you look for that same key.
NOTE: If you insert a node to a key that already exists in the tree
this function will allow you to do that. It will just drop the old pointer
to data and replace it with the new one you just provided.
This should not be a problem as long as the old and the new data blobs
-are se_allocated() since you cant free() such memory explicitely anyway
+are se_allocated() since you cant free() such memory explicitly anyway
and the old one will be release automatically anyway when the SEasonal
system reclaims all the SE data.
NOTE: It is a good idea to only provide data that point to blobs allocated
-bu se_alloc(). By doing that you will have a tree where the tree and all
-the data pointed to will be automatically released by the system at the same
-time.
-This is very neat and makes real difficult to have memory leaks in your code.
+by se_alloc(). By doing that you will have a tree where the tree and all
+the data pointed to will be automatically released by the system at the
+same time. This is very neat and makes it real difficult to have memory
+leaks in your code.
NOTE: When you insert items in the tree, it is very likely that you only
want to add any data to the tree during the very first time you process
a particular packet.
-Wireshark may reprocess the same packet multiple times afterwards by the user
+Wireshark may reprocess the same packet multiple times afterward by the user
clicking on the packet or for other reasons.
You probably DO want to protect the insert call within an if statement such
as
}
Please do think about how and when you want to add items to the tree.
-If you dont think you should not use the if statement to protect the insert
+If you don't think you should use the if statement to protect the insert
please reconsider and think it through one extra time.
...
}
-Dont forget to check that the returned pointer is non-NULL before you
+Don't forget to check that the returned pointer is non-NULL before you
dereference it, please.
-
-Simple as that, can it be easier?
+2.4 se_tree_lookup32_le(emem_tree_t *se_tree, guint32 key);
+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.
+Simple as that, can it be easier?
3. Advanced Usage
functions.
3.1 se_tree_create_non_persistent(int type, char *name);
-Sometimes you dont want a tree that is automatically reset to become an empty
+Sometimes you don't want a tree that is automatically reset to become an empty
tree. You might want a tree that is completely destroyed once the next
capture file is read and even the pointer to the tree itself becomes invalid.
This would most likely be the case when you do NOT want a global tree
but instead a tree that is held inside some other SE allocated structure.
So that when that encapsulating structure is released the entire tree will
-dissapear completely as well.
+disappear completely as well.
Maybe you have a normal tree to track all conversations for your protocol
and for each conversation you se_alloc() a structure to maintain some
void se_tree_insert32_array(emem_tree_t *se_tree, emem_tree_key_t *key, void *data);
void *se_tree_lookup32_array(emem_tree_t *se_tree, emem_tree_key_t *key);
-NOTE: the *key parameter taken by these functions WILL be modified by
-these functions so if you want to reuse the key for a second call
-you will have to reinitialize key.
+NOTE: the *key parameter taken by these functions WILL be modified by these
+functions so if you want to reuse the key for a second call you will have
+to reinitialize key.
These functions are used to insert and lookup a tree where nodes are NOT
indexed by a single guint32 but more like an array of guint32 elements.
These functions take as key an array of guint32 vectors : emem_tree_key_t.
-The fucntions will use vector by vector to search further down the tree
+The functions will use vector by vector to search further down the tree
until an array element where length==0 is found indicating the end of the
array.
NOTE: you MUST terminate the emem_tree_key_t array by {0, NULL}
If you forget to do this wireshark will immediately crash.
-NOTE: length indicates the number of guint32 values in the vector, not number
-of bytes.
+NOTE: length indicates the number of guint32 values in the vector, not the
+number of bytes.
If your keys are always of exactly the same length, always, and you are willing
to bet that there can never ever be a key of a different length you can
se_tree_insert32_array(se_tree, &key[0], data);
But IF you would accidentally pass a key with a different number of guint32s
in its vectors to this same se_tree you will crash.
-Dont use key like this. Please.
+Don't use key like this. Please.
Instead use this simple workaround to make it all safe :
Specify the first index as 1 guint32 holding the total number of guints in the
rest of the key.
-See NFS that does this to handle filehandes that may be of different lengths
+See NFS that does this to handle file handles that may be of different lengths
in the same tree :
emem_tree_key_t fhkey[3];
guint32 tmplen;
( /4 since we specify the length here in number of guint32 not number of bytes)
-
-3.3 se_tree_insert_string / se_tree_lookup_string
-to be added...
+3.3 se_tree_lookup32_array_le(emem_tree_t *se_tree, emem_tree_key_t *key);
+Much like the se_tree_lookup32_le, this 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.
+
+When using _array_ trees, the tree that is created is a "tree of trees" where the
+last leaf has the indexed data. Thus if you have 3 keys in the emme_tree_key_t
+structure, the "1st" tree indexes key[0]. Each node in this tree points to a
+tree indexed using key[1]. The nodes of the final tree will contain the data.
+
+This construction must be taken into account when using se_tree_lookup32_array_le.
+The program should verify that the node returned contains data that is expected.
+
+3.4 se_tree_insert_string / se_tree_lookup_string
+void emem_tree_insert_string(emem_tree_t* h, const gchar* k, void* v, guint32 flags);
+void* emem_tree_lookup_string(emem_tree_t* h, const gchar* k, guint32 flags);
+These functions are essentially wrappers for se_tree_insert32_array and
+se_tree_lookup32_array, tailored to text strings. They extend the text string
+into an array key and use that to key the se_tree_insert32_array and
+se_tree_lookup32_array functions.
+In order to support text string in a case insensitive way add the
+EMEM_TREE_STRING_NOCASE flag. This will uppercase all string data before using
+it as key data.
git.samba.org / obnox / wireshark / wip.git / blobdiff