yc_dblnklst.h

一个类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.
 */

/******************************************************************************/
/******************************************************************************/
#ifndef __MACRO_C_YOUNG_LIBRARY_DOUBLY_LINKED_LIST_HEADER_FILE__
#define __MACRO_C_YOUNG_LIBRARY_DOUBLY_LINKED_LIST_HEADER_FILE__
/******************************************************************************/
#include "yc_definition.h"

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

typedef  struct doubly_linked_list_node
{
    struct doubly_linked_list_node*  prev;
    struct doubly_linked_list_node*  next;
}  dblnklst_node;

typedef  struct doubly_linked_list_object
{
    dblnklst_node      m_header;
    size_t             m_element_size;
    ylib_fp_copy_t     m_elmt_init_copy;   /* safe function */
    ylib_fp_copy_t     m_elmt_assign_copy; /* safe function */
    ylib_fp_oper_t     m_elmt_destroy;     /* safe function */
    ylib_fp_alloc_t    m_alloc;            /* safe function */
    ylib_fp_dealloc_t  m_dealloc;          /* safe function */
}  dblnklst;

typedef  dblnklst_node*  dblnklst_iterator;

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

#define DBLNKLST_ITR_DEC( ITR )   ( (ITR) = (ITR).prev )

#define DBLNKLST_ITR_INC( ITR )   ( (ITR) = (ITR).next )

#define DBLNKLST_ITR_DEREF( ITR, TYPE ) \
        ( *( (TYPE*)( ((ylib_byte_t*)(ITR)) + sizeof(dblnklst_node) ) ) )

#define DBLNKLST_EMPTY( DLIST ) \
        ( &((DLIST).m_header) == (DLIST).m_header.next )

#define DBLNKLST_BEGIN( DLIST )  ( (DLIST).m_header.next )

#define DBLNKLST_END( DLIST )    ( &((DLIST).m_header) )

#define DBLNKLST_FRONT( DLIST, TYPE )                          \
        (  *( (TYPE*)( ((ylib_byte_t*)((DLIST).m_header.next)) \
                       + sizeof(dblnklst_node) ) ) )

#define DBLNKLST_BACK( DLIST, TYPE )                           \
        (  *( (TYPE*)( ((ylib_byte_t*)((DLIST).m_header.prev)) \
                       + sizeof(dblnklst_node) ) ) )

#define DBLNKLST_POP_BACK( DLIST ) \
        ( dblnklst_erase_pos( &(DLIST), (DLIST).m_header.prev ) )

#define DBLNKLST_POP_FRONT( DLIST ) \
        ( dblnklst_erase_pos( &(DLIST), (DLIST).m_header.next ) )

#define DBLNKLST_PUSH_BACK( DLIST, VAL, BOOLVAL )                          \
        ( (BOOLVAL) = dblnklst_insert_node( &(DLIST), &((DLIST).m_header), \
                                            &(VAL) ) ? true : false )

#define DBLNKLST_PUSH_FRONT( DLIST, VAL, BOOLVAL )                           \
        ( (BOOLVAL) = dblnklst_insert_node( &(DLIST), (DLIST).m_header.next, \
                                            &(VAL) ) ? true : false )

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

#ifndef __MACRO_C_YOUNG_LIBRARY_COMPILER_SUPPORT_INLINE_FUNCTION__
    /* *iterator */
    void* dblnklst_itr_deref( dblnklst_iterator itr );

    /* ++iterator */
    void dblnklst_itr_inc( dblnklst_iterator* pitr );

    /* --iterator */
    void dblnklst_itr_dec( dblnklst_iterator* pitr );
#else
    inline void* dblnklst_itr_deref( dblnklst_iterator itr )
    {
        return ((ylib_byte_t*)itr) + sizeof(dblnklst_node);
    }

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

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

/* iterator += n */
void dblnklst_itr_inc_n( dblnklst_iterator* pitr,
                         size_t n );

/* iterator -= n */
void dblnklst_itr_dec_n( dblnklst_iterator* pitr,
                         size_t n );

/* iterator + n */
dblnklst_iterator dblnklst_itr_add( dblnklst_iterator itr,
                                    size_t n );

/* iterator - n */
dblnklst_iterator dblnklst_itr_sub( dblnklst_iterator itr,
                                    size_t n );

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

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 );

void dblnklst_destroy( dblnklst* self );

/* (1) < 0: uninit_self = src;  (2) = 0: fail;  (3) > 0: succeed */
int dblnklst_init_copy( dblnklst* uninit_self,
                        const dblnklst* src );

/* (1) < 0: self = src or can't matching;  (2) = 0: fail;  (3) > 0: succeed */
int dblnklst_assign_copy( dblnklst* self,
                          const dblnklst* src );

void dblnklst_init_move( dblnklst* uninit_self,
                         dblnklst* src );

void dblnklst_assign_move( dblnklst* self,
                           dblnklst* src );

void dblnklst_swap( dblnklst* self,
                    dblnklst* other );

size_t dblnklst_size( dblnklst* self );

void* dblnklst_index( dblnklst* self,
                      size_t index );

/* if index < dblnklst_size() returns dblnklst_index(),
 * otherwise returns NULL */
void* dblnklst_at( dblnklst* self,
                   size_t index );

/* moves the elements in the range [src_first, src_last) to self,
 * inserting them before pos */
void dblnklst_splice_range( dblnklst* self,
                            dblnklst_iterator pos,
                            dblnklst* src,
                            dblnklst_iterator src_first,
                            dblnklst_iterator src_last );

void dblnklst_reverse( dblnklst* self );

/* removes the element pointed to by pos, returns an iterator pointing to
 * the element following the deleted element */
