ucx: src/cx/tree.h@a939872c284d

     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  *

    51  * @param parent the parent node

    52  * @param node the node that shall be linked

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

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

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

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

    57  * @see cx_tree_unlink()

    58  */

    59 __attribute__((__nonnull__))

    60 void cx_tree_link(

    61         void * restrict parent,

    62         void * restrict node,

    63         ptrdiff_t loc_parent,

    64         ptrdiff_t loc_children,

    65         ptrdiff_t loc_prev,

    66         ptrdiff_t loc_next

    67 );

    69 /**

    70  * Unlinks a node from its parent.

    71  *

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

    73  *

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

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

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

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

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

    79  * @see cx_tree_link()

    80  */

    81 __attribute__((__nonnull__))

    82 void cx_tree_unlink(

    83         void *node,

    84         ptrdiff_t loc_parent,

    85         ptrdiff_t loc_children,

    86         ptrdiff_t loc_prev,

    87         ptrdiff_t loc_next

    88 );

    90 /**

    91  * Function pointer for a search function.

    92  *

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

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

    95  * the data.

    96  *

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

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

    99  * return 1 to indicate that a child node might contain the searched item.

   100  * On the other hand, if the node denotes a path that is not a prefix of

   101  * the searched filename, the function would return -1 to indicate that

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

   103  *

   104  * @param node the node that is currently investigated

   105  * @param data the data that is searched for

   106  *

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

   108  * 1 if one of the children might contain the data,

   109  * -1 if neither the node, nor the children contains the data

   110  */

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

   113 #ifdef __cplusplus

   114 } // extern "C"

   115 #endif

   117 #endif //UCX_TREE_H

Mercurial > hg > ucx / file revision