id = wmem_strdup(wmem_packet_scope(), attr_id->value);
if (!pinfo->fd->flags.visited) {
- xmpp_trans = (xmpp_transaction_t *)wmem_tree_lookup_string(xmpp_info->req_resp, id, EMEM_TREE_STRING_NOCASE);
+ xmpp_trans = (xmpp_transaction_t *)wmem_tree_lookup_string(xmpp_info->req_resp, id, WMEM_TREE_STRING_NOCASE);
if (xmpp_trans) {
xmpp_trans->resp_frame = pinfo->fd->num;
xmpp_trans->req_frame = pinfo->fd->num;
xmpp_trans->resp_frame = 0;
- wmem_tree_insert_string(xmpp_info->req_resp, se_id, (void *) xmpp_trans, EMEM_TREE_STRING_NOCASE);
+ wmem_tree_insert_string(xmpp_info->req_resp, se_id, (void *) xmpp_trans, WMEM_TREE_STRING_NOCASE);
}
} else {
- wmem_tree_lookup_string(xmpp_info->req_resp, id, EMEM_TREE_STRING_NOCASE);
+ wmem_tree_lookup_string(xmpp_info->req_resp, id, WMEM_TREE_STRING_NOCASE);
}
}
se_id = wmem_strdup(wmem_file_scope(), attr_id->value);
se_sid = wmem_strdup(wmem_file_scope(), attr_sid->value);
- wmem_tree_insert_string(xmpp_info->jingle_sessions, se_id, (void*) se_sid, EMEM_TREE_STRING_NOCASE);
+ wmem_tree_insert_string(xmpp_info->jingle_sessions, se_id, (void*) se_sid, WMEM_TREE_STRING_NOCASE);
}
}
se_id = wmem_strdup(wmem_file_scope(), attr_id->value);
se_sid = wmem_strdup(wmem_file_scope(), attr_sid->value);
- wmem_tree_insert_string(xmpp_info->gtalk_sessions, se_id, (void*) se_sid, EMEM_TREE_STRING_NOCASE);
+ wmem_tree_insert_string(xmpp_info->gtalk_sessions, se_id, (void*) se_sid, WMEM_TREE_STRING_NOCASE);
}
}
{
se_id = wmem_strdup(wmem_file_scope(), attr_id->value);
se_sid = wmem_strdup(wmem_file_scope(), attr_sid->value);
- wmem_tree_insert_string(xmpp_info->ibb_sessions, se_id, (void*) se_sid, EMEM_TREE_STRING_NOCASE);
+ wmem_tree_insert_string(xmpp_info->ibb_sessions, se_id, (void*) se_sid, WMEM_TREE_STRING_NOCASE);
}
}
}
return NULL;
}
-void *
-emem_tree_lookup32_le(emem_tree_t *se_tree, guint32 key)
-{
- emem_tree_node_t *node;
-
- node=se_tree->tree;
-
- if(!node){
- return NULL;
- }
-
-
- while(node){
- if(key==node->key32){
- return node->data;
- }
- if(key<node->key32){
- if(node->left){
- node=node->left;
- continue;
- } else {
- break;
- }
- }
- if(key>node->key32){
- if(node->right){
- node=node->right;
- continue;
- } else {
- break;
- }
- }
- }
-
-
- if(!node){
- return NULL;
- }
-
- /* If we are still at the root of the tree this means that this node
- * is either smaller than the search key and then we return this
- * node or else there is no smaller key available and then
- * we return NULL.
- */
- if(!node->parent){
- if(key>node->key32){
- return node->data;
- } else {
- return NULL;
- }
- }
-
- if(node->parent->left==node){
- /* left child */
-
- if(key>node->key32){
- /* if this is a left child and its key is smaller than
- * the search key, then this is the node we want.
- */
- return node->data;
- } else {
- /* if this is a left child and its key is bigger than
- * the search key, we have to check if any
- * of our ancestors are smaller than the search key.
- */
- while(node){
- if(key>node->key32){
- return node->data;
- }
- node=node->parent;
- }
- return NULL;
- }
- } else {
- /* right child */
-
- if(node->key32<key){
- /* if this is the right child and its key is smaller
- * than the search key then this is the one we want.
- */
- return node->data;
- } else {
- /* if this is the right child and its key is larger
- * than the search key then our parent is the one we
- * want.
- */
- return node->parent->data;
- }
- }
-
-}
-
-
static inline emem_tree_node_t *
emem_tree_parent(emem_tree_node_t *node)
{
}
}
-static void *
-lookup_or_insert32(emem_tree_t *se_tree, guint32 key, void*(*func)(void*),void* ud, int is_subtree)
-{
- emem_tree_node_t *node;
-
- node=se_tree->tree;
-
- /* is this the first node ?*/
- if(!node){
- node=(emem_tree_node_t *)se_tree->malloc(sizeof(emem_tree_node_t));
- switch(se_tree->type){
- case EMEM_TREE_TYPE_RED_BLACK:
- node->u.rb_color=EMEM_TREE_RB_COLOR_BLACK;
- break;
- }
- node->parent=NULL;
- node->left=NULL;
- node->right=NULL;
- node->key32=key;
- node->data= func(ud);
- node->u.is_subtree = is_subtree;
- se_tree->tree=node;
- return node->data;
- }
-
- /* it was not the new root so walk the tree until we find where to
- * insert this new leaf.
- */
- while(1){
- /* this node already exists, so just return the data pointer*/
- if(key==node->key32){
- return node->data;
- }
- if(key<node->key32) {
- if(!node->left){
- /* new node to the left */
- emem_tree_node_t *new_node;
- new_node=(emem_tree_node_t *)se_tree->malloc(sizeof(emem_tree_node_t));
- node->left=new_node;
- new_node->parent=node;
- new_node->left=NULL;
- new_node->right=NULL;
- new_node->key32=key;
- new_node->data= func(ud);
- new_node->u.is_subtree = is_subtree;
- node=new_node;
- break;
- }
- node=node->left;
- continue;
- }
- if(key>node->key32) {
- if(!node->right){
- /* new node to the right */
- emem_tree_node_t *new_node;
- new_node=(emem_tree_node_t *)se_tree->malloc(sizeof(emem_tree_node_t));
- node->right=new_node;
- new_node->parent=node;
- new_node->left=NULL;
- new_node->right=NULL;
- new_node->key32=key;
- new_node->data= func(ud);
- new_node->u.is_subtree = is_subtree;
- node=new_node;
- break;
- }
- node=node->right;
- continue;
- }
- }
-
- /* node will now point to the newly created node */
- switch(se_tree->type){
- case EMEM_TREE_TYPE_RED_BLACK:
- node->u.rb_color=EMEM_TREE_RB_COLOR_RED;
- rb_insert_case1(se_tree, node);
- break;
- }
-
- return node->data;
-}
-
-/* create another (sub)tree using the same memory allocation scope
- * as the parent tree.
- */
-static emem_tree_t *
-emem_tree_create_subtree(emem_tree_t *parent_tree, const char *name)
-{
- emem_tree_t *tree_list;
-
- tree_list=(emem_tree_t *)parent_tree->malloc(sizeof(emem_tree_t));
- tree_list->next=NULL;
- tree_list->type=parent_tree->type;
- tree_list->tree=NULL;
- tree_list->name=name;
- tree_list->malloc=parent_tree->malloc;
-
- return tree_list;
-}
-
-static void *
-create_sub_tree(void* d)
-{
- emem_tree_t *se_tree = (emem_tree_t *)d;
- return emem_tree_create_subtree(se_tree, "subtree");
-}
-
-/* insert a new node in the tree. if this node matches an already existing node
- * then just replace the data for that node */
-
-void
-emem_tree_insert32_array(emem_tree_t *se_tree, emem_tree_key_t *key, void *data)
-{
- emem_tree_t *insert_tree = NULL;
- emem_tree_key_t *cur_key;
- guint32 i, insert_key32 = 0;
-
- if(!se_tree || !key) return;
-
- for (cur_key = key; cur_key->length > 0; cur_key++) {
- if(cur_key->length > 100) {
- DISSECTOR_ASSERT_NOT_REACHED();
- }
-
- for (i = 0; i < cur_key->length; i++) {
- /* Insert using the previous key32 */
- if (!insert_tree) {
- insert_tree = se_tree;
- } else {
- insert_tree = (emem_tree_t *)lookup_or_insert32(insert_tree, insert_key32, create_sub_tree, se_tree, EMEM_TREE_NODE_IS_SUBTREE);
- }
- insert_key32 = cur_key->key[i];
- }
- }
-
- if(!insert_tree) {
- /* We didn't get a valid key. Should we return NULL instead? */
- DISSECTOR_ASSERT_NOT_REACHED();
- }
-
- emem_tree_insert32(insert_tree, insert_key32, data);
-
-}
-
-void *
-emem_tree_lookup32_array(emem_tree_t *se_tree, emem_tree_key_t *key)
-{
- emem_tree_t *lookup_tree = NULL;
- emem_tree_key_t *cur_key;
- guint32 i, lookup_key32 = 0;
-
- if(!se_tree || !key) return NULL; /* prevent searching on NULL pointer */
-
- for (cur_key = key; cur_key->length > 0; cur_key++) {
- if(cur_key->length > 100) {
- DISSECTOR_ASSERT_NOT_REACHED();
- }
-
- for (i = 0; i < cur_key->length; i++) {
- /* Lookup using the previous key32 */
- if (!lookup_tree) {
- lookup_tree = se_tree;
- } else {
- lookup_tree = (emem_tree_t *)emem_tree_lookup32(lookup_tree, lookup_key32);
- if (!lookup_tree) {
- return NULL;
- }
- }
- lookup_key32 = cur_key->key[i];
- }
- }
-
- if(!lookup_tree) {
- /* We didn't get a valid key. Should we return NULL instead? */
- DISSECTOR_ASSERT_NOT_REACHED();
- }
-
- return emem_tree_lookup32(lookup_tree, lookup_key32);
-}
-
-void *
-emem_tree_lookup32_array_le(emem_tree_t *se_tree, emem_tree_key_t *key)
-{
- emem_tree_t *lookup_tree = NULL;
- emem_tree_key_t *cur_key;
- guint32 i, lookup_key32 = 0;
-
- if(!se_tree || !key) return NULL; /* prevent searching on NULL pointer */
-
- for (cur_key = key; cur_key->length > 0; cur_key++) {
- if(cur_key->length > 100) {
- DISSECTOR_ASSERT_NOT_REACHED();
- }
-
- for (i = 0; i < cur_key->length; i++) {
- /* Lookup using the previous key32 */
- if (!lookup_tree) {
- lookup_tree = se_tree;
- } else {
- lookup_tree = (emem_tree_t *)emem_tree_lookup32_le(lookup_tree, lookup_key32);
- if (!lookup_tree) {
- return NULL;
- }
- }
- lookup_key32 = cur_key->key[i];
- }
- }
-
- if(!lookup_tree) {
- /* We didn't get a valid key. Should we return NULL instead? */
- DISSECTOR_ASSERT_NOT_REACHED();
- }
-
- return emem_tree_lookup32_le(lookup_tree, lookup_key32);
-
-}
-
-/* Strings are stored as an array of uint32 containing the string characters
- with 4 characters in each uint32.
- The first byte of the string is stored as the most significant byte.
- If the string is not a multiple of 4 characters in length the last
- uint32 containing the string bytes are padded with 0 bytes.
- After the uint32's containing the string, there is one final terminator
- uint32 with the value 0x00000001
-*/
-void
-emem_tree_insert_string(emem_tree_t* se_tree, const gchar* k, void* v, guint32 flags)
-{
- emem_tree_key_t key[2];
- guint32 *aligned=NULL;
- guint32 len = (guint32) strlen(k);
- guint32 divx = (len+3)/4+1;
- guint32 i;
- guint32 tmp;
-
- aligned = (guint32 *)g_malloc(divx * sizeof (guint32));
-
- /* pack the bytes one one by one into guint32s */
- tmp = 0;
- for (i = 0;i < len;i++) {
- unsigned char ch;
-
- ch = (unsigned char)k[i];
- if (flags & EMEM_TREE_STRING_NOCASE) {
- if(isupper(ch)) {
- ch = tolower(ch);
- }
- }
- tmp <<= 8;
- tmp |= ch;
- if (i%4 == 3) {
- aligned[i/4] = tmp;
- tmp = 0;
- }
- }
- /* add required padding to the last uint32 */
- if (i%4 != 0) {
- while (i%4 != 0) {
- i++;
- tmp <<= 8;
- }
- aligned[i/4-1] = tmp;
- }
-
- /* add the terminator */
- aligned[divx-1] = 0x00000001;
-
- key[0].length = divx;
- key[0].key = aligned;
- key[1].length = 0;
- key[1].key = NULL;
-
-
- emem_tree_insert32_array(se_tree, key, v);
- g_free(aligned);
-}
-
-void *
-emem_tree_lookup_string(emem_tree_t* se_tree, const gchar* k, guint32 flags)
-{
- emem_tree_key_t key[2];
- guint32 *aligned=NULL;
- guint32 len = (guint) strlen(k);
- guint32 divx = (len+3)/4+1;
- guint32 i;
- guint32 tmp;
- void *ret;
-
- aligned = (guint32 *)g_malloc(divx * sizeof (guint32));
-
- /* pack the bytes one one by one into guint32s */
- tmp = 0;
- for (i = 0;i < len;i++) {
- unsigned char ch;
-
- ch = (unsigned char)k[i];
- if (flags & EMEM_TREE_STRING_NOCASE) {
- if(isupper(ch)) {
- ch = tolower(ch);
- }
- }
- tmp <<= 8;
- tmp |= ch;
- if (i%4 == 3) {
- aligned[i/4] = tmp;
- tmp = 0;
- }
- }
- /* add required padding to the last uint32 */
- if (i%4 != 0) {
- while (i%4 != 0) {
- i++;
- tmp <<= 8;
- }
- aligned[i/4-1] = tmp;
- }
-
- /* add the terminator */
- aligned[divx-1] = 0x00000001;
-
- key[0].length = divx;
- key[0].key = aligned;
- key[1].length = 0;
- key[1].key = NULL;
-
-
- ret = emem_tree_lookup32_array(se_tree, key);
- g_free(aligned);
- return ret;
-}
-
static gboolean
emem_tree_foreach_nodes(emem_tree_node_t* node, tree_foreach_func callback, void *user_data)
{
*/
#define se_tree_lookup32 emem_tree_lookup32
-/** se_tree_lookup32_le
- * Retrieve the data for the largest key that is less than or equal
- * to the search key.
- */
-#define se_tree_lookup32_le emem_tree_lookup32_le
-
-/** se_tree_insert32_array
- * Insert data into the tree and key it by a 32bit integer value
- */
-#define se_tree_insert32_array emem_tree_insert32_array
-
-/** se_tree_lookup32_array
- * Lookup data from the tree that is index by an array
- */
-#define se_tree_lookup32_array emem_tree_lookup32_array
-
-/** se_tree_lookup32_array_le
- * Retrieve the data for the largest key that is less than or equal
- * to the search key.
- */
-#define se_tree_lookup32_array_le emem_tree_lookup32_array_le
-
/* ******************************************************************
* Real tree functions
* ****************************************************************** */
WS_DLL_PUBLIC
void *emem_tree_lookup32(emem_tree_t *se_tree, guint32 key);
-/** This function will look up a node in the tree indexed by a guint32 integer
- * value.
- * 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.
- */
-WS_DLL_PUBLIC
-void *emem_tree_lookup32_le(emem_tree_t *se_tree, guint32 key);
-
typedef struct _emem_tree_key_t {
guint32 length; /**< length in guint32 words */
guint32 *key;
} emem_tree_key_t;
-/** This function is used to insert a node indexed by a sequence of guint32
- * key values.
- * The data pointer should be allocated by SE allocators so that the
- * data will be released at the same time as the tree itself is destroyed.
- *
- * 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.
- *
- * 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.
- * v2 filehandles are always 32 bytes (8 words) while v3 filehandles can have
- * any length (though 32 bytes are most common).
- * The NFS dissector handles this by providing a guint32 containing the length
- * as the very first item in this vector :
- *
- * emem_tree_key_t fhkey[3];
- *
- * fhlen=nns->fh_length;
- * fhkey[0].length=1;
- * fhkey[0].key=&fhlen;
- * fhkey[1].length=fhlen/4;
- * fhkey[1].key=nns->fh;
- * fhkey[2].length=0;
- */
-WS_DLL_PUBLIC
-void emem_tree_insert32_array(emem_tree_t *se_tree, emem_tree_key_t *key, void *data);
-
-/** This function will look up a node in the tree indexed by a sequence of
- * guint32 integer values.
- */
-WS_DLL_PUBLIC
-void *emem_tree_lookup32_array(emem_tree_t *se_tree, emem_tree_key_t *key);
-
-/** This function will look up a node in the tree indexed by a
- * multi-part tree value.
- * 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
- * of the returned node must be verified prior to use.
- */
-WS_DLL_PUBLIC
-void *emem_tree_lookup32_array_le(emem_tree_t *se_tree, emem_tree_key_t *key);
-
-/** case insensitive strings as keys */
-#define EMEM_TREE_STRING_NOCASE 0x00000001
-/** Insert a new value under a string key */
-WS_DLL_PUBLIC
-void emem_tree_insert_string(emem_tree_t* h, const gchar* k, void* v, guint32 flags);
-
-/** Lookup the value under a string key */
-WS_DLL_PUBLIC
-void* emem_tree_lookup_string(emem_tree_t* h, const gchar* k, guint32 flags);
-
-
/** traverse a tree. if the callback returns TRUE the traversal will end */
typedef gboolean (*tree_foreach_func)(void *value, void *userdata);
git.samba.org / metze / wireshark / wip.git / commitdiff