lld.c

C语言库函数的源代码,是C语言学习参考的好文档。

/* +++Date last modified: 05-Jul-1997 */

/* =======================================================================
    LLD.c           Generic Doubly Linked Lists for fixed size data.
                    Each List has its own specific data size.
                    This version uses dummy head and dummy tail nodes.
                    Which prevents special handling for the first and last
                    nodes.

                    v1.00  94-08-21
                    v1.01  95-10-21  Changed ListCountInit to unsigned.

                    Compile with NDEBUG not defined for debugging version.
                    Compile with NDEBUG defined for production version.

                    The node pointers are restricted to valid values.
                    They point only in empty lists to invalid data.

                    Possible future enhancements:
                    - List(s) of free nodes for fast node memory alloc.
                    - FindFirst() & FindNext().
                    - Data access via first and/or last node pointers.
                      (duplicate the functions and change .current to
                      .first or .last)
                    - Node deletion via first and/or last node pointers.
                      (as for access functions, then simplify ...)

 _____              This version is Public Domain.
 /_|__|             A.Reitsma, Delft, The Netherlands.
/  | \  --------------------------------------------------------------- */

#include <stdarg.h>         /* variable arg handling */
#include <assert.h>         /* debugging */

#if defined( __TURBOC__ ) && !defined( __BORLANDC__ )
 #include <stdio.h> /* required for early Turbo compilers with assert() */
#endif

#include "ll_defs.h"        /* debugging incl MALLOC (re-) definition   */
#include "LLD.h"            /* also includes extkword.h if necessary    */

#define NO_PROBLEMS LIST_NO_PROBLEMS /* local redefinition */

struct Node
{
    struct Node * next;
    struct Node * prev;
    int data;               /* also place-holder for larger items.      */
};                          /* actual nodes have various sizes,         */
                            /* but a fixed size within a list.          */
struct ListHead
{
    struct Node * current;  /* points to the actual current node        */
    struct Node * first;    /* always points to dummy head node         */
    struct Node * last;     /* always points to dummy tail node         */
    int itemsize ;          /* zero value: used as 'list not used' flag */
};

#define ERR_MEMORY          -1

#define NODE_MALLOC(list)   (struct Node *) \
                            MALLOC( ListControl[ list ].itemsize \
                                    + 2 * sizeof( struct Node * ), char )

#define NODE_FREE(node)     FREE(node)

/* ---- Local data ---------------------------------------------------- */

static struct ListHead * ListControl = NULL;
static unsigned int ListCount ;

/* ---- LL system management ------------------------------------------ */

static int ListInit( int List, int ItemSize )
{
    struct Node * Tmp ;

    if( 0 != ItemSize )
    {
        /* create dummy head node
        */
        Tmp = NODE_MALLOC( List );
        if( NULL == Tmp )
        {
            return ERR_MEMORY ;
        }
        Tmp->prev = NULL ;     /* NULL identifies it as dummy head node */
        Tmp->data = (int)0xA709;       /* dummy value                   */
        ListControl[ List ].first = Tmp ;

        /* create dummy tail node
        */
        Tmp = NODE_MALLOC( List );
        if( NULL == Tmp )
        {
            NODE_FREE( Tmp );          /* no need to cause memory leaks */
            ListControl[ List ].first = NULL ; /* or other errors       */
            return ERR_MEMORY ;        /* even if we're in trouble ...  */
        }
        Tmp->next = NULL ;     /* NULL identifies it as dummy tail node */
        Tmp->data = (int)0xA725;       /* dummy value                   */
        Tmp->prev = ListControl[ List ].first ;

        ListControl[ List ].current     =
        ListControl[ List ].last        =
        ListControl[ List ].first->next = Tmp ;
    }
    else
    {
        ListControl[ List ].current =
        ListControl[ List ].first   =
        ListControl[ List ].last    = NULL ;
    }

    ListControl[ List ].itemsize = ItemSize ; /* zero: list not used    */
    return NO_PROBLEMS ;
}

int LLDsystemInit( unsigned ListCountInit )
{
    assert( (unsigned) ( ListCountInit -1 ) <= 20 -1 );
                 /* higher than 20 is ridiculous for an initial setup   */
                 /* zero is useless                                     */

    if( NULL != ListControl )
    {
        return NO_PROBLEMS ; /* LL system already initialized */
    }

    ListControl = MALLOC( ListCountInit, struct ListHead );
    if( NULL == ListControl )
    {
        return ERR_MEMORY ;
    }

    for( ListCount = 0 ; ListCount < ListCountInit ; ListCount++ )
        ListInit( ListCount, 0 ); /* just mark it as usable ... */

    /* ListCount is now ListCountInit */
    assert( ListCount == ListCountInit );

    return NO_PROBLEMS;
}

