yc_dblnklst.c

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

        {
            if( erase == end ) /* 如果遇到头节点则跳出循环 */
            {
                first_prev->next = first;
                last->prev = end;
                end->next = last;
                return end;
            }

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

    return last;
}

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

dblnklst_node* dblnklst_insert_node( dblnklst* self,
                                     dblnklst_node* pos,
                                     const void* value )
{
    dblnklst_node* new_node = (dblnklst_node*)( self->m_alloc(
                              sizeof(dblnklst_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 = pos;
        new_node->prev = pos->prev;
        pos->prev->next = new_node;
        pos->prev = new_node;
    }

    return new_node;
}

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

size_t dblnklst_insert_value( dblnklst* self,
                              dblnklst_node* pos,
                              const void* value,
                              size_t count )
{
    size_t n;

    for( n = 0; n < count; ++n )
    {
        if( !dblnklst_insert_node( self, pos, value ) )
            break;
    }

    return n;
}

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

size_t dblnklst_insert_array( dblnklst* self,
                              dblnklst_node* pos,
                              const void* src,
                              size_t count )
{
    size_t n;

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

    return n;
}

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

size_t dblnklst_replace_fill( dblnklst* self,
                              dblnklst_node* first,
                              dblnklst_node* last,
                              const void* value,
                              size_t count )
{
    size_t ret;
    dblnklst_node* end = &(self->m_header);

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

    if( first != last && first != end && count == ret )
        dblnklst_erase_range( self, first, last );
    else if( (first == last || first == end) && ret < count )
        return dblnklst_insert_value( self, first, value, count - ret ) + ret;

    return ret;
}

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

size_t dblnklst_replace_array( dblnklst* self,
                               dblnklst_node* first,
                               dblnklst_node* last,
                               const void* src,
                               size_t count )
{
    size_t ret;
    dblnklst_node* end = &(self->m_header);

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

    if( first != last && first != end && count == ret )
        dblnklst_erase_range( self, first, last );
    else if( (first == last || first == end) && ret < count )
        return dblnklst_insert_array( self, first, src, count - ret ) + ret;

    return ret;
}

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

size_t dblnklst_resize( dblnklst* self, size_t new_size, const void* value )
{
    size_t count = 0;
    dblnklst_node* first = self->m_header.next;
    dblnklst_node* last = &(self->m_header);

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

    if( new_size == count && first != last )
        dblnklst_erase_range( self, first, last );
    else if( count < new_size && first == last )
        return dblnklst_insert_value(self, last, value, new_size - count)
               + count;

    return count;
}

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

void dblnklst_remove( dblnklst* self,
                      const void* right_param,
                      ylib_fp_cmp_t equal )
{
    int eq;
    dblnklst_node* curr = self->m_header.next;
    dblnklst_node* last = &(self->m_header);

    while( curr != last )
    {
        eq = equal( DATA(curr), right_param );
        curr = curr->next;
        if( eq == 0 )
            dblnklst_erase_pos( self, curr->prev );
    }
}

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

void dblnklst_unique( dblnklst* self, ylib_fp_cmp_t equal )
{
    dblnklst_node* curr = self->m_header.next;
    dblnklst_node* last = &(self->m_header);

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

            next_node = curr->next;
        }
    }
}

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

void dblnklst_merge( dblnklst* self, dblnklst* right_list, ylib_fp_cmp_t cmp )
{
    dblnklst_node* curr2 = right_list->m_header.next;
    dblnklst_node* last2 = &(right_list->m_header);

    if( curr2 != last2 )
    {
        dblnklst_node* curr1 = self->m_header.next;
        dblnklst_node* last1 = &(self->m_header);
        dblnklst_node* temp;

        while( curr1 != last1 && curr2 != last2 )
        {
            if( cmp( DATA(curr1), DATA(curr2) ) < 0 )
                curr1 = curr1->next;
            else
            {
                temp = curr2;
                curr2 = curr2->next;
                dblnklst_splice_range( self, curr1, right_list, temp, curr2 );
            }
        }

        if( curr2 != last2 )
            dblnklst_splice_range( self, curr1, right_list, curr2, last2 );
    }
}

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

bool dblnklst_sort( dblnklst* self,
                    size_t temp_dblnklst_count,
                    ylib_fp_cmp_t cmp )
{
    if( self->m_header.next != &(self->m_header)
        && self->m_header.next->next != &(self->m_header) ) /* size > 1 */
    {
        size_t i, fill = 0;
        dblnklst carry;
        dblnklst_node* second = NULL;

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

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

        while( self->m_header.next != &(self->m_header) )
        {
            second = self->m_header.next->next;
            dblnklst_splice_range( &carry, carry.m_header.next,
                                   self, self->m_header.next, second );

            for( i = 0; buf[i].m_header.next != &(buf[i].m_header)
                        && i < fill; ++i )
            {
                dblnklst_merge( buf + i, &carry, cmp );
                /* swap carry and result[temp] */
                dblnklst_swap( &carry, buf + i );
            }

            /* swap carry and result[temp] */
            dblnklst_swap( &carry, buf + i );

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

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

        self->m_header.prev = buf[fill - 1].m_header.prev;
        self->m_header.next = buf[fill - 1].m_header.next;
        self->m_header.prev->next = &(self->m_header);
        self->m_header.next->prev = &(self->m_header);

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

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

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

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

    size_t dblnklst_max_size( void )
    {
        return SIZE_MAX;
    }

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

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

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

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

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

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

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

    void* dblnklst_front( dblnklst* self )
    {
        return DATA( self->m_header.next );
    }

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

    void* dblnklst_back( dblnklst* self )
    {
        return DATA( self->m_header.prev );
    }

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

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

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

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

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

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

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

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