Thu, 21 Dec 2017 19:48:27 +0100
davql: allow ANYWHERE keyword in SELECT statements
This may seem pointless, but users might want to be explicit about this and the grammar is more consistent.
This commit also adds some no-ops to the functions body of the SET parser, because some day the grammar might allow more clauses after the WHERE clause.
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 | * |
335
c1bc13faadaa
updates ucx to version 1.0
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
314
diff
changeset
|
4 | * Copyright 2017 Mike Becker, 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 | |
335
c1bc13faadaa
updates ucx to version 1.0
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
314
diff
changeset
|
29 | #include "ucx/avl.h" |
314
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
30 | |
335
c1bc13faadaa
updates ucx to version 1.0
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
314
diff
changeset
|
31 | #include <limits.h> |
128
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 | #define ptrcast(ptr) ((void*)(ptr)) |
255
bf19378aed58
updates UCX to version 0.11
Mike Becker <universe@uap-core.de>
parents:
128
diff
changeset
|
34 | #define alloc_tree(al) (UcxAVLTree*) almalloc((al), sizeof(UcxAVLTree)) |
bf19378aed58
updates UCX to version 0.11
Mike Becker <universe@uap-core.de>
parents:
128
diff
changeset
|
35 | #define alloc_node(al) (UcxAVLNode*) almalloc((al), sizeof(UcxAVLNode)) |
128
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
36 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
37 | static void ucx_avl_connect(UcxAVLTree *tree, |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
38 | UcxAVLNode *node, UcxAVLNode *child, intptr_t nullkey) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
39 | if (child) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
40 | child->parent = node; |
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 | // if child is NULL, nullkey decides if left or right pointer is cleared |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
43 | if (tree->cmpfunc( |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
44 | ptrcast(child ? child->key : nullkey), |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
45 | ptrcast(node->key), tree->userdata) > 0) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
46 | node->right = child; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
47 | } else { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
48 | node->left = child; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
49 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
50 | size_t lh = node->left ? node->left->height : 0; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
51 | size_t rh = node->right ? node->right->height : 0; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
52 | node->height = 1 + (lh > rh ? lh : rh); |
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 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
55 | #define avlheight(node) ((node) ? (node)->height : 0) |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
56 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
57 | static UcxAVLNode* avl_rotright(UcxAVLTree *tree, UcxAVLNode *l0) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
58 | UcxAVLNode *p = l0->parent; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
59 | UcxAVLNode *l1 = l0->left; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
60 | if (p) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
61 | ucx_avl_connect(tree, p, l1, 0); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
62 | } else { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
63 | l1->parent = NULL; |
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 | ucx_avl_connect(tree, l0, l1->right, l1->key); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
66 | ucx_avl_connect(tree, l1, l0, 0); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
67 | return l1; |
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 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
70 | static UcxAVLNode* avl_rotleft(UcxAVLTree *tree, UcxAVLNode *l0) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
71 | UcxAVLNode *p = l0->parent; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
72 | UcxAVLNode *l1 = l0->right; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
73 | if (p) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
74 | ucx_avl_connect(tree, p, l1, 0); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
75 | } else { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
76 | l1->parent = NULL; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
77 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
78 | ucx_avl_connect(tree, l0, l1->left, l1->key); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
79 | ucx_avl_connect(tree, l1, l0, 0); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
80 | return l1; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
81 | } |
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 | static void ucx_avl_balance(UcxAVLTree *tree, UcxAVLNode *n) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
84 | int lh = avlheight(n->left); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
85 | int rh = avlheight(n->right); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
86 | n->height = 1 + (lh > rh ? lh : rh); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
87 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
88 | if (lh - rh == 2) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
89 | UcxAVLNode *c = n->left; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
90 | if (avlheight(c->right) - avlheight(c->left) == 1) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
91 | avl_rotleft(tree, c); |
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 | n = avl_rotright(tree, n); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
94 | } else if (rh - lh == 2) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
95 | UcxAVLNode *c = n->right; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
96 | if (avlheight(c->left) - avlheight(c->right) == 1) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
97 | avl_rotright(tree, c); |
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 | n = avl_rotleft(tree, n); |
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 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
102 | if (n->parent) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
103 | ucx_avl_balance(tree, n->parent); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
104 | } else { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
105 | tree->root = n; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
106 | } |
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 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
109 | 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
|
110 | return ucx_avl_new_a(cmpfunc, ucx_default_allocator()); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
111 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
112 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
113 | UcxAVLTree *ucx_avl_new_a(cmp_func cmpfunc, UcxAllocator *allocator) { |
255
bf19378aed58
updates UCX to version 0.11
Mike Becker <universe@uap-core.de>
parents:
128
diff
changeset
|
114 | UcxAVLTree* tree = alloc_tree(allocator); |
128
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
115 | if (tree) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
116 | tree->allocator = allocator; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
117 | tree->cmpfunc = cmpfunc; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
118 | tree->root = NULL; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
119 | tree->userdata = NULL; |
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 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
122 | return tree; |
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 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
125 | static void ucx_avl_free_node(UcxAllocator *al, UcxAVLNode *node) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
126 | if (node) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
127 | ucx_avl_free_node(al, node->left); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
128 | ucx_avl_free_node(al, node->right); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
129 | alfree(al, node); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
130 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
131 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
132 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
133 | 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
|
134 | UcxAllocator *al = tree->allocator; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
135 | ucx_avl_free_node(al, tree->root); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
136 | alfree(al, tree); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
137 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
138 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
139 | 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
|
140 | UcxAVLNode *n = tree->root; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
141 | int cmpresult; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
142 | while (n && (cmpresult = tree->cmpfunc( |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
143 | ptrcast(key), ptrcast(n->key), tree->userdata))) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
144 | n = cmpresult > 0 ? n->right : n->left; |
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 n; |
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 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
149 | 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
|
150 | UcxAVLNode *n = ucx_avl_get_node(tree, key); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
151 | return n ? n->value : NULL; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
152 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
153 | |
314
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
154 | UcxAVLNode *ucx_avl_find_node(UcxAVLTree *tree, intptr_t key, |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
155 | distance_func dfnc, int mode) { |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
156 | UcxAVLNode *n = tree->root; |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
157 | UcxAVLNode *closest = NULL; |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
158 | |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
159 | intmax_t cmpresult; |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
160 | intmax_t closest_dist; |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
161 | closest_dist = mode == UCX_AVL_FIND_LOWER_BOUNDED ? INTMAX_MIN : INTMAX_MAX; |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
162 | |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
163 | while (n && (cmpresult = dfnc( |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
164 | ptrcast(key), ptrcast(n->key), tree->userdata))) { |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
165 | if (mode == UCX_AVL_FIND_CLOSEST) { |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
166 | intmax_t dist = cmpresult; |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
167 | if (dist < 0) dist *= -1; |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
168 | if (dist < closest_dist) { |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
169 | closest_dist = dist; |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
170 | closest = n; |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
171 | } |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
172 | } else if (mode == UCX_AVL_FIND_LOWER_BOUNDED && cmpresult <= 0) { |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
173 | if (cmpresult > closest_dist) { |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
174 | closest_dist = cmpresult; |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
175 | closest = n; |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
176 | } |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
177 | } else if (mode == UCX_AVL_FIND_UPPER_BOUNDED && cmpresult >= 0) { |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
178 | if (cmpresult < closest_dist) { |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
179 | closest_dist = cmpresult; |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
180 | closest = n; |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
181 | } |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
182 | } |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
183 | n = cmpresult > 0 ? n->right : n->left; |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
184 | } |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
185 | return n ? n : closest; |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
186 | } |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
187 | |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
188 | void *ucx_avl_find(UcxAVLTree *tree, intptr_t key, |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
189 | distance_func dfnc, int mode) { |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
190 | UcxAVLNode *n = ucx_avl_find_node(tree, key, dfnc, mode); |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
191 | return n ? n->value : NULL; |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
192 | } |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
193 | |
128
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
194 | 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
|
195 | return ucx_avl_put_s(tree, key, value, NULL); |
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 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
198 | int ucx_avl_put_s(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
|
199 | void **oldvalue) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
200 | if (tree->root) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
201 | UcxAVLNode *n = tree->root; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
202 | int cmpresult; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
203 | while ((cmpresult = tree->cmpfunc( |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
204 | ptrcast(key), ptrcast(n->key), tree->userdata))) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
205 | UcxAVLNode *m = cmpresult > 0 ? n->right : n->left; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
206 | if (m) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
207 | n = m; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
208 | } else { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
209 | break; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
210 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
211 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
212 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
213 | if (cmpresult) { |
255
bf19378aed58
updates UCX to version 0.11
Mike Becker <universe@uap-core.de>
parents:
128
diff
changeset
|
214 | UcxAVLNode* e = alloc_node(tree->allocator); |
128
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
215 | if (e) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
216 | e->key = key; e->value = value; e->height = 1; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
217 | e->parent = e->left = e->right = NULL; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
218 | ucx_avl_connect(tree, n, e, 0); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
219 | ucx_avl_balance(tree, n); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
220 | return 0; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
221 | } else { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
222 | return 1; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
223 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
224 | } else { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
225 | if (oldvalue) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
226 | *oldvalue = n->value; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
227 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
228 | n->value = value; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
229 | return 0; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
230 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
231 | } else { |
255
bf19378aed58
updates UCX to version 0.11
Mike Becker <universe@uap-core.de>
parents:
128
diff
changeset
|
232 | tree->root = alloc_node(tree->allocator); |
128
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
233 | if (tree->root) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
234 | tree->root->key = key; tree->root->value = value; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
235 | tree->root->height = 1; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
236 | tree->root->parent = tree->root->left = tree->root->right = NULL; |
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 | if (oldvalue) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
239 | *oldvalue = NULL; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
240 | } |
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 | return 0; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
243 | } else { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
244 | return 1; |
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 | } |
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 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
249 | 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
|
250 | return ucx_avl_remove_s(tree, key, NULL, NULL); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
251 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
252 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
253 | 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
|
254 | return ucx_avl_remove_s(tree, node->key, NULL, NULL); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
255 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
256 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
257 | 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
|
258 | intptr_t *oldkey, void **oldvalue) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
259 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
260 | UcxAVLNode *n = tree->root; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
261 | int cmpresult; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
262 | while (n && (cmpresult = tree->cmpfunc( |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
263 | ptrcast(key), ptrcast(n->key), tree->userdata))) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
264 | n = cmpresult > 0 ? n->right : n->left; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
265 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
266 | if (n) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
267 | if (oldkey) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
268 | *oldkey = n->key; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
269 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
270 | if (oldvalue) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
271 | *oldvalue = n->value; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
272 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
273 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
274 | UcxAVLNode *p = n->parent; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
275 | if (n->left && n->right) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
276 | UcxAVLNode *s = n->right; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
277 | while (s->left) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
278 | s = s->left; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
279 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
280 | ucx_avl_connect(tree, s->parent, s->right, s->key); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
281 | n->key = s->key; n->value = s->value; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
282 | p = s->parent; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
283 | alfree(tree->allocator, s); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
284 | } else { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
285 | if (p) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
286 | ucx_avl_connect(tree, p, n->right ? n->right:n->left, n->key); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
287 | } else { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
288 | tree->root = n->right ? n->right : n->left; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
289 | if (tree->root) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
290 | tree->root->parent = NULL; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
291 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
292 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
293 | alfree(tree->allocator, n); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
294 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
295 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
296 | if (p) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
297 | ucx_avl_balance(tree, p); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
298 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
299 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
300 | return 0; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
301 | } else { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
302 | return 1; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
303 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
304 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
305 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
306 | static size_t ucx_avl_countn(UcxAVLNode *node) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
307 | if (node) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
308 | return 1 + ucx_avl_countn(node->left) + ucx_avl_countn(node->right); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
309 | } else { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
310 | return 0; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
311 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
312 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
313 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
314 | 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
|
315 | return ucx_avl_countn(tree->root); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
316 | } |
314
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
317 | |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
318 | UcxAVLNode* ucx_avl_pred(UcxAVLNode* node) { |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
319 | if (node->left) { |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
320 | UcxAVLNode* n = node->left; |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
321 | while (n->right) { |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
322 | n = n->right; |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
323 | } |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
324 | return n; |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
325 | } else { |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
326 | UcxAVLNode* n = node; |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
327 | while (n->parent) { |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
328 | if (n->parent->right == n) { |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
329 | return n->parent; |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
330 | } else { |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
331 | n = n->parent; |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
332 | } |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
333 | } |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
334 | return NULL; |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
335 | } |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
336 | } |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
337 | |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
338 | UcxAVLNode* ucx_avl_succ(UcxAVLNode* node) { |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
339 | if (node->right) { |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
340 | UcxAVLNode* n = node->right; |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
341 | while (n->left) { |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
342 | n = n->left; |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
343 | } |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
344 | return n; |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
345 | } else { |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
346 | UcxAVLNode* n = node; |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
347 | while (n->parent) { |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
348 | if (n->parent->left == n) { |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
349 | return n->parent; |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
350 | } else { |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
351 | n = n->parent; |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
352 | } |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
353 | } |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
354 | return NULL; |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
355 | } |
8722a668fb2a
updates ucx version (most importantly this adds the new sstrstr implementation)
Mike Becker <universe@uap-core.de>
parents:
255
diff
changeset
|
356 | } |