1 /* 2 * 3 * Copyright 2015 gRPC authors. 4 * 5 * Licensed under the Apache License, Version 2.0 (the "License"); 6 * you may not use this file except in compliance with the License. 7 * You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 * 17 */ 18 19 #ifndef GRPC_CORE_LIB_AVL_AVL_H 20 #define GRPC_CORE_LIB_AVL_AVL_H 21 22 #include <grpc/support/port_platform.h> 23 24 #include <grpc/support/sync.h> 25 26 /** internal node of an AVL tree */ 27 typedef struct grpc_avl_node { 28 gpr_refcount refs; 29 void* key; 30 void* value; 31 struct grpc_avl_node* left; 32 struct grpc_avl_node* right; 33 long height; 34 } grpc_avl_node; 35 36 /** vtable for the AVL tree 37 * The optional user_data is propagated from the top level grpc_avl_XXX API. 38 * From the same API call, multiple vtable functions may be called multiple 39 * times. 40 */ 41 typedef struct grpc_avl_vtable { 42 /** destroy a key */ 43 void (*destroy_key)(void* key, void* user_data); 44 /** copy a key, returning new value */ 45 void* (*copy_key)(void* key, void* user_data); 46 /** compare key1, key2; return <0 if key1 < key2, 47 >0 if key1 > key2, 0 if key1 == key2 */ 48 long (*compare_keys)(void* key1, void* key2, void* user_data); 49 /** destroy a value */ 50 void (*destroy_value)(void* value, void* user_data); 51 /** copy a value */ 52 void* (*copy_value)(void* value, void* user_data); 53 } grpc_avl_vtable; 54 55 /** "pointer" to an AVL tree - this is a reference 56 counted object - use grpc_avl_ref to add a reference, 57 grpc_avl_unref when done with a reference */ 58 typedef struct grpc_avl { 59 const grpc_avl_vtable* vtable; 60 grpc_avl_node* root; 61 } grpc_avl; 62 63 /** Create an immutable AVL tree. */ 64 grpc_avl grpc_avl_create(const grpc_avl_vtable* vtable); 65 /** Add a reference to an existing tree - returns 66 the tree as a convenience. The optional user_data will be passed to vtable 67 functions. */ 68 grpc_avl grpc_avl_ref(grpc_avl avl, void* user_data); 69 /** Remove a reference to a tree - destroying it if there 70 are no references left. The optional user_data will be passed to vtable 71 functions. */ 72 void grpc_avl_unref(grpc_avl avl, void* user_data); 73 /** Return a new tree with (key, value) added to avl. 74 implicitly unrefs avl to allow easy chaining. 75 if key exists in avl, the new tree's key entry updated 76 (i.e. a duplicate is not created). The optional user_data will be passed to 77 vtable functions. */ 78 grpc_avl grpc_avl_add(grpc_avl avl, void* key, void* value, void* user_data); 79 /** Return a new tree with key deleted 80 implicitly unrefs avl to allow easy chaining. The optional user_data will be 81 passed to vtable functions. */ 82 grpc_avl grpc_avl_remove(grpc_avl avl, void* key, void* user_data); 83 /** Lookup key, and return the associated value. 84 Does not mutate avl. 85 Returns NULL if key is not found. The optional user_data will be passed to 86 vtable functions.*/ 87 void* grpc_avl_get(grpc_avl avl, void* key, void* user_data); 88 /** Return 1 if avl contains key, 0 otherwise; if it has the key, sets *value to 89 its value. The optional user_data will be passed to vtable functions. */ 90 int grpc_avl_maybe_get(grpc_avl avl, void* key, void** value, void* user_data); 91 /** Return 1 if avl is empty, 0 otherwise */ 92 int grpc_avl_is_empty(grpc_avl avl); 93 94 #endif /* GRPC_CORE_LIB_AVL_AVL_H */ 95