yc_hashtable.c

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

        ++( self->m_node_count );
    }

    return result;
}

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

static void hstb_replace_key_node( hashtable* self,
                                   hashtable_node* replace_node,
                                   const void* new_key,
                                   ylib_fp_copy_t copy_key,
                                   bool equal_mode )
{
    bool get = ( self->m_get_key ? true : false );
    void* oldkey = (void*)GET_NODE_KEY( self, replace_node );
    size_t newindex = HASH_KEY( self, new_key );

    hstb_weed_node( self, replace_node );
    COPY_VALUE( oldkey, new_key, self->m_element_size, copy_key );

    if( true == equal_mode )
    {
        hashtable_node* current = self->m_chain_table[newindex];

        while( current )
        {
            if( self->m_equal_key( GET_KEY_BOOL(self, current, get),
                                   new_key ) != 0 )
                current = current->next;
            else
            {
                replace_node->next = current->next;
                current->next = replace_node;
                return;
            }
        }
    }

    replace_node->next = self->m_chain_table[newindex];
    self->m_chain_table[newindex] = replace_node;
}

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

void hstb_init( hashtable* uninit_self,
                float max_load_factor,
                size_t element_size,
                ylib_fp_copy_t elmt_init_copy,
                ylib_fp_oper_t elmt_destroy,
                ylib_fp_get_t get_key,
                ylib_fp_cmp_t equal_key,
                ylib_fp_hash_t hash_key,
                ylib_fp_alloc_t alloc,
                ylib_fp_dealloc_t dealloc )
{
    uninit_self->m_chain_table = NULL;
    uninit_self->m_node_count = 0;
    uninit_self->m_table_len = 0;
    uninit_self->m_element_size = element_size;
    uninit_self->m_elmt_init_copy = elmt_init_copy;
    uninit_self->m_elmt_destroy = elmt_destroy;
    uninit_self->m_get_key = get_key;
    uninit_self->m_equal_key = equal_key;
    uninit_self->m_hash_key = hash_key;
    uninit_self->m_alloc = alloc;
    uninit_self->m_dealloc = dealloc;

    uninit_self->m_factor = ( max_load_factor > 0 ? max_load_factor
                                                  : DEFAULT_LOAD_FACTOR );
}

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

void hstb_destroy( hashtable* self )
{
    if( self->m_chain_table )
    {
        hstb_erase_range( self, hstb_begin(self), hstb_end(self) );
        self->m_dealloc( self->m_chain_table,
                         sizeof(hashtable_node*) * self->m_table_len );
    }
    self->m_chain_table = NULL;
    self->m_table_len = 0;
    self->m_node_count = 0;
}

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

int hstb_init_copy( hashtable* uninit_self, const hashtable* src )
{
    if( uninit_self == src )
        return -1;

    *uninit_self = *src;
    uninit_self->m_chain_table = NULL;
    uninit_self->m_node_count = 0;
    uninit_self->m_table_len = 0;

    return src->m_node_count > 0 ? hstb_copy_table( uninit_self, src ) : 1;
}

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

int hstb_assign_copy( hashtable* self, const hashtable* src )
{
    if( self == src || self->m_element_size != src->m_element_size
        || self->m_elmt_init_copy != src->m_elmt_init_copy )
        return -1;

    hstb_destroy( self );
    return src->m_node_count > 0 ? hstb_copy_table( self, src ) : 1;
}

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

void hstb_init_move( hashtable* uninit_self, hashtable* src )
{
    if( uninit_self != src )
    {
        *uninit_self = *src;
        src->m_chain_table = NULL;
        src->m_node_count = 0;
        src->m_table_len = 0;
    }
}

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

void hstb_assign_move( hashtable* self, hashtable* src )
{
    if( self != src )
    {
        hashtable temp = *self;
        *self = *src;
        *src = temp;
    }
}

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

hstb_iterator hstb_begin( hashtable* self )
{
    size_t i;
    hstb_iterator result;
    result.node = NULL;
    result.table = self;

    for( i = 0; i < self->m_table_len; ++i )
    {
        if( self->m_chain_table[i] )
        {
            result.node = self->m_chain_table[i];
            break;
        }
    }

    return result;
}

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

bool hstb_rehash( hashtable* self, size_t new_capacity )
{
    if( (size_t)(self->m_table_len * self->m_factor) < new_capacity )
    {
        size_t old_table_len = self->m_table_len;
        size_t new_table_len = hash_table_next_prime(
                                        new_capacity > old_table_len
                                        ? new_capacity : old_table_len + 1 );

        /* 当 hstb_max_chain_count() 等于 old_table_len 时
         * old_table_len 等于 new_table_len */
        if( new_table_len > old_table_len )
        {
            size_t i, newi;
            hashtable_node* current;
            table_t new_table = (table_t)( self->m_alloc(
                                sizeof(hashtable_node*) * new_table_len ) );

            if( !new_table )
                return false;

            ylib_memset( new_table, 0, new_table_len * sizeof(hashtable_node*) );

            for( i = 0; i < old_table_len; ++i )
            {
                current = self->m_chain_table[i];
                while( current )
                {
                    /* 需重新计算插入的位置 */
                    newi = HASH_NODE( self, current, new_table_len );
                    self->m_chain_table[i] = current->next;
                    current->next = new_table[newi];
                    new_table[newi] = current;
                    current = self->m_chain_table[i];
                }
            }

            if( self->m_chain_table )
                self->m_dealloc( self->m_chain_table,
                                 sizeof(hashtable_node*) * self->m_table_len );
            self->m_chain_table = new_table;
            self->m_table_len = new_table_len;
        }
    }

    return true;
}

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

