📄 yc_hashtable.c
字号:
/*
* 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.
*/
/******************************************************************************/
/******************************************************************************/
#include "yc_memalgo.h"
#include "yc_hashtable.h"
#ifdef __cplusplus
namespace youngc { extern "C" {
#endif
/******************************************************************************/
/******************************************************************************/
#define DEFAULT_LOAD_FACTOR ( (float)1.0 )
#define NODE_DATA( NODE ) ( ((ylib_byte_t*)(NODE)) + sizeof(hashtable_node) )
#define NODE_KEY( HT, NODE ) ( (HT)->m_get_key( NODE_DATA(NODE) ) )
#define GET_NODE_KEY( HT, NODE ) \
( (HT)->m_get_key ? (HT)->m_get_key(NODE_DATA(NODE)) : NODE_DATA(NODE) )
#define GET_KEY_BOOL( HT, NODE, BOOLVAL ) \
( true == BOOLVAL ? (HT)->m_get_key(NODE_DATA(NODE)) : NODE_DATA(NODE) )
#define HASH_KEY( HT, KEY ) ( (HT)->m_hash_key((KEY)) % ((HT)->m_table_len) )
#define HASH_DATA( HT, DATA, POOLSIZE ) \
( (HT)->m_hash_key( (HT)->m_get_key ? (HT)->m_get_key(DATA) \
: (DATA) ) % (POOLSIZE) )
#define HASH_NODE( HT, NODE, POOLSIZE ) \
( (HT)->m_hash_key( (HT)->m_get_key \
? (HT)->m_get_key(NODE_DATA(NODE)) \
: NODE_DATA(NODE) ) % (POOLSIZE) )
#define COPY_VALUE( PDST, PSRC, ELMTSIZE, COPYFUN ) \
if( COPYFUN ) \
(COPYFUN)( (PDST), (PSRC) ); \
else if( sizeof(int) == (ELMTSIZE) ) \
*( (int*)(PDST) ) = *( (int*)(PSRC) ); \
else if( sizeof(double) == (ELMTSIZE) ) \
*( (double*)(PDST) ) = *( (double*)(PSRC) ); \
else if( sizeof(char) == (ELMTSIZE) ) \
*( (char*)(PDST) ) = *( (char*)(PSRC) ); \
else if( sizeof(short) == (ELMTSIZE) ) \
*( (short*)(PDST) ) = *( (short*)(PSRC) ); \
else \
ylib_memcopy( (PDST), (PSRC), ELMTSIZE )
/******************************************************************************/
typedef hashtable_node** table_t;
enum YOUNG_LIBRARY_HASH_TABLE_CONSTANT { HASH_TABLE_PRIMES = 28 };
static const size_t hash_table_prime_list[ HASH_TABLE_PRIMES ] =
{
53UL, 97UL, 193UL, 389UL, 769UL,
1543UL, 3079UL, 6151UL, 12289UL, 24593UL,
49157UL, 98317UL, 196613UL, 393241UL, 786433UL,
1572869UL, 3145739UL, 6291469UL, 12582917UL, 25165843UL,
50331653UL, 100663319UL, 201326611UL, 402653189UL, 805306457UL,
1610612741UL, 3221225473UL, 4294967291UL
};
/******************************************************************************/
/******************************************************************************/
/* 返回用二分查找法从素数表中查找到的第一个不小于 num 的素数，如果找到的值大于
* 散列表所能拥有的最大链表数，则直接返回最大链表数 */
static size_t hash_table_next_prime( size_t num )
{
const size_t* middle = NULL;
const size_t* first = hash_table_prime_list;
const size_t* last = hash_table_prime_list + HASH_TABLE_PRIMES;
size_t half = 0, len = HASH_TABLE_PRIMES;
size_t max = SIZE_MAX / sizeof(hashtable_node*); /* 最大链表数 */
while( len > 0 )
{
half = len / 2;
middle = first + half;
if( *middle < num )
{
first = middle + 1;
len = len - half - 1;
}
else
len = half;
}
num = ( first == last ? *(last - 1) : *first );
return num < max ? num : max;
}
/******************************************************************************/
/* iterator */
/******************************************************************************/
#ifndef __MACRO_C_YOUNG_LIBRARY_COMPILER_SUPPORT_INLINE_FUNCTION__
bool hstb_itr_equal( const hstb_iterator left, const hstb_iterator right )
{
return left.node == right.node ? true : false;
}
/******************************************************************************/
void* hstb_itr_deref( hstb_iterator itr )
{
return NODE_DATA( itr.node );
}
/******************************************************************************/
void hstb_lc_itr_inc( hstb_local_iterator* plcitr )
{
*plcitr = (*plcitr)->next;
}
/******************************************************************************/
void* hstb_lc_itr_deref( hstb_local_iterator lcitr )
{
return ((ylib_byte_t*)lcitr) + sizeof(hashtable_node);
}
#endif
/******************************************************************************/
void hstb_itr_inc( hstb_iterator* pitr )
{
const hashtable_node* old = pitr->node;
pitr->node = pitr->node->next;
if( !(pitr->node) ) /* 寻找下一个有子节点的 chain */
{
size_t size = pitr->table->m_table_len;
size_t chain = HASH_NODE( pitr->table, old, size );
while( !(pitr->node) && ++chain < size )
pitr->node = pitr->table->m_chain_table[chain];
}
}
/******************************************************************************/
/* hash table */
/******************************************************************************/
static hashtable_node* hstb_create_node( hashtable* self, const void* value )
{
hashtable_node* node = (hashtable_node*)( self->m_alloc(
sizeof(hashtable_node) + self->m_element_size ) );
if( node )
{
node->next = NULL;
COPY_VALUE( NODE_DATA(node), value, self->m_element_size,
self->m_elmt_init_copy );
}
return node;
}
/******************************************************************************/
static bool hstb_copy_table( hashtable* self,
const hashtable* src )
{
self->m_chain_table = (table_t)( self->m_alloc( sizeof(hashtable_node*)
* src->m_table_len ) );
if( !(self->m_chain_table) )
return false;
else
{
size_t i;
hashtable_node* dst_current = NULL;
hashtable_node* src_current = NULL;
self->m_table_len = src->m_table_len;
ylib_memset( self->m_chain_table, 0,
src->m_table_len * sizeof(hashtable_node*) );
for( i = 0; i < self->m_table_len; ++i )
{
src_current = src->m_chain_table[i];
if( src_current )
{
self->m_chain_table[i]
= hstb_create_node( self, NODE_DATA(src_current) );
if( !(self->m_chain_table[i]) )
{
hstb_destroy( self );
return false;
}
++( self->m_node_count );
dst_current = self->m_chain_table[i];
src_current = src_current->next;
while( src_current )
{
dst_current->next
= hstb_create_node( self, NODE_DATA(src_current) );
if( dst_current->next )
{
++( self->m_node_count );
dst_current = dst_current->next;
src_current = src_current->next;
}
else
{
hstb_destroy( self );
return false;
}
} /* end while */
} /* end if( src_current ) */
} /* end for */
} /* end else */
return true;
}
/******************************************************************************/
static void hstb_weed_node( hashtable* self, hashtable_node* erase_node )
{
if( erase_node )
{
size_t index = HASH_NODE( self, erase_node, self->m_table_len );
hashtable_node* current = self->m_chain_table[index];
if( erase_node == current )
self->m_chain_table[index] = current->next;
else
{
hashtable_node* after = current->next;
while( after )
{
if( after == erase_node )
{
current->next = after->next;
return;
}
else
{
current = after;
after = current->next;
}
} /* end while */
} /* end else */
}
}
/******************************************************************************/
static void hstb_erase_chain_from_front( hashtable* self,
size_t index,
hashtable_node* last )
{
if( self->m_chain_table[index] && index < self->m_table_len )
{
bool destroy = ( self->m_elmt_destroy ? true : false );
hashtable_node* after;
hashtable_node* current = self->m_chain_table[index];
size_t node_size = sizeof(hashtable_node) + self->m_element_size;
while( current != last )
{
after = current->next;
if( true == destroy )
self->m_elmt_destroy( NODE_DATA(current) );
self->m_dealloc( current, node_size );
current = after;
--( self->m_node_count );
}
self->m_chain_table[index] = current;
}
}
/******************************************************************************/
static void hstb_erase_chain_from_middle( hashtable* self,
size_t index,
hashtable_node* first,
hashtable_node* last )
{
if( !(self->m_chain_table[index]) || index >= self->m_table_len )
return;
else if( self->m_chain_table[index] == first )
hstb_erase_chain_from_front( self, index, last );
else
{
bool destroy = ( self->m_elmt_destroy ? true : false );
size_t node_size = sizeof(hashtable_node) + self->m_element_size;
hashtable_node* before = self->m_chain_table[index];
hashtable_node* erase = before->next;
while( erase != first )
{
before = before->next;
erase = before->next;
}
while( erase != last )
{
before->next = erase->next;
if( true == destroy )
self->m_elmt_destroy( NODE_DATA(erase) );
self->m_dealloc( erase, node_size );
erase = before->next;
--( self->m_node_count );
}
}
}
/******************************************************************************/
static hstb_iterator hstb_insert_unique_node( hashtable* self,
const void* value )
{
bool get = ( self->m_get_key ? true : false );
size_t index = HASH_DATA( self, value, self->m_table_len );
hashtable_node* first = self->m_chain_table[index];
hashtable_node* current = first;
const void* insert_key = self->m_get_key ? self->m_get_key(value) : value;
hstb_iterator result;
result.node = NULL;
result.table = self;
while( current )
{
if( self->m_equal_key( GET_KEY_BOOL(self, current, get),
insert_key ) != 0 )
current = current->next;
else
{
result.node = current;
return result;
}
}
result.node = hstb_create_node( self, value );
if( result.node )
{
result.node->next = first;
self->m_chain_table[index] = result.node;
++( self->m_node_count );
}
return result;
}
/******************************************************************************/
static hstb_iterator hstb_insert_equal_node( hashtable* self,
const void* value )
{
bool get = ( self->m_get_key ? true : false );
size_t index = HASH_DATA( self, value, self->m_table_len );
hashtable_node* first = self->m_chain_table[index];
hashtable_node* current = first;
const void* insert_key = self->m_get_key ? self->m_get_key(value) : value;
hstb_iterator result;
result.node = NULL;
result.table = self;
result.node = hstb_create_node( self, value );
if( result.node )
{
while( current )
{
if( self->m_equal_key( GET_KEY_BOOL(self, current, get),
insert_key ) != 0 )
current = current->next;
else
{
first = current;
break;
}
}
if( first == self->m_chain_table[index] ) /* 没有相等的节点 */
{
result.node->next = first;
self->m_chain_table[index] = result.node;
}
else
{
result.node->next = first->next;
first->next = result.node;
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -