yc_dblnklst.c

一个类STL的多平台可移植的算法容器库,主要用于嵌入式系统编程时的内存管理等方面

/*
 * The young Library
 * Copyright (c) 2005 by Yang Huan(杨桓)

 * Permission to use, copy, modify, distribute and sell this software for any
 * purpose is hereby granted without fee, provided that the above copyright
 * notice appear in all copies and that both that copyright notice and this
 * permission notice appear in supporting documentation.
 * The author make no representations about the suitability of this software
 * for any purpose. It is provided "as is" without express or implied warranty.
 */

/******************************************************************************/
/******************************************************************************/
#include "yc_memalgo.h"
#include "yc_dblnklst.h"

#ifdef __cplusplus
    namespace youngc {  extern "C" {
#endif
/******************************************************************************/
/******************************************************************************/

#define DATA( NODE )  ( ((ylib_byte_t*)(NODE)) + sizeof(dblnklst_node) )

#define COPY_VALUE( PDST, PSRC, ELMTSIZE, COPYFUN )      \
        if( COPYFUN )                                    \
            (COPYFUN)( (PDST), (PSRC) );                 \
        else if( sizeof(int) == (ELMTSIZE) )             \
            *( (int*)(PDST) ) = *( (int*)(PSRC) );       \
        else if( sizeof(double) == (ELMTSIZE) )          \
            *( (double*)(PDST) ) = *( (double*)(PSRC) ); \
        else if( sizeof(char) == (ELMTSIZE) )            \
            *( (char*)(PDST) ) = *( (char*)(PSRC) );     \
        else if( sizeof(short) == (ELMTSIZE) )           \
            *( (short*)(PDST) ) = *( (short*)(PSRC) );   \
        else                                             \
            ylib_memcopy( (PDST), (PSRC), ELMTSIZE )

/******************************************************************************/
/* iterator */
/******************************************************************************/

#ifndef __MACRO_C_YOUNG_LIBRARY_COMPILER_SUPPORT_INLINE_FUNCTION__
    void* dblnklst_itr_deref( dblnklst_node* itr )
    {
        return DATA( itr );
    }

/******************************************************************************/

    void dblnklst_itr_inc( dblnklst_node** pitr )
    {
        *pitr = (*pitr)->next;
    }

/******************************************************************************/

    void dblnklst_itr_dec( dblnklst_node** pitr )
    {
        *pitr = (*pitr)->prev;
    }
#endif

/******************************************************************************/

void dblnklst_itr_inc_n( dblnklst_node** pitr, size_t n )
{
    for( ; n > 0; --n )
        *pitr = (*pitr)->next;
}

/******************************************************************************/

void dblnklst_itr_dec_n( dblnklst_node** pitr, size_t n )
{
    for( ; n > 0; --n )
        *pitr = (*pitr)->prev;
}

/******************************************************************************/

dblnklst_node* dblnklst_itr_add( dblnklst_node* itr, size_t n )
{
    for( ; n > 0; --n )
        itr = itr->next;
    return itr;
}

/******************************************************************************/

dblnklst_node* dblnklst_itr_sub( dblnklst_node* itr, size_t n )
{
    for( ; n > 0; --n )
        itr = itr->prev;
    return itr;
}

/******************************************************************************/
/* doubly linked list */
/******************************************************************************/

void dblnklst_init( dblnklst* uninit_self,
                    size_t element_size,
                    ylib_fp_copy_t elmt_init_copy,
                    ylib_fp_copy_t elmt_assign_copy,
                    ylib_fp_oper_t elmt_destroy,
                    ylib_fp_alloc_t alloc,
                    ylib_fp_dealloc_t dealloc )
{
    uninit_self->m_header.prev = &(uninit_self->m_header);
    uninit_self->m_header.next = &(uninit_self->m_header);
    uninit_self->m_element_size = element_size;
    uninit_self->m_elmt_destroy = elmt_destroy;
    uninit_self->m_elmt_init_copy = elmt_init_copy;
    uninit_self->m_elmt_assign_copy = elmt_assign_copy;
    uninit_self->m_alloc = alloc;
    uninit_self->m_dealloc = dealloc;
}

/******************************************************************************/

void dblnklst_destroy( dblnklst* self )
{
    if( &(self->m_header) != self->m_header.next )
    {
        dblnklst_erase_range( self, self->m_header.next, &(self->m_header) );
        self->m_header.prev = &(self->m_header);
        self->m_header.next = &(self->m_header);
    }
}

/******************************************************************************/

int dblnklst_init_copy( dblnklst* uninit_self, const dblnklst* src )
{
    if( uninit_self == src )
        return -1;
    else
    {
        dblnklst_node* last = &(uninit_self->m_header);
        const dblnklst_node* srcfirst = src->m_header.next;
        const dblnklst_node* srclast = &(src->m_header);

        *uninit_self = *src;
        uninit_self->m_header.prev = &(uninit_self->m_header);
        uninit_self->m_header.next = &(uninit_self->m_header);

        while( srcfirst != srclast )
        {
            if( !dblnklst_insert_node( uninit_self, last, DATA(srcfirst) ) )
            {
                dblnklst_destroy( uninit_self );
                return 0;
            }
            srcfirst = srcfirst->next;
        }
    }

    return 1;
}

/******************************************************************************/

int dblnklst_assign_copy( dblnklst* self, const dblnklst* src )
{
    if( self == src || self->m_element_size != src->m_element_size
        || self->m_elmt_init_copy != src->m_elmt_init_copy
        || self->m_elmt_assign_copy != src->m_elmt_assign_copy )
        return -1;
    else
    {
        dblnklst_node* dstfirst = self->m_header.next;
        dblnklst_node* dstlast = &(self->m_header);
        const dblnklst_node* srcfirst = src->m_header.next;
        const dblnklst_node* srclast = &(src->m_header);

        while( dstfirst != dstlast && srcfirst != srclast )
        {
            COPY_VALUE( DATA(dstfirst), DATA(srcfirst),
                        self->m_element_size, self->m_elmt_assign_copy );
            dstfirst = dstfirst->next;
            srcfirst = srcfirst->next;
        }

        if( dstfirst != dstlast && srcfirst == srclast )
            dblnklst_erase_range( self, dstfirst, dstlast );
        else if( dstfirst == dstlast && srcfirst != srclast )
        {
            while( srcfirst != srclast )
            {
                if( !dblnklst_insert_node( self, dstlast, DATA(srcfirst) ) )
                    return 0;
                srcfirst = srcfirst->next;
            }
        }
    }

    return 1;
}

/******************************************************************************/

void dblnklst_init_move( dblnklst* uninit_self, dblnklst* src )
{
    if( uninit_self != src )
    {
        *uninit_self = *src;
        uninit_self->m_header.prev = &(uninit_self->m_header);
        uninit_self->m_header.next = &(uninit_self->m_header);
        dblnklst_swap( uninit_self, src );
    }
}

/******************************************************************************/

void dblnklst_assign_move( dblnklst* self, dblnklst* src )
{
    if( self != src )
        dblnklst_swap( self, src );
}

/******************************************************************************/

void dblnklst_swap( dblnklst* self, dblnklst* other )
{
    if( self != other )
    {
        if( self->m_header.next != &(self->m_header)
            && other->m_header.next != &(other->m_header) )
        {
            /* self isn't empty, other isn't empty */
            dblnklst_node* tmp;
            self->m_header.next->prev = &(other->m_header);
            self->m_header.prev->next = &(other->m_header);
            other->m_header.next->prev = &(self->m_header);
            other->m_header.prev->next = &(self->m_header);
            tmp = self->m_header.next;  /* old front */
            self->m_header.next = other->m_header.next;
            other->m_header.next = tmp;
            tmp = self->m_header.prev;  /* old back */
            self->m_header.prev = other->m_header.prev;
            other->m_header.prev = tmp;
        }
        else if( self->m_header.next == &(self->m_header)
                 && other->m_header.next != &(other->m_header) )
        {
            /* self is empty, other isn't empty */
            other->m_header.next->prev = &(self->m_header);
            other->m_header.prev->next = &(self->m_header);
            self->m_header.next = other->m_header.next;
            self->m_header.prev = other->m_header.prev;
            other->m_header.next = &(other->m_header);
            other->m_header.prev = &(other->m_header);
        }
        else if( other->m_header.next == &(other->m_header)
                 && self->m_header.next != &(self->m_header) )
        {
            /* self isn't empty, other is empty */
            self->m_header.next->prev = &(other->m_header);
            self->m_header.prev->next = &(other->m_header);
            other->m_header.next = self->m_header.next;
            other->m_header.prev = self->m_header.prev;
            self->m_header.next = &(self->m_header);
            self->m_header.prev = &(self->m_header);
        }
    }
}

/******************************************************************************/

size_t dblnklst_size( dblnklst* self )
{
    size_t count = 0;
    dblnklst_node* first = self->m_header.next;
    dblnklst_node* last = &(self->m_header);

    while( first != last )
    {
        ++count;
        first = first->next;
    }

    return count;
}

/******************************************************************************/

void* dblnklst_index( dblnklst* self, size_t index )
{
    dblnklst_node* first = self->m_header.next;

    for( ; index > 0; --index )
        first = first->next;

    return DATA( first );
}

/******************************************************************************/

void* dblnklst_at( dblnklst* self, size_t index )
{
    dblnklst_node* first = self->m_header.next;
    dblnklst_node* last = &(self->m_header);

    for( ; index > 0; --index )
    {
        if( first == last )
            return NULL;
        first = first->next;
    }

    return DATA( first );
}

/******************************************************************************/

void dblnklst_splice_range( dblnklst* self,
                            dblnklst_node* pos,
                            dblnklst* src,
                            dblnklst_node* src_first,
                            dblnklst_node* src_last )
{
    if( pos != src_first && pos != src_last && src_first != src_last )
    {
        dblnklst_node* temp;

        self = self;
        src = src;
        src_last->prev->next = pos;
        src_first->prev->next = src_last;
        pos->prev->next = src_first;
        temp = pos->prev;
        pos->prev = src_last->prev;
        src_last->prev = src_first->prev;
        src_first->prev = temp;
    }
}

/******************************************************************************/

void dblnklst_reverse( dblnklst* self )
{
    if( self->m_header.next != &(self->m_header)            /* size != 0 */
        && self->m_header.next->next != &(self->m_header) ) /* size != 1 */
    {
        dblnklst_node* curr = self->m_header.next->next;

        while( curr != &(self->m_header) )
        {
            curr = curr->next;
            dblnklst_splice_range( self, self->m_header.next,
                                   self, curr->prev, curr );
        }
    }
}

/******************************************************************************/

dblnklst_node* dblnklst_erase_pos( dblnklst* self, dblnklst_node* pos )
{
    if( pos == &(self->m_header) )
        return pos;
    else
    {
        dblnklst_node* prev_node = pos->prev;
        dblnklst_node* next_node = pos->next;
        prev_node->next = next_node;
        next_node->prev = prev_node;
        if( self->m_elmt_destroy )
            self->m_elmt_destroy( DATA(pos) );
        self->m_dealloc( pos, sizeof(dblnklst_node) + self->m_element_size );
        return next_node;
    }
}

/******************************************************************************/

dblnklst_node* dblnklst_erase_range( dblnklst* self,
                                     dblnklst_node* first,
                                     dblnklst_node* last )
{
    dblnklst_node* end = &(self->m_header);

    if( first != last && first != end )
    {
        bool destroy = ( self->m_elmt_destroy ? true : false );
        size_t node_size = sizeof(dblnklst_node) + self->m_element_size;
        dblnklst_node *temp, *erase, *first_prev;

        first_prev = first->prev;
        erase = last->prev;
        first_prev->next = last;
        last->prev = first_prev;

        while( erase != first_prev )