yc_sglnklst.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_SINGLY_LINKED_LIST_HEADER_FILE__
#define __MACRO_C_YOUNG_LIBRARY_SINGLY_LINKED_LIST_HEADER_FILE__
/******************************************************************************/
#include "yc_definition.h"

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

typedef  struct singly_linked_list_node
{
    struct singly_linked_list_node*  next;
}  sglnklst_node;

typedef  struct singly_linked_list_object
{
    sglnklst_node      m_header;
    sglnklst_node*     m_tail;
    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 */
}  sglnklst;

typedef  sglnklst_node*  sglnklst_iterator;

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

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

#define SGLNKLST_ITR_DEREF( ITR, TYPE ) \
        ( *( (TYPE*)( ((ylib_byte_t*)(ITR)) + sizeof(sglnklst_node) ) ) )

#define SGLNKLST_EMPTY( SLIST )   ( !((SLIST).m_header.next) )

#define SGLNKLST_HEADER( SLIST )  ( &((SLIST).m_header) )

#define SGLNKLST_BEGIN( SLIST )   ( (SLIST).m_header.next )

#define SGLNKLST_END()  ( NULL )

#define SGLNKLST_FRONT( SLIST, TYPE )                         \
        ( *( (TYPE*)( ((ylib_byte_t*)((SLIST).m_header.next)) \
                      + sizeof(sglnklst_node) ) ) )

#define SGLNKLST_POP_FRONT( SLIST ) \
        ( sglnklst_erase_after_pos( &(SLIST), &((SLIST).m_header) ) )

#define SGLNKLST_PUSH_FRONT( SLIST, VAL, BOOLVAL )          \
        ( (BOOLVAL) = sglnklst_insert_after_node( &(SLIST), \
                            (SLIST).m_header.next, &(VAL) ) ? true : false )

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

#ifndef __MACRO_C_YOUNG_LIBRARY_COMPILER_SUPPORT_INLINE_FUNCTION__
    /* *iterator */
    void* sglnklst_itr_deref( sglnklst_iterator itr );

    /* ++iterator */
    void sglnklst_itr_inc( sglnklst_iterator* pitr );
#else
    inline void* sglnklst_itr_deref( sglnklst_iterator itr )
    {
        return ((ylib_byte_t*)itr) + sizeof(sglnklst_node);
    }

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

/* iterator += n */
void sglnklst_itr_inc_n( sglnklst_iterator* pitr,
                         size_t n );

/* iterator + n */
sglnklst_iterator sglnklst_itr_add( sglnklst_iterator itr,
                                    size_t n );

/* returns an iterator pointer to before pos */
sglnklst_iterator sglnklst_itr_prev( sglnklst_iterator header,
                                     sglnklst_iterator pos );

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

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

void sglnklst_destroy( sglnklst* self );

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

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

void sglnklst_init_move( sglnklst* uninit_self,
                         sglnklst* src );

void sglnklst_assign_move( sglnklst* self,
                           sglnklst* src );

void sglnklst_reverse( sglnklst* self );

size_t sglnklst_size( sglnklst* self );

void* sglnklst_index( sglnklst* self,
                      size_t index );

/* if index < sglnklst_size() returns sglnklst_index(),
 * otherwise returns NULL */
void* sglnklst_at( sglnklst* self,
                   size_t index );

/* moves the elements in the range [src_first, src_last) to self,
 * inserting them after before_pos */
void sglnklst_splice_after_range( sglnklst* self,
                                  sglnklst_iterator before_pos,
                                  sglnklst* src,
                                  sglnklst_iterator before_first,
                                  sglnklst_iterator before_last );

/* removes the element pointed to by after before_pos, returns an iterator
 * pointing to the element following the deleted element */
sglnklst_iterator sglnklst_erase_after_pos( sglnklst* self,
                                            sglnklst_iterator before_pos );

/* removes the elements in the range (before_first, last), returns an iterator
 * pointing to the element following the element following the last
 * deleted element */
void sglnklst_erase_after_range( sglnklst* self,
                                 sglnklst_iterator before_first,
                                 sglnklst_iterator last );

/* inserts value after before_pos, if succeeded returns an iterator that
 * points to the inserted value, otherwise returns NULL */
sglnklst_iterator sglnklst_insert_after_node( sglnklst* self,
                                              sglnklst_iterator before_pos,
                                              const void* value );

/* inserts count copies of value after before_pos, returns the number of
 * inserted elements */
