Sun, 09 Jun 2024 15:43:08 +0200
update toolkit
2
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
1 | /* |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
2 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
3 | * |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
4 | * Copyright 2024 Mike Becker, Olaf Wintermann All rights reserved. |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
5 | * |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
6 | * Redistribution and use in source and binary forms, with or without |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
7 | * modification, are permitted provided that the following conditions are met: |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
8 | * |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
9 | * 1. Redistributions of source code must retain the above copyright |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
10 | * notice, this list of conditions and the following disclaimer. |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
11 | * |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
12 | * 2. Redistributions in binary form must reproduce the above copyright |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
13 | * notice, this list of conditions and the following disclaimer in the |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
14 | * documentation and/or other materials provided with the distribution. |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
15 | * |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
16 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
17 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
18 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
19 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
20 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
21 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
22 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
23 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
24 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
fbdfaacc4182
update ucx, libidav and add first gui code
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 |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
26 | * POSSIBILITY OF SUCH DAMAGE. |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
27 | */ |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
28 | |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
29 | #include "cx/tree.h" |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
30 | |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
31 | #include <assert.h> |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
32 | |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
33 | #define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off))) |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
34 | #define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off))) |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
35 | #define tree_parent(node) CX_TREE_PTR(node, loc_parent) |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
36 | #define tree_children(node) CX_TREE_PTR(node, loc_children) |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
37 | #define tree_prev(node) CX_TREE_PTR(node, loc_prev) |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
38 | #define tree_next(node) CX_TREE_PTR(node, loc_next) |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
39 | |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
40 | void cx_tree_link( |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
41 | void *restrict parent, |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
42 | void *restrict node, |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
43 | ptrdiff_t loc_parent, |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
44 | ptrdiff_t loc_children, |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
45 | ptrdiff_t loc_prev, |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
46 | ptrdiff_t loc_next |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
47 | ) { |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
48 | void *current_parent = tree_parent(node); |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
49 | if (current_parent == parent) return; |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
50 | if (current_parent != NULL) { |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
51 | cx_tree_unlink(node, loc_parent, loc_children, |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
52 | loc_prev, loc_next); |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
53 | } |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
54 | |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
55 | if (tree_children(parent) == NULL) { |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
56 | tree_children(parent) = node; |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
57 | } else { |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
58 | void *children = tree_children(parent); |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
59 | tree_prev(children) = node; |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
60 | tree_next(node) = children; |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
61 | tree_children(parent) = node; |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
62 | } |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
63 | tree_parent(node) = parent; |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
64 | } |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
65 | |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
66 | void cx_tree_unlink( |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
67 | void *node, |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
68 | ptrdiff_t loc_parent, |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
69 | ptrdiff_t loc_children, |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
70 | ptrdiff_t loc_prev, |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
71 | ptrdiff_t loc_next |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
72 | ) { |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
73 | if (tree_parent(node) == NULL) return; |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
74 | |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
75 | void *left = tree_prev(node); |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
76 | void *right = tree_next(node); |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
77 | assert(left == NULL || tree_children(tree_parent(node)) != node); |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
78 | if (left == NULL) { |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
79 | tree_children(tree_parent(node)) = right; |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
80 | } else { |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
81 | tree_next(left) = right; |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
82 | } |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
83 | if (right != NULL) tree_prev(right) = left; |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
84 | tree_parent(node) = NULL; |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
85 | tree_prev(node) = NULL; |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
86 | tree_next(node) = NULL; |
fbdfaacc4182
update ucx, libidav and add first gui code
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
87 | } |