diff options
Diffstat (limited to 'src/core/lib/support/avl.cc')
| -rw-r--r-- | src/core/lib/support/avl.cc | 107 |
1 files changed, 54 insertions, 53 deletions
diff --git a/src/core/lib/support/avl.cc b/src/core/lib/support/avl.cc index 0e28b24c98..4ba101b74a 100644 --- a/src/core/lib/support/avl.cc +++ b/src/core/lib/support/avl.cc @@ -25,22 +25,22 @@ #include <grpc/support/string_util.h> #include <grpc/support/useful.h> -gpr_avl gpr_avl_create(const gpr_avl_vtable *vtable) { +gpr_avl gpr_avl_create(const gpr_avl_vtable* vtable) { gpr_avl out; out.vtable = vtable; out.root = NULL; return out; } -static gpr_avl_node *ref_node(gpr_avl_node *node) { +static gpr_avl_node* ref_node(gpr_avl_node* node) { if (node) { gpr_ref(&node->refs); } return node; } -static void unref_node(const gpr_avl_vtable *vtable, gpr_avl_node *node, - void *user_data) { +static void unref_node(const gpr_avl_vtable* vtable, gpr_avl_node* node, + void* user_data) { if (node == NULL) { return; } @@ -53,17 +53,18 @@ static void unref_node(const gpr_avl_vtable *vtable, gpr_avl_node *node, } } -static long node_height(gpr_avl_node *node) { +static long node_height(gpr_avl_node* node) { return node == NULL ? 0 : node->height; } #ifndef NDEBUG -static long calculate_height(gpr_avl_node *node) { - return node == NULL ? 0 : 1 + GPR_MAX(calculate_height(node->left), - calculate_height(node->right)); +static long calculate_height(gpr_avl_node* node) { + return node == NULL ? 0 + : 1 + GPR_MAX(calculate_height(node->left), + calculate_height(node->right)); } -static gpr_avl_node *assert_invariants(gpr_avl_node *n) { +static gpr_avl_node* assert_invariants(gpr_avl_node* n) { if (n == NULL) return NULL; assert_invariants(n->left); assert_invariants(n->right); @@ -72,12 +73,12 @@ static gpr_avl_node *assert_invariants(gpr_avl_node *n) { return n; } #else -static gpr_avl_node *assert_invariants(gpr_avl_node *n) { return n; } +static gpr_avl_node* assert_invariants(gpr_avl_node* n) { return n; } #endif -gpr_avl_node *new_node(void *key, void *value, gpr_avl_node *left, - gpr_avl_node *right) { - gpr_avl_node *node = (gpr_avl_node *)gpr_malloc(sizeof(*node)); +gpr_avl_node* new_node(void* key, void* value, gpr_avl_node* left, + gpr_avl_node* right) { + gpr_avl_node* node = (gpr_avl_node*)gpr_malloc(sizeof(*node)); gpr_ref_init(&node->refs, 1); node->key = key; node->value = value; @@ -87,8 +88,8 @@ gpr_avl_node *new_node(void *key, void *value, gpr_avl_node *left, return node; } -static gpr_avl_node *get(const gpr_avl_vtable *vtable, gpr_avl_node *node, - void *key, void *user_data) { +static gpr_avl_node* get(const gpr_avl_vtable* vtable, gpr_avl_node* node, + void* key, void* user_data) { long cmp; if (node == NULL) { @@ -105,13 +106,13 @@ static gpr_avl_node *get(const gpr_avl_vtable *vtable, gpr_avl_node *node, } } -void *gpr_avl_get(gpr_avl avl, void *key, void *user_data) { - gpr_avl_node *node = get(avl.vtable, avl.root, key, user_data); +void* gpr_avl_get(gpr_avl avl, void* key, void* user_data) { + gpr_avl_node* node = get(avl.vtable, avl.root, key, user_data); return node ? node->value : NULL; } -int gpr_avl_maybe_get(gpr_avl avl, void *key, void **value, void *user_data) { - gpr_avl_node *node = get(avl.vtable, avl.root, key, user_data); +int gpr_avl_maybe_get(gpr_avl avl, void* key, void** value, void* user_data) { + gpr_avl_node* node = get(avl.vtable, avl.root, key, user_data); if (node != NULL) { *value = node->value; return 1; @@ -119,10 +120,10 @@ int gpr_avl_maybe_get(gpr_avl avl, void *key, void **value, void *user_data) { return 0; } -static gpr_avl_node *rotate_left(const gpr_avl_vtable *vtable, void *key, - void *value, gpr_avl_node *left, - gpr_avl_node *right, void *user_data) { - gpr_avl_node *n = new_node(vtable->copy_key(right->key, user_data), +static gpr_avl_node* rotate_left(const gpr_avl_vtable* vtable, void* key, + void* value, gpr_avl_node* left, + gpr_avl_node* right, void* user_data) { + gpr_avl_node* n = new_node(vtable->copy_key(right->key, user_data), vtable->copy_value(right->value, user_data), new_node(key, value, left, ref_node(right->left)), ref_node(right->right)); @@ -130,10 +131,10 @@ static gpr_avl_node *rotate_left(const gpr_avl_vtable *vtable, void *key, return n; } -static gpr_avl_node *rotate_right(const gpr_avl_vtable *vtable, void *key, - void *value, gpr_avl_node *left, - gpr_avl_node *right, void *user_data) { - gpr_avl_node *n = +static gpr_avl_node* rotate_right(const gpr_avl_vtable* vtable, void* key, + void* value, gpr_avl_node* left, + gpr_avl_node* right, void* user_data) { + gpr_avl_node* n = new_node(vtable->copy_key(left->key, user_data), vtable->copy_value(left->value, user_data), ref_node(left->left), new_node(key, value, ref_node(left->right), right)); @@ -141,11 +142,11 @@ static gpr_avl_node *rotate_right(const gpr_avl_vtable *vtable, void *key, return n; } -static gpr_avl_node *rotate_left_right(const gpr_avl_vtable *vtable, void *key, - void *value, gpr_avl_node *left, - gpr_avl_node *right, void *user_data) { +static gpr_avl_node* rotate_left_right(const gpr_avl_vtable* vtable, void* key, + void* value, gpr_avl_node* left, + gpr_avl_node* right, void* user_data) { /* rotate_right(..., rotate_left(left), right) */ - gpr_avl_node *n = + gpr_avl_node* n = new_node(vtable->copy_key(left->right->key, user_data), vtable->copy_value(left->right->value, user_data), new_node(vtable->copy_key(left->key, user_data), @@ -156,11 +157,11 @@ static gpr_avl_node *rotate_left_right(const gpr_avl_vtable *vtable, void *key, return n; } -static gpr_avl_node *rotate_right_left(const gpr_avl_vtable *vtable, void *key, - void *value, gpr_avl_node *left, - gpr_avl_node *right, void *user_data) { +static gpr_avl_node* rotate_right_left(const gpr_avl_vtable* vtable, void* key, + void* value, gpr_avl_node* left, + gpr_avl_node* right, void* user_data) { /* rotate_left(..., left, rotate_right(right)) */ - gpr_avl_node *n = + gpr_avl_node* n = new_node(vtable->copy_key(right->left->key, user_data), vtable->copy_value(right->left->value, user_data), new_node(key, value, left, ref_node(right->left->left)), @@ -171,9 +172,9 @@ static gpr_avl_node *rotate_right_left(const gpr_avl_vtable *vtable, void *key, return n; } -static gpr_avl_node *rebalance(const gpr_avl_vtable *vtable, void *key, - void *value, gpr_avl_node *left, - gpr_avl_node *right, void *user_data) { +static gpr_avl_node* rebalance(const gpr_avl_vtable* vtable, void* key, + void* value, gpr_avl_node* left, + gpr_avl_node* right, void* user_data) { switch (node_height(left) - node_height(right)) { case 2: if (node_height(left->left) - node_height(left->right) == -1) { @@ -196,8 +197,8 @@ static gpr_avl_node *rebalance(const gpr_avl_vtable *vtable, void *key, } } -static gpr_avl_node *add_key(const gpr_avl_vtable *vtable, gpr_avl_node *node, - void *key, void *value, void *user_data) { +static gpr_avl_node* add_key(const gpr_avl_vtable* vtable, gpr_avl_node* node, + void* key, void* value, void* user_data) { long cmp; if (node == NULL) { return new_node(key, value, NULL, NULL); @@ -218,31 +219,31 @@ static gpr_avl_node *add_key(const gpr_avl_vtable *vtable, gpr_avl_node *node, } } -gpr_avl gpr_avl_add(gpr_avl avl, void *key, void *value, void *user_data) { - gpr_avl_node *old_root = avl.root; +gpr_avl gpr_avl_add(gpr_avl avl, void* key, void* value, void* user_data) { + gpr_avl_node* old_root = avl.root; avl.root = add_key(avl.vtable, avl.root, key, value, user_data); assert_invariants(avl.root); unref_node(avl.vtable, old_root, user_data); return avl; } -static gpr_avl_node *in_order_head(gpr_avl_node *node) { +static gpr_avl_node* in_order_head(gpr_avl_node* node) { while (node->left != NULL) { node = node->left; } return node; } -static gpr_avl_node *in_order_tail(gpr_avl_node *node) { +static gpr_avl_node* in_order_tail(gpr_avl_node* node) { while (node->right != NULL) { node = node->right; } return node; } -static gpr_avl_node *remove_key(const gpr_avl_vtable *vtable, - gpr_avl_node *node, void *key, - void *user_data) { +static gpr_avl_node* remove_key(const gpr_avl_vtable* vtable, + gpr_avl_node* node, void* key, + void* user_data) { long cmp; if (node == NULL) { return NULL; @@ -254,13 +255,13 @@ static gpr_avl_node *remove_key(const gpr_avl_vtable *vtable, } else if (node->right == NULL) { return ref_node(node->left); } else if (node->left->height < node->right->height) { - gpr_avl_node *h = in_order_head(node->right); + gpr_avl_node* h = in_order_head(node->right); return rebalance( vtable, vtable->copy_key(h->key, user_data), vtable->copy_value(h->value, user_data), ref_node(node->left), remove_key(vtable, node->right, h->key, user_data), user_data); } else { - gpr_avl_node *h = in_order_tail(node->left); + gpr_avl_node* h = in_order_tail(node->left); return rebalance(vtable, vtable->copy_key(h->key, user_data), vtable->copy_value(h->value, user_data), remove_key(vtable, node->left, h->key, user_data), @@ -279,20 +280,20 @@ static gpr_avl_node *remove_key(const gpr_avl_vtable *vtable, } } -gpr_avl gpr_avl_remove(gpr_avl avl, void *key, void *user_data) { - gpr_avl_node *old_root = avl.root; +gpr_avl gpr_avl_remove(gpr_avl avl, void* key, void* user_data) { + gpr_avl_node* old_root = avl.root; avl.root = remove_key(avl.vtable, avl.root, key, user_data); assert_invariants(avl.root); unref_node(avl.vtable, old_root, user_data); return avl; } -gpr_avl gpr_avl_ref(gpr_avl avl, void *user_data) { +gpr_avl gpr_avl_ref(gpr_avl avl, void* user_data) { ref_node(avl.root); return avl; } -void gpr_avl_unref(gpr_avl avl, void *user_data) { +void gpr_avl_unref(gpr_avl avl, void* user_data) { unref_node(avl.vtable, avl.root, user_data); } |