yc_sglnklst.c

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

    }

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

    return new_node;
}

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

size_t sglnklst_insert_after_value( sglnklst* self,
                                    sglnklst_node* before_pos,
                                    const void* value,
                                    size_t count )
{
    size_t n;

    for( n = 0; n < count; ++n )
    {
        if( !sglnklst_insert_after_node(self, before_pos, value) )
            break;
        before_pos = before_pos->next;
    }

    return n;
}

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

size_t sglnklst_insert_after_array( sglnklst* self,
                                    sglnklst_node* before_pos,
                                    const void* src,
                                    size_t count )
{
    size_t n;

    for( n = 0; n < count; ++n )
    {
        if( !sglnklst_insert_after_node(self, before_pos, src) )
            break;
        src = (const ylib_byte_t*)src + self->m_element_size;
        before_pos = before_pos->next;
    }

    return n;
}

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

size_t sglnklst_resize( sglnklst* self, size_t new_size, const void* value )
{
    size_t count = 0;
    sglnklst_node* curr = &( self->m_header );

    while( curr->next && count < new_size )
    {
        ++count;
        curr = curr->next;
    }

    if( new_size == count && curr->next )
        sglnklst_erase_after_range( self, curr, NULL );
    else if( count < new_size && !(curr->next) )
        return sglnklst_insert_after_value( self, curr, value,
                                            new_size - count ) + count;

    return count;
}

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

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

    if( !before_first )
        return 0;

    for( ret = 0; before_first->next != last && before_first->next
                  && ret < count; ++ret )
    {
        before_first = before_first->next;
        COPY_VALUE( DATA(before_first), value, self->m_element_size,
                    self->m_elmt_assign_copy );
    }

    if( before_first->next != last && before_first->next && count == ret )
        sglnklst_erase_after_range( self, before_first, NULL );
    else if( ( before_first->next == last || !(before_first->next) )
             && ret < count )
        return sglnklst_insert_after_value( self, before_first, value,
                                            count - ret ) + ret;

    return ret;
}

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

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

    if( !before_first )
        return 0;

    for( ret = 0; before_first->next != last && before_first->next
                  && ret < count; ++ret )
    {
        before_first = before_first->next;
        COPY_VALUE( DATA(before_first), src, self->m_element_size,
                    self->m_elmt_assign_copy );
        src = (const ylib_byte_t*)src + self->m_element_size;
    }

    if( before_first->next != last && before_first->next && count == ret )
        sglnklst_erase_after_range( self, before_first, NULL );
    else if( ( before_first->next == last || !(before_first->next) )
             && ret < count )
        return sglnklst_insert_after_array( self, before_first, src,
                                            count - ret ) + ret;

    return ret;
}

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

void sglnklst_remove( sglnklst* self,
                      const void* right_param,
                      ylib_fp_cmp_t equal )
{
    sglnklst_node* before = &( self->m_header );

    while( before->next )
    {
        if( equal( DATA(before->next), right_param ) != 0 )
            before = before->next;
        else
            sglnklst_erase_after_pos( self, before );
    }
}

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

void sglnklst_unique( sglnklst* self, ylib_fp_cmp_t equal )
{
    sglnklst_node* curr = self->m_header.next;
    sglnklst_node* next;

    if( curr && curr->next )  /* size != 0 or 1 */
    {
        while( curr->next )
        {
            next = curr->next;
            if( equal( DATA(curr), DATA(next) ) != 0 )
                curr = curr->next;
            else
                sglnklst_erase_after_pos( self, curr );
        }
    }
}

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

void sglnklst_merge( sglnklst* self, sglnklst* right_list, ylib_fp_cmp_t cmp )
{
    if( right_list->m_header.next )
    {
        sglnklst_node* before = &( self->m_header );
        sglnklst_node* cur;

        while( before->next && right_list->m_header.next )
        {
            cur = before->next;
            if( cmp( DATA(cur), DATA(right_list->m_header.next) ) > 0 )
                sglnklst_splice_after_range( self, before, right_list,
                                             &(right_list->m_header),
                                             right_list->m_header.next );
            before = before->next;
        }

        if( right_list->m_header.next )
        {
            before->next = right_list->m_header.next;
            right_list->m_header.next = NULL;
            self->m_tail = right_list->m_tail;
        }

        right_list->m_tail = &(right_list->m_header);
    }
}

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

bool sglnklst_sort( sglnklst* self,
                    size_t temp_sglnklst_count,
                    ylib_fp_cmp_t cmp )
{
    if( self->m_header.next && self->m_header.next->next )
    {
        size_t i, fill = 0;
        sglnklst_node* swap_itr;
        sglnklst carry;

#ifndef __MACRO_C_YOUNG_LIBRARY_COMPILER_SUPPORT_VARIABLE_LENGTH_ARRAY__
        size_t array_size = sizeof(sglnklst) * temp_sglnklst_count;
        sglnklst* buf = (sglnklst*)( self->m_alloc( array_size ) );
        if( !buf )
            return false;
#else
        sglnklst buf[ temp_sglnklst_count ];
#endif

        /* 所有的链表初始化 */
        carry.m_header.next = NULL;
        carry.m_tail = &(carry.m_header);
        for( i = 0; i < temp_sglnklst_count; ++i )
        {
            buf[i].m_header.next = NULL;
            buf[i].m_tail = &(buf[i].m_header);
        }

        while( self->m_header.next )
        {
            sglnklst_splice_after_range( &carry, &(carry.m_header),
                                         self, &(self->m_header),
                                         self->m_header.next );

            for( i = 0; i < fill && buf[i].m_header.next; ++i )
            {
                sglnklst_merge( buf + i, &carry, cmp );

                /* swap carry and result[i] */
                swap_itr = carry.m_header.next;
                carry.m_header.next = buf[i].m_header.next;
                buf[i].m_header.next = swap_itr;
            }

            /* swap carry and result[i] */
            swap_itr = carry.m_header.next;
            carry.m_header.next = buf[i].m_header.next;
            buf[i].m_header.next = swap_itr;

            if( i == fill )
                ++fill;
        }

        for( i = 1; i < fill; ++i )
            sglnklst_merge( buf + i, buf + i - 1, cmp );

        self->m_header.next = buf[fill - 1].m_header.next;

#ifndef __MACRO_C_YOUNG_LIBRARY_COMPILER_SUPPORT_VARIABLE_LENGTH_ARRAY__
        self->m_dealloc( buf, array_size );
#endif
    }

    return true;
}

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

#ifndef __MACRO_C_YOUNG_LIBRARY_COMPILER_SUPPORT_INLINE_FUNCTION__
    void sglnklst_splice_after_node( sglnklst* self,
                                     sglnklst_node* before_pos,
                                     sglnklst* src,
                                     sglnklst_node* before_node )
    {
        sglnklst_splice_after_range( self, before_pos, sec, before_node,
                                     before_node->next );
    }

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

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

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

    size_t sglnklst_max_size( void )
    {
        return SIZE_MAX;
    }

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

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

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

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

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

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

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

    sglnklst_node* sglnklst_end( void )
    {
        return NULL;
    }

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

    void* sglnklst_front( sglnklst* self )
    {
        return DATA( self->m_header.next );
    }

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

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

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

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

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

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

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

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

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

    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
/******************************************************************************/
/******************************************************************************/