comparison: src/cx/tree.h
src/cx/tree.h
- changeset 826
- 21840975d541
- parent 824
- a939872c284d
- child 827
- 13b40a598d16
equal
deleted
inserted
replaced
| 825:3f324ea53152 | 826:21840975d541 |
|---|---|
| 45 | 45 |
| 46 /** | 46 /** |
| 47 * Links a node to a (new) parent. | 47 * Links a node to a (new) parent. |
| 48 * | 48 * |
| 49 * If the node has already a parent, it is unlinked, first. | 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. | |
| 50 * | 52 * |
| 51 * @param parent the parent node | 53 * @param parent the parent node |
| 52 * @param node the node that shall be linked | 54 * @param node the node that shall be linked |
| 53 * @param loc_parent offset in the node struct for the parent pointer | 55 * @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 | 56 * @param loc_children offset in the node struct for the children linked list |
| 92 * | 94 * |
| 93 * A function of this kind shall check if the specified \p node | 95 * 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 | 96 * contains the given \p data or if one of the children might contain |
| 95 * the data. | 97 * the data. |
| 96 * | 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 * | |
| 97 * For example if a tree stores file path information, a node that is | 102 * 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 | 103 * 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. | 104 * return a positive number to indicate that a child node might contain the |
| 100 * On the other hand, if the node denotes a path that is not a prefix of | 105 * searched item. On the other hand, if the node denotes a path that is not a |
| 101 * the searched filename, the function would return -1 to indicate that | 106 * prefix of the searched filename, the function would return -1 to indicate |
| 102 * the search does not need to be continued in that branch. | 107 * that * the search does not need to be continued in that branch. |
| 103 * | 108 * |
| 104 * @param node the node that is currently investigated | 109 * @param node the node that is currently investigated |
| 105 * @param data the data that is searched for | 110 * @param data the data that is searched for |
| 106 * | 111 * |
| 107 * @return 0 if the node contains the data, | 112 * @return 0 if the node contains the data, |
| 108 * 1 if one of the children might contain the data, | 113 * positive if one of the children might contain the data, |
| 109 * -1 if neither the node, nor the children contains the data | 114 * negative if neither the node, nor the children contains the data |
| 110 */ | 115 */ |
| 111 typedef int (*cx_tree_search_func)(void const *node, void const* data); | 116 typedef int (*cx_tree_search_func)(void const *node, void const* data); |
| 117 | |
| 118 | |
| 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 ); | |
| 112 | 151 |
| 113 #ifdef __cplusplus | 152 #ifdef __cplusplus |
| 114 } // extern "C" | 153 } // extern "C" |
| 115 #endif | 154 #endif |
| 116 | 155 |
