ucx: src/cx/tree.h@21840975d541

     1 /*

     2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.

     3  *

     4  * Copyright 2024 Mike Becker, Olaf Wintermann All rights reserved.

     5  *

     6  * Redistribution and use in source and binary forms, with or without

     7  * modification, are permitted provided that the following conditions are met:

     8  *

     9  *   1. Redistributions of source code must retain the above copyright

    10  *      notice, this list of conditions and the following disclaimer.

    11  *

    12  *   2. Redistributions in binary form must reproduce the above copyright

    13  *      notice, this list of conditions and the following disclaimer in the

    14  *      documentation and/or other materials provided with the distribution.

    15  *

    16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"

    17  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

    18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

    19  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE

    20  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR

    21  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF

    22  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS

    23  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN

    24  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)

    25  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE

    26  * POSSIBILITY OF SUCH DAMAGE.

    27  */

    28 /**

    29  * \file tree.h

    30  * \brief Interface for tree implementations.

    31  * \author Mike Becker

    32  * \author Olaf Wintermann

    33  * \copyright 2-Clause BSD License

    34  */

    36 #ifndef UCX_TREE_H

    37 #define UCX_TREE_H

    39 #include "common.h"

    41 #ifdef __cplusplus

    42 extern "C" {

    43 #endif

    46 /**

    47  * Links a node to a (new) parent.

    48  *

    49  * If the node has already a parent, it is unlinked, first.

    50  * If the parent has children already, the node is prepended to the list

    51  * of all currently existing children.

    52  *

    53  * @param parent the parent node

    54  * @param node the node that shall be linked

    55  * @param loc_parent offset in the node struct for the parent pointer

    56  * @param loc_children offset in the node struct for the children linked list

    57  * @param loc_prev offset in the node struct for the prev pointer

    58  * @param loc_next offset in the node struct for the next pointer

    59  * @see cx_tree_unlink()

    60  */

    61 __attribute__((__nonnull__))

    62 void cx_tree_link(

    63         void * restrict parent,

    64         void * restrict node,

    65         ptrdiff_t loc_parent,

    66         ptrdiff_t loc_children,

    67         ptrdiff_t loc_prev,

    68         ptrdiff_t loc_next

    69 );

    71 /**

    72  * Unlinks a node from its parent.

    73  *

    74  * If the node has no parent, this function does nothing.

    75  *

    76  * @param node the node that shall be unlinked from its parent

    77  * @param loc_parent offset in the node struct for the parent pointer

    78  * @param loc_children offset in the node struct for the children linked list

    79  * @param loc_prev offset in the node struct for the prev pointer

    80  * @param loc_next offset in the node struct for the next pointer

    81  * @see cx_tree_link()

    82  */

    83 __attribute__((__nonnull__))

    84 void cx_tree_unlink(

    85         void *node,

    86         ptrdiff_t loc_parent,

    87         ptrdiff_t loc_children,

    88         ptrdiff_t loc_prev,

    89         ptrdiff_t loc_next

    90 );

    92 /**

    93  * Function pointer for a search function.

    94  *

    95  * A function of this kind shall check if the specified \p node

    96  * contains the given \p data or if one of the children might contain

    97  * the data.

    98  *

    99  * The function should use the returned integer to indicate how close the

   100  * match is, where a negative number means that it does not match at all.

   101  *

   102  * For example if a tree stores file path information, a node that is

   103  * describing a parent directory of a filename that is searched, shall

   104  * return a positive number to indicate that a child node might contain the

   105  * searched item. On the other hand, if the node denotes a path that is not a

   106  * prefix of the searched filename, the function would return -1 to indicate

   107  * that * the search does not need to be continued in that branch.

   108  *

   109  * @param node the node that is currently investigated

   110  * @param data the data that is searched for

   111  *

   112  * @return 0 if the node contains the data,

   113  * positive if one of the children might contain the data,

   114  * negative if neither the node, nor the children contains the data

   115  */

   116 typedef int (*cx_tree_search_func)(void const *node, void const* data);

   119 /**

   120  * Searches for data in a tree.

   121  *

   122  * When the data cannot be found exactly, the search function might return a

   123  * closest result which might be a good starting point for adding a new node

   124  * to the tree.

   125  *

   126  * Depending on the tree structure it is not necessarily guaranteed that the

   127  * "closest" match is uniquely defined. This function will search for a node

   128  * with the best match according to the \p sfunc (meaning: the return value of

   129  * \p sfunc which is closest to zero). If that is also ambiguous, an arbitrary

   130  * node matching the criteria is returned.

   131  *

   132  * @param root the root node

   133  * @param data the data to search for

   134  * @param sfunc the search function

   135  * @param result where the result shall be stored

   136  * @param loc_children offset in the node struct for the children linked list

   137  * @param loc_next offset in the node struct for the next pointer

   138  * @return zero if the node was found exactly, positive if a node was found that

   139  * could contain the node (but doesn't right now), negative if the tree does not

   140  * contain any node that might be related to the searched data

   141  */

   142 __attribute__((__nonnull__))

   143 int cx_tree_search(

   144         void const *root,

   145         void const *data,

   146         cx_tree_search_func sfunc,

   147         void **result,

   148         ptrdiff_t loc_children,

   149         ptrdiff_t loc_next

   150 );

   152 #ifdef __cplusplus

   153 } // extern "C"

   154 #endif

   156 #endif //UCX_TREE_H

Mercurial > hg > ucx / file revision