Rev 2499 | Rev 2503 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 2499 | Rev 2501 | ||
---|---|---|---|
Line 50... | Line 50... | ||
50 | */ |
50 | */ |
51 | 51 | ||
52 | #include <adt/avl.h> |
52 | #include <adt/avl.h> |
53 | #include <debug.h> |
53 | #include <debug.h> |
54 | 54 | ||
55 | - | ||
56 | #define LEFT 0 |
55 | #define LEFT 0 |
57 | #define RIGHT 1 |
56 | #define RIGHT 1 |
58 | 57 | ||
59 | - | ||
60 | /** Search for the first occurence of the given key in an AVL tree. |
58 | /** Search for the first occurence of the given key in an AVL tree. |
61 | * |
59 | * |
62 | * @param t AVL tree. |
60 | * @param t AVL tree. |
63 | * @param key Key to be searched. |
61 | * @param key Key to be searched. |
64 | * |
62 | * |
65 | * @return Pointer to a node or NULL if there is no such key. |
63 | * @return Pointer to a node or NULL if there is no such key. |
66 | */ |
64 | */ |
67 | avltree_node_t *avltree_search(avltree_t *t, uint64_t key) |
65 | avltree_node_t *avltree_search(avltree_t *t, avltree_key_t key) |
68 | { |
66 | { |
69 | avltree_node_t *p; |
67 | avltree_node_t *p; |
70 | 68 | ||
71 | /* |
69 | /* |
72 | * Iteratively descend to the leaf that can contain the searched key. |
70 | * Iteratively descend to the leaf that can contain the searched key. |
Line 118... | Line 116... | ||
118 | { |
116 | { |
119 | avltree_node_t *par; |
117 | avltree_node_t *par; |
120 | avltree_node_t *gpa; |
118 | avltree_node_t *gpa; |
121 | avltree_node_t *top; |
119 | avltree_node_t *top; |
122 | avltree_node_t **dpc; |
120 | avltree_node_t **dpc; |
123 | uint64_t key; |
121 | avltree_key_t key; |
124 | 122 | ||
125 | ASSERT(t); |
123 | ASSERT(t); |
126 | ASSERT(newnode); |
124 | ASSERT(newnode); |
127 | 125 | ||
128 | /* |
126 | /* |
Line 705... | Line 703... | ||
705 | avltree_delete(t, node); |
703 | avltree_delete(t, node); |
706 | 704 | ||
707 | return true; |
705 | return true; |
708 | } |
706 | } |
709 | 707 | ||
- | 708 | static void _avltree_walk(avltree_node_t *node, avltree_walker_t walker) |
|
- | 709 | { |
|
- | 710 | if (node->lft) |
|
- | 711 | _avltree_walk(node->lft, walker); |
|
- | 712 | walker(node); |
|
- | 713 | if (node->rgt) |
|
- | 714 | _avltree_walk(node->rgt, walker); |
|
- | 715 | } |
|
- | 716 | ||
- | 717 | /** Walk the AVL tree and apply the walker function on each visited node. |
|
- | 718 | * |
|
- | 719 | * @param t AVL tree to be walked. |
|
- | 720 | * @param walker Walker function that will be called on each visited |
|
- | 721 | * node. |
|
- | 722 | */ |
|
- | 723 | void avltree_walk(avltree_t *t, avltree_walker_t walker) |
|
- | 724 | { |
|
- | 725 | _avltree_walk(t->root, walker); |
|
- | 726 | } |
|
- | 727 | ||
710 | /** @} |
728 | /** @} |
711 | */ |
729 | */ |
712 | 730 |