dblnklst_iterator dblnklst_erase_pos( dblnklst* self,
                                      dblnklst_iterator pos );

/* removes the elements in the range [first, last), returns an iterator
 * pointing to the element following the element following the last
 * deleted element */
dblnklst_iterator dblnklst_erase_range( dblnklst* self,
                                        dblnklst_iterator first,
                                        dblnklst_iterator last );

/* inserts value before pos, if succeeded returns an iterator that points to
 * the inserted value, otherwise returns NULL */
dblnklst_iterator dblnklst_insert_node( dblnklst* self,
                                        dblnklst_iterator pos,
                                        const void* value );

/* inserts count copies of value before pos, returns the number of
 * inserted elements */
size_t dblnklst_insert_value( dblnklst* self,
                              dblnklst_iterator pos,
                              const void* value,
                              size_t count );

/* inserts copies of the elements in the range [src, src + count) before pos,
 * returns the number of inserted elements */
size_t dblnklst_insert_array( dblnklst* self,
                              dblnklst_iterator pos,
                              const void* src,
                              size_t count );

/* returns the number of replaced elements */
size_t dblnklst_replace_fill( dblnklst* self,
                              dblnklst_iterator first,
                              dblnklst_iterator last,
                              const void* value,
                              size_t count );

/* returns the number of replaced elements */
size_t dblnklst_replace_array( dblnklst* self,
                               dblnklst_iterator first,
                               dblnklst_iterator last,
                               const void* src,
                               size_t count );

/* returns all elements in the dblnklst */
size_t dblnklst_resize( dblnklst* self,
                        size_t new_size,
                        const void* value );

/* removes all elements in the dblnklst referenced by the dblnklst iterator i
 * for which equal( dblnklst_itr_deref(i), right_param ) == 0 */
void dblnklst_remove( dblnklst* self,
                      const void* right_param,
                      ylib_fp_cmp_t equal );

/* erases copies of consecutive repeated elements leaving the first occurrence */
void dblnklst_unique( dblnklst* self,
                      ylib_fp_cmp_t equal );

/* merges a sorted right_list with a sorted self using
 * cmp( self, right_list ) < 0 */
void dblnklst_merge( dblnklst* self,
                     dblnklst* right_list,
                     ylib_fp_cmp_t cmp );

/* sorts self according to the cmp( left, right ) < 0, sort maintains
 * the relative order of equal elements */
bool dblnklst_sort( dblnklst* self,
                    size_t temp_dblnklst_count,
                    ylib_fp_cmp_t cmp );

#ifndef __MACRO_C_YOUNG_LIBRARY_COMPILER_SUPPORT_INLINE_FUNCTION__
    void dblnklst_splice_node( dblnklst* self,
                               dblnklst_iterator pos,
                               dblnklst* other,
                               dblnklst_iterator src_node );

    void dblnklst_splice_dblnklst( dblnklst* self,
                                   dblnklst_iterator pos,
                                   dblnklst* other,
                                   dblnklst* src );

    size_t dblnklst_max_size( void );

    bool dblnklst_empty( dblnklst* self );

    dblnklst_iterator dblnklst_begin( dblnklst* self );

    dblnklst_iterator dblnklst_end( dblnklst* self );

    void* dblnklst_front( dblnklst* self );

    void* dblnklst_back( dblnklst* self );

    void dblnklst_pop_back( dblnklst* self );

    void dblnklst_pop_front( dblnklst* self );

    bool dblnklst_push_back( dblnklst* self,
                             const void* value );

    bool dblnklst_push_front( dblnklst* self,
                              const void* value );
#else
    inline void dblnklst_splice_node( dblnklst* self,
                                      dblnklst_node* pos,
                                      dblnklst* src,
                                      dblnklst_node* src_node )
    {
        dblnklst_splice_range( self, pos, src, src_node, src_node->next );
    }

    inline void dblnklst_splice_dblnklst( dblnklst* self,
                                          dblnklst_node* pos,
                                          dblnklst* src )
    {
        dblnklst_splice_range( self, pos, src,
                               src->m_header.next, &(src->m_header) );
    }

    inline size_t dblnklst_max_size( void )
    {
        return SIZE_MAX;
    }

    inline bool dblnklst_empty( dblnklst* self )
    {
        return &(self->m_header) == self->m_header.next ? true : false;
    }

    inline dblnklst_iterator dblnklst_begin( dblnklst* self )
    {
        return self->m_header.next;
    }

    inline dblnklst_iterator dblnklst_end( dblnklst* self )
    {
        return &(self->m_header);
    }

    inline void* dblnklst_front( dblnklst* self )
    {
        return ((ylib_byte_t*)(self->m_header.next)) + sizeof(dblnklst_node);
    }

    inline void* dblnklst_back( dblnklst* self )
    {
        return ((ylib_byte_t*)(self->m_header.prev)) + sizeof(dblnklst_node);
    }

    inline void dblnklst_pop_back( dblnklst* self )
    {
        dblnklst_erase_pos( self, self->m_header.prev );
    }

    inline void dblnklst_pop_front( dblnklst* self )
    {
        dblnklst_erase_pos( self, self->m_header.next );
    }

    inline bool dblnklst_push_back( dblnklst* self,
                                    const void* value )
    {
        return dblnklst_insert_node( self, &(self->m_header), value )
               ? true : false;
    }

    inline bool dblnklst_push_front( dblnklst* self,
                                     const void* value )
    {
        return dblnklst_insert_node( self, self->m_header.next, value )
               ? true : false;
    }
#endif

/******************************************************************************/
/******************************************************************************/
#ifdef __cplusplus
    }  }
#endif
#endif
/******************************************************************************/
/******************************************************************************/