src/cx/tree.h

Wed, 14 Feb 2024 22:32:13 +0100

author
Mike Becker <universe@uap-core.de>
date
Wed, 14 Feb 2024 22:32:13 +0100
changeset 825
3f324ea53152
parent 824
a939872c284d
child 826
21840975d541
permissions
-rw-r--r--

be honest at least in the lib version

816
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
1 /*
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
3 *
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
4 * Copyright 2024 Mike Becker, Olaf Wintermann All rights reserved.
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
5 *
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
6 * Redistribution and use in source and binary forms, with or without
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
7 * modification, are permitted provided that the following conditions are met:
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
8 *
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
9 * 1. Redistributions of source code must retain the above copyright
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
10 * notice, this list of conditions and the following disclaimer.
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
11 *
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
12 * 2. Redistributions in binary form must reproduce the above copyright
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
13 * notice, this list of conditions and the following disclaimer in the
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
14 * documentation and/or other materials provided with the distribution.
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
15 *
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
26 * POSSIBILITY OF SUCH DAMAGE.
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
27 */
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
28 /**
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
29 * \file tree.h
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
30 * \brief Interface for tree implementations.
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
31 * \author Mike Becker
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
32 * \author Olaf Wintermann
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
33 * \copyright 2-Clause BSD License
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
34 */
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
35
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
36 #ifndef UCX_TREE_H
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
37 #define UCX_TREE_H
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
38
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
39 #include "common.h"
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
40
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
41 #ifdef __cplusplus
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
42 extern "C" {
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
43 #endif
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
44
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
45
822
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
46 /**
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
47 * Links a node to a (new) parent.
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
48 *
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
49 * If the node has already a parent, it is unlinked, first.
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
50 *
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
51 * @param parent the parent node
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
52 * @param node the node that shall be linked
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
53 * @param loc_parent offset in the node struct for the parent pointer
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
54 * @param loc_children offset in the node struct for the children linked list
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
55 * @param loc_prev offset in the node struct for the prev pointer
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
56 * @param loc_next offset in the node struct for the next pointer
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
57 * @see cx_tree_unlink()
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
58 */
816
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
59 __attribute__((__nonnull__))
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
60 void cx_tree_link(
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
61 void * restrict parent,
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
62 void * restrict node,
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
63 ptrdiff_t loc_parent,
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
64 ptrdiff_t loc_children,
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
65 ptrdiff_t loc_prev,
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
66 ptrdiff_t loc_next
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
67 );
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
68
822
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
69 /**
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
70 * Unlinks a node from its parent.
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
71 *
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
72 * If the node has no parent, this function does nothing.
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
73 *
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
74 * @param node the node that shall be unlinked from its parent
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
75 * @param loc_parent offset in the node struct for the parent pointer
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
76 * @param loc_children offset in the node struct for the children linked list
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
77 * @param loc_prev offset in the node struct for the prev pointer
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
78 * @param loc_next offset in the node struct for the next pointer
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
79 * @see cx_tree_link()
e2243453127f add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
80 */
816
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
81 __attribute__((__nonnull__))
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
82 void cx_tree_unlink(
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
83 void *node,
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
84 ptrdiff_t loc_parent,
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
85 ptrdiff_t loc_children,
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
86 ptrdiff_t loc_prev,
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
87 ptrdiff_t loc_next
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
88 );
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
89
823
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
90 /**
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
91 * Function pointer for a search function.
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
92 *
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
93 * A function of this kind shall check if the specified \p node
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
94 * contains the given \p data or if one of the children might contain
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
95 * the data.
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
96 *
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
97 * For example if a tree stores file path information, a node that is
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
98 * describing a parent directory of a filename that is searched, shall
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
99 * return 1 to indicate that a child node might contain the searched item.
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
100 * On the other hand, if the node denotes a path that is not a prefix of
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
101 * the searched filename, the function would return -1 to indicate that
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
102 * the search does not need to be continued in that branch.
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
103 *
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
104 * @param node the node that is currently investigated
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
105 * @param data the data that is searched for
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
106 *
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
107 * @return 0 if the node contains the data,
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
108 * 1 if one of the children might contain the data,
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
109 * -1 if neither the node, nor the children contains the data
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
110 */
824
a939872c284d fix missing typedef
Mike Becker <universe@uap-core.de>
parents: 823
diff changeset
111 typedef int (*cx_tree_search_func)(void const *node, void const* data);
823
f4faa7f73cb8 declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents: 822
diff changeset
112
816
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
113 #ifdef __cplusplus
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
114 } // extern "C"
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
115 #endif
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
116
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
117 #endif //UCX_TREE_H

mercurial