yc_hashtable.c

来自「一个类STL的多平台可移植的算法容器库,主要用于嵌入式系统编程时的内存管理等方面」· C语言 代码 · 共 1,218 行 · 第 1/3 页

    node_size = sizeof(hashtable_node) + self->m_element_size;
    destroy = ( self->m_elmt_destroy ? true : false );
    index = HASH_KEY( self, key );
    first = self->m_chain_table[index];

    if( !first )
        return 0;

    current = first;
    after = current->next;

    /* 删除 first 后面的节点 */
    while( after )
    {
        if( self->m_equal_key( GET_NODE_KEY(self, after), key ) != 0 )
        {
            current = after;
            after = current->next;
        }
        else
        {
            current->next = after->next;
            if( true == destroy )
                self->m_elmt_destroy( NODE_DATA(after) );
            self->m_dealloc( after, node_size );
            after = current->next;
            --( self->m_node_count );
            ++erase_count;
        }
    }

    /* 判断是否需要删除 first 节点 */
    if( self->m_equal_key( GET_NODE_KEY(self, first), key ) == 0 )
    {
        self->m_chain_table[index] = first->next;
        if( true == destroy )
            self->m_elmt_destroy( NODE_DATA(first) );
        self->m_dealloc( first, node_size );
        --( self->m_node_count );
        ++erase_count;
    }

    return erase_count;
}

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

hstb_iterator hstb_insert_unique( hashtable* self, const void* value )
{
    hstb_rehash( self, self->m_node_count + 1 );
    return hstb_insert_unique_node( self, value );
}

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

hstb_iterator hstb_insert_unique_pos( hashtable* self,
                                      hstb_iterator pos,
                                      const void* value )
{
    if( pos.node && pos.table == self
        && self->m_equal_key( NODE_DATA(pos.node), value ) == 0 )
        return pos;

    hstb_rehash( self, self->m_node_count + 1 );
    return hstb_insert_unique_node( self, value );
}

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

hstb_iterator hstb_insert_equal( hashtable* self, const void* value )
{
    hstb_rehash( self, self->m_node_count + 1 );
    return hstb_insert_equal_node( self, value );
}

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

hstb_iterator hstb_insert_equal_pos( hashtable* self,
                                     hstb_iterator pos,
                                     const void* value )
{
    hstb_rehash( self, self->m_node_count + 1 );

    /* 如果 pos 和 value 的键值相等，则直接在 pos 后面插入新节点 */
    if( pos.node && pos.table == self
        && self->m_equal_key( NODE_DATA(pos.node), value ) == 0 )
    {
        hashtable_node* new_node = hstb_create_node( self, value );
        if( new_node )
        {
            new_node->next = pos.node->next;
            pos.node->next = new_node;
            ++( self->m_table_len );
        }
        pos.node = new_node;
        return pos;
    }

    return hstb_insert_equal_node( self, value );
}

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

bool hstb_replace_key_unique_pos( hashtable* self,
                                  hstb_iterator pos,
                                  const void* new_key,
                                  ylib_fp_copy_t copy_key )
{
    if( self == pos.table && self->m_node_count > 0 && pos.node )
    {
        hstb_iterator itr = hstb_find( self, new_key );
        if( !(itr.node) )
        {
            hstb_replace_key_node( self, pos.node, new_key, copy_key, false );
            return true;
        }
    }

    return false;
}

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

hstb_iterator hstb_replace_key_unique( hashtable* self,
                                       const void* old_key,
                                       const void* new_key,
                                       ylib_fp_copy_t copy_key )
{
    hstb_iterator result = hstb_find( self, old_key );

    if( result.node )
    {
        hstb_iterator itr = hstb_find( self, new_key );
        if( !(itr.node) )
            hstb_replace_key_node( self, result.node, new_key, copy_key,
                                   false );
    }

    return result;
}

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

void hstb_replace_key_equal_pos( hashtable* self,
                                 hstb_iterator pos,
                                 const void* new_key,
                                 ylib_fp_copy_t copy_key )
{
    if( self == pos.table && self->m_node_count > 0 && pos.node )
        hstb_replace_key_node( self, pos.node, new_key, copy_key, true );
}

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

