| /* |
| * Copyright (c) 2010 The VP8 project authors. All Rights Reserved. |
| * |
| * Use of this source code is governed by a BSD-style license |
| * that can be found in the LICENSE file in the root of the source |
| * tree. An additional intellectual property rights grant can be found |
| * in the file PATENTS. All contributing project authors may |
| * be found in the AUTHORS file in the root of the source tree. |
| */ |
| |
| |
| /* Abstract AVL Tree Generic C Package. |
| ** Implementation generation header file. |
| ** |
| ** This code is in the public domain. See cavl_tree.html for interface |
| ** documentation. |
| ** |
| ** Version: 1.5 Author: Walt Karas |
| */ |
| |
| #undef L_ |
| #undef L_EST_LONG_BIT |
| #undef L_SIZE |
| #undef l_tree |
| #undef L_MASK_HIGH_BIT |
| #undef L_LONG_BIT |
| #undef L_BIT_ARR_DEFN |
| #undef L_BIT_ARR_VAL |
| #undef L_BIT_ARR_0 |
| #undef L_BIT_ARR_1 |
| #undef L_BIT_ARR_ALL |
| #undef L_BIT_ARR_LONGS |
| #undef L_IMPL_MASK |
| #undef L_CHECK_READ_ERROR |
| #undef L_CHECK_READ_ERROR_INV_DEPTH |
| #undef L_SC |
| #undef L_BALANCE_PARAM_PREFIX |
| |
| #ifdef AVL_UNIQUE |
| |
| #define L_ AVL_UNIQUE |
| |
| #else |
| |
| #define L_(X) X |
| |
| #endif |
| |
| /* Determine correct storage class for functions */ |
| #ifdef AVL_PRIVATE |
| |
| #define L_SC static |
| |
| #else |
| |
| #define L_SC |
| |
| #endif |
| |
| #ifdef AVL_SIZE |
| |
| #define L_SIZE AVL_SIZE |
| |
| #else |
| |
| #define L_SIZE unsigned long |
| |
| #endif |
| |
| #define L_MASK_HIGH_BIT ((int) ~ ((~ (unsigned) 0) >> 1)) |
| |
| /* ANSI C/ISO C++ require that a long have at least 32 bits. Set |
| ** L_EST_LONG_BIT to be the greatest multiple of 8 in the range |
| ** 32 - 64 (inclusive) that is less than or equal to the number of |
| ** bits in a long. |
| */ |
| |
| #if (((LONG_MAX >> 31) >> 7) == 0) |
| |
| #define L_EST_LONG_BIT 32 |
| |
| #elif (((LONG_MAX >> 31) >> 15) == 0) |
| |
| #define L_EST_LONG_BIT 40 |
| |
| #elif (((LONG_MAX >> 31) >> 23) == 0) |
| |
| #define L_EST_LONG_BIT 48 |
| |
| #elif (((LONG_MAX >> 31) >> 31) == 0) |
| |
| #define L_EST_LONG_BIT 56 |
| |
| #else |
| |
| #define L_EST_LONG_BIT 64 |
| |
| #endif |
| |
| #define L_LONG_BIT (sizeof(long) * CHAR_BIT) |
| |
| #if ((AVL_MAX_DEPTH) > L_EST_LONG_BIT) |
| |
| /* The maximum depth may be greater than the number of bits in a long, |
| ** so multiple longs are needed to hold a bit array indexed by node |
| ** depth. */ |
| |
| #define L_BIT_ARR_LONGS (((AVL_MAX_DEPTH) + L_LONG_BIT - 1) / L_LONG_BIT) |
| |
| #define L_BIT_ARR_DEFN(NAME) unsigned long NAME[L_BIT_ARR_LONGS]; |
| |
| #define L_BIT_ARR_VAL(BIT_ARR, BIT_NUM) \ |
| ((BIT_ARR)[(BIT_NUM) / L_LONG_BIT] & (1L << ((BIT_NUM) % L_LONG_BIT))) |
| |
| #define L_BIT_ARR_0(BIT_ARR, BIT_NUM) \ |
| (BIT_ARR)[(BIT_NUM) / L_LONG_BIT] &= ~(1L << ((BIT_NUM) % L_LONG_BIT)); |
| |
| #define L_BIT_ARR_1(BIT_ARR, BIT_NUM) \ |
| (BIT_ARR)[(BIT_NUM) / L_LONG_BIT] |= 1L << ((BIT_NUM) % L_LONG_BIT); |
| |
| #define L_BIT_ARR_ALL(BIT_ARR, BIT_VAL) \ |
| { int i = L_BIT_ARR_LONGS; do (BIT_ARR)[--i] = 0L - (BIT_VAL); while(i); } |
| |
| #else /* The bit array can definitely fit in one long */ |
| |
| #define L_BIT_ARR_DEFN(NAME) unsigned long NAME; |
| |
| #define L_BIT_ARR_VAL(BIT_ARR, BIT_NUM) ((BIT_ARR) & (1L << (BIT_NUM))) |
| |
| #define L_BIT_ARR_0(BIT_ARR, BIT_NUM) (BIT_ARR) &= ~(1L << (BIT_NUM)); |
| |
| #define L_BIT_ARR_1(BIT_ARR, BIT_NUM) (BIT_ARR) |= 1L << (BIT_NUM); |
| |
| #define L_BIT_ARR_ALL(BIT_ARR, BIT_VAL) (BIT_ARR) = 0L - (BIT_VAL); |
| |
| #endif |
| |
| #ifdef AVL_READ_ERRORS_HAPPEN |
| |
| #define L_CHECK_READ_ERROR(ERROR_RETURN) \ |
| { if (AVL_READ_ERROR) return(ERROR_RETURN); } |
| |
| #else |
| |
| #define L_CHECK_READ_ERROR(ERROR_RETURN) |
| |
| #endif |
| |
| /* The presumed reason that an instantiation places additional fields |
| ** inside the AVL tree structure is that the SET_ and GET_ macros |
| ** need these fields. The "balance" function does not explicitly use |
| ** any fields in the AVL tree structure, so only pass an AVL tree |
| ** structure pointer to "balance" if it has instantiation-specific |
| ** fields that are (presumably) needed by the SET_/GET_ calls within |
| ** "balance". |
| */ |
| #ifdef AVL_INSIDE_STRUCT |
| |
| #define L_BALANCE_PARAM_CALL_PREFIX l_tree, |
| #define L_BALANCE_PARAM_DECL_PREFIX L_(avl) *l_tree, |
| |
| #else |
| |
| #define L_BALANCE_PARAM_CALL_PREFIX |
| #define L_BALANCE_PARAM_DECL_PREFIX |
| |
| #endif |
| |
| #ifdef AVL_IMPL_MASK |
| |
| #define L_IMPL_MASK (AVL_IMPL_MASK) |
| |
| #else |
| |
| /* Define all functions. */ |
| #define L_IMPL_MASK AVL_IMPL_ALL |
| |
| #endif |
| |
| #if (L_IMPL_MASK & AVL_IMPL_INIT) |
| |
| L_SC void L_(init)(L_(avl) *l_tree) |
| { |
| l_tree->root = AVL_NULL; |
| } |
| |
| #endif |
| |
| #if (L_IMPL_MASK & AVL_IMPL_IS_EMPTY) |
| |
| L_SC int L_(is_empty)(L_(avl) *l_tree) |
| { |
| return(l_tree->root == AVL_NULL); |
| } |
| |
| #endif |
| |
| /* Put the private balance function in the same compilation module as |
| ** the insert function. */ |
| #if (L_IMPL_MASK & AVL_IMPL_INSERT) |
| |
| /* Balances subtree, returns handle of root node of subtree after balancing. |
| */ |
| L_SC AVL_HANDLE L_(balance)(L_BALANCE_PARAM_DECL_PREFIX AVL_HANDLE bal_h) |
| { |
| AVL_HANDLE deep_h; |
| |
| /* Either the "greater than" or the "less than" subtree of |
| ** this node has to be 2 levels deeper (or else it wouldn't |
| ** need balancing). |
| */ |
| if (AVL_GET_BALANCE_FACTOR(bal_h) > 0) |
| { |
| /* "Greater than" subtree is deeper. */ |
| |
| deep_h = AVL_GET_GREATER(bal_h, 1); |
| |
| L_CHECK_READ_ERROR(AVL_NULL) |
| |
| if (AVL_GET_BALANCE_FACTOR(deep_h) < 0) |
| { |
| int bf; |
| |
| AVL_HANDLE old_h = bal_h; |
| bal_h = AVL_GET_LESS(deep_h, 1); |
| L_CHECK_READ_ERROR(AVL_NULL) |
| AVL_SET_GREATER(old_h, AVL_GET_LESS(bal_h, 1)) |
| AVL_SET_LESS(deep_h, AVL_GET_GREATER(bal_h, 1)) |
| AVL_SET_LESS(bal_h, old_h) |
| AVL_SET_GREATER(bal_h, deep_h) |
| |
| bf = AVL_GET_BALANCE_FACTOR(bal_h); |
| |
| if (bf != 0) |
| { |
| if (bf > 0) |
| { |
| AVL_SET_BALANCE_FACTOR(old_h, -1) |
| AVL_SET_BALANCE_FACTOR(deep_h, 0) |
| } |
| else |
| { |
| AVL_SET_BALANCE_FACTOR(deep_h, 1) |
| AVL_SET_BALANCE_FACTOR(old_h, 0) |
| } |
| |
| AVL_SET_BALANCE_FACTOR(bal_h, 0) |
| } |
| else |
| { |
| AVL_SET_BALANCE_FACTOR(old_h, 0) |
| AVL_SET_BALANCE_FACTOR(deep_h, 0) |
| } |
| } |
| else |
| { |
| AVL_SET_GREATER(bal_h, AVL_GET_LESS(deep_h, 0)) |
| AVL_SET_LESS(deep_h, bal_h) |
| |
| if (AVL_GET_BALANCE_FACTOR(deep_h) == 0) |
| { |
| AVL_SET_BALANCE_FACTOR(deep_h, -1) |
| AVL_SET_BALANCE_FACTOR(bal_h, 1) |
| } |
| else |
| { |
| AVL_SET_BALANCE_FACTOR(deep_h, 0) |
| AVL_SET_BALANCE_FACTOR(bal_h, 0) |
| } |
| |
| bal_h = deep_h; |
| } |
| } |
| else |
| { |
| /* "Less than" subtree is deeper. */ |
| |
| deep_h = AVL_GET_LESS(bal_h, 1); |
| L_CHECK_READ_ERROR(AVL_NULL) |
| |
| if (AVL_GET_BALANCE_FACTOR(deep_h) > 0) |
| { |
| int bf; |
| AVL_HANDLE old_h = bal_h; |
| bal_h = AVL_GET_GREATER(deep_h, 1); |
| L_CHECK_READ_ERROR(AVL_NULL) |
| AVL_SET_LESS(old_h, AVL_GET_GREATER(bal_h, 0)) |
| AVL_SET_GREATER(deep_h, AVL_GET_LESS(bal_h, 0)) |
| AVL_SET_GREATER(bal_h, old_h) |
| AVL_SET_LESS(bal_h, deep_h) |
| |
| bf = AVL_GET_BALANCE_FACTOR(bal_h); |
| |
| if (bf != 0) |
| { |
| if (bf < 0) |
| { |
| AVL_SET_BALANCE_FACTOR(old_h, 1) |
| AVL_SET_BALANCE_FACTOR(deep_h, 0) |
| } |
| else |
| { |
| AVL_SET_BALANCE_FACTOR(deep_h, -1) |
| AVL_SET_BALANCE_FACTOR(old_h, 0) |
| } |
| |
| AVL_SET_BALANCE_FACTOR(bal_h, 0) |
| } |
| else |
| { |
| AVL_SET_BALANCE_FACTOR(old_h, 0) |
| AVL_SET_BALANCE_FACTOR(deep_h, 0) |
| } |
| } |
| else |
| { |
| AVL_SET_LESS(bal_h, AVL_GET_GREATER(deep_h, 0)) |
| AVL_SET_GREATER(deep_h, bal_h) |
| |
| if (AVL_GET_BALANCE_FACTOR(deep_h) == 0) |
| { |
| AVL_SET_BALANCE_FACTOR(deep_h, 1) |
| AVL_SET_BALANCE_FACTOR(bal_h, -1) |
| } |
| else |
| { |
| AVL_SET_BALANCE_FACTOR(deep_h, 0) |
| AVL_SET_BALANCE_FACTOR(bal_h, 0) |
| } |
| |
| bal_h = deep_h; |
| } |
| } |
| |
| return(bal_h); |
| } |
| |
| L_SC AVL_HANDLE L_(insert)(L_(avl) *l_tree, AVL_HANDLE h) |
| { |
| AVL_SET_LESS(h, AVL_NULL) |
| AVL_SET_GREATER(h, AVL_NULL) |
| AVL_SET_BALANCE_FACTOR(h, 0) |
| |
| if (l_tree->root == AVL_NULL) |
| l_tree->root = h; |
| else |
| { |
| /* Last unbalanced node encountered in search for insertion point. */ |
| AVL_HANDLE unbal = AVL_NULL; |
| /* Parent of last unbalanced node. */ |
| AVL_HANDLE parent_unbal = AVL_NULL; |
| /* Balance factor of last unbalanced node. */ |
| int unbal_bf; |
| |
| /* Zero-based depth in tree. */ |
| unsigned depth = 0, unbal_depth = 0; |
| |
| /* Records a path into the tree. If bit n is true, indicates |
| ** take greater branch from the nth node in the path, otherwise |
| ** take the less branch. bit 0 gives branch from root, and |
| ** so on. */ |
| L_BIT_ARR_DEFN(branch) |
| |
| AVL_HANDLE hh = l_tree->root; |
| AVL_HANDLE parent = AVL_NULL; |
| int cmp; |
| |
| do |
| { |
| if (AVL_GET_BALANCE_FACTOR(hh) != 0) |
| { |
| unbal = hh; |
| parent_unbal = parent; |
| unbal_depth = depth; |
| } |
| |
| cmp = AVL_COMPARE_NODE_NODE(h, hh); |
| |
| if (cmp == 0) |
| /* Duplicate key. */ |
| return(hh); |
| |
| parent = hh; |
| |
| if (cmp > 0) |
| { |
| hh = AVL_GET_GREATER(hh, 1); |
| L_BIT_ARR_1(branch, depth) |
| } |
| else |
| { |
| hh = AVL_GET_LESS(hh, 1); |
| L_BIT_ARR_0(branch, depth) |
| } |
| |
| L_CHECK_READ_ERROR(AVL_NULL) |
| depth++; |
| } |
| while (hh != AVL_NULL); |
| |
| /* Add node to insert as leaf of tree. */ |
| if (cmp < 0) |
| AVL_SET_LESS(parent, h) |
| else |
| AVL_SET_GREATER(parent, h) |
| |
| depth = unbal_depth; |
| |
| if (unbal == AVL_NULL) |
| hh = l_tree->root; |
| else |
| { |
| cmp = L_BIT_ARR_VAL(branch, depth) ? 1 : -1; |
| depth++; |
| unbal_bf = AVL_GET_BALANCE_FACTOR(unbal); |
| |
| if (cmp < 0) |
| unbal_bf--; |
| else /* cmp > 0 */ |
| unbal_bf++; |
| |
| hh = cmp < 0 ? AVL_GET_LESS(unbal, 1) : AVL_GET_GREATER(unbal, 1); |
| L_CHECK_READ_ERROR(AVL_NULL) |
| |
| if ((unbal_bf != -2) && (unbal_bf != 2)) |
| { |
| /* No rebalancing of tree is necessary. */ |
| AVL_SET_BALANCE_FACTOR(unbal, unbal_bf) |
| unbal = AVL_NULL; |
| } |
| } |
| |
| if (hh != AVL_NULL) |
| while (h != hh) |
| { |
| cmp = L_BIT_ARR_VAL(branch, depth) ? 1 : -1; |
| depth++; |
| |
| if (cmp < 0) |
| { |
| AVL_SET_BALANCE_FACTOR(hh, -1) |
| hh = AVL_GET_LESS(hh, 1); |
| } |
| else /* cmp > 0 */ |
| { |
| AVL_SET_BALANCE_FACTOR(hh, 1) |
| hh = AVL_GET_GREATER(hh, 1); |
| } |
| |
| L_CHECK_READ_ERROR(AVL_NULL) |
| } |
| |
| if (unbal != AVL_NULL) |
| { |
| unbal = L_(balance)(L_BALANCE_PARAM_CALL_PREFIX unbal); |
| L_CHECK_READ_ERROR(AVL_NULL) |
| |
| if (parent_unbal == AVL_NULL) |
| l_tree->root = unbal; |
| else |
| { |
| depth = unbal_depth - 1; |
| cmp = L_BIT_ARR_VAL(branch, depth) ? 1 : -1; |
| |
| if (cmp < 0) |
| AVL_SET_LESS(parent_unbal, unbal) |
| else /* cmp > 0 */ |
| AVL_SET_GREATER(parent_unbal, unbal) |
| } |
| } |
| |
| } |
| |
| return(h); |
| } |
| |
| #endif |
| |
| #if (L_IMPL_MASK & AVL_IMPL_SEARCH) |
| |
| L_SC AVL_HANDLE L_(search)(L_(avl) *l_tree, AVL_KEY k, avl_search_type st) |
| { |
| int cmp, target_cmp; |
| AVL_HANDLE match_h = AVL_NULL; |
| AVL_HANDLE h = l_tree->root; |
| |
| if (st & AVL_LESS) |
| target_cmp = 1; |
| else if (st & AVL_GREATER) |
| target_cmp = -1; |
| else |
| target_cmp = 0; |
| |
| while (h != AVL_NULL) |
| { |
| cmp = AVL_COMPARE_KEY_NODE(k, h); |
| |
| if (cmp == 0) |
| { |
| if (st & AVL_EQUAL) |
| { |
| match_h = h; |
| break; |
| } |
| |
| cmp = -target_cmp; |
| } |
| else if (target_cmp != 0) |
| if (!((cmp ^ target_cmp) & L_MASK_HIGH_BIT)) |
| /* cmp and target_cmp are both positive or both negative. */ |
| match_h = h; |
| |
| h = cmp < 0 ? AVL_GET_LESS(h, 1) : AVL_GET_GREATER(h, 1); |
| L_CHECK_READ_ERROR(AVL_NULL) |
| } |
| |
| return(match_h); |
| } |
| |
| #endif |
| |
| #if (L_IMPL_MASK & AVL_IMPL_SEARCH_LEAST) |
| |
| L_SC AVL_HANDLE L_(search_least)(L_(avl) *l_tree) |
| { |
| AVL_HANDLE h = l_tree->root; |
| AVL_HANDLE parent = AVL_NULL; |
| |
| while (h != AVL_NULL) |
| { |
| parent = h; |
| h = AVL_GET_LESS(h, 1); |
| L_CHECK_READ_ERROR(AVL_NULL) |
| } |
| |
| return(parent); |
| } |
| |
| #endif |
| |
| #if (L_IMPL_MASK & AVL_IMPL_SEARCH_GREATEST) |
| |
| L_SC AVL_HANDLE L_(search_greatest)(L_(avl) *l_tree) |
| { |
| AVL_HANDLE h = l_tree->root; |
| AVL_HANDLE parent = AVL_NULL; |
| |
| while (h != AVL_NULL) |
| { |
| parent = h; |
| h = AVL_GET_GREATER(h, 1); |
| L_CHECK_READ_ERROR(AVL_NULL) |
| } |
| |
| return(parent); |
| } |
| |
| #endif |
| |
| #if (L_IMPL_MASK & AVL_IMPL_REMOVE) |
| |
| /* Prototype of balance function (called by remove) in case not in |
| ** same compilation unit. |
| */ |
| L_SC AVL_HANDLE L_(balance)(L_BALANCE_PARAM_DECL_PREFIX AVL_HANDLE bal_h); |
| |
| L_SC AVL_HANDLE L_(remove)(L_(avl) *l_tree, AVL_KEY k) |
| { |
| /* Zero-based depth in tree. */ |
| unsigned depth = 0, rm_depth; |
| |
| /* Records a path into the tree. If bit n is true, indicates |
| ** take greater branch from the nth node in the path, otherwise |
| ** take the less branch. bit 0 gives branch from root, and |
| ** so on. */ |
| L_BIT_ARR_DEFN(branch) |
| |
| AVL_HANDLE h = l_tree->root; |
| AVL_HANDLE parent = AVL_NULL; |
| AVL_HANDLE child; |
| AVL_HANDLE path; |
| int cmp, cmp_shortened_sub_with_path; |
| int reduced_depth; |
| int bf; |
| AVL_HANDLE rm; |
| AVL_HANDLE parent_rm; |
| |
| for (; ;) |
| { |
| if (h == AVL_NULL) |
| /* No node in tree with given key. */ |
| return(AVL_NULL); |
| |
| cmp = AVL_COMPARE_KEY_NODE(k, h); |
| |
| if (cmp == 0) |
| /* Found node to remove. */ |
| break; |
| |
| parent = h; |
| |
| if (cmp > 0) |
| { |
| h = AVL_GET_GREATER(h, 1); |
| L_BIT_ARR_1(branch, depth) |
| } |
| else |
| { |
| h = AVL_GET_LESS(h, 1); |
| L_BIT_ARR_0(branch, depth) |
| } |
| |
| L_CHECK_READ_ERROR(AVL_NULL) |
| depth++; |
| cmp_shortened_sub_with_path = cmp; |
| } |
| |
| rm = h; |
| parent_rm = parent; |
| rm_depth = depth; |
| |
| /* If the node to remove is not a leaf node, we need to get a |
| ** leaf node, or a node with a single leaf as its child, to put |
| ** in the place of the node to remove. We will get the greatest |
| ** node in the less subtree (of the node to remove), or the least |
| ** node in the greater subtree. We take the leaf node from the |
| ** deeper subtree, if there is one. */ |
| |
| if (AVL_GET_BALANCE_FACTOR(h) < 0) |
| { |
| child = AVL_GET_LESS(h, 1); |
| L_BIT_ARR_0(branch, depth) |
| cmp = -1; |
| } |
| else |
| { |
| child = AVL_GET_GREATER(h, 1); |
| L_BIT_ARR_1(branch, depth) |
| cmp = 1; |
| } |
| |
| L_CHECK_READ_ERROR(AVL_NULL) |
| depth++; |
| |
| if (child != AVL_NULL) |
| { |
| cmp = -cmp; |
| |
| do |
| { |
| parent = h; |
| h = child; |
| |
| if (cmp < 0) |
| { |
| child = AVL_GET_LESS(h, 1); |
| L_BIT_ARR_0(branch, depth) |
| } |
| else |
| { |
| child = AVL_GET_GREATER(h, 1); |
| L_BIT_ARR_1(branch, depth) |
| } |
| |
| L_CHECK_READ_ERROR(AVL_NULL) |
| depth++; |
| } |
| while (child != AVL_NULL); |
| |
| if (parent == rm) |
| /* Only went through do loop once. Deleted node will be replaced |
| ** in the tree structure by one of its immediate children. */ |
| cmp_shortened_sub_with_path = -cmp; |
| else |
| cmp_shortened_sub_with_path = cmp; |
| |
| /* Get the handle of the opposite child, which may not be null. */ |
| child = cmp > 0 ? AVL_GET_LESS(h, 0) : AVL_GET_GREATER(h, 0); |
| } |
| |
| if (parent == AVL_NULL) |
| /* There were only 1 or 2 nodes in this tree. */ |
| l_tree->root = child; |
| else if (cmp_shortened_sub_with_path < 0) |
| AVL_SET_LESS(parent, child) |
| else |
| AVL_SET_GREATER(parent, child) |
| |
| /* "path" is the parent of the subtree being eliminated or reduced |
| ** from a depth of 2 to 1. If "path" is the node to be removed, we |
| ** set path to the node we're about to poke into the position of the |
| ** node to be removed. */ |
| path = parent == rm ? h : parent; |
| |
| if (h != rm) |
| { |
| /* Poke in the replacement for the node to be removed. */ |
| AVL_SET_LESS(h, AVL_GET_LESS(rm, 0)) |
| AVL_SET_GREATER(h, AVL_GET_GREATER(rm, 0)) |
| AVL_SET_BALANCE_FACTOR(h, AVL_GET_BALANCE_FACTOR(rm)) |
| |
| if (parent_rm == AVL_NULL) |
| l_tree->root = h; |
| else |
| { |
| depth = rm_depth - 1; |
| |
| if (L_BIT_ARR_VAL(branch, depth)) |
| AVL_SET_GREATER(parent_rm, h) |
| else |
| AVL_SET_LESS(parent_rm, h) |
| } |
| } |
| |
| if (path != AVL_NULL) |
| { |
| /* Create a temporary linked list from the parent of the path node |
| ** to the root node. */ |
| h = l_tree->root; |
| parent = AVL_NULL; |
| depth = 0; |
| |
| while (h != path) |
| { |
| if (L_BIT_ARR_VAL(branch, depth)) |
| { |
| child = AVL_GET_GREATER(h, 1); |
| AVL_SET_GREATER(h, parent) |
| } |
| else |
| { |
| child = AVL_GET_LESS(h, 1); |
| AVL_SET_LESS(h, parent) |
| } |
| |
| L_CHECK_READ_ERROR(AVL_NULL) |
| depth++; |
| parent = h; |
| h = child; |
| } |
| |
| /* Climb from the path node to the root node using the linked |
| ** list, restoring the tree structure and rebalancing as necessary. |
| */ |
| reduced_depth = 1; |
| cmp = cmp_shortened_sub_with_path; |
| |
| for (; ;) |
| { |
| if (reduced_depth) |
| { |
| bf = AVL_GET_BALANCE_FACTOR(h); |
| |
| if (cmp < 0) |
| bf++; |
| else /* cmp > 0 */ |
| bf--; |
| |
| if ((bf == -2) || (bf == 2)) |
| { |
| h = L_(balance)(L_BALANCE_PARAM_CALL_PREFIX h); |
| L_CHECK_READ_ERROR(AVL_NULL) |
| bf = AVL_GET_BALANCE_FACTOR(h); |
| } |
| else |
| AVL_SET_BALANCE_FACTOR(h, bf) |
| reduced_depth = (bf == 0); |
| } |
| |
| if (parent == AVL_NULL) |
| break; |
| |
| child = h; |
| h = parent; |
| depth--; |
| cmp = L_BIT_ARR_VAL(branch, depth) ? 1 : -1; |
| |
| if (cmp < 0) |
| { |
| parent = AVL_GET_LESS(h, 1); |
| AVL_SET_LESS(h, child) |
| } |
| else |
| { |
| parent = AVL_GET_GREATER(h, 1); |
| AVL_SET_GREATER(h, child) |
| } |
| |
| L_CHECK_READ_ERROR(AVL_NULL) |
| } |
| |
| l_tree->root = h; |
| } |
| |
| return(rm); |
| } |
| |
| #endif |
| |
| #if (L_IMPL_MASK & AVL_IMPL_SUBST) |
| |
| L_SC AVL_HANDLE L_(subst)(L_(avl) *l_tree, AVL_HANDLE new_node) |
| { |
| AVL_HANDLE h = l_tree->root; |
| AVL_HANDLE parent = AVL_NULL; |
| int cmp, last_cmp; |
| |
| /* Search for node already in tree with same key. */ |
| for (; ;) |
| { |
| if (h == AVL_NULL) |
| /* No node in tree with same key as new node. */ |
| return(AVL_NULL); |
| |
| cmp = AVL_COMPARE_NODE_NODE(new_node, h); |
| |
| if (cmp == 0) |
| /* Found the node to substitute new one for. */ |
| break; |
| |
| last_cmp = cmp; |
| parent = h; |
| h = cmp < 0 ? AVL_GET_LESS(h, 1) : AVL_GET_GREATER(h, 1); |
| L_CHECK_READ_ERROR(AVL_NULL) |
| } |
| |
| /* Copy tree housekeeping fields from node in tree to new node. */ |
| AVL_SET_LESS(new_node, AVL_GET_LESS(h, 0)) |
| AVL_SET_GREATER(new_node, AVL_GET_GREATER(h, 0)) |
| AVL_SET_BALANCE_FACTOR(new_node, AVL_GET_BALANCE_FACTOR(h)) |
| |
| if (parent == AVL_NULL) |
| /* New node is also new root. */ |
| l_tree->root = new_node; |
| else |
| { |
| /* Make parent point to new node. */ |
| if (last_cmp < 0) |
| AVL_SET_LESS(parent, new_node) |
| else |
| AVL_SET_GREATER(parent, new_node) |
| } |
| |
| return(h); |
| } |
| |
| #endif |
| |
| #ifdef AVL_BUILD_ITER_TYPE |
| |
| #if (L_IMPL_MASK & AVL_IMPL_BUILD) |
| |
| L_SC int L_(build)( |
| L_(avl) *l_tree, AVL_BUILD_ITER_TYPE p, L_SIZE num_nodes) |
| { |
| /* Gives path to subtree being built. If bit n is false, branch |
| ** less from the node at depth n, if true branch greater. */ |
| L_BIT_ARR_DEFN(branch) |
| |
| /* If bit n is true, then for the current subtree at depth n, its |
| ** greater subtree has one more node than its less subtree. */ |
| L_BIT_ARR_DEFN(rem) |
| |
| /* Depth of root node of current subtree. */ |
| unsigned depth = 0; |
| |
| /* Number of nodes in current subtree. */ |
| L_SIZE num_sub = num_nodes; |
| |
| /* The algorithm relies on a stack of nodes whose less subtree has |
| ** been built, but whose greater subtree has not yet been built. |
| ** The stack is implemented as linked list. The nodes are linked |
| ** together by having the "greater" handle of a node set to the |
| ** next node in the list. "less_parent" is the handle of the first |
| ** node in the list. */ |
| AVL_HANDLE less_parent = AVL_NULL; |
| |
| /* h is root of current subtree, child is one of its children. */ |
| AVL_HANDLE h; |
| AVL_HANDLE child; |
| |
| if (num_nodes == 0) |
| { |
| l_tree->root = AVL_NULL; |
| return(1); |
| } |
| |
| for (; ;) |
| { |
| while (num_sub > 2) |
| { |
| /* Subtract one for root of subtree. */ |
| num_sub--; |
| |
| if (num_sub & 1) |
| L_BIT_ARR_1(rem, depth) |
| else |
| L_BIT_ARR_0(rem, depth) |
| L_BIT_ARR_0(branch, depth) |
| depth++; |
| |
| num_sub >>= 1; |
| } |
| |
| if (num_sub == 2) |
| { |
| /* Build a subtree with two nodes, slanting to greater. |
| ** I arbitrarily chose to always have the extra node in the |
| ** greater subtree when there is an odd number of nodes to |
| ** split between the two subtrees. */ |
| |
| h = AVL_BUILD_ITER_VAL(p); |
| L_CHECK_READ_ERROR(0) |
| AVL_BUILD_ITER_INCR(p) |
| child = AVL_BUILD_ITER_VAL(p); |
| L_CHECK_READ_ERROR(0) |
| AVL_BUILD_ITER_INCR(p) |
| AVL_SET_LESS(child, AVL_NULL) |
| AVL_SET_GREATER(child, AVL_NULL) |
| AVL_SET_BALANCE_FACTOR(child, 0) |
| AVL_SET_GREATER(h, child) |
| AVL_SET_LESS(h, AVL_NULL) |
| AVL_SET_BALANCE_FACTOR(h, 1) |
| } |
| else /* num_sub == 1 */ |
| { |
| /* Build a subtree with one node. */ |
| |
| h = AVL_BUILD_ITER_VAL(p); |
| L_CHECK_READ_ERROR(0) |
| AVL_BUILD_ITER_INCR(p) |
| AVL_SET_LESS(h, AVL_NULL) |
| AVL_SET_GREATER(h, AVL_NULL) |
| AVL_SET_BALANCE_FACTOR(h, 0) |
| } |
| |
| while (depth) |
| { |
| depth--; |
| |
| if (!L_BIT_ARR_VAL(branch, depth)) |
| /* We've completed a less subtree. */ |
| break; |
| |
| /* We've completed a greater subtree, so attach it to |
| ** its parent (that is less than it). We pop the parent |
| ** off the stack of less parents. */ |
| child = h; |
| h = less_parent; |
| less_parent = AVL_GET_GREATER(h, 1); |
| L_CHECK_READ_ERROR(0) |
| AVL_SET_GREATER(h, child) |
| /* num_sub = 2 * (num_sub - rem[depth]) + rem[depth] + 1 */ |
| num_sub <<= 1; |
| num_sub += L_BIT_ARR_VAL(rem, depth) ? 0 : 1; |
| |
| if (num_sub & (num_sub - 1)) |
| /* num_sub is not a power of 2. */ |
| AVL_SET_BALANCE_FACTOR(h, 0) |
| else |
| /* num_sub is a power of 2. */ |
| AVL_SET_BALANCE_FACTOR(h, 1) |
| } |
| |
| if (num_sub == num_nodes) |
| /* We've completed the full tree. */ |
| break; |
| |
| /* The subtree we've completed is the less subtree of the |
| ** next node in the sequence. */ |
| |
| child = h; |
| h = AVL_BUILD_ITER_VAL(p); |
| L_CHECK_READ_ERROR(0) |
| AVL_BUILD_ITER_INCR(p) |
| AVL_SET_LESS(h, child) |
| |
| /* Put h into stack of less parents. */ |
| AVL_SET_GREATER(h, less_parent) |
| less_parent = h; |
| |
| /* Proceed to creating greater than subtree of h. */ |
| L_BIT_ARR_1(branch, depth) |
| num_sub += L_BIT_ARR_VAL(rem, depth) ? 1 : 0; |
| depth++; |
| |
| } /* end for ( ; ; ) */ |
| |
| l_tree->root = h; |
| |
| return(1); |
| } |
| |
| #endif |
| |
| #endif |
| |
| #if (L_IMPL_MASK & AVL_IMPL_INIT_ITER) |
| |
| /* Initialize depth to invalid value, to indicate iterator is |
| ** invalid. (Depth is zero-base.) It's not necessary to initialize |
| ** iterators prior to passing them to the "start" function. |
| */ |
| L_SC void L_(init_iter)(L_(iter) *iter) |
| { |
| iter->depth = ~0; |
| } |
| |
| #endif |
| |
| #ifdef AVL_READ_ERRORS_HAPPEN |
| |
| #define L_CHECK_READ_ERROR_INV_DEPTH \ |
| { if (AVL_READ_ERROR) { iter->depth = ~0; return; } } |
| |
| #else |
| |
| #define L_CHECK_READ_ERROR_INV_DEPTH |
| |
| #endif |
| |
| #if (L_IMPL_MASK & AVL_IMPL_START_ITER) |
| |
| L_SC void L_(start_iter)( |
| L_(avl) *l_tree, L_(iter) *iter, AVL_KEY k, avl_search_type st) |
| { |
| AVL_HANDLE h = l_tree->root; |
| unsigned d = 0; |
| int cmp, target_cmp; |
| |
| /* Save the tree that we're going to iterate through in a |
| ** member variable. */ |
| iter->tree_ = l_tree; |
| |
| iter->depth = ~0; |
| |
| if (h == AVL_NULL) |
| /* Tree is empty. */ |
| return; |
| |
| if (st & AVL_LESS) |
| /* Key can be greater than key of starting node. */ |
| target_cmp = 1; |
| else if (st & AVL_GREATER) |
| /* Key can be less than key of starting node. */ |
| target_cmp = -1; |
| else |
| /* Key must be same as key of starting node. */ |
| target_cmp = 0; |
| |
| for (; ;) |
| { |
| cmp = AVL_COMPARE_KEY_NODE(k, h); |
| |
| if (cmp == 0) |
| { |
| if (st & AVL_EQUAL) |
| { |
| /* Equal node was sought and found as starting node. */ |
| iter->depth = d; |
| break; |
| } |
| |
| cmp = -target_cmp; |
| } |
| else if (target_cmp != 0) |
| if (!((cmp ^ target_cmp) & L_MASK_HIGH_BIT)) |
| /* cmp and target_cmp are both negative or both positive. */ |
| iter->depth = d; |
| |
| h = cmp < 0 ? AVL_GET_LESS(h, 1) : AVL_GET_GREATER(h, 1); |
| L_CHECK_READ_ERROR_INV_DEPTH |
| |
| if (h == AVL_NULL) |
| break; |
| |
| if (cmp > 0) |
| L_BIT_ARR_1(iter->branch, d) |
| else |
| L_BIT_ARR_0(iter->branch, d) |
| iter->path_h[d++] = h; |
| } |
| } |
| |
| #endif |
| |
| #if (L_IMPL_MASK & AVL_IMPL_START_ITER_LEAST) |
| |
| L_SC void L_(start_iter_least)(L_(avl) *l_tree, L_(iter) *iter) |
| { |
| AVL_HANDLE h = l_tree->root; |
| |
| iter->tree_ = l_tree; |
| |
| iter->depth = ~0; |
| |
| L_BIT_ARR_ALL(iter->branch, 0) |
| |
| while (h != AVL_NULL) |
| { |
| if (iter->depth != ~0) |
| iter->path_h[iter->depth] = h; |
| |
| iter->depth++; |
| h = AVL_GET_LESS(h, 1); |
| L_CHECK_READ_ERROR_INV_DEPTH |
| } |
| } |
| |
| #endif |
| |
| #if (L_IMPL_MASK & AVL_IMPL_START_ITER_GREATEST) |
| |
| L_SC void L_(start_iter_greatest)(L_(avl) *l_tree, L_(iter) *iter) |
| { |
| AVL_HANDLE h = l_tree->root; |
| |
| iter->tree_ = l_tree; |
| |
| iter->depth = ~0; |
| |
| L_BIT_ARR_ALL(iter->branch, 1) |
| |
| while (h != AVL_NULL) |
| { |
| if (iter->depth != ~0) |
| iter->path_h[iter->depth] = h; |
| |
| iter->depth++; |
| h = AVL_GET_GREATER(h, 1); |
| L_CHECK_READ_ERROR_INV_DEPTH |
| } |
| } |
| |
| #endif |
| |
| #if (L_IMPL_MASK & AVL_IMPL_GET_ITER) |
| |
| L_SC AVL_HANDLE L_(get_iter)(L_(iter) *iter) |
| { |
| if (iter->depth == ~0) |
| return(AVL_NULL); |
| |
| return(iter->depth == 0 ? |
| iter->tree_->root : iter->path_h[iter->depth - 1]); |
| } |
| |
| #endif |
| |
| #if (L_IMPL_MASK & AVL_IMPL_INCR_ITER) |
| |
| L_SC void L_(incr_iter)(L_(iter) *iter) |
| { |
| #define l_tree (iter->tree_) |
| |
| if (iter->depth != ~0) |
| { |
| AVL_HANDLE h = |
| AVL_GET_GREATER((iter->depth == 0 ? |
| iter->tree_->root : iter->path_h[iter->depth - 1]), 1); |
| L_CHECK_READ_ERROR_INV_DEPTH |
| |
| if (h == AVL_NULL) |
| do |
| { |
| if (iter->depth == 0) |
| { |
| iter->depth = ~0; |
| break; |
| } |
| |
| iter->depth--; |
| } |
| while (L_BIT_ARR_VAL(iter->branch, iter->depth)); |
| else |
| { |
| L_BIT_ARR_1(iter->branch, iter->depth) |
| iter->path_h[iter->depth++] = h; |
| |
| for (; ;) |
| { |
| h = AVL_GET_LESS(h, 1); |
| L_CHECK_READ_ERROR_INV_DEPTH |
| |
| if (h == AVL_NULL) |
| break; |
| |
| L_BIT_ARR_0(iter->branch, iter->depth) |
| iter->path_h[iter->depth++] = h; |
| } |
| } |
| } |
| |
| #undef l_tree |
| } |
| |
| #endif |
| |
| #if (L_IMPL_MASK & AVL_IMPL_DECR_ITER) |
| |
| L_SC void L_(decr_iter)(L_(iter) *iter) |
| { |
| #define l_tree (iter->tree_) |
| |
| if (iter->depth != ~0) |
| { |
| AVL_HANDLE h = |
| AVL_GET_LESS((iter->depth == 0 ? |
| iter->tree_->root : iter->path_h[iter->depth - 1]), 1); |
| L_CHECK_READ_ERROR_INV_DEPTH |
| |
| if (h == AVL_NULL) |
| do |
| { |
| if (iter->depth == 0) |
| { |
| iter->depth = ~0; |
| break; |
| } |
| |
| iter->depth--; |
| } |
| while (!L_BIT_ARR_VAL(iter->branch, iter->depth)); |
| else |
| { |
| L_BIT_ARR_0(iter->branch, iter->depth) |
| iter->path_h[iter->depth++] = h; |
| |
| for (; ;) |
| { |
| h = AVL_GET_GREATER(h, 1); |
| L_CHECK_READ_ERROR_INV_DEPTH |
| |
| if (h == AVL_NULL) |
| break; |
| |
| L_BIT_ARR_1(iter->branch, iter->depth) |
| iter->path_h[iter->depth++] = h; |
| } |
| } |
| } |
| |
| #undef l_tree |
| } |
| |
| #endif |
| |
| /* Tidy up the preprocessor symbol name space. */ |
| #undef L_ |
| #undef L_EST_LONG_BIT |
| #undef L_SIZE |
| #undef L_MASK_HIGH_BIT |
| #undef L_LONG_BIT |
| #undef L_BIT_ARR_DEFN |
| #undef L_BIT_ARR_VAL |
| #undef L_BIT_ARR_0 |
| #undef L_BIT_ARR_1 |
| #undef L_BIT_ARR_ALL |
| #undef L_CHECK_READ_ERROR |
| #undef L_CHECK_READ_ERROR_INV_DEPTH |
| #undef L_BIT_ARR_LONGS |
| #undef L_IMPL_MASK |
| #undef L_CHECK_READ_ERROR |
| #undef L_CHECK_READ_ERROR_INV_DEPTH |
| #undef L_SC |
| #undef L_BALANCE_PARAM_CALL_PREFIX |
| #undef L_BALANCE_PARAM_DECL_PREFIX |