size_t sglnklst_insert_after_value( sglnklst* self,
                                    sglnklst_iterator before_pos,
                                    const void* value,
                                    size_t count );

/* inserts copies of the elements in the range [src, src + count)
 * after before_pos, returns the number of inserted elements */
size_t sglnklst_insert_after_array( sglnklst* self,
                                    sglnklst_iterator before_pos,
                                    const void* src,
                                    size_t count );

size_t sglnklst_replace_after_fill( sglnklst* self,
                                    sglnklst_iterator before_first,
                                    sglnklst_iterator last,
                                    const void* value,
                                    size_t count );

size_t sglnklst_replace_after_array( sglnklst* self,
                                     sglnklst_iterator before_first,
                                     sglnklst_iterator last,
                                     const void* src,
                                     size_t count );

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

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

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

/* merges a sorted right_list with a sorted self using
 * cmp( self, right_list ) < 0 */
void sglnklst_merge( sglnklst* self,
                     sglnklst* 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 sglnklst_sort( sglnklst* self,
                    size_t temp_sglnklst_count,
                    ylib_fp_cmp_t cmp );

#ifndef __MACRO_C_YOUNG_LIBRARY_COMPILER_SUPPORT_INLINE_FUNCTION__
    void sglnklst_splice_after_node( sglnklst* self,
                                     sglnklst_iterator before_pos,
                                     sglnklst* src,
                                     sglnklst_iterator before_node );

    void sglnklst_splice_after_sglnklst( sglnklst* self,
                                         sglnklst_iterator before_pos,
                                         sglnklst* src );

    size_t sglnklst_max_size( void );

    bool sglnklst_empty( sglnklst* self );

    /* before sglnklst_begin() */
    sglnklst_iterator sglnklst_header( sglnklst* self );

    sglnklst_iterator sglnklst_begin( sglnklst* self );

    sglnklst_iterator sglnklst_end( void );

    void* sglnklst_front( sglnklst* self );

    void* sglnklst_back( sglnklst* self );

    void sglnklst_pop_back( sglnklst* self );

    bool sglnklst_push_back( sglnklst* self,
                             const void* value );

    void sglnklst_pop_front( sglnklst* self );

    bool sglnklst_push_front( sglnklst* self,
                              const void* value );
#else
    inline void sglnklst_splice_after_node( sglnklst* self,
                                            sglnklst_node* before_pos,
                                            sglnklst* src,
                                            sglnklst_node* before_node )
    {
        sglnklst_splice_after_range( self, before_pos, src, before_node,
                                     before_node->next );
    }

    inline void sglnklst_splice_after_sglnklst( sglnklst* self,
                                                sglnklst_node* before_pos,
                                                sglnklst* src )
    {
        sglnklst_splice_after_range( self, before_pos, src,
                                     &(src->m_header), src->m_tail );
    }

    inline size_t sglnklst_max_size( void )
    {
        return SIZE_MAX;
    }

    inline bool sglnklst_empty( sglnklst* self )
    {
        return self->m_header.next ? false : true;
    }

    inline sglnklst_iterator sglnklst_header( sglnklst* self )
    {
        return &(self->m_header);
    }

    inline sglnklst_iterator sglnklst_begin( sglnklst* self )
    {
        return self->m_header.next;
    }

    inline sglnklst_iterator sglnklst_end( void )
    {
        return NULL;
    }

    inline void* sglnklst_front( sglnklst* self )
    {
        return ((ylib_byte_t*)(self->m_header.next)) + sizeof(sglnklst_node);
    }

    inline void* sglnklst_back( sglnklst* self )
    {
        return ((ylib_byte_t*)(self->m_tail)) + sizeof(sglnklst_node);
    }

    inline void sglnklst_pop_back( sglnklst* self )
    {
        sglnklst_erase_after_pos( self, sglnklst_itr_prev( &(self->m_header),
                                                           self->m_tail ) );
    }

    inline bool sglnklst_push_back( sglnklst* self,
                                    const void* value )
    {
        return sglnklst_insert_after_node( self, self->m_tail, value )
               ? true : false;
    }

    inline void sglnklst_pop_front( sglnklst* self )
    {
        sglnklst_erase_after_pos( self, &(self->m_header) );
    }

    inline bool sglnklst_push_front( sglnklst* self,
                                     const void* value )
    {
        return sglnklst_insert_after_node( self, &(self->m_header), value )
               ? true : false;
    }
#endif

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