libvpx: Pull from upstream

source/libvpx/vpx_mem/memory_manager/include/cavl_impl.h

Index: source/libvpx/vpx_mem/memory_manager/include/cavl_impl.h
diff --git a/source/libvpx/vpx_mem/memory_manager/include/cavl_impl.h b/source/libvpx/vpx_mem/memory_manager/include/cavl_impl.h
deleted file mode 100644
index 8b9ae27a8c92e387a1ebeff1a47cbd04b14ea8b1..0000000000000000000000000000000000000000
--- a/source/libvpx/vpx_mem/memory_manager/include/cavl_impl.h
+++ /dev/null
@@ -1,1152 +0,0 @@
-/*
- *  Copyright (c) 2010 The WebM 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.
- */
-
-#ifndef VPX_MEM_MEMORY_MANAGER_INCLUDE_CAVL_IMPL_H_
-#define VPX_MEM_MEMORY_MANAGER_INCLUDE_CAVL_IMPL_H_
-
-/* 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
-
-#endif  // VPX_MEM_MEMORY_MANAGER_INCLUDE_CAVL_IMPL_H_