Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(34)

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: source/libvpx/vpx_mem/memory_manager/include/cavl_impl.h

Issue 11555023: libvpx: Add VP9 decoder. (Closed) Base URL: svn://chrome-svn/chrome/trunk/deps/third_party/libvpx/
Patch Set: Created 8 years ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« libvpx.gyp ('K') | « source/libvpx/vpx_mem/memory_manager/include/cavl_if.h ('k') | source/libvpx/vpx_mem/memory_manager/include/heapmm.h » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: source/libvpx/vpx_mem/memory_manager/include/cavl_impl.h
===================================================================
--- source/libvpx/vpx_mem/memory_manager/include/cavl_impl.h (revision 172621)
+++ source/libvpx/vpx_mem/memory_manager/include/cavl_impl.h (working copy)
@@ -110,16 +110,16 @@
#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)))
+ ((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));
+ (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);
+ (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); }
+ { 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 */
@@ -138,7 +138,7 @@
#ifdef AVL_READ_ERRORS_HAPPEN
#define L_CHECK_READ_ERROR(ERROR_RETURN) \
- { if (AVL_READ_ERROR) return(ERROR_RETURN); }
+ { if (AVL_READ_ERROR) return(ERROR_RETURN); }
#else
@@ -179,18 +179,16 @@
#if (L_IMPL_MASK & AVL_IMPL_INIT)
-L_SC void L_(init)(L_(avl) *l_tree)
-{
- l_tree->root = AVL_NULL;
+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);
+L_SC int L_(is_empty)(L_(avl) *l_tree) {
+ return(l_tree->root == AVL_NULL);
}
#endif
@@ -201,358 +199,305 @@
/* 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;
+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. */
+ /* 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);
+ deep_h = AVL_GET_GREATER(bal_h, 1);
- L_CHECK_READ_ERROR(AVL_NULL)
+ L_CHECK_READ_ERROR(AVL_NULL)
- if (AVL_GET_BALANCE_FACTOR(deep_h) < 0)
- {
- int bf;
+ 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)
+ 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);
+ 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)
- }
+ 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)
}
- 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)
- }
+ 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)
- bal_h = deep_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. */
+ } else {
+ /* "Less than" subtree is deeper. */
- deep_h = AVL_GET_LESS(bal_h, 1);
- L_CHECK_READ_ERROR(AVL_NULL)
+ 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)
+ 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);
+ 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)
- }
+ 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)
}
- 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)
- }
+ 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)
- bal_h = deep_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);
+ 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)
+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;
+ 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;
+ /* 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)
+ /* 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;
+ 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;
- }
+ do {
+ if (AVL_GET_BALANCE_FACTOR(hh) != 0) {
+ unbal = hh;
+ parent_unbal = parent;
+ unbal_depth = depth;
+ }
- cmp = AVL_COMPARE_NODE_NODE(h, hh);
+ cmp = AVL_COMPARE_NODE_NODE(h, hh);
- if (cmp == 0)
- /* Duplicate key. */
- return(hh);
+ if (cmp == 0)
+ /* Duplicate key. */
+ return(hh);
- parent = 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)
- }
+ 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);
+ 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)
+ /* 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;
+ 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 (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++;
+ 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)
+ 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 ((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 (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);
- }
+ 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)
- }
+ 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 (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 (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)
- }
- }
-
+ if (cmp < 0)
+ AVL_SET_LESS(parent_unbal, unbal)
+ else /* cmp > 0 */
+ AVL_SET_GREATER(parent_unbal, unbal)
+ }
}
- return(h);
+ }
+
+ 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;
+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;
+ 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);
+ while (h != AVL_NULL) {
+ cmp = AVL_COMPARE_KEY_NODE(k, h);
- if (cmp == 0)
- {
- if (st & AVL_EQUAL)
- {
- match_h = h;
- break;
- }
+ 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;
+ 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)
- }
+ h = cmp < 0 ? AVL_GET_LESS(h, 1) : AVL_GET_GREATER(h, 1);
+ L_CHECK_READ_ERROR(AVL_NULL)
+ }
- return(match_h);
+ 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;
+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)
- }
+ while (h != AVL_NULL) {
+ parent = h;
+ h = AVL_GET_LESS(h, 1);
+ L_CHECK_READ_ERROR(AVL_NULL)
+ }
- return(parent);
+ 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;
+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)
- }
+ while (h != AVL_NULL) {
+ parent = h;
+ h = AVL_GET_GREATER(h, 1);
+ L_CHECK_READ_ERROR(AVL_NULL)
+ }
- return(parent);
+ return(parent);
}
#endif
@@ -564,284 +509,253 @@
*/
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;
+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)
+ /* 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;
+ 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);
+ for (;;) {
+ if (h == AVL_NULL)
+ /* No node in tree with given key. */
+ return(AVL_NULL);
- cmp = AVL_COMPARE_KEY_NODE(k, h);
+ cmp = AVL_COMPARE_KEY_NODE(k, h);
- if (cmp == 0)
- /* Found node to remove. */
- break;
+ if (cmp == 0)
+ /* Found node to remove. */
+ break;
- parent = h;
+ 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;
+ 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)
}
- rm = h;
- parent_rm = parent;
- rm_depth = depth;
+ L_CHECK_READ_ERROR(AVL_NULL)
+ depth++;
+ cmp_shortened_sub_with_path = cmp;
+ }
- /* 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. */
+ rm = h;
+ parent_rm = parent;
+ rm_depth = depth;
- if (AVL_GET_BALANCE_FACTOR(h) < 0)
- {
+ /* 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)
- cmp = -1;
- }
- else
- {
+ } else {
child = AVL_GET_GREATER(h, 1);
L_BIT_ARR_1(branch, depth)
- cmp = 1;
- }
+ }
- L_CHECK_READ_ERROR(AVL_NULL)
- depth++;
+ L_CHECK_READ_ERROR(AVL_NULL)
+ depth++;
+ } while (child != AVL_NULL);
- if (child != AVL_NULL)
- {
- cmp = -cmp;
+ 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;
- do
- {
- parent = h;
- h = child;
+ /* 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 (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)
- }
+ 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)
- L_CHECK_READ_ERROR(AVL_NULL)
- depth++;
- }
- while (child != AVL_NULL);
+ /* "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 (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;
+ 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))
- /* 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_rm == AVL_NULL)
+ l_tree->root = h;
+ else {
+ depth = rm_depth - 1;
- 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)
+ if (L_BIT_ARR_VAL(branch, depth))
+ AVL_SET_GREATER(parent_rm, h)
else
- AVL_SET_GREATER(parent, child)
+ AVL_SET_LESS(parent_rm, h)
+ }
+ }
- /* "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 (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;
- 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))
+ 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)
+ }
- 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)
- }
+ L_CHECK_READ_ERROR(AVL_NULL)
+ depth++;
+ parent = h;
+ h = child;
}
- 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;
+ /* 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;
- 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)
- }
+ for (;;) {
+ if (reduced_depth) {
+ bf = AVL_GET_BALANCE_FACTOR(h);
- L_CHECK_READ_ERROR(AVL_NULL)
- depth++;
- parent = h;
- h = child;
- }
+ if (cmp < 0)
+ bf++;
+ else /* cmp > 0 */
+ bf--;
- /* 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;
+ 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);
+ }
- for (; ;)
- {
- if (reduced_depth)
- {
- bf = AVL_GET_BALANCE_FACTOR(h);
+ if (parent == AVL_NULL)
+ break;
- if (cmp < 0)
- bf++;
- else /* cmp > 0 */
- bf--;
+ child = h;
+ h = parent;
+ depth--;
+ cmp = L_BIT_ARR_VAL(branch, depth) ? 1 : -1;
- 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 (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)
+ }
- 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;
+ L_CHECK_READ_ERROR(AVL_NULL)
}
- return(rm);
+ 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;
+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);
+ /* 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);
+ cmp = AVL_COMPARE_NODE_NODE(new_node, h);
- if (cmp == 0)
- /* Found the node to substitute new one for. */
- break;
+ 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)
- }
+ 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))
+ /* 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)
- }
+ 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);
+ return(h);
}
#endif
@@ -851,144 +765,136 @@
#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)
+ 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)
+ /* 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;
+ /* Depth of root node of current subtree. */
+ unsigned depth = 0;
- /* Number of nodes in current subtree. */
- L_SIZE num_sub = num_nodes;
+ /* 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;
+ /* 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;
+ /* 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);
- }
+ if (num_nodes == 0) {
+ l_tree->root = AVL_NULL;
+ return(1);
+ }
- for (; ;)
- {
- while (num_sub > 2)
- {
- /* Subtract one for root of subtree. */
- num_sub--;
+ 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++;
+ 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;
- }
+ 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. */
+ 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)
+ 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)
- }
+ 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--;
+ while (depth) {
+ depth--;
- if (!L_BIT_ARR_VAL(branch, depth))
- /* We've completed a less subtree. */
- break;
+ 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;
+ /* 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_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;
+ 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. */
+ /* 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)
+ 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;
+ /* 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++;
+ /* 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 ( ; ; ) */
+ } /* end for (;; ) */
- l_tree->root = h;
+ l_tree->root = h;
- return(1);
+ return(1);
}
#endif
@@ -1001,9 +907,8 @@
** 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;
+L_SC void L_(init_iter)(L_(iter) *iter) {
+ iter->depth = ~0;
}
#endif
@@ -1011,7 +916,7 @@
#ifdef AVL_READ_ERRORS_HAPPEN
#define L_CHECK_READ_ERROR_INV_DEPTH \
- { if (AVL_READ_ERROR) { iter->depth = ~0; return; } }
+ { if (AVL_READ_ERROR) { iter->depth = ~0; return; } }
#else
@@ -1022,174 +927,157 @@
#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;
+ 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;
+ /* Save the tree that we're going to iterate through in a
+ ** member variable. */
+ iter->tree_ = l_tree;
- iter->depth = ~0;
+ iter->depth = ~0;
- if (h == AVL_NULL)
- /* Tree is empty. */
- return;
+ 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;
+ 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);
+ 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;
- }
+ 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;
+ 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
+ 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 (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;
- }
+ 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;
+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->tree_ = l_tree;
- iter->depth = ~0;
+ iter->depth = ~0;
- L_BIT_ARR_ALL(iter->branch, 0)
+ L_BIT_ARR_ALL(iter->branch, 0)
- while (h != AVL_NULL)
- {
- if (iter->depth != ~0)
- iter->path_h[iter->depth] = h;
+ 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
- }
+ 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;
+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->tree_ = l_tree;
- iter->depth = ~0;
+ iter->depth = ~0;
- L_BIT_ARR_ALL(iter->branch, 1)
+ L_BIT_ARR_ALL(iter->branch, 1)
- while (h != AVL_NULL)
- {
- if (iter->depth != ~0)
- iter->path_h[iter->depth] = h;
+ 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
- }
+ 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);
+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]);
+ 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)
-{
+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 (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;
- }
+ 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;
+ 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
+ for (;;) {
+ h = AVL_GET_LESS(h, 1);
+ L_CHECK_READ_ERROR_INV_DEPTH
- if (h == AVL_NULL)
- break;
+ if (h == AVL_NULL)
+ break;
- L_BIT_ARR_0(iter->branch, iter->depth)
- iter->path_h[iter->depth++] = h;
- }
- }
+ L_BIT_ARR_0(iter->branch, iter->depth)
+ iter->path_h[iter->depth++] = h;
+ }
}
+ }
#undef l_tree
}
@@ -1198,47 +1086,40 @@
#if (L_IMPL_MASK & AVL_IMPL_DECR_ITER)
-L_SC void L_(decr_iter)(L_(iter) *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 (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;
- }
+ 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;
+ 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
+ for (;;) {
+ h = AVL_GET_GREATER(h, 1);
+ L_CHECK_READ_ERROR_INV_DEPTH
- if (h == AVL_NULL)
- break;
+ if (h == AVL_NULL)
+ break;
- L_BIT_ARR_1(iter->branch, iter->depth)
- iter->path_h[iter->depth++] = h;
- }
- }
+ L_BIT_ARR_1(iter->branch, iter->depth)
+ iter->path_h[iter->depth++] = h;
+ }
}
+ }
#undef l_tree
}
« libvpx.gyp ('K') | « source/libvpx/vpx_mem/memory_manager/include/cavl_if.h ('k') | source/libvpx/vpx_mem/memory_manager/include/heapmm.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698