diff options
Diffstat (limited to 'epan/wmem')
-rw-r--r-- | epan/wmem/wmem_splay.c | 110 | ||||
-rw-r--r-- | epan/wmem/wmem_splay.h | 25 |
2 files changed, 73 insertions, 62 deletions
diff --git a/epan/wmem/wmem_splay.c b/epan/wmem/wmem_splay.c index 59d035b84a..e6ae05ad9f 100644 --- a/epan/wmem/wmem_splay.c +++ b/epan/wmem/wmem_splay.c @@ -182,59 +182,59 @@ wmem_splay_pred_succ(wmem_splay_t *tree, const void *key, } } -#define TRAVERSE(CUR, NXT) \ -do { \ - if ((*CUR) == NULL) { \ - return (CUR); \ - } \ - cmp = COMPARE(key, (*CUR)->key); \ - if (cmp == 0) { \ - return (CUR); \ - } \ - else if (cmp < 0) { \ - (NXT) = &((*CUR)->left); \ - } \ - else { \ - (NXT) = &((*CUR)->right); \ - } \ +#define TRAVERSE(CUR, NXT, KEY) \ +do { \ + if ((*CUR) == NULL) { \ + return (CUR); \ + } \ + cmp = COMPARE((KEY), (*CUR)->key); \ + if (cmp == 0) { \ + return (CUR); \ + } \ + else if (cmp < 0) { \ + (NXT) = &((*CUR)->left); \ + } \ + else { \ + (NXT) = &((*CUR)->right); \ + } \ } while (0) -#define ZIGZIG(CHILD) \ -do { \ - tmp = *p; \ - *p = tmp->CHILD; \ - tmp->CHILD = *gp; \ - *gp = tmp; \ - cmp = COMPARE(key, (*cur)->key); \ - if (cmp == 0) { \ - return cur; \ - } \ - else if (cmp < 0) { \ - gp = &((*cur)->left); \ - } \ - else { \ - gp = &((*cur)->right); \ - } \ +#define ZIGZIG(CHILD, KEY) \ +do { \ + tmp = *p; \ + *p = tmp->CHILD; \ + tmp->CHILD = *gp; \ + *gp = tmp; \ + cmp = COMPARE((KEY), (*cur)->key); \ + if (cmp == 0) { \ + return cur; \ + } \ + else if (cmp < 0) { \ + gp = &((*cur)->left); \ + } \ + else { \ + gp = &((*cur)->right); \ + } \ } while (0) -#define ZIGZAG(LEFT, RIGHT) \ -do { \ - tmp = *cur; \ - *cur = tmp->LEFT; \ - tmp->LEFT = *p; \ - *p = tmp->RIGHT; \ - tmp->RIGHT = *gp; \ - *gp = tmp; \ - cmp = COMPARE(key, tmp->key); \ - if (cmp == 0) { \ - return gp; \ - } \ - else if (cmp < 0) { \ - gp = &(tmp->left->right); \ - } \ - else { \ - gp = &(tmp->right->left); \ - } \ +#define ZIGZAG(LEFT, RIGHT, KEY) \ +do { \ + tmp = *cur; \ + *cur = tmp->LEFT; \ + tmp->LEFT = *p; \ + *p = tmp->RIGHT; \ + tmp->RIGHT = *gp; \ + *gp = tmp; \ + cmp = COMPARE((KEY), tmp->key); \ + if (cmp == 0) { \ + return gp; \ + } \ + else if (cmp < 0) { \ + gp = &(tmp->left->right); \ + } \ + else { \ + gp = &(tmp->right->left); \ + } \ } while (0) static wmem_splay_node_t ** @@ -246,8 +246,8 @@ wmem_splay_splay(wmem_splay_t *tree, const void *key) gp = &(tree->root); while (TRUE) { - TRAVERSE(gp, p); - TRAVERSE(p, cur); + TRAVERSE(gp, p, key); + TRAVERSE(p, cur, key); if ((*cur) == NULL) { return cur; @@ -255,18 +255,18 @@ wmem_splay_splay(wmem_splay_t *tree, const void *key) if (p == &((*gp)->left)) { if (cur == &((*p)->left)) { - ZIGZIG(right); + ZIGZIG(right, key); } else { - ZIGZAG(left, right); + ZIGZAG(left, right, key); } } else { if (cur == &((*p)->right)) { - ZIGZIG(left); + ZIGZIG(left, key); } else { - ZIGZAG(right, left); + ZIGZAG(right, left, key); } } } diff --git a/epan/wmem/wmem_splay.h b/epan/wmem/wmem_splay.h index def86e9c2c..dd83bdd7ba 100644 --- a/epan/wmem/wmem_splay.h +++ b/epan/wmem/wmem_splay.h @@ -52,18 +52,21 @@ extern "C" { struct _wmem_splay_t; typedef struct _wmem_splay_t wmem_splay_t; -/* like strcmp: 0 means a==b, - * >0 means a>b - * <0 means a<b +/** A wmem_compare_func compares two keys in a tree, and must return: + * 0 if a==b + * >0 if a>b + * <0 if a<b + * It must be able to compare any two keys, and must form a total order on the + * space of keys (https://en.wikipedia.org/wiki/Total_order). For example, the + * builtin strcmp() function satisfies these requirements. */ typedef int (*wmem_compare_func)(const void *a, const void *b); /** Creates a tree with the given allocator scope. When the scope is emptied, * the tree is fully destroyed. The given comparison function is used to compare - * keys; it must provide a coherent ordering on the key-space for the tree to - * work sensibly. It is permitted to pass NULL for the comparison function, in - * which case the key pointer values will be compared directly (cast to - * integers). */ + * keys. It is permitted to pass NULL for the comparison function, in which case + * the key pointer values will be compared directly (cast to signed integers). + */ WS_DLL_PUBLIC wmem_splay_t * wmem_splay_new(wmem_allocator_t *allocator, wmem_compare_func cmp) @@ -112,6 +115,11 @@ wmem_splay_lookup_le(wmem_splay_t *tree, const void *key); * Value is a pointer to the structure you want to be able to retrieve by * searching for the same key later. * + * Unlike the old wmem_tree/emem_tree, inserting does *not* take a copy of + * whatever key is pointed to, it simply stores a pointer. As such, inserted + * keys cannot be on the stack and must instead last as long as the tree itself + * (keys used during lookups are not stored, and can be on the stack). + * * 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 @@ -130,6 +138,9 @@ gboolean wmem_splay_foreach(wmem_splay_t* tree, wmem_foreach_func callback, void *user_data); +/** @} + * @} */ + #ifdef __cplusplus } #endif /* __cplusplus */ |