int LLDcreate( int ItemSize )
{
    unsigned List ;

    assert( (unsigned) ( ItemSize -1 ) < 1024 -1 ) ;
                             /* limit to 1kB. A size of 0 is ridiculous */

    /* trigger automatic system initialisation if necessary
    */
    if( NULL == ListControl  &&  0 != LLDsystemInit( 1 ))
    {
        return ERR_MEMORY ;
    }

    /* Look for empty slot
    */
    for( List = 0; List < ListCount; List++ )
    {
        if( 0 == ListControl[ List ].itemsize )
            break;
    }

    /*  What if NO EMPTY slot ???
    */
    if( List == ListCount )
    {
        struct ListHead * tmp ;         /* ListControl expansion needed */

        tmp = MALLOC( ListCount + 1, struct ListHead );
        if( NULL == tmp )
        {
            return ERR_MEMORY ;
        }

        memcpy( tmp, ListControl, ListCount * sizeof( struct ListHead ));
        ListControl = tmp ;
        ListCount++ ;
    }

    /* create dummy head node and set up ListControl for the list.
    */
    if( ERR_MEMORY == ListInit( List, ItemSize ))
    {
        return ERR_MEMORY ;
    }

    return (int) List ;
}

void LLDdelete( int List )
{
    struct Node * Tmp ;
    struct Node * Old ;

    assert( (unsigned) List < ListCount );

    Tmp = ListControl[ List ].first ; /* dummies are also deleted !!!   */
    while( NULL != Tmp )              /* still assuming last node has   */
    {                                 /* a NULL next pointer ...        */
        Old = Tmp ;
        Tmp = Old->next;
        NODE_FREE( Old ); /* data already presumed to be deleted */
    }

    ListInit( List, 0 ); /* 0: mark list as not used. */

    return ;
}

/* ---- LL system maintenance ----------------------------------------- */

int LLDcheck( int List )
{
    if( NULL == ListControl )
    {
        return LIST_SYSTEM_NULL ;
    }

    if( (unsigned) List >= ListCount )
    {
        return LIST_INV_NUMBER ;
    }

    if( 0 == ListControl[ List ].itemsize )
    {
        return LIST_NOT_CREATED ;
    }

    if( NULL == ListControl[ List ].first
        || NULL == ListControl[ List ].first->next    /* missing tail ? */
        || NULL != ListControl[ List ].first->prev )
    {
        return LIST_ERR_HEAD ;
    }

    /* Validate current pointer
    */
    if( NULL == ListControl[ List ].current )
    {
        return LIST_CORRUPT7 ;    /* shouldn't be NULL with a good head */
    }

    if( NULL != ListControl[ List ].first->next->next ) /* empty list ? */
    {                                                   /* not empty.   */
        struct Node * tmp = ListControl[ List ].first ;

        if( NULL == ListControl[ List ].current->next )
        {
            return LIST_CORRUPT6 ; /* a NULL next pointer is only valid */
        }                          /* for an empty list.                */

        /* look for .current in list,
           checking the .prev links along the way
        */
        do
        {
            tmp = tmp->next ;

            if( NULL == tmp || NULL == tmp->prev
                || tmp != tmp->prev->next )
            {
                return LIST_CORRUPT5 ;  /* current not found in list */
            }                           /* or link to/from next node */
                                        /* invalid                   */
        }while( tmp != ListControl[ List ].current );

        /* Found .current in list. Also without link errors.
           Now look for valid last node pointer in the list,
           checking the .prev links along the way
           Note that .current itself is never supposed to be equal
           to .last (which points to the dummy tail) !
        */
        if( NULL == ListControl[ List ].last )
        {
            return LIST_ERR_LAST ;
        }

        do
        {
            tmp = tmp->next ;
            if( NULL == tmp || NULL == tmp->prev
                || tmp != tmp->prev->next )
            {
                return LIST_CORRUPT4 ;  /* last not found in list    */
            }                           /* or link to/from prev node */
                                        /* invalid                   */
        }while( tmp != ListControl[ List ].last );

        /* Found .last in list but is it really a valid last pointer?
           Note: tmp == .last
        */
        if( NULL != tmp->next )
        {
            return LIST_CORRUPT3 ;
        }

        return NO_PROBLEMS ;
    }

    /* .first->next->next == NULL  =>  list is empty
    */
    if( ListControl[ List ].current != ListControl[ List ].first->next )
    {
        return LIST_CORRUPT2 ;
    }

    if( ListControl[ List ].last != ListControl[ List ].first->next
        || ListControl[ List ].last
                             != ListControl[ List ].current->prev->next )
    {
        return LIST_CORRUPT1 ;
    }

    return LIST_EMPTY ;
}

/* ---- node management ----------------------------------------------- */

int LLDnodeInsert( int List, ... )      /* insert _BEFORE_ current node */
{
    va_list DataPtr ;
    int Retval ;

    /* set DataPtr to the address of "..."
       then action, cleanup and return.
    */
    va_start( DataPtr, List );