libvpx: Pull from upstream

source/libvpx/vpx_mem/memory_manager/hmm_base.c

-/*
- *  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.
- */
-
-
-/* This code is in the public domain.
-** Version: 1.1  Author: Walt Karas
-*/
-
-#include "hmm_intrnl.h"
-
-void U(init)(U(descriptor) *desc) {
-  desc->avl_tree_root = 0;
-  desc->last_freed = 0;
-}
-
-/* Remove a free block from a bin's doubly-linked list when it is not,
-** the first block in the bin.
-*/
-void U(dll_remove)(
-  /* Pointer to pointer record in the block to be removed. */
-  ptr_record *to_remove) {
-  to_remove->prev->next = to_remove->next;
-
-  if (to_remove->next)
-    to_remove->next->prev = to_remove->prev;
-}
-
-/* Put a block into the free collection of a heap.
-*/
-void U(into_free_collection)(
-  /* Pointer to heap descriptor. */
-  U(descriptor) *desc,
-  /* Pointer to head record of block. */
-  head_record *head_ptr) {
-  ptr_record *ptr_rec_ptr = HEAD_TO_PTR_REC(head_ptr);
-
-  ptr_record *bin_front_ptr =
-    U(avl_insert)((U(avl_avl) *) & (desc->avl_tree_root), ptr_rec_ptr);
-
-  if (bin_front_ptr != ptr_rec_ptr) {
-    /* The block was not inserted into the AVL tree because there is
-    ** already a bin for the size of the block. */
-
-    MARK_SUCCESSIVE_BLOCK_IN_FREE_BIN(head_ptr)
-    ptr_rec_ptr->self = ptr_rec_ptr;
-
-    /* Make the block the new second block in the bin's doubly-linked
-    ** list. */
-    ptr_rec_ptr->prev = bin_front_ptr;
-    ptr_rec_ptr->next = bin_front_ptr->next;
-    bin_front_ptr->next = ptr_rec_ptr;
-
-    if (ptr_rec_ptr->next)
-      ptr_rec_ptr->next->prev = ptr_rec_ptr;
-  } else
-    /* Block is first block in new bin. */
-    ptr_rec_ptr->next = 0;
-}
-
-/* Allocate a block from a given bin.  Returns a pointer to the payload
-** of the removed block.  The "last freed" pointer must be null prior
-** to calling this function.
-*/
-void *U(alloc_from_bin)(
-  /* Pointer to heap descriptor. */
-  U(descriptor) *desc,
-  /* Pointer to pointer record of first block in bin. */
-  ptr_record *bin_front_ptr,
-  /* Number of BAUs needed in the allocated block.  If the block taken
-  ** from the bin is significantly larger than the number of BAUs needed,
-  ** the "extra" BAUs are split off to form a new free block. */
-  U(size_bau) n_baus) {
-  head_record *head_ptr;
-  U(size_bau) rem_baus;
-
-  if (bin_front_ptr->next) {
-    /* There are multiple blocks in this bin.  Use the 2nd block in
-    ** the bin to avoid needless change to the AVL tree.
-    */
-
-    ptr_record *ptr_rec_ptr = bin_front_ptr->next;
-    head_ptr = PTR_REC_TO_HEAD(ptr_rec_ptr);
-
-#ifdef AUDIT_FAIL
-    AUDIT_BLOCK(head_ptr)
-#endif
-
-    U(dll_remove)(ptr_rec_ptr);
-  } else {
-    /* There is only one block in the bin, so it has to be removed
-    ** from the AVL tree.
-    */
-
-    head_ptr = PTR_REC_TO_HEAD(bin_front_ptr);
-
-    U(avl_remove)(
-      (U(avl_avl) *) & (desc->avl_tree_root), BLOCK_BAUS(head_ptr));
-  }
-
-  MARK_BLOCK_ALLOCATED(head_ptr)
-
-  rem_baus = BLOCK_BAUS(head_ptr) - n_baus;
-
-  if (rem_baus >= MIN_BLOCK_BAUS) {
-    /* Since there are enough "extra" BAUs, split them off to form
-    ** a new free block.
-    */
-
-    head_record *rem_head_ptr =
-      (head_record *) BAUS_FORWARD(head_ptr, n_baus);
-
-    /* Change the next block's header to reflect the fact that the
-    ** block preceeding it is now smaller.
-    */
-    SET_PREV_BLOCK_BAUS(
-      BAUS_FORWARD(head_ptr, head_ptr->block_size), rem_baus)
-
-    head_ptr->block_size = n_baus;
-
-    rem_head_ptr->previous_block_size = n_baus;
-    rem_head_ptr->block_size = rem_baus;
-
-    desc->last_freed = rem_head_ptr;
-  }
-
-  return(HEAD_TO_PTR_REC(head_ptr));
-}
-
-/* Take a block out of the free collection.
-*/
-void U(out_of_free_collection)(
-  /* Descriptor of heap that block is in. */
-  U(descriptor) *desc,
-  /* Pointer to head of block to take out of free collection. */
-  head_record *head_ptr) {
-  ptr_record *ptr_rec_ptr = HEAD_TO_PTR_REC(head_ptr);
-
-  if (ptr_rec_ptr->self == ptr_rec_ptr)
-    /* Block is not the front block in its bin, so all we have to
-    ** do is take it out of the bin's doubly-linked list. */
-    U(dll_remove)(ptr_rec_ptr);
-  else {
-    ptr_record *next = ptr_rec_ptr->next;
-
-    if (next)
-      /* Block is the front block in its bin, and there is at least
-      ** one other block in the bin.  Substitute the next block for
-      ** the front block. */
-      U(avl_subst)((U(avl_avl) *) & (desc->avl_tree_root), next);
-    else
-      /* Block is the front block in its bin, but there is no other
-      ** block in the bin.  Eliminate the bin. */
-      U(avl_remove)(
-        (U(avl_avl) *) & (desc->avl_tree_root), BLOCK_BAUS(head_ptr));
-  }
-}
-
-void U(free)(U(descriptor) *desc, void *payload_ptr) {
-  /* Flags if coalesce with adjacent block. */
-  int coalesce;
-
-  head_record *fwd_head_ptr;
-  head_record *free_head_ptr = PTR_REC_TO_HEAD(payload_ptr);
-
-  desc->num_baus_can_shrink = 0;
-
-#ifdef HMM_AUDIT_FAIL
-
-  AUDIT_BLOCK(free_head_ptr)
-
-  /* Make sure not freeing an already free block. */
-  if (!IS_BLOCK_ALLOCATED(free_head_ptr))
-    HMM_AUDIT_FAIL
-
-    if (desc->avl_tree_root)
-      /* Audit root block in AVL tree. */
-      AUDIT_BLOCK(PTR_REC_TO_HEAD(desc->avl_tree_root))
-
-#endif
-
-      fwd_head_ptr =
-        (head_record *) BAUS_FORWARD(free_head_ptr, free_head_ptr->block_size);
-
-  if (free_head_ptr->previous_block_size) {
-    /* Coalesce with backward block if possible. */
-
-    head_record *bkwd_head_ptr =
-      (head_record *) BAUS_BACKWARD(
-        free_head_ptr, free_head_ptr->previous_block_size);
-
-#ifdef HMM_AUDIT_FAIL
-    AUDIT_BLOCK(bkwd_head_ptr)
-#endif
-
-    if (bkwd_head_ptr == (head_record *)(desc->last_freed)) {
-      desc->last_freed = 0;
-      coalesce = 1;
-    } else if (IS_BLOCK_ALLOCATED(bkwd_head_ptr))
-      coalesce = 0;
-    else {
-      U(out_of_free_collection)(desc, bkwd_head_ptr);
-      coalesce = 1;
-    }
-
-    if (coalesce) {
-      bkwd_head_ptr->block_size += free_head_ptr->block_size;
-      SET_PREV_BLOCK_BAUS(fwd_head_ptr, BLOCK_BAUS(bkwd_head_ptr))
-      free_head_ptr = bkwd_head_ptr;
-    }
-  }
-
-  if (fwd_head_ptr->block_size == 0) {
-    /* Block to be freed is last block before dummy end-of-chunk block. */
-    desc->end_of_shrinkable_chunk =
-      BAUS_FORWARD(fwd_head_ptr, DUMMY_END_BLOCK_BAUS);
-    desc->num_baus_can_shrink = BLOCK_BAUS(free_head_ptr);
-
-    if (PREV_BLOCK_BAUS(free_head_ptr) == 0)
-      /* Free block is the entire chunk, so shrinking can eliminate
-      ** entire chunk including dummy end block. */
-      desc->num_baus_can_shrink += DUMMY_END_BLOCK_BAUS;
-  } else {
-    /* Coalesce with forward block if possible. */
-
-#ifdef HMM_AUDIT_FAIL
-    AUDIT_BLOCK(fwd_head_ptr)
-#endif
-
-    if (fwd_head_ptr == (head_record *)(desc->last_freed)) {
-      desc->last_freed = 0;
-      coalesce = 1;
-    } else if (IS_BLOCK_ALLOCATED(fwd_head_ptr))
-      coalesce = 0;
-    else {
-      U(out_of_free_collection)(desc, fwd_head_ptr);
-      coalesce = 1;
-    }
-
-    if (coalesce) {
-      free_head_ptr->block_size += fwd_head_ptr->block_size;
-
-      fwd_head_ptr =
-        (head_record *) BAUS_FORWARD(
-          fwd_head_ptr, BLOCK_BAUS(fwd_head_ptr));
-
-      SET_PREV_BLOCK_BAUS(fwd_head_ptr, BLOCK_BAUS(free_head_ptr))
-
-      if (fwd_head_ptr->block_size == 0) {
-        /* Coalesced block to be freed is last block before dummy
-        ** end-of-chunk block. */
-        desc->end_of_shrinkable_chunk =
-          BAUS_FORWARD(fwd_head_ptr, DUMMY_END_BLOCK_BAUS);
-        desc->num_baus_can_shrink = BLOCK_BAUS(free_head_ptr);
-
-        if (PREV_BLOCK_BAUS(free_head_ptr) == 0)
-          /* Free block is the entire chunk, so shrinking can
-          ** eliminate entire chunk including dummy end block. */
-          desc->num_baus_can_shrink += DUMMY_END_BLOCK_BAUS;
-      }
-    }
-  }
-
-  if (desc->last_freed) {
-    /* There is a last freed block, but it is not adjacent to the
-    ** block being freed by this call to free, so put the last
-    ** freed block into the free collection.
-    */
-
-#ifdef HMM_AUDIT_FAIL
-    AUDIT_BLOCK(desc->last_freed)
-#endif
-
-    U(into_free_collection)(desc, (head_record *)(desc->last_freed));
-  }
-
-  desc->last_freed = free_head_ptr;
-}
-
-void U(new_chunk)(U(descriptor) *desc, void *start, U(size_bau) n_baus) {
-#ifdef HMM_AUDIT_FAIL
-
-  if (desc->avl_tree_root)
-    /* Audit root block in AVL tree. */
-    AUDIT_BLOCK(PTR_REC_TO_HEAD(desc->avl_tree_root))
-#endif
-
-#undef HEAD_PTR
-#define HEAD_PTR ((head_record *) start)
-
-    /* Make the chunk one big free block followed by a dummy end block.
-    */
-
-    n_baus -= DUMMY_END_BLOCK_BAUS;
-
-  HEAD_PTR->previous_block_size = 0;
-  HEAD_PTR->block_size = n_baus;
-
-  U(into_free_collection)(desc, HEAD_PTR);
-
-  /* Set up the dummy end block. */
-  start = BAUS_FORWARD(start, n_baus);
-  HEAD_PTR->previous_block_size = n_baus;
-  HEAD_PTR->block_size = 0;
-
-#undef HEAD_PTR
-}
-
-#ifdef HMM_AUDIT_FAIL
-
-/* Function that does audit fail actions defined my preprocessor symbol,
-** and returns a dummy integer value.
-*/
-int U(audit_block_fail_dummy_return)(void) {
-  HMM_AUDIT_FAIL
-
-  /* Dummy return. */
-  return(0);
-}
-
-#endif
-
-/* AVL Tree instantiation. */
-
-#ifdef HMM_AUDIT_FAIL
-
-/* The AVL tree generic package passes an ACCESS of 1 when it "touches"
-** a child node for the first time during a particular operation.  I use
-** this feature to audit only one time (per operation) the free blocks
-** that are tree nodes.  Since the root node is not a child node, it has
-** to be audited directly.
-*/
-
-/* The pain you feel while reading these macros will not be in vain.  It
-** will remove all doubt from you mind that C++ inline functions are
-** a very good thing.
-*/
-
-#define AVL_GET_LESS(H, ACCESS) \
-  (((ACCESS) ? AUDIT_BLOCK_AS_EXPR(PTR_REC_TO_HEAD(H)) : 0), (H)->self)
-#define AVL_GET_GREATER(H, ACCESS) \
-  (((ACCESS) ? AUDIT_BLOCK_AS_EXPR(PTR_REC_TO_HEAD(H)) : 0), (H)->prev)
-
-#else
-
-#define AVL_GET_LESS(H, ACCESS) ((H)->self)
-#define AVL_GET_GREATER(H, ACCESS) ((H)->prev)
-
-#endif
-
-#define AVL_SET_LESS(H, LH) (H)->self = (LH);
-#define AVL_SET_GREATER(H, GH) (H)->prev = (GH);
-
-/*  high bit of high bit of
-**  block_size  previous_block_size balance factor
-**  ----------- ------------------- --------------
-**  0       0           n/a (block allocated)
-**  0       1           1
-**  1       0           -1
-**  1       1           0
-*/
-
-#define AVL_GET_BALANCE_FACTOR(H) \
-  ((((head_record *) (PTR_REC_TO_HEAD(H)))->block_size & \
-    HIGH_BIT_BAU_SIZE) ? \
-   (((head_record *) (PTR_REC_TO_HEAD(H)))->previous_block_size & \
-    HIGH_BIT_BAU_SIZE ? 0 : -1) : 1)
-
-#define AVL_SET_BALANCE_FACTOR(H, BF) \
-  {                         \
-    register head_record *p =               \
-                                            (head_record *) PTR_REC_TO_HEAD(H);       \
-    register int bal_f = (BF);              \
-    \
-    if (bal_f <= 0)                 \
-      p->block_size |= HIGH_BIT_BAU_SIZE;       \
-    else                        \
-      p->block_size &= ~HIGH_BIT_BAU_SIZE;      \
-    if (bal_f >= 0)                 \
-      p->previous_block_size |= HIGH_BIT_BAU_SIZE;  \
-    else                        \
-      p->previous_block_size &= ~HIGH_BIT_BAU_SIZE; \
-  }
-
-#define COMPARE_KEY_KEY(K1, K2) ((K1) == (K2) ? 0 : ((K1) > (K2) ? 1 : -1))
-
-#define AVL_COMPARE_KEY_NODE(K, H) \
-  COMPARE_KEY_KEY(K, BLOCK_BAUS(PTR_REC_TO_HEAD(H)))
-
-#define AVL_COMPARE_NODE_NODE(H1, H2) \
-  COMPARE_KEY_KEY(BLOCK_BAUS(PTR_REC_TO_HEAD(H1)), \
-                  BLOCK_BAUS(PTR_REC_TO_HEAD(H2)))
-
-#define AVL_NULL ((ptr_record *) 0)
-
-#define AVL_IMPL_MASK \
-  ( AVL_IMPL_INSERT | AVL_IMPL_SEARCH | AVL_IMPL_REMOVE | AVL_IMPL_SUBST )
-
-#include "cavl_impl.h"