diff options
| -rw-r--r-- | debian/wireshark-dev.docs | 2 | ||||
| -rw-r--r-- | doc/Makefile.am | 1 | ||||
| -rw-r--r-- | doc/README.binarytrees | 241 | ||||
| -rw-r--r-- | doc/README.developer | 1 | ||||
| -rw-r--r-- | doc/README.dissector | 1 | ||||
| -rw-r--r-- | doc/doc.vcproj | 4 | ||||
| -rw-r--r-- | epan/wmem/wmem_tree.h | 73 |
7 files changed, 60 insertions, 263 deletions
diff --git a/debian/wireshark-dev.docs b/debian/wireshark-dev.docs index 58947a03f1..6e5aa55a50 100644 --- a/debian/wireshark-dev.docs +++ b/debian/wireshark-dev.docs @@ -1,4 +1,3 @@ -doc/README.binarytrees doc/README.capture doc/README.design doc/README.developer @@ -11,4 +10,5 @@ doc/README.regression doc/README.request_response_tracking doc/README.stats_tree doc/README.tapping +doc/README.wmem doc/README.xml-output diff --git a/doc/Makefile.am b/doc/Makefile.am index 544b0d0e2e..8e28e58876 100644 --- a/doc/Makefile.am +++ b/doc/Makefile.am @@ -246,7 +246,6 @@ MAINTAINERCLEANFILES = \ EXTRA_DIST = \ Makefile.nmake \ - README.binarytrees \ README.capture \ README.design \ README.developer \ diff --git a/doc/README.binarytrees b/doc/README.binarytrees deleted file mode 100644 index 7e0fc3652a..0000000000 --- a/doc/README.binarytrees +++ /dev/null @@ -1,241 +0,0 @@ -$Id$ - -1. Introduction - -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. -Such trees are often very fast for accessing data, and may average O(log(n)) -for lookups, compared to linked lists that are of order O(n). - -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 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 -often associated with such trees. - -The trees supported by wireshark are currently all created using SEasonal -storage which means that when you load a new trace into wireshark, the SEasonal -memory management will automatically release every single byte of data -associated with the tree. - -Please see README.malloc for a description of EPhemeral and SEasonal storage. - - -2. Basic Usage -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 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 -debugging of the trees easier. Specify a name here that uniquely identifies -both the protocol you create the tree for and its purpose. - - -This function is most likely called once from your -proto_register_<yourprotocol>() function. - -Example (from packet-tcp.c): -#include <epan/emem.h> -... -static emem_tree_t *tcp_pdu_time_table = NULL; -... -void proto_register_...(void) { - ... - 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. 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); -This function is used to add a new node into the tree. -This function is used for such trees where you always use a guint32 as the -identifier/key for the node. Most trees you want to use are likely in this -category. - -As data you should specify a pointer to the data structure you want to be -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 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 -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 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 - -Example: - /* only TRUE first time we process this packet*/ - if(!pinfo->fd->flags.visited){ - ... - data=se_alloc(...); - data->... - ... - se_tree_insert32(se_tree, key, data); - ... - } - -Please do think about how and when you want to add items to the tree. -If you don't think you should use the if statement to protect the insert -please reconsider and think it through one extra time. - - -2.3 se_tree_lookup32(emem_tree_t *se_tree, guint32 key); -This function is used to read back from the tree the data value that is -associated with this key. -If no such node was found the function will return NULL. - -Example: - ... - data_structure = se_tree_lookup32(se_tree, key); - if(data_structure){ - ... - } - -Don't forget to check that the returned pointer is non-NULL before you -dereference it, please. - -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 -This will list some of the more unconventional and hopefully rarely used -functions. - -3.1 se_tree_create_non_persistent(int type, char *name); -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 -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 -data about that conversation. Assume you want to add to that structure -another binary tree a binary tree that is private to that structure/ -conversation to hold some other data. -In that case, this is the function you want. - - -3.2 se_tree_insert32_array / se_tree_lookup32_array -typedef struct _emem_tree_key_t { - guint32 length; /*length in guint32 words */ - guint32 *key; -} emem_tree_key_t; -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. - - -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 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 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 -get away with a simple : - emem_tree_key_t key[2]; - key[0].length= LEN; - key[0].key= KEY; - key[1].length=0; - key[1].key=NULL; - 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. -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 file handles that may be of different lengths -in the same tree : - emem_tree_key_t fhkey[3]; - guint32 tmplen; - - tmplen = <length of filehandle/4>; - fhkey[0].length = 1; - fhkey[0].key = &tmplen; - fhkey[1].length = tmplen; - fhkey[1].key = <filehandle>; - fhkey[2].length = 0; - fhkey[2].key = NULL; - -( /4 since we specify the length here in number of guint32 not number of bytes) - -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. - diff --git a/doc/README.developer b/doc/README.developer index b37dfa5417..8a1f9d6fe5 100644 --- a/doc/README.developer +++ b/doc/README.developer @@ -47,7 +47,6 @@ You'll find additional information in the following README files: You'll find additional dissector related information in the file README.dissector as well as the following README files: -- README.binarytrees - fast access to large data collections - README.heuristic - what are heuristic dissectors and how to write them - README.plugins - how to "pluginize" a dissector - README.python - writing a dissector in PYTHON. diff --git a/doc/README.dissector b/doc/README.dissector index 94871fae5a..97fdd24b8a 100644 --- a/doc/README.dissector +++ b/doc/README.dissector @@ -29,7 +29,6 @@ root dir. You'll find additional dissector related information in the following README files: -- README.binarytrees - fast access to large data collections - README.heuristic - what are heuristic dissectors and how to write them - README.plugins - how to "pluginize" a dissector - README.python - writing a dissector in PYTHON. diff --git a/doc/doc.vcproj b/doc/doc.vcproj index f3c44e2abe..e4eba01c06 100644 --- a/doc/doc.vcproj +++ b/doc/doc.vcproj @@ -67,10 +67,6 @@ > </File> <File - RelativePath=".\README.binarytrees" - > - </File> - <File RelativePath=".\README.capture" > </File> diff --git a/epan/wmem/wmem_tree.h b/epan/wmem/wmem_tree.h index c36f33c547..acb35786db 100644 --- a/epan/wmem/wmem_tree.h +++ b/epan/wmem/wmem_tree.h @@ -35,9 +35,14 @@ extern "C" { /** @addtogroup wmem * @{ - * @defgroup wmem-tree Red-Black Tree + * @defgroup wmem-tree Red/Black Tree * - * A red-black tree implementation on top of wmem. + * Binary trees are a well-known and popular device in computer science to + * handle storage of objects based on a search key or identity. The + * particular binary tree style implemented here is the red/black tree, which + * has the nice property of being self-balancing. This guarantees O(log(n)) + * time for lookups, compared to linked lists that are O(n). This means + * red/black trees scale very well when many objects are being stored. * * @{ */ @@ -45,7 +50,8 @@ extern "C" { struct _wmem_tree_t; typedef struct _wmem_tree_t wmem_tree_t; -/** Creates a tree with the given allocator scope */ +/** Creates a tree with the given allocator scope. When the scope is emptied, + * the tree is fully destroyed. */ WS_DLL_PUBLIC wmem_tree_t * wmem_tree_new(wmem_allocator_t *allocator) @@ -57,7 +63,11 @@ G_GNUC_MALLOC; * the location of the master structure. * * WARNING: None of the tree (even the part in the master scope) can be used - * after the slave scope has been destroyed. + * after the slave scope has been *destroyed*. + * + * The primary use for this function is to create trees that reset for each new + * capture file that is loaded. This can be done by specifying wmem_epan_scope() + * as the master and wmem_file_scope() as the slave. */ WS_DLL_PUBLIC wmem_tree_t * @@ -69,12 +79,24 @@ WS_DLL_PUBLIC gboolean wmem_tree_is_empty(wmem_tree_t *tree); -/** Insert a node indexed by a guint32 key value. */ +/** Insert a node indexed by a guint32 key value. + * + * Data is a pointer to the structure you want to be able to retrieve by + * searching for the same key later. + * + * NOTE: If you insert a node to a key that already exists in the tree this + * function will simply overwrite the old value. If the structures you are + * storing are allocated in a wmem pool this is not a problem as they will still + * be freed with the pool. If you are managing them manually however, you must + * either ensure the key is unique, or do a lookup before each insert. + */ WS_DLL_PUBLIC void wmem_tree_insert32(wmem_tree_t *tree, guint32 key, void *data); -/** Look up a node in the tree indexed by a guint32 integer value */ +/** Look up a node in the tree indexed by a guint32 integer value. If no node is + * found the function will return NULL. + */ WS_DLL_PUBLIC void * wmem_tree_lookup32(wmem_tree_t *tree, guint32 key); @@ -89,13 +111,18 @@ wmem_tree_lookup32_le(wmem_tree_t *tree, guint32 key); /** case insensitive strings as keys */ #define WMEM_TREE_STRING_NOCASE 0x00000001 -/** Insert a new value under a string key */ +/** Insert a new value under a string key. Like wmem_tree_insert32 but where the + * key is a null-terminated string instead of a guint32. You may pass + * WMEM_TREE_STRING_NOCASE to the flags argument in order to make it store the + * key in a case-insensitive way. */ WS_DLL_PUBLIC void wmem_tree_insert_string(wmem_tree_t *tree, const gchar* key, void *data, guint32 flags); -/** Lookup the value under a string key */ +/** Lookup the value under a string key, like wmem_tree_lookup32 but where the + * keye is a null-terminated string instead of a guint32. See + * wmem_tree_insert_string for an explanation of flags. */ WS_DLL_PUBLIC void * wmem_tree_lookup_string(wmem_tree_t* tree, const gchar* key, guint32 flags); @@ -107,15 +134,22 @@ typedef struct _wmem_tree_key_t { /** Insert a node indexed by a sequence of guint32 key values. * - * Note: all the "key" members of the "key" argument MUST be aligned on + * Takes as key an array of guint32 vectors of type wmem_tree_key_t. It will + * iterate through each key to search further down the tree until it reaches an + * element where length==0, indicating the end of the array. You MUST terminate + * the key array by {0, NULL} or this will crash. + * + * NOTE: length indicates the number of guint32 values in the vector, not the + * number of bytes. + * + * NOTE: all the "key" members of the "key" argument MUST be aligned on * 32-bit boundaries; otherwise, this code will crash on platforms such * as SPARC that require aligned pointers. * * If you use ...32_array() calls you MUST make sure that every single node * you add to a specific tree always has a key of exactly the same number of - * keylen words or things will most likely crash. Or at least that every single - * item that sits behind the same top level node always have exactly the same - * number of words. + * keylen words or it will crash. Or at least that every single item that sits + * behind the same top level node always has exactly the same number of words. * * One way to guarantee this is the way that NFS does this for the * nfs_name_snoop_known tree which holds filehandles for both v2 and v3. @@ -138,6 +172,7 @@ void wmem_tree_insert32_array(wmem_tree_t *tree, wmem_tree_key_t *key, void *data); /** Look up a node in the tree indexed by a sequence of guint32 integer values. + * See wmem_tree_insert32_array for details on the key. */ WS_DLL_PUBLIC void * @@ -147,21 +182,31 @@ wmem_tree_lookup32_array(wmem_tree_t *tree, wmem_tree_key_t *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. - * Note: The key returned will be "less" in key order. The usefullness + * + * NOTE: The key returned will be "less" in key order. The usefulness * of the returned node must be verified prior to use. + * + * See wmem_tree_insert32_array for details on the key. */ WS_DLL_PUBLIC void * wmem_tree_lookup32_array_le(wmem_tree_t *tree, wmem_tree_key_t *key); -/** traverse a tree. if the callback returns TRUE the traversal will end */ +/** Function type for processing one node of a tree during a traversal. Value is + * the value of the node, userdata is whatever was passed to the traversal + * function. If the function returns TRUE the traversal will end prematurely. + */ typedef gboolean (*wmem_foreach_func)(void *value, void *userdata); +/** Traverse the tree and call callback(value, userdata) for each value found. + * Returns TRUE if the traversal was ended prematurely by the callback. + */ WS_DLL_PUBLIC gboolean wmem_tree_foreach(wmem_tree_t* tree, wmem_foreach_func callback, void *user_data); +/** Prints the structure of the tree to stdout. Primarily for debugging. */ void wmem_print_tree(wmem_tree_t *tree); |