ref: 9ed0e071fe83b2cbe70967cb75392ed2c23c826e
parent: a6e9ae906641db51acfa7ca9d3aeacb8c435d9a2
parent: e5eda53e3d42c3b14b6b7705bc9cf95d27eb74f0
author: Johann <johannkoenig@google.com>
date: Wed Apr 22 09:09:39 EDT 2015
Merge "vpx_mem: remove memory manager code"
--- a/configure
+++ b/configure
@@ -296,7 +296,6 @@
codec_srcs
debug_libs
fast_unaligned
- mem_manager
mem_tracker
mem_checks
--- a/vpx_mem/include/vpx_mem_intrnl.h
+++ b/vpx_mem/include/vpx_mem_intrnl.h
@@ -13,15 +13,6 @@
#define VPX_MEM_INCLUDE_VPX_MEM_INTRNL_H_
#include "./vpx_config.h"
-#ifndef CONFIG_MEM_MANAGER
-# if defined(VXWORKS)
-# define CONFIG_MEM_MANAGER 1 /*include heap manager functionality,*/
-/*default: enabled on vxworks*/
-# else
-# define CONFIG_MEM_MANAGER 0 /*include heap manager functionality*/
-# endif
-#endif /*CONFIG_MEM_MANAGER*/
-
#ifndef CONFIG_MEM_TRACKER
# define CONFIG_MEM_TRACKER 1 /*include xvpx_* calls in the lib*/
#endif
--- a/vpx_mem/memory_manager/hmm_alloc.c
+++ /dev/null
@@ -1,58 +1,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.
- */
-
-
-/* This code is in the public domain.
-** Version: 1.1 Author: Walt Karas
-*/
-
-#include "hmm_intrnl.h"
-
-void *U(alloc)(U(descriptor) *desc, U(size_aau) n) {-#ifdef HMM_AUDIT_FAIL
-
- if (desc->avl_tree_root)
- AUDIT_BLOCK(PTR_REC_TO_HEAD(desc->avl_tree_root))
-#endif
-
- if (desc->last_freed) {-#ifdef HMM_AUDIT_FAIL
- AUDIT_BLOCK(desc->last_freed)
-#endif
-
- U(into_free_collection)(desc, (head_record *)(desc->last_freed));
-
- desc->last_freed = 0;
- }
-
- /* Add space for block header. */
- n += HEAD_AAUS;
-
- /* Convert n from number of address alignment units to block alignment
- ** units. */
- n = DIV_ROUND_UP(n, HMM_BLOCK_ALIGN_UNIT);
-
- if (n < MIN_BLOCK_BAUS)
- n = MIN_BLOCK_BAUS;
-
- {- /* Search for the first node of the bin containing the smallest
- ** block big enough to satisfy request. */
- ptr_record *ptr_rec_ptr =
- U(avl_search)(
- (U(avl_avl) *) & (desc->avl_tree_root), (U(size_bau)) n,
- AVL_GREATER_EQUAL);
-
- /* If an approprate bin is found, satisfy the allocation request,
- ** otherwise return null pointer. */
- return(ptr_rec_ptr ?
- U(alloc_from_bin)(desc, ptr_rec_ptr, (U(size_bau)) n) : 0);
- }
-}
--- a/vpx_mem/memory_manager/hmm_base.c
+++ /dev/null
@@ -1,405 +1,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.
- */
-
-
-/* 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"
--- a/vpx_mem/memory_manager/hmm_dflt_abort.c
+++ /dev/null
@@ -1,53 +1,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.
- */
-
-
-/* This code is in the public domain.
-** Version: 1.1 Author: Walt Karas
-*/
-
-/* The function in this file performs default actions if self-auditing
-** finds heap corruption. Don't rely on this code to handle the
-** case where HMM is being used to implement the malloc and free standard
-** library functions. Rewrite the function if necessary to avoid using
-** I/O and execution termination functions that call malloc or free.
-** In Unix, for example, you would replace the fputs calls with calls
-** to the write system call using file handle number 2.
-*/
-#include "hmm_intrnl.h"
-#include <stdio.h>
-#include <stdlib.h>
-
-static int entered = 0;
-
-/* Print abort message, file and line. Terminate execution.
-*/
-void hmm_dflt_abort(const char *file, const char *line) {- /* Avoid use of printf(), which is more likely to use heap. */
-
- if (entered)
-
- /* The standard I/O functions called a heap function and caused
- ** an indirect recursive call to this function. So we'll have
- ** to just exit without printing a message. */
- while (1);
-
- entered = 1;
-
- fputs("\n_abort - Heap corruption\n" "File: ", stderr);- fputs(file, stderr);
- fputs(" Line: ", stderr);- fputs(line, stderr);
- fputs("\n\n", stderr);- fputs("hmm_dflt_abort: while(1)!!!\n", stderr);- fflush(stderr);
-
- while (1);
-}
--- a/vpx_mem/memory_manager/hmm_grow.c
+++ /dev/null
@@ -1,49 +1,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.
- */
-
-
-/* This code is in the public domain.
-** Version: 1.1 Author: Walt Karas
-*/
-
-#include "hmm_intrnl.h"
-
-void U(grow_chunk)(U(descriptor) *desc, void *end, U(size_bau) n_baus) {-#undef HEAD_PTR
-#define HEAD_PTR ((head_record *) end)
-
- end = BAUS_BACKWARD(end, DUMMY_END_BLOCK_BAUS);
-
-#ifdef HMM_AUDIT_FAIL
-
- if (HEAD_PTR->block_size != 0)
- /* Chunk does not have valid dummy end block. */
- HMM_AUDIT_FAIL
-
-#endif
-
- /* Create a new block that absorbs the old dummy end block. */
- HEAD_PTR->block_size = n_baus;
-
- /* Set up the new dummy end block. */
- {- head_record *dummy = (head_record *) BAUS_FORWARD(end, n_baus);
- dummy->previous_block_size = n_baus;
- dummy->block_size = 0;
- }
-
- /* Simply free the new block, allowing it to coalesce with any
- ** free block at that was the last block in the chunk prior to
- ** growth.
- */
- U(free)(desc, HEAD_TO_PTR_REC(end));
-
-#undef HEAD_PTR
-}
--- a/vpx_mem/memory_manager/hmm_largest.c
+++ /dev/null
@@ -1,57 +1,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.
- */
-
-
-/* This code is in the public domain.
-** Version: 1.1 Author: Walt Karas
-*/
-
-#include "hmm_intrnl.h"
-
-U(size_aau) U(largest_available)(U(descriptor) *desc) {- U(size_bau) largest;
-
- if (!(desc->avl_tree_root))
- largest = 0;
- else {-#ifdef HMM_AUDIT_FAIL
- /* Audit root block in AVL tree. */
- AUDIT_BLOCK(PTR_REC_TO_HEAD(desc->avl_tree_root))
-#endif
-
- largest =
- BLOCK_BAUS(
- PTR_REC_TO_HEAD(
- U(avl_search)(
- (U(avl_avl) *) & (desc->avl_tree_root),
- (U(size_bau)) ~(U(size_bau)) 0, AVL_LESS)));
- }
-
- if (desc->last_freed) {- /* Size of last freed block. */
- register U(size_bau) lf_size;
-
-#ifdef HMM_AUDIT_FAIL
- AUDIT_BLOCK(desc->last_freed)
-#endif
-
- lf_size = BLOCK_BAUS(desc->last_freed);
-
- if (lf_size > largest)
- largest = lf_size;
- }
-
- /* Convert largest size to AAUs and subract head size leaving payload
- ** size.
- */
- return(largest ?
- ((largest * ((U(size_aau)) HMM_BLOCK_ALIGN_UNIT)) - HEAD_AAUS) :
- 0);
-}
--- a/vpx_mem/memory_manager/hmm_resize.c
+++ /dev/null
@@ -1,114 +1,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.
- */
-
-
-/* This code is in the public domain.
-** Version: 1.1 Author: Walt Karas
-*/
-
-#include "hmm_intrnl.h"
-
-int U(resize)(U(descriptor) *desc, void *mem, U(size_aau) n) {- U(size_aau) i;
- head_record *next_head_ptr;
- head_record *head_ptr = PTR_REC_TO_HEAD(mem);
-
- /* Flag. */
- int next_block_free;
-
- /* Convert n from desired block size in AAUs to BAUs. */
- n += HEAD_AAUS;
- n = DIV_ROUND_UP(n, HMM_BLOCK_ALIGN_UNIT);
-
- if (n < MIN_BLOCK_BAUS)
- n = MIN_BLOCK_BAUS;
-
-#ifdef HMM_AUDIT_FAIL
-
- AUDIT_BLOCK(head_ptr)
-
- if (!IS_BLOCK_ALLOCATED(head_ptr))
- HMM_AUDIT_FAIL
-
- if (desc->avl_tree_root)
- AUDIT_BLOCK(PTR_REC_TO_HEAD(desc->avl_tree_root))
-
-#endif
-
- i = head_ptr->block_size;
-
- next_head_ptr =
- (head_record *) BAUS_FORWARD(head_ptr, head_ptr->block_size);
-
- next_block_free =
- (next_head_ptr == desc->last_freed) ||
- !IS_BLOCK_ALLOCATED(next_head_ptr);
-
- if (next_block_free)
- /* Block can expand into next free block. */
- i += BLOCK_BAUS(next_head_ptr);
-
- if (n > i)
- /* Not enough room for block to expand. */
- return(-1);
-
- if (next_block_free) {-#ifdef HMM_AUDIT_FAIL
- AUDIT_BLOCK(next_head_ptr)
-#endif
-
- if (next_head_ptr == desc->last_freed)
- desc->last_freed = 0;
- else
- U(out_of_free_collection)(desc, next_head_ptr);
-
- next_head_ptr =
- (head_record *) BAUS_FORWARD(head_ptr, (U(size_bau)) i);
- }
-
- /* Set i to number of "extra" BAUs. */
- i -= n;
-
- if (i < MIN_BLOCK_BAUS)
- /* Not enough extra BAUs to be a block on their own, so just keep them
- ** in the block being resized.
- */
- {- n += i;
- i = n;
- } else {- /* There are enough "leftover" BAUs in the next block to
- ** form a remainder block. */
-
- head_record *rem_head_ptr;
-
- rem_head_ptr = (head_record *) BAUS_FORWARD(head_ptr, n);
-
- rem_head_ptr->previous_block_size = (U(size_bau)) n;
- rem_head_ptr->block_size = (U(size_bau)) i;
-
- if (desc->last_freed) {-#ifdef HMM_AUDIT_FAIL
- AUDIT_BLOCK(desc->last_freed)
-#endif
-
- U(into_free_collection)(desc, (head_record *)(desc->last_freed));
-
- desc->last_freed = 0;
- }
-
- desc->last_freed = rem_head_ptr;
- }
-
- head_ptr->block_size = (U(size_bau)) n;
- next_head_ptr->previous_block_size = (U(size_bau)) i;
-
- return(0);
-}
--- a/vpx_mem/memory_manager/hmm_shrink.c
+++ /dev/null
@@ -1,103 +1,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.
- */
-
-
-/* This code is in the public domain.
-** Version: 1.1 Author: Walt Karas
-*/
-
-#include "hmm_intrnl.h"
-
-void U(shrink_chunk)(U(descriptor) *desc, U(size_bau) n_baus_to_shrink) {- head_record *dummy_end_block = (head_record *)
- BAUS_BACKWARD(desc->end_of_shrinkable_chunk, DUMMY_END_BLOCK_BAUS);
-
-#ifdef HMM_AUDIT_FAIL
-
- if (dummy_end_block->block_size != 0)
- /* Chunk does not have valid dummy end block. */
- HMM_AUDIT_FAIL
-
-#endif
-
- if (n_baus_to_shrink) {- head_record *last_block = (head_record *)
- BAUS_BACKWARD(
- dummy_end_block, dummy_end_block->previous_block_size);
-
-#ifdef HMM_AUDIT_FAIL
- AUDIT_BLOCK(last_block)
-#endif
-
- if (last_block == desc->last_freed) {- U(size_bau) bs = BLOCK_BAUS(last_block);
-
- /* Chunk will not be shrunk out of existence if
- ** 1. There is at least one allocated block in the chunk
- ** and the amount to shrink is exactly the size of the
- ** last block, OR
- ** 2. After the last block is shrunk, there will be enough
- ** BAUs left in it to form a minimal size block. */
- int chunk_will_survive =
- (PREV_BLOCK_BAUS(last_block) && (n_baus_to_shrink == bs)) ||
- (n_baus_to_shrink <= (U(size_bau))(bs - MIN_BLOCK_BAUS));
-
- if (chunk_will_survive ||
- (!PREV_BLOCK_BAUS(last_block) &&
- (n_baus_to_shrink ==
- (U(size_bau))(bs + DUMMY_END_BLOCK_BAUS)))) {- desc->last_freed = 0;
-
- if (chunk_will_survive) {- bs -= n_baus_to_shrink;
-
- if (bs) {- /* The last (non-dummy) block was not completely
- ** eliminated by the shrink. */
-
- last_block->block_size = bs;
-
- /* Create new dummy end record.
- */
- dummy_end_block =
- (head_record *) BAUS_FORWARD(last_block, bs);
- dummy_end_block->previous_block_size = bs;
- dummy_end_block->block_size = 0;
-
-#ifdef HMM_AUDIT_FAIL
-
- if (desc->avl_tree_root)
- AUDIT_BLOCK(PTR_REC_TO_HEAD(desc->avl_tree_root))
-#endif
-
- U(into_free_collection)(desc, last_block);
- } else {- /* The last (non-dummy) block was completely
- ** eliminated by the shrink. Make its head
- ** the new dummy end block.
- */
- last_block->block_size = 0;
- last_block->previous_block_size &= ~HIGH_BIT_BAU_SIZE;
- }
- }
- }
-
-#ifdef HMM_AUDIT_FAIL
- else
- HMM_AUDIT_FAIL
-#endif
- }
-
-#ifdef HMM_AUDIT_FAIL
- else
- HMM_AUDIT_FAIL
-#endif
- }
-}
--- a/vpx_mem/memory_manager/hmm_true.c
+++ /dev/null
@@ -1,31 +1,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.
- */
-
-
-/* This code is in the public domain.
-** Version: 1.1 Author: Walt Karas
-*/
-
-#include "hmm_intrnl.h"
-
-U(size_aau) U(true_size)(void *payload_ptr) {- register head_record *head_ptr = PTR_REC_TO_HEAD(payload_ptr);
-
-#ifdef HMM_AUDIT_FAIL
- AUDIT_BLOCK(head_ptr)
-#endif
-
- /* Convert block size from BAUs to AAUs. Subtract head size, leaving
- ** payload size.
- */
- return(
- (BLOCK_BAUS(head_ptr) * ((U(size_aau)) HMM_BLOCK_ALIGN_UNIT)) -
- HEAD_AAUS);
-}
--- a/vpx_mem/memory_manager/include/cavl_if.h
+++ /dev/null
@@ -1,228 +1,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_IF_H_
-#define VPX_MEM_MEMORY_MANAGER_INCLUDE_CAVL_IF_H_
-
-/* Abstract AVL Tree Generic C Package.
-** Interface generation header file.
-**
-** This code is in the public domain. See cavl_tree.html for interface
-** documentation.
-**
-** Version: 1.5 Author: Walt Karas
-*/
-
-/* This header contains the definition of CHAR_BIT (number of bits in a
-** char). */
-#include <limits.h>
-
-#undef L_
-#undef L_EST_LONG_BIT
-#undef L_SIZE
-#undef L_SC
-#undef L_LONG_BIT
-#undef L_BIT_ARR_DEFN
-
-#ifndef AVL_SEARCH_TYPE_DEFINED_
-#define AVL_SEARCH_TYPE_DEFINED_
-
-typedef enum {- AVL_EQUAL = 1,
- AVL_LESS = 2,
- AVL_GREATER = 4,
- AVL_LESS_EQUAL = AVL_EQUAL | AVL_LESS,
- AVL_GREATER_EQUAL = AVL_EQUAL | AVL_GREATER
-}
-avl_search_type;
-
-#endif
-
-#ifdef AVL_UNIQUE
-
-#define L_ AVL_UNIQUE
-
-#else
-
-#define L_(X) X
-
-#endif
-
-/* Determine storage class for function prototypes. */
-#ifdef AVL_PRIVATE
-
-#define L_SC static
-
-#else
-
-#define L_SC extern
-
-#endif
-
-#ifdef AVL_SIZE
-
-#define L_SIZE AVL_SIZE
-
-#else
-
-#define L_SIZE unsigned long
-
-#endif
-
-typedef struct {-#ifdef AVL_INSIDE_STRUCT
-
- AVL_INSIDE_STRUCT
-
-#endif
-
- AVL_HANDLE root;
-}
-L_(avl);
-
-/* Function prototypes. */
-
-L_SC void L_(init)(L_(avl) *tree);
-
-L_SC int L_(is_empty)(L_(avl) *tree);
-
-L_SC AVL_HANDLE L_(insert)(L_(avl) *tree, AVL_HANDLE h);
-
-L_SC AVL_HANDLE L_(search)(L_(avl) *tree, AVL_KEY k, avl_search_type st);
-
-L_SC AVL_HANDLE L_(search_least)(L_(avl) *tree);
-
-L_SC AVL_HANDLE L_(search_greatest)(L_(avl) *tree);
-
-L_SC AVL_HANDLE L_(remove)(L_(avl) *tree, AVL_KEY k);
-
-L_SC AVL_HANDLE L_(subst)(L_(avl) *tree, AVL_HANDLE new_node);
-
-#ifdef AVL_BUILD_ITER_TYPE
-
-L_SC int L_(build)(
- L_(avl) *tree, AVL_BUILD_ITER_TYPE p, L_SIZE num_nodes);
-
-#endif
-
-/* 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
-
-/* Number of bits in a long. */
-#define L_LONG_BIT (sizeof(long) * CHAR_BIT)
-
-/* The macro L_BIT_ARR_DEFN defines a bit array whose index is a (0-based)
-** node depth. The definition depends on whether the maximum depth is more
-** or less than the number of bits in a single long.
-*/
-
-#if ((AVL_MAX_DEPTH) > L_EST_LONG_BIT)
-
-/* Maximum depth may be more than number of bits in a long. */
-
-#define L_BIT_ARR_DEFN(NAME) \
- unsigned long NAME[((AVL_MAX_DEPTH) + L_LONG_BIT - 1) / L_LONG_BIT];
-
-#else
-
-/* Maximum depth is definitely less than number of bits in a long. */
-
-#define L_BIT_ARR_DEFN(NAME) unsigned long NAME;
-
-#endif
-
-/* Iterator structure. */
-typedef struct {- /* Tree being iterated over. */
- L_(avl) *tree_;
-
- /* 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)
-
- /* Zero-based depth of path into tree. */
- unsigned depth;
-
- /* Handles of nodes in path from root to current node (returned by *). */
- AVL_HANDLE path_h[(AVL_MAX_DEPTH) - 1];
-}
-L_(iter);
-
-/* Iterator function prototypes. */
-
-L_SC void L_(start_iter)(
- L_(avl) *tree, L_(iter) *iter, AVL_KEY k, avl_search_type st);
-
-L_SC void L_(start_iter_least)(L_(avl) *tree, L_(iter) *iter);
-
-L_SC void L_(start_iter_greatest)(L_(avl) *tree, L_(iter) *iter);
-
-L_SC AVL_HANDLE L_(get_iter)(L_(iter) *iter);
-
-L_SC void L_(incr_iter)(L_(iter) *iter);
-
-L_SC void L_(decr_iter)(L_(iter) *iter);
-
-L_SC void L_(init_iter)(L_(iter) *iter);
-
-#define AVL_IMPL_INIT 1
-#define AVL_IMPL_IS_EMPTY (1 << 1)
-#define AVL_IMPL_INSERT (1 << 2)
-#define AVL_IMPL_SEARCH (1 << 3)
-#define AVL_IMPL_SEARCH_LEAST (1 << 4)
-#define AVL_IMPL_SEARCH_GREATEST (1 << 5)
-#define AVL_IMPL_REMOVE (1 << 6)
-#define AVL_IMPL_BUILD (1 << 7)
-#define AVL_IMPL_START_ITER (1 << 8)
-#define AVL_IMPL_START_ITER_LEAST (1 << 9)
-#define AVL_IMPL_START_ITER_GREATEST (1 << 10)
-#define AVL_IMPL_GET_ITER (1 << 11)
-#define AVL_IMPL_INCR_ITER (1 << 12)
-#define AVL_IMPL_DECR_ITER (1 << 13)
-#define AVL_IMPL_INIT_ITER (1 << 14)
-#define AVL_IMPL_SUBST (1 << 15)
-
-#define AVL_IMPL_ALL (~0)
-
-#undef L_
-#undef L_EST_LONG_BIT
-#undef L_SIZE
-#undef L_SC
-#undef L_LONG_BIT
-#undef L_BIT_ARR_DEFN
-
-#endif // VPX_MEM_MEMORY_MANAGER_INCLUDE_CAVL_IF_H_
--- a/vpx_mem/memory_manager/include/cavl_impl.h
+++ /dev/null
@@ -1,1152 +1,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_
--- a/vpx_mem/memory_manager/include/heapmm.h
+++ /dev/null
@@ -1,155 +1,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_HEAPMM_H_
-#define VPX_MEM_MEMORY_MANAGER_INCLUDE_HEAPMM_H_
-
-/* This code is in the public domain.
-** Version: 1.1 Author: Walt Karas
-*/
-
-/* External header file for Heap Memory Manager. See documentation in
-** heapmm.html.
-*/
-
-#undef HMM_PROCESS
-
-/* Include once per configuration in a particular translation unit. */
-
-#ifndef HMM_CNFG_NUM
-
-/* Default configuration. */
-
-#ifndef HMM_INC_CNFG_DFLT
-#define HMM_INC_CNFG_DFLT
-#define HMM_PROCESS
-#endif
-
-#elif HMM_CNFG_NUM == 0
-
-/* Test configuration. */
-
-#ifndef HMM_INC_CNFG_0
-#define HMM_INC_CNFG_0
-#define HMM_PROCESS
-#endif
-
-#elif HMM_CNFG_NUM == 1
-
-#ifndef HMM_INC_CNFG_1
-#define HMM_INC_CNFG_1
-#define HMM_PROCESS
-#endif
-
-#elif HMM_CNFG_NUM == 2
-
-#ifndef HMM_INC_CNFG_2
-#define HMM_INC_CNFG_2
-#define HMM_PROCESS
-#endif
-
-#elif HMM_CNFG_NUM == 3
-
-#ifndef HMM_INC_CNFG_3
-#define HMM_INC_CNFG_3
-#define HMM_PROCESS
-#endif
-
-#elif HMM_CNFG_NUM == 4
-
-#ifndef HMM_INC_CNFG_4
-#define HMM_INC_CNFG_4
-#define HMM_PROCESS
-#endif
-
-#elif HMM_CNFG_NUM == 5
-
-#ifndef HMM_INC_CNFG_5
-#define HMM_INC_CNFG_5
-#define HMM_PROCESS
-#endif
-
-#endif
-
-#ifdef HMM_PROCESS
-
-#include "hmm_cnfg.h"
-
-/* Heap descriptor. */
-typedef struct HMM_UNIQUE(structure) {- /* private: */
-
- /* Pointer to (payload of) root node in AVL tree. This field should
- ** really be the AVL tree descriptor (type avl_avl). But (in the
- ** instantiation of the AVL tree generic package used in package) the
- ** AVL tree descriptor simply contains a pointer to the root. So,
- ** whenever a pointer to the AVL tree descriptor is needed, I use the
- ** cast:
- **
- ** (avl_avl *) &(heap_desc->avl_tree_root)
- **
- ** (where heap_desc is a pointer to a heap descriptor). This trick
- ** allows me to avoid including cavl_if.h in this external header. */
- void *avl_tree_root;
-
- /* Pointer to first byte of last block freed, after any coalescing. */
- void *last_freed;
-
- /* public: */
-
- HMM_UNIQUE(size_bau) num_baus_can_shrink;
- void *end_of_shrinkable_chunk;
-}
-HMM_UNIQUE(descriptor);
-
-/* Prototypes for externally-callable functions. */
-
-void HMM_UNIQUE(init)(HMM_UNIQUE(descriptor) *desc);
-
-void *HMM_UNIQUE(alloc)(
- HMM_UNIQUE(descriptor) *desc, HMM_UNIQUE(size_aau) num_addr_align_units);
-
-/* NOT YET IMPLEMENTED */
-void *HMM_UNIQUE(greedy_alloc)(
- HMM_UNIQUE(descriptor) *desc, HMM_UNIQUE(size_aau) needed_addr_align_units,
- HMM_UNIQUE(size_aau) coveted_addr_align_units);
-
-int HMM_UNIQUE(resize)(
- HMM_UNIQUE(descriptor) *desc, void *mem,
- HMM_UNIQUE(size_aau) num_addr_align_units);
-
-/* NOT YET IMPLEMENTED */
-int HMM_UNIQUE(greedy_resize)(
- HMM_UNIQUE(descriptor) *desc, void *mem,
- HMM_UNIQUE(size_aau) needed_addr_align_units,
- HMM_UNIQUE(size_aau) coveted_addr_align_units);
-
-void HMM_UNIQUE(free)(HMM_UNIQUE(descriptor) *desc, void *mem);
-
-HMM_UNIQUE(size_aau) HMM_UNIQUE(true_size)(void *mem);
-
-HMM_UNIQUE(size_aau) HMM_UNIQUE(largest_available)(
- HMM_UNIQUE(descriptor) *desc);
-
-void HMM_UNIQUE(new_chunk)(
- HMM_UNIQUE(descriptor) *desc, void *start_of_chunk,
- HMM_UNIQUE(size_bau) num_block_align_units);
-
-void HMM_UNIQUE(grow_chunk)(
- HMM_UNIQUE(descriptor) *desc, void *end_of_chunk,
- HMM_UNIQUE(size_bau) num_block_align_units);
-
-/* NOT YET IMPLEMENTED */
-void HMM_UNIQUE(shrink_chunk)(
- HMM_UNIQUE(descriptor) *desc,
- HMM_UNIQUE(size_bau) num_block_align_units);
-
-#endif /* defined HMM_PROCESS */
-#endif // VPX_MEM_MEMORY_MANAGER_INCLUDE_HEAPMM_H_
--- a/vpx_mem/memory_manager/include/hmm_cnfg.h
+++ /dev/null
@@ -1,120 +1,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_HMM_CNFG_H_
-#define VPX_MEM_MEMORY_MANAGER_INCLUDE_HMM_CNFG_H_
-
-/* This code is in the public domain.
-** Version: 1.1 Author: Walt Karas
-*/
-
-/* Configure Heap Memory Manager for processor architecture, compiler,
-** and desired performance characteristics. This file is included
-** by heapmm.h, so these definitions can be used by code external to
-** HMM. You can change the default configuration, and/or create alternate
-** configuration(s).
-*/
-
-/* To allow for multiple configurations of HMM to be used in the same
-** compilation unit, undefine all preprocessor symbols that will be
-** defined below.
-*/
-#undef HMM_ADDR_ALIGN_UNIT
-#undef HMM_BLOCK_ALIGN_UNIT
-#undef HMM_UNIQUE
-#undef HMM_DESC_PARAM
-#undef HMM_SYM_TO_STRING
-#undef HMM_SYM_TO_STRING
-#undef HMM_AUDIT_FAIL
-
-/* Turn X into a string after one macro expansion pass of X. This trick
-** works with both GCC and Visual C++. */
-#define HMM_SYM_TO_STRING(X) HMM_SYM_TO_STRING(X)
-#define HMM_SYM_TO_STRING(X) #X
-
-#ifndef HMM_CNFG_NUM
-
-/* Default configuration. */
-
-/* Use hmm_ prefix to avoid identifier conflicts. */
-#define HMM_UNIQUE(BASE) hmm_ ## BASE
-
-/* Number of bytes in an Address Alignment Unit (AAU). */
-// fwg
-// #define HMM_ADDR_ALIGN_UNIT sizeof(int)
-#define HMM_ADDR_ALIGN_UNIT 32
-
-/* Number of AAUs in a Block Alignment Unit (BAU). */
-#define HMM_BLOCK_ALIGN_UNIT 1
-
-/* Type of unsigned integer big enough to hold the size of a Block in AAUs. */
-typedef unsigned long HMM_UNIQUE(size_aau);
-
-/* Type of unsigned integer big enough to hold the size of a Block/Chunk
-** in BAUs. The high bit will be robbed. */
-typedef unsigned long HMM_UNIQUE(size_bau);
-
-void hmm_dflt_abort(const char *, const char *);
-
-/* Actions upon a self-audit failure. Must expand to a single complete
-** statement. If you remove the definition of this macro, no self-auditing
-** will be performed. */
-#define HMM_AUDIT_FAIL \
- hmm_dflt_abort(__FILE__, HMM_SYM_TO_STRING(__LINE__));
-
-#elif HMM_CNFG_NUM == 0
-
-/* Definitions for testing. */
-
-#define HMM_UNIQUE(BASE) thmm_ ## BASE
-
-#define HMM_ADDR_ALIGN_UNIT sizeof(int)
-
-#define HMM_BLOCK_ALIGN_UNIT 3
-
-typedef unsigned HMM_UNIQUE(size_aau);
-
-typedef unsigned short HMM_UNIQUE(size_bau);
-
-/* Under this test setup, a long jump is done if there is a self-audit
-** failure.
-*/
-
-extern jmp_buf HMM_UNIQUE(jmp_buf);
-extern const char *HMM_UNIQUE(fail_file);
-extern unsigned HMM_UNIQUE(fail_line);
-
-#define HMM_AUDIT_FAIL \
- { HMM_UNIQUE(fail_file) = __FILE__; HMM_UNIQUE(fail_line) = __LINE__; \- longjmp(HMM_UNIQUE(jmp_buf), 1); }
-
-#elif HMM_CNFG_NUM == 1
-
-/* Put configuration 1 definitions here (if there is a configuration 1). */
-
-#elif HMM_CNFG_NUM == 2
-
-/* Put configuration 2 definitions here. */
-
-#elif HMM_CNFG_NUM == 3
-
-/* Put configuration 3 definitions here. */
-
-#elif HMM_CNFG_NUM == 4
-
-/* Put configuration 4 definitions here. */
-
-#elif HMM_CNFG_NUM == 5
-
-/* Put configuration 5 definitions here. */
-
-#endif
-
-#endif // VPX_MEM_MEMORY_MANAGER_INCLUDE_HMM_CNFG_H_
--- a/vpx_mem/memory_manager/include/hmm_intrnl.h
+++ /dev/null
@@ -1,159 +1,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.
- */
-
-
-/* This code is in the public domain.
-** Version: 1.1 Author: Walt Karas
-*/
-
-#ifndef VPX_MEM_MEMORY_MANAGER_INCLUDE_HMM_INTRNL_H_
-#define VPX_MEM_MEMORY_MANAGER_INCLUDE_HMM_INTRNL_H_
-
-#ifdef __uClinux__
-# include <lddk.h>
-#endif
-
-#include "heapmm.h"
-
-#define U(BASE) HMM_UNIQUE(BASE)
-
-/* Mask of high bit of variable of size_bau type. */
-#define HIGH_BIT_BAU_SIZE \
- ((U(size_bau)) ~ (((U(size_bau)) ~ (U(size_bau)) 0) >> 1))
-
-/* Add a given number of AAUs to pointer. */
-#define AAUS_FORWARD(PTR, AAU_OFFSET) \
- (((char *) (PTR)) + ((AAU_OFFSET) * ((U(size_aau)) HMM_ADDR_ALIGN_UNIT)))
-
-/* Subtract a given number of AAUs from pointer. */
-#define AAUS_BACKWARD(PTR, AAU_OFFSET) \
- (((char *) (PTR)) - ((AAU_OFFSET) * ((U(size_aau)) HMM_ADDR_ALIGN_UNIT)))
-
-/* Add a given number of BAUs to a pointer. */
-#define BAUS_FORWARD(PTR, BAU_OFFSET) \
- AAUS_FORWARD((PTR), (BAU_OFFSET) * ((U(size_aau)) HMM_BLOCK_ALIGN_UNIT))
-
-/* Subtract a given number of BAUs to a pointer. */
-#define BAUS_BACKWARD(PTR, BAU_OFFSET) \
- AAUS_BACKWARD((PTR), (BAU_OFFSET) * ((U(size_aau)) HMM_BLOCK_ALIGN_UNIT))
-
-typedef struct head_struct {- /* Sizes in Block Alignment Units. */
- HMM_UNIQUE(size_bau) previous_block_size, block_size;
-}
-head_record;
-
-typedef struct ptr_struct {- struct ptr_struct *self, *prev, *next;
-}
-ptr_record;
-
-/* Divide and round up any fraction to the next whole number. */
-#define DIV_ROUND_UP(NUMER, DENOM) (((NUMER) + (DENOM) - 1) / (DENOM))
-
-/* Number of AAUs in a block head. */
-#define HEAD_AAUS DIV_ROUND_UP(sizeof(head_record), HMM_ADDR_ALIGN_UNIT)
-
-/* Number of AAUs in a block pointer record. */
-#define PTR_RECORD_AAUS DIV_ROUND_UP(sizeof(ptr_record), HMM_ADDR_ALIGN_UNIT)
-
-/* Number of BAUs in a dummy end record (at end of chunk). */
-#define DUMMY_END_BLOCK_BAUS DIV_ROUND_UP(HEAD_AAUS, HMM_BLOCK_ALIGN_UNIT)
-
-/* Minimum number of BAUs in a block (allowing room for the pointer record. */
-#define MIN_BLOCK_BAUS \
- DIV_ROUND_UP(HEAD_AAUS + PTR_RECORD_AAUS, HMM_BLOCK_ALIGN_UNIT)
-
-/* Return number of BAUs in block (masking off high bit containing block
-** status). */
-#define BLOCK_BAUS(HEAD_PTR) \
- (((head_record *) (HEAD_PTR))->block_size & ~HIGH_BIT_BAU_SIZE)
-
-/* Return number of BAUs in previous block (masking off high bit containing
-** block status). */
-#define PREV_BLOCK_BAUS(HEAD_PTR) \
- (((head_record *) (HEAD_PTR))->previous_block_size & ~HIGH_BIT_BAU_SIZE)
-
-/* Set number of BAUs in previous block, preserving high bit containing
-** block status. */
-#define SET_PREV_BLOCK_BAUS(HEAD_PTR, N_BAUS) \
- { register head_record *h_ptr = (head_record *) (HEAD_PTR); \- h_ptr->previous_block_size &= HIGH_BIT_BAU_SIZE; \
- h_ptr->previous_block_size |= (N_BAUS); }
-
-/* Convert pointer to pointer record of block to pointer to block's head
-** record. */
-#define PTR_REC_TO_HEAD(PTR_REC_PTR) \
- ((head_record *) AAUS_BACKWARD(PTR_REC_PTR, HEAD_AAUS))
-
-/* Convert pointer to block head to pointer to block's pointer record. */
-#define HEAD_TO_PTR_REC(HEAD_PTR) \
- ((ptr_record *) AAUS_FORWARD(HEAD_PTR, HEAD_AAUS))
-
-/* Returns non-zero if block is allocated. */
-#define IS_BLOCK_ALLOCATED(HEAD_PTR) \
- (((((head_record *) (HEAD_PTR))->block_size | \
- ((head_record *) (HEAD_PTR))->previous_block_size) & \
- HIGH_BIT_BAU_SIZE) == 0)
-
-#define MARK_BLOCK_ALLOCATED(HEAD_PTR) \
- { register head_record *h_ptr = (head_record *) (HEAD_PTR); \- h_ptr->block_size &= ~HIGH_BIT_BAU_SIZE; \
- h_ptr->previous_block_size &= ~HIGH_BIT_BAU_SIZE; }
-
-/* Mark a block as free when it is not the first block in a bin (and
-** therefore not a node in the AVL tree). */
-#define MARK_SUCCESSIVE_BLOCK_IN_FREE_BIN(HEAD_PTR) \
- { register head_record *h_ptr = (head_record *) (HEAD_PTR); \- h_ptr->block_size |= HIGH_BIT_BAU_SIZE; }
-
-/* Prototypes for internal functions implemented in one file and called in
-** another.
-*/
-
-void U(into_free_collection)(U(descriptor) *desc, head_record *head_ptr);
-
-void U(out_of_free_collection)(U(descriptor) *desc, head_record *head_ptr);
-
-void *U(alloc_from_bin)(
- U(descriptor) *desc, ptr_record *bin_front_ptr, U(size_bau) n_baus);
-
-#ifdef HMM_AUDIT_FAIL
-
-/* Simply contains a reference to the HMM_AUDIT_FAIL macro and a
-** dummy return. */
-int U(audit_block_fail_dummy_return)(void);
-
-
-/* Auditing a block consists of checking that the size in its head
-** matches the previous block size in the head of the next block. */
-#define AUDIT_BLOCK_AS_EXPR(HEAD_PTR) \
- ((BLOCK_BAUS(HEAD_PTR) == \
- PREV_BLOCK_BAUS(BAUS_FORWARD(HEAD_PTR, BLOCK_BAUS(HEAD_PTR)))) ? \
- 0 : U(audit_block_fail_dummy_return)())
-
-#define AUDIT_BLOCK(HEAD_PTR) \
- { void *h_ptr = (HEAD_PTR); AUDIT_BLOCK_AS_EXPR(h_ptr); }-
-#endif
-
-/* Interface to AVL tree generic package instantiation. */
-
-#define AVL_UNIQUE(BASE) U(avl_ ## BASE)
-
-#define AVL_HANDLE ptr_record *
-
-#define AVL_KEY U(size_bau)
-
-#define AVL_MAX_DEPTH 64
-
-#include "cavl_if.h"
-
-#endif // VPX_MEM_MEMORY_MANAGER_INCLUDE_HMM_INTRNL_H_
--- a/vpx_mem/vpx_mem.c
+++ b/vpx_mem/vpx_mem.c
@@ -27,30 +27,6 @@
#endif
#endif
-#if CONFIG_MEM_MANAGER
-# include "heapmm.h"
-# include "hmm_intrnl.h"
-
-# define SHIFT_HMM_ADDR_ALIGN_UNIT 5
-# define TOTAL_MEMORY_TO_ALLOCATE 20971520 /* 20 * 1024 * 1024 */
-
-# define MM_DYNAMIC_MEMORY 1
-# if MM_DYNAMIC_MEMORY
-static unsigned char *g_p_mng_memory_raw = NULL;
-static unsigned char *g_p_mng_memory = NULL;
-# else
-static unsigned char g_p_mng_memory[TOTAL_MEMORY_TO_ALLOCATE];
-# endif
-
-static size_t g_mm_memory_size = TOTAL_MEMORY_TO_ALLOCATE;
-
-static hmm_descriptor hmm_d;
-static int g_mng_memory_allocated = 0;
-
-static int vpx_mm_create_heap_memory();
-static void *vpx_mm_realloc(void *memblk, size_t size);
-#endif /*CONFIG_MEM_MANAGER*/
-
#if USE_GLOBAL_FUNCTION_POINTERS
struct GLOBAL_FUNC_POINTERS {g_malloc_func g_malloc;
@@ -85,46 +61,11 @@
return ver;
}
-int vpx_mem_set_heap_size(size_t size) {- int ret = -1;
-
-#if CONFIG_MEM_MANAGER
-#if MM_DYNAMIC_MEMORY
-
- if (!g_mng_memory_allocated && size) {- g_mm_memory_size = size;
- ret = 0;
- } else
- ret = -3;
-
-#else
- ret = -2;
-#endif
-#else
- (void)size;
-#endif
-
- return ret;
-}
-
void *vpx_memalign(size_t align, size_t size) {void *addr,
* x = NULL;
-#if CONFIG_MEM_MANAGER
- int number_aau;
-
- if (vpx_mm_create_heap_memory() < 0) {- _P(printf("[vpx][mm] ERROR vpx_memalign() Couldn't create memory for Heap.\n");)- }
-
- number_aau = ((size + align - 1 + ADDRESS_STORAGE_SIZE) >>
- SHIFT_HMM_ADDR_ALIGN_UNIT) + 1;
-
- addr = hmm_alloc(&hmm_d, number_aau);
-#else
addr = VPX_MALLOC_L(size + align - 1 + ADDRESS_STORAGE_SIZE);
-#endif /*CONFIG_MEM_MANAGER*/
if (addr) {x = align_addr((unsigned char *)addr + ADDRESS_STORAGE_SIZE, (int)align);
@@ -171,11 +112,7 @@
addr = (void *)(((size_t *)memblk)[-1]);
memblk = NULL;
-#if CONFIG_MEM_MANAGER
- new_addr = vpx_mm_realloc(addr, size + align + ADDRESS_STORAGE_SIZE);
-#else
new_addr = VPX_REALLOC_L(addr, size + align + ADDRESS_STORAGE_SIZE);
-#endif
if (new_addr) {addr = new_addr;
@@ -193,11 +130,7 @@
void vpx_free(void *memblk) { if (memblk) {void *addr = (void *)(((size_t *)memblk)[-1]);
-#if CONFIG_MEM_MANAGER
- hmm_free(&hmm_d, addr);
-#else
VPX_FREE_L(addr);
-#endif
}
}
@@ -493,108 +426,6 @@
return VPX_MEMMOVE_L(dest, src, count);
}
-
-#if CONFIG_MEM_MANAGER
-
-static int vpx_mm_create_heap_memory() {- int i_rv = 0;
-
- if (!g_mng_memory_allocated) {-#if MM_DYNAMIC_MEMORY
- g_p_mng_memory_raw =
- (unsigned char *)malloc(g_mm_memory_size + HMM_ADDR_ALIGN_UNIT);
-
- if (g_p_mng_memory_raw) {- g_p_mng_memory = (unsigned char *)((((unsigned int)g_p_mng_memory_raw) +
- HMM_ADDR_ALIGN_UNIT - 1) &
- -(int)HMM_ADDR_ALIGN_UNIT);
-
- _P(printf("[vpx][mm] total memory size:%d g_p_mng_memory_raw:0x%x g_p_mng_memory:0x%x\n"-, g_mm_memory_size + HMM_ADDR_ALIGN_UNIT
-, (unsigned int)g_p_mng_memory_raw
-, (unsigned int)g_p_mng_memory);)
- } else {- _P(printf("[vpx][mm] Couldn't allocate memory:%d for vpx memory manager.\n"-, g_mm_memory_size);)
-
- i_rv = -1;
- }
-
- if (g_p_mng_memory)
-#endif
- {- int chunk_size = 0;
-
- g_mng_memory_allocated = 1;
-
- hmm_init(&hmm_d);
-
- chunk_size = g_mm_memory_size >> SHIFT_HMM_ADDR_ALIGN_UNIT;
-
- chunk_size -= DUMMY_END_BLOCK_BAUS;
-
- _P(printf("[vpx][mm] memory size:%d for vpx memory manager. g_p_mng_memory:0x%x chunk_size:%d\n"-, g_mm_memory_size
-, (unsigned int)g_p_mng_memory
-, chunk_size);)
-
- hmm_new_chunk(&hmm_d, (void *)g_p_mng_memory, chunk_size);
- }
-
-#if MM_DYNAMIC_MEMORY
- else {- _P(printf("[vpx][mm] Couldn't allocate memory:%d for vpx memory manager.\n"-, g_mm_memory_size);)
-
- i_rv = -1;
- }
-
-#endif
- }
-
- return i_rv;
-}
-
-static void *vpx_mm_realloc(void *memblk, size_t size) {- void *p_ret = NULL;
-
- if (vpx_mm_create_heap_memory() < 0) {- _P(printf("[vpx][mm] ERROR vpx_mm_realloc() Couldn't create memory for Heap.\n");)- } else {- int i_rv = 0;
- int old_num_aaus;
- int new_num_aaus;
-
- old_num_aaus = hmm_true_size(memblk);
- new_num_aaus = (size >> SHIFT_HMM_ADDR_ALIGN_UNIT) + 1;
-
- if (old_num_aaus == new_num_aaus) {- p_ret = memblk;
- } else {- i_rv = hmm_resize(&hmm_d, memblk, new_num_aaus);
-
- if (i_rv == 0) {- p_ret = memblk;
- } else {- /* Error. Try to malloc and then copy data. */
- void *p_from_malloc;
-
- new_num_aaus = (size >> SHIFT_HMM_ADDR_ALIGN_UNIT) + 1;
- p_from_malloc = hmm_alloc(&hmm_d, new_num_aaus);
-
- if (p_from_malloc) {- vpx_memcpy(p_from_malloc, memblk, size);
- hmm_free(&hmm_d, memblk);
-
- p_ret = p_from_malloc;
- }
- }
- }
- }
-
- return p_ret;
-}
-#endif /*CONFIG_MEM_MANAGER*/
#if USE_GLOBAL_FUNCTION_POINTERS
# if CONFIG_MEM_TRACKER
--- a/vpx_mem/vpx_mem.h
+++ b/vpx_mem/vpx_mem.h
@@ -53,18 +53,6 @@
*/
unsigned int vpx_mem_get_version(void);
- /*
- vpx_mem_set_heap_size(size_t size)
- size - size in bytes for the memory manager to allocate for its heap
- Sets the memory manager's initial heap size
- Return:
- 0: on success
- -1: if memory manager calls have not been included in the vpx_mem lib
- -2: if the memory manager has been compiled to use static memory
- -3: if the memory manager has already allocated its heap
- */
- int vpx_mem_set_heap_size(size_t size);
-
void *vpx_memalign(size_t align, size_t size);
void *vpx_malloc(size_t size);
void *vpx_calloc(size_t num, size_t size);
--- a/vpx_mem/vpx_mem.mk
+++ b/vpx_mem/vpx_mem.mk
@@ -5,18 +5,3 @@
MEM_SRCS-$(CONFIG_MEM_TRACKER) += vpx_mem_tracker.c
MEM_SRCS-$(CONFIG_MEM_TRACKER) += include/vpx_mem_tracker.h
-
-MEM_SRCS-$(CONFIG_MEM_MANAGER) += memory_manager/hmm_true.c
-MEM_SRCS-$(CONFIG_MEM_MANAGER) += memory_manager/hmm_resize.c
-MEM_SRCS-$(CONFIG_MEM_MANAGER) += memory_manager/hmm_shrink.c
-MEM_SRCS-$(CONFIG_MEM_MANAGER) += memory_manager/hmm_largest.c
-MEM_SRCS-$(CONFIG_MEM_MANAGER) += memory_manager/hmm_dflt_abort.c
-MEM_SRCS-$(CONFIG_MEM_MANAGER) += memory_manager/hmm_base.c
-MEM_SRCS-$(CONFIG_MEM_MANAGER) += memory_manager/include
-MEM_SRCS-$(CONFIG_MEM_MANAGER) += memory_manager/include/hmm_intrnl.h
-MEM_SRCS-$(CONFIG_MEM_MANAGER) += memory_manager/include/cavl_if.h
-MEM_SRCS-$(CONFIG_MEM_MANAGER) += memory_manager/include/hmm_cnfg.h
-MEM_SRCS-$(CONFIG_MEM_MANAGER) += memory_manager/include/heapmm.h
-MEM_SRCS-$(CONFIG_MEM_MANAGER) += memory_manager/include/cavl_impl.h
-MEM_SRCS-$(CONFIG_MEM_MANAGER) += memory_manager/hmm_grow.c
-MEM_SRCS-$(CONFIG_MEM_MANAGER) += memory_manager/hmm_alloc.c