1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
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_AVL_AVL_H
#define GRPC_CORE_LIB_AVL_AVL_H
#include <grpc/support/sync.h>
/** 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_AVL_AVL_H */
|
