abl_heap.c

来自「SHARP_ARM720T_LH79524/5软件开发包_支持TFT_LCD_N」· C语言 代码 · 共 742 行 · 第 1/2 页

/***********************************************************************
 * $Workfile:   abl_heap.c  $
 * $Revision:   1.1  $
 * $Author:   WellsK  $
 * $Date:   Sep 02 2003 14:24:46  $
 *
 * Project: Simple heap manager
 *
 * Description:
 *     See the header file for a description of this package.
 *
 * Revision History:
 * $Log:   //smaicnt2/pvcs/VM/sharpmcu/archives/sharpmcu/software/abl/source/abl_heap.c-arc  $
 * 
 *    Rev 1.1   Sep 02 2003 14:24:46   WellsK
 * Corrected naming conventions to abl_ from sma_.
 * 
 *    Rev 1.0   Jun 09 2003 12:06:28   WellsK
 * Initial revision.
 * 
 *
 ***********************************************************************
 * SHARP MICROELECTRONICS OF THE AMERICAS MAKES NO REPRESENTATION
 * OR WARRANTIES WITH RESPECT TO THE PERFORMANCE OF THIS SOFTWARE,
 * AND SPECIFICALLY DISCLAIMS ANY RESPONSIBILITY FOR ANY DAMAGES, 
 * SPECIAL OR CONSEQUENTIAL, CONNECTED WITH THE USE OF THIS SOFTWARE.
 *
 * SHARP MICROELECTRONICS OF THE AMERICAS PROVIDES THIS SOFTWARE SOLELY 
 * FOR THE PURPOSE OF SOFTWARE DEVELOPMENT INCORPORATING THE USE OF A 
 * SHARP MICROCONTROLLER OR SYSTEM-ON-CHIP PRODUCT. USE OF THIS SOURCE
 * FILE IMPLIES ACCEPTANCE OF THESE CONDITIONS.
 *
 * COPYRIGHT (C) 2001 SHARP MICROELECTRONICS OF THE AMERICAS, INC.
 *     CAMAS, WA
 **********************************************************************/

#include "abl_heap.h"

/***********************************************************************
 * Package types
 **********************************************************************/

/* Heap descriptor */
typedef struct
{
    UNS_32 entry_size;       /* Size of this heap entry including
                                the descriptor (0 = used) */
    void *next_descriptor;   /* Pointer to next descriptor (0 = last) */
    void *prev_descriptor;   /* Pointer to previous descriptor
                                (heap_base = no previous entry) */
} HEAP_DESCRIPTOR_T;

/***********************************************************************
 * Package data
 **********************************************************************/

/* Heap base address */
HEAP_DESCRIPTOR_T *heap_base;
/* Heap size */
UNS_32 heap_size_saved;

/***********************************************************************
 * Package defines
 **********************************************************************/

/* Pointer to NULL heap descriptor */
#define HEAP_POINTER_NULL   ((HEAP_DESCRIPTOR_T *) 0)
/* Heap descriptor size */
#define HEAP_HEAD_SIZE      (sizeof (HEAP_DESCRIPTOR_T))
/* Smallest heap descriptor entry */
#define SMALLEST_ENTRY_SIZE (HEAP_HEAD_SIZE + sizeof (UNS_32))

/***********************************************************************
 * Private functions
 **********************************************************************/

/***********************************************************************
 *
 * Function: abl_find_free_entry
 *
 * Purpose: Finds a chunk of free heap memory with the required size
 *
 * Processing:
 *     The heap list is traversed until an entry with the minimum
 *     required size available is found.
 *
 * Parameters:
 *     size_in_bytes : Byte size of the requested allocation area
 *
 * Outputs: None
 *
 * Returns: A pointer to the chunk with the minimum required size, or
 *          '0' if a chunk does not exist.
 *
 * Notes: None
 *
 **********************************************************************/
HEAP_DESCRIPTOR_T *abl_find_free_entry (UNS_32 size_in_bytes)
{
    HEAP_DESCRIPTOR_T *found_ptr;
    INT_32 found = 0;

    /* Start at top of list */
    found_ptr = heap_base;

    /* Loop through entries */
    while (found == 0)
    {
        if (found_ptr->entry_size >= (size_in_bytes + HEAP_HEAD_SIZE))
        {
            /* There is enough room in this heap chunk for the required
               data allocation and a new heap descriptor */
            found = 1;
        }
        else
        {
            /* Go to next heap descriptor in the list */
            found_ptr = found_ptr->next_descriptor;

            /* Exit on last descriptor */
            found = (found_ptr == HEAP_POINTER_NULL);
        }
    }

    return found_ptr;
}