void hstb_replace_key_equal( hashtable* self,
                             const void* old_key,
                             const void* new_key,
                             ylib_fp_copy_t copy_key )
{
    bool get;
    size_t old_index, new_index;
    hashtable_node* front;
    hashtable_node* back;
    hashtable_node* current;
    hashtable_node* old_first;
    hashtable_node* old_last;

    if( self->m_node_count < 1 )
        return;

    get = ( self->m_get_key ? true : false );
    old_index = HASH_KEY( self, old_key );
    front = self->m_chain_table[old_index];
    back = NULL;
    current = NULL;
    old_first = front;
    old_last = NULL;

    /* 找到键值等于 old_key 的所有节点 */
    while( front )
    {
        /* 寻找第一个键值等于 old_key 的节点 */
        if( self->m_equal_key( GET_KEY_BOOL(self, front, get), old_key ) != 0 )
        {
            old_first = front;
            front = front->next;
        }
        else
        {
            /* 已找到键值等于 old_key 的节点，此时寻找第一个键值不等于
             * old_key 的节点 */
            back = front;
            old_last = front->next;
            while( old_last )
            {
                if( self->m_equal_key( GET_KEY_BOOL(self, old_last, get),
                                       old_key ) == 0 )
                {
                    back = old_last;
                    old_last = old_last->next;
                }
                else
                {
                    back->next = NULL;
                    break;  /* end while( old_last ) */
                }
            }
            break;  /* end while( front ) */
        }
    }

    /* 没有和 old_key 键值相等的节点 */
    if( !front )
        return;

    /* 将找到的节点退出原来的 chain */
    if( old_first == self->m_chain_table[old_index] )
        self->m_chain_table[old_index] = old_last;
    else
        old_first->next = old_last;

    /* 修改键值 */
    current = front;
    while( current )
    {
        COPY_VALUE( (void*)GET_KEY_BOOL(self, current, get),
                    new_key, self->m_element_size, copy_key );

        current = current->next;
    }

    /* 插入新的 chain */
    new_index = HASH_KEY( self, new_key );
    current = self->m_chain_table[new_index];

    while( current )
    {
        /* 在新的 chain 中寻找是否有键值等于 new_key 的节点 */
        if( self->m_equal_key(GET_KEY_BOOL(self, current, get), new_key) != 0 )
            current = current->next;
        else
        {
            back->next = current->next;
            current->next = front;
            return;
        }
    }

    back->next = self->m_chain_table[new_index];
    self->m_chain_table[new_index] = front;
}

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

void hstb_set_max_load_factor( hashtable* self, float max_load_factor )
{
    if( max_load_factor > 0 )
    {
        float old = self->m_factor;
        self->m_factor = max_load_factor;
        if( self->m_chain_table && max_load_factor < old )
            hstb_rehash( self, (size_t)(self->m_node_count / max_load_factor) );
    }
}

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

size_t hstb_max_chain_count( void )
{
    return hash_table_next_prime( SIZE_MAX );
}

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

size_t hstb_chain_count( hashtable* self )
{
    size_t i = 0, len = 0;

    for( ; i < self->m_table_len; ++i )
    {
        if( self->m_chain_table[i] )
            ++len;
    }

    return len;
}

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

size_t hstb_chain_size( hashtable* self, size_t index )
{
    size_t result = 0;

    if( index < self->m_table_len )
    {
        hashtable_node* current = self->m_chain_table[index];

        while( current )
        {
            ++result;
            current = current->next;
        }
    }

    return result;
}

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

void hstb_foreach( hashtable* self,
                   void (*oper_node)(size_t, const hashtable_node*) )
{
    hashtable_node* current = NULL;
    size_t current_index = 0, last_index = self->m_table_len;

    for( ; current_index < last_index; ++current_index )
    {
        current = self->m_chain_table[current_index];

        while( current )
        {
            oper_node( current_index, current );
            current = current->next;
        }
    }
}

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

#ifndef __MACRO_C_YOUNG_LIBRARY_COMPILER_SUPPORT_INLINE_FUNCTION__
    hstb_iterator hstb_end( hashtable* self )
    {
        hstb_iterator end;
        end.node = NULL;
        end.table = self;
        return end;
    }

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

    hstb_local_iterator hstb_local_begin( hashtable* self, size_t index )
    {
        return self->m_chain_table[ index ];
    }

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

    hstb_local_iterator hstb_local_end( void )
    {
        return NULL;
    }

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

    size_t hstb_max_size( void )
    {
        return SIZE_MAX;
    }

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

    size_t hstb_size( hashtable* self )
    {
        return self->m_node_count;
    }

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

    float hstb_load_factor( hashtable* self )
    {
        return self->m_table_len == 0
               ? (float)0.0
               : (float)(self->m_node_count) / (float)(self->m_table_len);
    }

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

    float hstb_get_max_load_factor( hashtable* self )
    {
        return self->m_factor;
    }

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

    size_t hstb_table_size( hashtable* self )
    {
        return self->m_table_len;
    }

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

    size_t hstb_key_chain( hashtable* self, const void* key )
    {
        return self->m_table_len == 0 ? 0 : HASH_KEY( self, key );
    }
#endif

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