ucx/avl.h

Sun, 17 Sep 2017 17:56:02 +0200

author
Olaf Wintermann <olaf.wintermann@gmail.com>
date
Sun, 17 Sep 2017 17:56:02 +0200
changeset 309
8a474d2ad209
parent 255
bf19378aed58
child 314
8722a668fb2a
permissions
-rw-r--r--

adds option to dav get for downloading only the directory structure

this is an undocumented feature and may be replaced in the future

128
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1 /*
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
3 *
255
bf19378aed58 updates UCX to version 0.11
Mike Becker <universe@uap-core.de>
parents: 128
diff changeset
4 * Copyright 2016 Olaf Wintermann. All rights reserved.
128
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
5 *
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
6 * Redistribution and use in source and binary forms, with or without
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
7 * modification, are permitted provided that the following conditions are met:
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
8 *
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
9 * 1. Redistributions of source code must retain the above copyright
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
10 * notice, this list of conditions and the following disclaimer.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
11 *
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
12 * 2. Redistributions in binary form must reproduce the above copyright
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
13 * notice, this list of conditions and the following disclaimer in the
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
14 * documentation and/or other materials provided with the distribution.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
15 *
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
26 * POSSIBILITY OF SUCH DAMAGE.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
27 */
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
28
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
29
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
30 /**
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
31 * @file avl.h
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
32 *
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
33 * AVL tree implementation.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
34 *
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
35 * This binary search tree implementation allows average O(1) insertion and
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
36 * removal of elements (excluding binary search time).
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
37 *
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
38 * @author Mike Becker
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
39 * @author Olaf Wintermann
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
40 */
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
41
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
42 #ifndef UCX_AVL_H
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
43 #define UCX_AVL_H
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
44
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
45 #include "ucx.h"
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
46 #include "allocator.h"
255
bf19378aed58 updates UCX to version 0.11
Mike Becker <universe@uap-core.de>
parents: 128
diff changeset
47 #include <inttypes.h>
128
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
48
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
49 #ifdef __cplusplus
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
50 extern "C" {
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
51 #endif
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
52
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
53 /**
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
54 * UCX AVL Node type.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
55 *
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
56 * @see UcxAVLNode
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
57 */
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
58 typedef struct UcxAVLNode UcxAVLNode;
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
59
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
60 /**
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
61 * UCX AVL Node.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
62 */
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
63 struct UcxAVLNode {
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
64 /**
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
65 * The key for this node.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
66 */
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
67 intptr_t key;
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
68 /**
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
69 * Data contained by this node.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
70 */
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
71 void *value;
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
72 /**
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
73 * The height of this (sub)-tree.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
74 */
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
75 size_t height;
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
76 /**
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
77 * Parent node.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
78 */
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
79 UcxAVLNode *parent;
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
80 /**
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
81 * Root node of left subtree.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
82 */
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
83 UcxAVLNode *left;
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
84 /**
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
85 * Root node of right subtree.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
86 */
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
87 UcxAVLNode *right;
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
88 };
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
89
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
90 /**
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
91 * UCX AVL Tree.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
92 */
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
93 typedef struct {
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
94 /**
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
95 * The UcxAllocator that shall be used to manage the memory for node data.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
96 */
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
97 UcxAllocator *allocator;
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
98 /**
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
99 * Root node of the tree.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
100 */
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
101 UcxAVLNode *root;
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
102 /**
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
103 * Compare function that shall be used to compare the UcxAVLNode keys.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
104 * @see UcxAVLNode.key
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
105 */
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
106 cmp_func cmpfunc;
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
107 /**
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
108 * Custom user data.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
109 * This data will also be provided to the cmpfunc.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
110 */
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
111 void *userdata;
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
112 } UcxAVLTree;
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
113
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
114 /**
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
115 * Initializes a new UcxAVLTree with a default allocator.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
116 *
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
117 * @param cmpfunc the compare function that shall be used
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
118 * @return a new UcxAVLTree object
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
119 * @see ucx_avl_new_a()
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
120 */
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
121 UcxAVLTree *ucx_avl_new(cmp_func cmpfunc);
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
122
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
123 /**
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
124 * Initializes a new UcxAVLTree with the specified allocator.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
125 *
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
126 * The cmpfunc should be capable of comparing two keys within this AVL tree.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
127 * So if you want to use null terminated strings as keys, you could use the
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
128 * ucx_strcmp() function here.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
129 *
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
130 * @param cmpfunc the compare function that shall be used
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
131 * @param allocator the UcxAllocator that shall be used
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
132 * @return a new UcxAVLTree object
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
133 */
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
134 UcxAVLTree *ucx_avl_new_a(cmp_func cmpfunc, UcxAllocator *allocator);
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
135
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
136 /**
255
bf19378aed58 updates UCX to version 0.11
Mike Becker <universe@uap-core.de>
parents: 128
diff changeset
137 * Destroys a UcxAVLTree.
128
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
138 * @param tree the tree to destroy
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
139 */
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
140 void ucx_avl_free(UcxAVLTree *tree);
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
141
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
142 /**
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
143 * Macro for initializing a new UcxAVLTree with the default allocator and a
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
144 * ucx_ptrcmp() compare function.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
145 *
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
146 * @return a new default UcxAVLTree object
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
147 */
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
148 #define ucx_avl_default_new() ucx_avl_new_a(ucx_ptrcmp, ucx_default_allocator())
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
149
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
150 /**
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
151 * Gets the node from the tree, that is associated with the specified key.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
152 * @param tree the UcxAVLTree
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
153 * @param key the key
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
154 * @return the node (or <code>NULL</code>, if the key is not present)
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
155 */
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
156 UcxAVLNode *ucx_avl_get_node(UcxAVLTree *tree, intptr_t key);
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
157
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
158 /**
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
159 * Gets the value from the tree, that is associated with the specified key.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
160 * @param tree the UcxAVLTree
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
161 * @param key the key
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
162 * @return the value (or <code>NULL</code>, if the key is not present)
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
163 */
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
164 void *ucx_avl_get(UcxAVLTree *tree, intptr_t key);
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
165
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
166 /**
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
167 * Puts a key/value pair into the tree.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
168 *
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
169 * Attention: use this function only, if a possible old value does not need
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
170 * to be preserved.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
171 *
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
172 * @param tree the UcxAVLTree
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
173 * @param key the key
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
174 * @param value the new value
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
175 * @return zero, if and only if the operation succeeded
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
176 */
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
177 int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value);
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
178
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
179 /**
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
180 * Puts a key/value pair into the tree.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
181 *
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
182 * This is a secure function which saves the old value to the variable pointed
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
183 * at by oldvalue.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
184 *
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
185 * @param tree the UcxAVLTree
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
186 * @param key the key
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
187 * @param value the new value
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
188 * @param oldvalue optional: a pointer to the location where a possible old
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
189 * value shall be stored
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
190 * @return zero, if and only if the operation succeeded
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
191 */
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
192 int ucx_avl_put_s(UcxAVLTree *tree, intptr_t key, void *value, void **oldvalue);
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
193
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
194 /**
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
195 * Removes a node from the AVL tree.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
196 *
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
197 * Note: the specified node is logically removed. The tree implementation
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
198 * decides which memory area is freed. In most cases the here provided node
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
199 * is freed, so it's further use is generally undefined.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
200 *
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
201 * @param tree the UcxAVLTree
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
202 * @param node the node to remove
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
203 * @return zero, if and only if an element has been removed
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
204 */
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
205 int ucx_avl_remove_node(UcxAVLTree *tree, UcxAVLNode *node);
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
206
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
207 /**
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
208 * Removes an element from the AVL tree.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
209 *
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
210 * @param tree the UcxAVLTree
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
211 * @param key the key
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
212 * @return zero, if and only if an element has been removed
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
213 */
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
214 int ucx_avl_remove(UcxAVLTree *tree, intptr_t key);
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
215
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
216 /**
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
217 * Removes an element from the AVL tree.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
218 *
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
219 * This is a secure function which saves the old key and value data from node
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
220 * to the variables at the location of oldkey and oldvalue (if specified), so
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
221 * they can be freed afterwards (if necessary).
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
222 *
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
223 * Note: the returned key in oldkey is possibly not the same as the provided
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
224 * key for the lookup (in terms of memory location).
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
225 *
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
226 * @param tree the UcxAVLTree
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
227 * @param key the key of the element to remove
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
228 * @param oldkey optional: a pointer to the location where the old key shall be
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
229 * stored
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
230 * @param oldvalue optional: a pointer to the location where the old value
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
231 * shall be stored
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
232 * @return zero, if and only if an element has been removed
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
233 */
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
234 int ucx_avl_remove_s(UcxAVLTree *tree, intptr_t key,
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
235 intptr_t *oldkey, void **oldvalue);
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
236
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
237 /**
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
238 * Counts the nodes in the specified UcxAVLTree.
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
239 * @param tree the AVL tree
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
240 * @return the node count
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
241 */
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
242 size_t ucx_avl_count(UcxAVLTree *tree);
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
243
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
244 #ifdef __cplusplus
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
245 }
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
246 #endif
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
247
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
248 #endif /* UCX_AVL_H */
649eb328674a implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
249

mercurial