/***********************************************************************
 *
 * Function: abl_heap_insert_entry
 *
 * Purpose: Get an allocated area from the heap
 *
 * Processing:
 *     A data entry in the heap must always have a data size evenly
 *     divided by 4. The size may be adjusted up the meet this size
 *     requirement. A call to 'abl_find_free_entry' is performed to
 *     determine if and where the next available chunk in the heap
 *     area exists. If a NULL pointer is returned, a valid size chunk
 *     does not exist, and the function will exit with the NULL return
 *     status. If a valid pointer is return, then the pointer indicates
 *     the start of a new available heap chunk entry.
 *
 * Parameters:
 *     size_in_bytes : Where to insert in the linked list
 *
 * Outputs: None
 *
 * Returns: A pointer to the allocated data area (not the heap
 *          descriptor pointer) or NULL if there is no more room for
 *          the data entry.
 *
 * Notes: None
 *
 **********************************************************************/
void *abl_heap_insert_entry (UNS_32 size_in_bytes)
{
    HEAP_DESCRIPTOR_T *insert_ptr, *save_entry, *new_entry;
    UNS_32 heap_chunk_size, return_address = 0;

    /* If the size is not mod 4, then increase it until it is */
    if ((size_in_bytes & 0x00000003) != 0)
    {
        size_in_bytes = size_in_bytes + 4;
        size_in_bytes = size_in_bytes & 0xFFFFFFFC;
    }

    /* See if a chunk of heap memory with the required size exists */
    insert_ptr = abl_find_free_entry (size_in_bytes);

    /* Only insert the heap entry if space is available */
    if (insert_ptr != HEAP_POINTER_NULL)
    {
        /* This is the real required chunk size and includes the heap
           descriptor */
        heap_chunk_size = size_in_bytes + sizeof (HEAP_DESCRIPTOR_T);

        /* Determine if the size of this entry plus the size of the
           heap descriptor will leave enough room in this chunk for
           another entry with the minimum heap entry size */
        if ((heap_chunk_size + SMALLEST_ENTRY_SIZE) >
           insert_ptr->entry_size)
        {
            /* Next entry will not have enough room for the heap
               descriptor and a minimum data entry, so use the entire
               heap chunk for this heap entry */
            heap_chunk_size = insert_ptr->entry_size;
        }
        else
        {
            /* This area of heap memory is large enough for another
               chunk after this one is allocated, so insert this chunk
               and set the heap descriptor link to point to the chunk
               after this chunk */

            /* Save link to next entry */
            save_entry = insert_ptr->next_descriptor;

            /* Create the new entry to insert into the chunk (the chunk
               will be broken into a smaller chunk and an allocated
               data entry */
            new_entry = (HEAP_DESCRIPTOR_T *) ((UNS_32) insert_ptr +
                heap_chunk_size);

            /* Point the new entry to the link where the insert entry
               was originally pointing to */
            new_entry->next_descriptor = save_entry;

            /* Update the size of the new entry to be the size of the
               original entry minus the required and heap descriptor
               sizes */
            new_entry->entry_size = insert_ptr->entry_size -
                heap_chunk_size;

            /* Link this data entry to new chunk entry */
            insert_ptr->next_descriptor = new_entry;

            /* Link the following entry back to this entry */
            new_entry->prev_descriptor = insert_ptr;

            /* If the next entry after the new entry is not the last
               entry, then updates it previous entry link to point
              to the new entry */
            if (new_entry->next_descriptor != HEAP_POINTER_NULL)
            {
                ((HEAP_DESCRIPTOR_T *)
                    (new_entry->next_descriptor))->prev_descriptor =
                    new_entry;
            }

            /* Set return address past the heap descriptor */
            return_address = (UNS_32) insert_ptr + HEAP_HEAD_SIZE;
        }

        /* Set this entire chunk as allocated */
        insert_ptr->entry_size = 0;
    }

    return (UNS_32 *) return_address;
}

/***********************************************************************
 *
 * Function: abl_find_entry
 *
 * Purpose: Finds a chunk of heap memory which matches the passed data
 *          address.
 *
 * Processing:
 *     The data address passed to this search function must be adjusted
 *     by the heap descriptor size to get the address of the heap
 *     descriptor entry. To provide high realiability, the heap list is
 *     traversed instead of directly accessed to find the entry. If the
 *     entry exists, the address of the heap descriptor is returned.
 *
 * Parameters:
 *     data_entry_addr : Address of an allocated data entry in the heap
 *
 * Outputs: None
 *
 * Returns: A pointer to heap entry, or NULL if it does not exist.
 *
 * Notes: None
 *
 **********************************************************************/
HEAP_DESCRIPTOR_T *abl_find_entry (UNS_32 *data_entry_addr)
{
    HEAP_DESCRIPTOR_T *search_heap_ptr = heap_base;
    HEAP_DESCRIPTOR_T *found_heap_ptr = HEAP_POINTER_NULL;

    /* Loop until match is found or all entries exhausted */
    while ((search_heap_ptr != HEAP_POINTER_NULL) &&
        (found_heap_ptr == HEAP_POINTER_NULL))
    {
        if (search_heap_ptr->entry_size == 0)
        {
            /* This entry is used, does the data address match entry? */
            if ((UNS_32) data_entry_addr ==
                ((UNS_32) search_heap_ptr + HEAP_HEAD_SIZE))
            {
                /* It matches, this entry must be deleted */
                found_heap_ptr = search_heap_ptr;
            }
        }

        search_heap_ptr = search_heap_ptr->next_descriptor;
    }

    return found_heap_ptr;
}

/***********************************************************************
 *
 * Function: abl_remove_entry
 *
 * Purpose:
 *     Removes the heap data entry with the passed address if it exists
 *
 * Processing:
 *     This function performs restoration of a heap entry into the heap
 *     chunk list. (A chunk is a free area of the heap). Depending on
 *     the data location in the heap list, a different function may be
 *      performed for each case. See the function for more details.
 *
 * Parameters:
 *     heap_entry_addr : Address of a data entry to return to the heap
 *                       chunk list
 *
 * Outputs: None
 *
 * Returns: '1' if the entry was removed, otherwise '0'.
 *
 * Notes: None
 *
 **********************************************************************/
INT_32 abl_remove_entry (UNS_32 *heap_entry_addr)
{
    HEAP_DESCRIPTOR_T *found_ptr, *next_ptr, *prev_ptr, *saved_ptr;
    INT_32 status = 0;

    /* Determine if the chunk to deallocate is valid */
    found_ptr = abl_find_entry (heap_entry_addr);

    /* If the chunk is valid, then deallocate it */
    if (found_ptr != HEAP_POINTER_NULL)
    {
        next_ptr = found_ptr->next_descriptor;

        /* There are a number of different permutations of the heap
           entry return function. The following list is are the
           possible choices for the entry:
            * This is the only heap entry (first entry only)
            * This is the first entry, and the next entry is used
            * This is the first entry, and the next entry is empty
            * This is the last entry, and the previous entry is used
            * This is the last entry, and the previous entry is empty
            * The previous entry and next entry are both used
            * The previous entry is not used, and the next entry is used
            * The previous entry is used, and the next entry is not used
            * The previous entry and next entry are both not used */

        /* First or only entry cases */
        if (found_ptr == heap_base)
        {
            if (next_ptr == HEAP_POINTER_NULL)
            {
                /* This is the only heap entry (first entry only)
                   Simply restore heap size to full size */
                found_ptr->entry_size = heap_size_saved;
            }
            else if (next_ptr->entry_size == 0)
            {
                /* Next entry is used, simply clear this entry by
                   restoring it's size */
                found_ptr->entry_size = (UNS_32) next_ptr -
                    (UNS_32) found_ptr;
            }
            else
            {
                /* Next entry is also empty, so the first entry
                   and the next entry need to be merged */

                /* Save pointer to entry after next entry */
                prev_ptr = next_ptr->next_descriptor;

                /* Update the current next entry point to the entry
                   after the next entry */
                found_ptr->next_descriptor = prev_ptr;

                /* If the 'new' next descriptor exists, update its
                   previous descriptor pointer to point to the entry */