comparison: src/tree.c
src/tree.c
- changeset 921
- 5a7aa9cf9c3a
- parent 918
- ec1f2015ec79
equal
deleted
inserted
replaced
| 920:02adaa52d0c4 | 921:5a7aa9cf9c3a |
|---|---|
| 49 ptrdiff_t loc_last_child, | 49 ptrdiff_t loc_last_child, |
| 50 ptrdiff_t loc_prev, | 50 ptrdiff_t loc_prev, |
| 51 ptrdiff_t loc_next | 51 ptrdiff_t loc_next |
| 52 ) { | 52 ) { |
| 53 tree_parent(node) = NULL; | 53 tree_parent(node) = NULL; |
| 54 tree_prev(node) = NULL; | 54 if (loc_prev >= 0) { |
| 55 tree_prev(node) = NULL; | |
| 56 } | |
| 55 tree_next(node) = NULL; | 57 tree_next(node) = NULL; |
| 56 tree_children(node) = NULL; | 58 tree_children(node) = NULL; |
| 57 if (loc_last_child >= 0) { | 59 if (loc_last_child >= 0) { |
| 58 tree_last_child(node) = NULL; | 60 tree_last_child(node) = NULL; |
| 59 } | 61 } |
| 66 ptrdiff_t loc_children, | 68 ptrdiff_t loc_children, |
| 67 ptrdiff_t loc_last_child, | 69 ptrdiff_t loc_last_child, |
| 68 ptrdiff_t loc_prev, | 70 ptrdiff_t loc_prev, |
| 69 ptrdiff_t loc_next | 71 ptrdiff_t loc_next |
| 70 ) { | 72 ) { |
| 73 assert(loc_parent >= 0); | |
| 74 assert(loc_children >= 0); | |
| 75 assert(loc_next >= 0); | |
| 76 | |
| 71 void *current_parent = tree_parent(node); | 77 void *current_parent = tree_parent(node); |
| 72 if (current_parent == parent) return; | 78 if (current_parent == parent) return; |
| 73 if (current_parent != NULL) { | 79 if (current_parent != NULL) { |
| 74 cx_tree_unlink(node, cx_tree_ptr_locations); | 80 cx_tree_unlink(node, cx_tree_ptr_locations); |
| 75 } | 81 } |
| 78 tree_children(parent) = node; | 84 tree_children(parent) = node; |
| 79 if (loc_last_child >= 0) { | 85 if (loc_last_child >= 0) { |
| 80 tree_last_child(parent) = node; | 86 tree_last_child(parent) = node; |
| 81 } | 87 } |
| 82 } else { | 88 } else { |
| 89 void *child; | |
| 83 if (loc_last_child >= 0) { | 90 if (loc_last_child >= 0) { |
| 84 void *child = tree_last_child(parent); | 91 child = tree_last_child(parent); |
| 85 tree_prev(node) = child; | |
| 86 tree_next(child) = node; | |
| 87 tree_last_child(parent) = node; | 92 tree_last_child(parent) = node; |
| 88 } else { | 93 } else { |
| 89 void *child = tree_children(parent); | 94 child = tree_children(parent); |
| 90 void *next; | 95 void *next; |
| 91 while ((next = tree_next(child)) != NULL) { | 96 while ((next = tree_next(child)) != NULL) { |
| 92 child = next; | 97 child = next; |
| 93 } | 98 } |
| 99 } | |
| 100 if (loc_prev >= 0) { | |
| 94 tree_prev(node) = child; | 101 tree_prev(node) = child; |
| 95 tree_next(child) = node; | 102 } |
| 96 } | 103 tree_next(child) = node; |
| 97 } | 104 } |
| 98 tree_parent(node) = parent; | 105 tree_parent(node) = parent; |
| 106 } | |
| 107 | |
| 108 static void *cx_tree_node_prev( | |
| 109 ptrdiff_t loc_parent, | |
| 110 ptrdiff_t loc_children, | |
| 111 ptrdiff_t loc_next, | |
| 112 const void *node | |
| 113 ) { | |
| 114 void *parent = tree_parent(node); | |
| 115 void *begin = tree_children(parent); | |
| 116 if (begin == node) return NULL; | |
| 117 const void *cur = begin; | |
| 118 const void *next; | |
| 119 while (1) { | |
| 120 next = tree_next(cur); | |
| 121 if (next == node) return (void *) cur; | |
| 122 cur = next; | |
| 123 } | |
| 99 } | 124 } |
| 100 | 125 |
| 101 void cx_tree_unlink( | 126 void cx_tree_unlink( |
| 102 void *node, | 127 void *node, |
| 103 ptrdiff_t loc_parent, | 128 ptrdiff_t loc_parent, |
| 106 ptrdiff_t loc_prev, | 131 ptrdiff_t loc_prev, |
| 107 ptrdiff_t loc_next | 132 ptrdiff_t loc_next |
| 108 ) { | 133 ) { |
| 109 if (tree_parent(node) == NULL) return; | 134 if (tree_parent(node) == NULL) return; |
| 110 | 135 |
| 111 void *left = tree_prev(node); | 136 assert(loc_children >= 0); |
| 137 assert(loc_next >= 0); | |
| 138 assert(loc_parent >= 0); | |
| 139 void *left; | |
| 140 if (loc_prev >= 0) { | |
| 141 left = tree_prev(node); | |
| 142 } else { | |
| 143 left = cx_tree_node_prev(loc_parent, loc_children, loc_next, node); | |
| 144 } | |
| 112 void *right = tree_next(node); | 145 void *right = tree_next(node); |
| 113 void *parent = tree_parent(node); | 146 void *parent = tree_parent(node); |
| 114 assert(left == NULL || tree_children(parent) != node); | 147 assert(left == NULL || tree_children(parent) != node); |
| 115 assert(right == NULL || loc_last_child < 0 || | 148 assert(right == NULL || loc_last_child < 0 || |
| 116 tree_last_child(parent) != node); | 149 tree_last_child(parent) != node); |
| 123 if (right == NULL) { | 156 if (right == NULL) { |
| 124 if (loc_last_child >= 0) { | 157 if (loc_last_child >= 0) { |
| 125 tree_last_child(parent) = left; | 158 tree_last_child(parent) = left; |
| 126 } | 159 } |
| 127 } else { | 160 } else { |
| 128 tree_prev(right) = left; | 161 if (loc_prev >= 0) { |
| 162 tree_prev(right) = left; | |
| 163 } | |
| 129 } | 164 } |
| 130 | 165 |
| 131 tree_parent(node) = NULL; | 166 tree_parent(node) = NULL; |
| 132 tree_prev(node) = NULL; | |
| 133 tree_next(node) = NULL; | 167 tree_next(node) = NULL; |
| 168 if (loc_prev >= 0) { | |
| 169 tree_prev(node) = NULL; | |
| 170 } | |
| 134 } | 171 } |
| 135 | 172 |
| 136 int cx_tree_search( | 173 int cx_tree_search( |
| 137 const void *root, | 174 const void *root, |
| 138 const void *node, | 175 const void *node, |
