/*
 *  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"