1.1 --- a/src/cx/tree.h Wed Feb 14 22:32:13 2024 +0100 1.2 +++ b/src/cx/tree.h Thu Feb 15 21:54:43 2024 +0100 1.3 @@ -47,6 +47,8 @@ 1.4 * Links a node to a (new) parent. 1.5 * 1.6 * If the node has already a parent, it is unlinked, first. 1.7 + * If the parent has children already, the node is prepended to the list 1.8 + * of all currently existing children. 1.9 * 1.10 * @param parent the parent node 1.11 * @param node the node that shall be linked 1.12 @@ -94,22 +96,59 @@ 1.13 * contains the given \p data or if one of the children might contain 1.14 * the data. 1.15 * 1.16 + * The function should use the returned integer to indicate how close the 1.17 + * match is, where a negative number means that it does not match at all. 1.18 + * 1.19 * For example if a tree stores file path information, a node that is 1.20 * describing a parent directory of a filename that is searched, shall 1.21 - * return 1 to indicate that a child node might contain the searched item. 1.22 - * On the other hand, if the node denotes a path that is not a prefix of 1.23 - * the searched filename, the function would return -1 to indicate that 1.24 - * the search does not need to be continued in that branch. 1.25 + * return a positive number to indicate that a child node might contain the 1.26 + * searched item. On the other hand, if the node denotes a path that is not a 1.27 + * prefix of the searched filename, the function would return -1 to indicate 1.28 + * that * the search does not need to be continued in that branch. 1.29 * 1.30 * @param node the node that is currently investigated 1.31 * @param data the data that is searched for 1.32 * 1.33 * @return 0 if the node contains the data, 1.34 - * 1 if one of the children might contain the data, 1.35 - * -1 if neither the node, nor the children contains the data 1.36 + * positive if one of the children might contain the data, 1.37 + * negative if neither the node, nor the children contains the data 1.38 */ 1.39 typedef int (*cx_tree_search_func)(void const *node, void const* data); 1.40 1.41 + 1.42 +/** 1.43 + * Searches for data in a tree. 1.44 + * 1.45 + * When the data cannot be found exactly, the search function might return a 1.46 + * closest result which might be a good starting point for adding a new node 1.47 + * to the tree. 1.48 + * 1.49 + * Depending on the tree structure it is not necessarily guaranteed that the 1.50 + * "closest" match is uniquely defined. This function will search for a node 1.51 + * with the best match according to the \p sfunc (meaning: the return value of 1.52 + * \p sfunc which is closest to zero). If that is also ambiguous, an arbitrary 1.53 + * node matching the criteria is returned. 1.54 + * 1.55 + * @param root the root node 1.56 + * @param data the data to search for 1.57 + * @param sfunc the search function 1.58 + * @param result where the result shall be stored 1.59 + * @param loc_children offset in the node struct for the children linked list 1.60 + * @param loc_next offset in the node struct for the next pointer 1.61 + * @return zero if the node was found exactly, positive if a node was found that 1.62 + * could contain the node (but doesn't right now), negative if the tree does not 1.63 + * contain any node that might be related to the searched data 1.64 + */ 1.65 +__attribute__((__nonnull__)) 1.66 +int cx_tree_search( 1.67 + void const *root, 1.68 + void const *data, 1.69 + cx_tree_search_func sfunc, 1.70 + void **result, 1.71 + ptrdiff_t loc_children, 1.72 + ptrdiff_t loc_next 1.73 +); 1.74 + 1.75 #ifdef __cplusplus 1.76 } // extern "C" 1.77 #endif