yc_sglnklst.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_sglnklst.h"

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

#define DATA( NODE )  ( ((ylib_byte_t*)(NODE)) + sizeof(sglnklst_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* sglnklst_itr_deref( sglnklst_node* itr )
    {
        return DATA( itr );
    }

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

    void sglnklst_itr_inc( sglnklst_node** pitr )
    {
        *pitr = (*pitr)->next;
    }
#endif

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

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

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

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

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

sglnklst_node* sglnklst_itr_prev( sglnklst_node* header, sglnklst_node* pos )
{
    if( header != pos )
    {
        while( header && header->next != pos )
            header = header->next;
    }
    return header;
}

/******************************************************************************/
/* singly linked list */
/******************************************************************************/

void sglnklst_init( sglnklst* 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.next = NULL;
    uninit_self->m_tail = &(uninit_self->m_header);
    uninit_self->m_element_size = element_size;
    uninit_self->m_elmt_init_copy = elmt_init_copy;
    uninit_self->m_elmt_assign_copy = elmt_assign_copy;
    uninit_self->m_elmt_destroy = elmt_destroy;
    uninit_self->m_alloc = alloc;
    uninit_self->m_dealloc = dealloc;
}

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

void sglnklst_destroy( sglnklst* self )
{
    sglnklst_erase_after_range( self, &(self->m_header), NULL );
}

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

int sglnklst_init_copy( sglnklst* uninit_self, const sglnklst* src )
{
    if( uninit_self == src )
        return -1;
    else
    {
        sglnklst_node* dstbefore = &(uninit_self->m_header);
        const sglnklst_node* srcfirst = src->m_header.next;

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

        while( srcfirst )
        {
            if( !sglnklst_insert_after_node( uninit_self, dstbefore,
                                             DATA(srcfirst) ) )
            {
                sglnklst_destroy( uninit_self );
                return 0;
            }
            dstbefore = dstbefore->next;
            srcfirst = srcfirst->next;
        }
    }

    return 1;
}

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

int sglnklst_assign_copy( sglnklst* self, const sglnklst* 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
    {
        sglnklst_node* dstbefore = &(self->m_header);
        const sglnklst_node* srcfirst = src->m_header.next;

        while( dstbefore->next && srcfirst )
        {
            COPY_VALUE( DATA(dstbefore->next), DATA(srcfirst),
                        self->m_element_size, self->m_elmt_assign_copy );

            dstbefore = dstbefore->next;
            srcfirst = srcfirst->next;
        }

        if( dstbefore->next && !srcfirst )
            sglnklst_erase_after_range( self, dstbefore, NULL );
        else if( !(dstbefore->next) && srcfirst )
        {
            while( srcfirst )
            {
                if( !sglnklst_insert_after_node( self, dstbefore,
                                                 DATA(srcfirst) ) )
                    return 0;
                dstbefore = dstbefore->next;
                srcfirst = srcfirst->next;
            }
        }
    }

    return 1;
}

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

void sglnklst_init_move( sglnklst* uninit_self, sglnklst* src )
{
    if( uninit_self != src )
    {
        *uninit_self = *src;
        src->m_header.next = NULL;
        src->m_tail = &(src->m_header);
        if( !(uninit_self->m_header.next) )
            uninit_self->m_tail = &(uninit_self->m_header);
    }
}

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

void sglnklst_assign_move( sglnklst* self, sglnklst* src )
{
    if( self != src )
    {
        sglnklst temp = *self;
        *self = *src;
        *src = temp;
        if( !(self->m_header.next) )
            self->m_tail = &(self->m_header);
        if( !(src->m_header.next) )
            src->m_tail = &(src->m_header);
    }
}

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

void sglnklst_reverse( sglnklst* self )
{
    if( self->m_header.next && self->m_header.next->next )
    {
        sglnklst_node* first = self->m_header.next->next;
        sglnklst_node* tmplist = self->m_header.next;
        sglnklst_node* next_node;
        tmplist->next = NULL;

        if( first )
            self->m_tail = first;

        while( first )
        {
            next_node = first->next;
            first->next = tmplist;
            tmplist = first;
            first = next_node;
        }

        self->m_header.next = tmplist;
    }
}

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

size_t sglnklst_size( sglnklst* self )
{
    size_t count = 0;
    sglnklst_node* first = self->m_header.next;

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

    return count;
}

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

void* sglnklst_index( sglnklst* self, size_t index )
{
    sglnklst_node* first = self->m_header.next;

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

    return DATA( first );
}

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

void* sglnklst_at( sglnklst* self, size_t index )
{
    sglnklst_node* first = self->m_header.next;

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

    return DATA( first );
}

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

void sglnklst_splice_after_range( sglnklst* self,
                                  sglnklst_node* before_pos,
                                  sglnklst* src,
                                  sglnklst_node* before_first,
                                  sglnklst_node* before_last )
{
    if( before_pos != before_first && before_pos != before_last
        && before_first != before_last )
    {
        sglnklst_node* first = before_first->next;
        sglnklst_node* pos = before_pos->next;
        before_first->next = before_last->next;
        before_pos->next = first;
        before_last->next = pos;

        if( self->m_tail == before_pos )
            self->m_tail = before_last;

        if( src->m_tail == before_last )
            src->m_tail = before_first;
    }
}

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

sglnklst_node* sglnklst_erase_after_pos( sglnklst* self,
                                         sglnklst_node* before_pos )
{
    if( !before_pos || !(before_pos->next) )
        return before_pos;
    else
    {
        sglnklst_node* erase_node = before_pos->next;
        before_pos->next = erase_node->next;
        if( self->m_elmt_destroy )
            self->m_elmt_destroy( DATA(erase_node) );
        self->m_dealloc( erase_node,
                         sizeof(sglnklst_node) + self->m_element_size );
        if( !(before_pos->next) )
            self->m_tail = before_pos;
        return before_pos->next;
    }
}

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

void sglnklst_erase_after_range( sglnklst* self,
                                 sglnklst_node* before_first,
                                 sglnklst_node* last )
{
    size_t node_size = sizeof(sglnklst_node) + self->m_element_size;
    bool destroy = ( self->m_elmt_destroy ? true : false );
    sglnklst_node* first = before_first->next;
    sglnklst_node* erase;

    while( first != last )
    {
        if( !first )
        {
            last = NULL;
            break;
        }

        erase = first;
        first = first->next;
        if( true == destroy )
            self->m_elmt_destroy( DATA(erase) );
        self->m_dealloc( erase, node_size );
    }

    if( !last )
        self->m_tail = before_first;

    before_first->next = last;
}

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

sglnklst_node* sglnklst_insert_after_node( sglnklst* self,
                                           sglnklst_node* before_pos,
                                           const void* value )
{
    sglnklst_node* new_node = (sglnklst_node*)( self->m_alloc(
                              sizeof(sglnklst_node) + self->m_element_size ) );

    if( new_node )
    {
        COPY_VALUE( DATA(new_node), value, self->m_element_size,
                    self->m_elmt_init_copy );

        new_node->next = before_pos->next;
        before_pos->next = new_node;