comparison: src/tree.c
src/tree.c
- changeset 826
- 21840975d541
- parent 816
- 425234b05dff
- child 830
- c4dae6fe6d5b
equal
deleted
inserted
replaced
| 825:3f324ea53152 | 826:21840975d541 |
|---|---|
| 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE | 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
| 26 * POSSIBILITY OF SUCH DAMAGE. | 26 * POSSIBILITY OF SUCH DAMAGE. |
| 27 */ | 27 */ |
| 28 | 28 |
| 29 #include "cx/tree.h" | 29 #include "cx/tree.h" |
| 30 | |
| 31 #include "cx/array_list.h" | |
| 30 | 32 |
| 31 #include <assert.h> | 33 #include <assert.h> |
| 32 | 34 |
| 33 #define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off))) | 35 #define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off))) |
| 34 #define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off))) | 36 #define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off))) |
| 83 if (right != NULL) tree_prev(right) = left; | 85 if (right != NULL) tree_prev(right) = left; |
| 84 tree_parent(node) = NULL; | 86 tree_parent(node) = NULL; |
| 85 tree_prev(node) = NULL; | 87 tree_prev(node) = NULL; |
| 86 tree_next(node) = NULL; | 88 tree_next(node) = NULL; |
| 87 } | 89 } |
| 90 | |
| 91 int cx_tree_search( | |
| 92 void const *root, | |
| 93 void const *data, | |
| 94 cx_tree_search_func sfunc, | |
| 95 void **result, | |
| 96 ptrdiff_t loc_children, | |
| 97 ptrdiff_t loc_next | |
| 98 ) { | |
| 99 int ret; | |
| 100 *result = NULL; | |
| 101 | |
| 102 // shortcut: compare root before doing anything else | |
| 103 ret = sfunc(root, data); | |
| 104 if (ret < 0) { | |
| 105 return ret; | |
| 106 } else if (ret == 0 || tree_children(root) == NULL) { | |
| 107 *result = (void*)root; | |
| 108 return ret; | |
| 109 } | |
| 110 | |
| 111 // create a working stack | |
| 112 size_t work_cap = 32; | |
| 113 size_t work_size = 0; | |
| 114 void const **work = malloc(sizeof(void*) * work_cap); | |
| 115 #define work_add(node) cx_array_add(&work, &work_size, &work_cap, \ | |
| 116 sizeof(void*), &(node), cx_array_default_reallocator) | |
| 117 | |
| 118 // add the children of root to the working stack | |
| 119 { | |
| 120 void *c = tree_children(root); | |
| 121 while (c != NULL) { | |
| 122 work_add(c); | |
| 123 c = tree_next(c); | |
| 124 } | |
| 125 } | |
| 126 | |
| 127 // remember a candidate for adding the data | |
| 128 // also remember the exact return code from sfunc | |
| 129 void *candidate = NULL; | |
| 130 int ret_candidate = -1; | |
| 131 | |
| 132 // process the working stack | |
| 133 while (work_size > 0) { | |
| 134 // pop element | |
| 135 void const *node = work[--work_size]; | |
| 136 | |
| 137 // apply the search function | |
| 138 ret = sfunc(node, data); | |
| 139 | |
| 140 if (ret == 0) { | |
| 141 // if found, exit the search | |
| 142 *result = (void*) node; | |
| 143 work_size = 0; | |
| 144 break; | |
| 145 } else if (ret > 0) { | |
| 146 // if children might contain the data, add them to the stack | |
| 147 void *c = tree_children(node); | |
| 148 while (c != NULL) { | |
| 149 work_add(c); | |
| 150 c = tree_next(c); | |
| 151 } | |
| 152 | |
| 153 // remember this node in case no child is suitable | |
| 154 if (ret_candidate < 0 || ret < ret_candidate) { | |
| 155 candidate = (void *) node; | |
| 156 ret_candidate = ret; | |
| 157 } | |
| 158 } | |
| 159 } | |
| 160 | |
| 161 // not found, but was there a candidate? | |
| 162 if (ret != 0 && candidate != NULL) { | |
| 163 ret = ret_candidate; | |
| 164 *result = candidate; | |
| 165 } | |
| 166 | |
| 167 // free the working queue and return | |
| 168 #undef workq_add | |
| 169 free(work); | |
| 170 return ret; | |
| 171 } |
