From 8f4fbb1c550c99e25f42ceafec3af92b34279db5 Mon Sep 17 00:00:00 2001 From: Vijay Pai Date: Thu, 8 Feb 2018 10:04:08 -0800 Subject: Move avl to its own directory and rename it to grpc_avl --- src/core/lib/avl/avl.h | 92 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 92 insertions(+) create mode 100644 src/core/lib/avl/avl.h (limited to 'src/core/lib/avl/avl.h') diff --git a/src/core/lib/avl/avl.h b/src/core/lib/avl/avl.h new file mode 100644 index 0000000000..03d9bfd7bd --- /dev/null +++ b/src/core/lib/avl/avl.h @@ -0,0 +1,92 @@ +/* + * + * Copyright 2015 gRPC authors. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + * + */ + +#ifndef GRPC_CORE_LIB_GRPC_AVL_H +#define GRPC_CORE_LIB_GRPC_AVL_H + +#include + +/** internal node of an AVL tree */ +typedef struct grpc_avl_node { + gpr_refcount refs; + void* key; + void* value; + struct grpc_avl_node* left; + struct grpc_avl_node* right; + long height; +} grpc_avl_node; + +/** vtable for the AVL tree + * The optional user_data is propagated from the top level grpc_avl_XXX API. + * From the same API call, multiple vtable functions may be called multiple + * times. + */ +typedef struct grpc_avl_vtable { + /** destroy a key */ + void (*destroy_key)(void* key, void* user_data); + /** copy a key, returning new value */ + void* (*copy_key)(void* key, void* user_data); + /** compare key1, key2; return <0 if key1 < key2, + >0 if key1 > key2, 0 if key1 == key2 */ + long (*compare_keys)(void* key1, void* key2, void* user_data); + /** destroy a value */ + void (*destroy_value)(void* value, void* user_data); + /** copy a value */ + void* (*copy_value)(void* value, void* user_data); +} grpc_avl_vtable; + +/** "pointer" to an AVL tree - this is a reference + counted object - use grpc_avl_ref to add a reference, + grpc_avl_unref when done with a reference */ +typedef struct grpc_avl { + const grpc_avl_vtable* vtable; + grpc_avl_node* root; +} grpc_avl; + +/** Create an immutable AVL tree. */ +grpc_avl grpc_avl_create(const grpc_avl_vtable* vtable); +/** Add a reference to an existing tree - returns + the tree as a convenience. The optional user_data will be passed to vtable + functions. */ +grpc_avl grpc_avl_ref(grpc_avl avl, void* user_data); +/** Remove a reference to a tree - destroying it if there + are no references left. The optional user_data will be passed to vtable + functions. */ +void grpc_avl_unref(grpc_avl avl, void* user_data); +/** Return a new tree with (key, value) added to avl. + implicitly unrefs avl to allow easy chaining. + if key exists in avl, the new tree's key entry updated + (i.e. a duplicate is not created). The optional user_data will be passed to + vtable functions. */ +grpc_avl grpc_avl_add(grpc_avl avl, void* key, void* value, void* user_data); +/** Return a new tree with key deleted + implicitly unrefs avl to allow easy chaining. The optional user_data will be + passed to vtable functions. */ +grpc_avl grpc_avl_remove(grpc_avl avl, void* key, void* user_data); +/** Lookup key, and return the associated value. + Does not mutate avl. + Returns NULL if key is not found. The optional user_data will be passed to + vtable functions.*/ +void* grpc_avl_get(grpc_avl avl, void* key, void* user_data); +/** Return 1 if avl contains key, 0 otherwise; if it has the key, sets *value to + its value. The optional user_data will be passed to vtable functions. */ +int grpc_avl_maybe_get(grpc_avl avl, void* key, void** value, void* user_data); +/** Return 1 if avl is empty, 0 otherwise */ +int grpc_avl_is_empty(grpc_avl avl); + +#endif /* GRPC_CORE_LIB_GRPC_AVL_H */ -- cgit v1.2.3 From 804f339338695879b7529c6d7f1d46c6bfdec19d Mon Sep 17 00:00:00 2001 From: Vijay Pai Date: Thu, 8 Feb 2018 12:08:45 -0800 Subject: Fix header guard --- src/core/lib/avl/avl.h | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'src/core/lib/avl/avl.h') diff --git a/src/core/lib/avl/avl.h b/src/core/lib/avl/avl.h index 03d9bfd7bd..df5d2e89ec 100644 --- a/src/core/lib/avl/avl.h +++ b/src/core/lib/avl/avl.h @@ -16,8 +16,8 @@ * */ -#ifndef GRPC_CORE_LIB_GRPC_AVL_H -#define GRPC_CORE_LIB_GRPC_AVL_H +#ifndef GRPC_CORE_LIB_AVL_AVL_H +#define GRPC_CORE_LIB_AVL_AVL_H #include @@ -89,4 +89,4 @@ int grpc_avl_maybe_get(grpc_avl avl, void* key, void** value, void* user_data); /** Return 1 if avl is empty, 0 otherwise */ int grpc_avl_is_empty(grpc_avl avl); -#endif /* GRPC_CORE_LIB_GRPC_AVL_H */ +#endif /* GRPC_CORE_LIB_AVL_AVL_H */ -- cgit v1.2.3