comparison: ucx/avl.c
ucx/avl.c
- changeset 243
- 2e74828c5e94
- parent 225
- a1a068c2c4ef
- child 245
- db732f8c083a
equal
deleted
inserted
replaced
| 242:a3597d704421 | 243:2e74828c5e94 |
|---|---|
| 24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | 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 | 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 <limits.h> | |
| 30 | |
| 29 #include "avl.h" | 31 #include "avl.h" |
| 30 | 32 |
| 31 #define ptrcast(ptr) ((void*)(ptr)) | 33 #define ptrcast(ptr) ((void*)(ptr)) |
| 32 #define alloc_tree(al) (UcxAVLTree*) almalloc((al), sizeof(UcxAVLTree)) | 34 #define alloc_tree(al) (UcxAVLTree*) almalloc((al), sizeof(UcxAVLTree)) |
| 33 #define alloc_node(al) (UcxAVLNode*) almalloc((al), sizeof(UcxAVLNode)) | 35 #define alloc_node(al) (UcxAVLNode*) almalloc((al), sizeof(UcxAVLNode)) |
| 147 void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) { | 149 void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) { |
| 148 UcxAVLNode *n = ucx_avl_get_node(tree, key); | 150 UcxAVLNode *n = ucx_avl_get_node(tree, key); |
| 149 return n ? n->value : NULL; | 151 return n ? n->value : NULL; |
| 150 } | 152 } |
| 151 | 153 |
| 154 UcxAVLNode *ucx_avl_find_node(UcxAVLTree *tree, intptr_t key, | |
| 155 distance_func dfnc, int mode) { | |
| 156 UcxAVLNode *n = tree->root; | |
| 157 UcxAVLNode *closest = NULL; | |
| 158 | |
| 159 intmax_t cmpresult; | |
| 160 intmax_t closest_dist; | |
| 161 closest_dist = mode == UCX_AVL_FIND_LOWER_BOUNDED ? INTMAX_MIN : INTMAX_MAX; | |
| 162 | |
| 163 while (n && (cmpresult = dfnc( | |
| 164 ptrcast(key), ptrcast(n->key), tree->userdata))) { | |
| 165 if (mode == UCX_AVL_FIND_CLOSEST) { | |
| 166 intmax_t dist = cmpresult; | |
| 167 if (dist < 0) dist *= -1; | |
| 168 if (dist < closest_dist) { | |
| 169 closest_dist = dist; | |
| 170 closest = n; | |
| 171 } | |
| 172 } else if (mode == UCX_AVL_FIND_LOWER_BOUNDED && cmpresult <= 0) { | |
| 173 if (cmpresult > closest_dist) { | |
| 174 closest_dist = cmpresult; | |
| 175 closest = n; | |
| 176 } | |
| 177 } else if (mode == UCX_AVL_FIND_UPPER_BOUNDED && cmpresult >= 0) { | |
| 178 if (cmpresult < closest_dist) { | |
| 179 closest_dist = cmpresult; | |
| 180 closest = n; | |
| 181 } | |
| 182 } | |
| 183 n = cmpresult > 0 ? n->right : n->left; | |
| 184 } | |
| 185 return n ? n : closest; | |
| 186 } | |
| 187 | |
| 188 void *ucx_avl_find(UcxAVLTree *tree, intptr_t key, | |
| 189 distance_func dfnc, int mode) { | |
| 190 UcxAVLNode *n = ucx_avl_find_node(tree, key, dfnc, mode); | |
| 191 return n ? n->value : NULL; | |
| 192 } | |
| 193 | |
| 152 int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) { | 194 int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) { |
| 153 return ucx_avl_put_s(tree, key, value, NULL); | 195 return ucx_avl_put_s(tree, key, value, NULL); |
| 154 } | 196 } |
| 155 | 197 |
| 156 int ucx_avl_put_s(UcxAVLTree *tree, intptr_t key, void *value, | 198 int ucx_avl_put_s(UcxAVLTree *tree, intptr_t key, void *value, |