size_t hstb_count( hashtable* self, const void* key )
{
    size_t count = 0, index;
    hashtable_node* current;

    if( self->m_node_count < 1 )
        return 0;

    index = HASH_KEY( self, key );
    current = self->m_chain_table[index];

    if( self->m_get_key )
    {
        while( current )
        {
            if( self->m_equal_key( NODE_KEY(self, current), key ) == 0 )
                ++count;
            current = current->next;
        }
    }
    else
    {
        while( current )
        {
            if( self->m_equal_key( NODE_DATA(current), key ) == 0 )
                ++count;
            current = current->next;
        }
    }

    return count;
}

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

hstb_iterator hstb_find( hashtable* self, const void* key )
{
    size_t index;
    hashtable_node* current;
    hstb_iterator result;
    result.node = NULL;
    result.table = self;

    if( self->m_node_count < 1 )
        return result;

    index = HASH_KEY( self, key );
    current = self->m_chain_table[index];

    if( self->m_get_key )
    {
        while( current )
        {
            if( self->m_equal_key( NODE_KEY(self, current), key ) == 0 )
                break;
            current = current->next;
        }
    }
    else
    {
        while( current )
        {
            if( self->m_equal_key( NODE_DATA(current), key ) == 0 )
                break;
            current = current->next;
        }
    }

    result.node = current;
    return result;
}

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

hstb_pair_iterator hstb_equal_range( hashtable* self, const void* key )
{
    bool get;
    size_t index;
    hashtable_node* first;
    hstb_pair_iterator result;
    result.first.node = NULL;
    result.first.table = self;
    result.second.node = NULL;
    result.second.table = self;

    if( self->m_node_count < 1 )
        return result;

    get = ( self->m_get_key ? true : false );
    index = HASH_KEY( self, key );
    first = self->m_chain_table[index];

    while( first )
    {
        if( self->m_equal_key( GET_KEY_BOOL(self, first, get), key ) == 0 )
        {
            /* 发现第一个相等的节点 */
            hashtable_node* last = first->next;
            result.first.node = first;

            while( last )
            {
                if( self->m_equal_key(GET_KEY_BOOL(self, last, get), key) != 0 )
                {
                    result.second.node = last;
                    return result;
                }
                last = last->next;
            }

            for( ++index; index < self->m_table_len; ++index )
            {
                if( self->m_chain_table[index] )
                {
                    result.second.node = self->m_chain_table[index];
                    return result;
                }
            }

            return result;
        }   /* end if */

        first = first->next;
    }   /* end while( first ) */

    return result;
}

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

void hstb_erase_pos( hashtable* self, hstb_iterator pos )
{
    if( self == pos.table && self->m_node_count > 0 && pos.node )
    {
        hstb_weed_node( self, pos.node );
        if( self->m_elmt_destroy )
            self->m_elmt_destroy( NODE_DATA(pos.node) );
        self->m_dealloc( pos.node,
                         sizeof(hashtable_node) + self->m_element_size );
        --( self->m_node_count );
    }
}

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

void hstb_erase_range( hashtable* self,
                       hstb_iterator first,
                       hstb_iterator last )
{
    if( first.node && first.node != last.node && self == first.table
        && self == last.table && self->m_node_count > 0 )
    {
        size_t f_index = first.node
                         ? HASH_NODE( self, first.node, self->m_table_len )
                         : self->m_table_len;
        size_t l_index = last.node
                         ? HASH_NODE( self, last.node, self->m_table_len )
                         : self->m_table_len;

        if( f_index > l_index )
            return;
        else if( f_index == l_index )
            hstb_erase_chain_from_middle( self, f_index, first.node,
                                          last.node );
        else
        {
            size_t index;

            hstb_erase_chain_from_middle( self, f_index, first.node, NULL );

            for( index = f_index + 1; index < l_index; ++index )
                hstb_erase_chain_from_front( self, index, NULL );

            if( l_index < self->m_table_len )
                hstb_erase_chain_from_front( self, index, last.node );
        }
    }
}

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

size_t hstb_erase_key( hashtable* self, const void* key )
{
    bool destroy;
    size_t erase_count, node_size, index;
    hashtable_node* first;
    hashtable_node* current;
    hashtable_node* after;

    if( self->m_node_count < 1 )
        return 0;

    erase_count = 0;