C/C++ で使える Hashtable - BOOLEANLABEL
Link: C/C++ で使える Hashtable - BOOLEANLABEL
<blockquote class="link_og_blockquote"> Java のように豊富なライブラリを標準で提供している開発言語を使い慣れてしまうと、ふと C に戻った時に..</blockquote>
Cでハッシュテーブルを使おうと思った時に、車輪の再発明は嫌だし性能もどうせ悪いだろうしっていうことで調べてみた。
ちなみに、はじめに使おうとしたlibcのhsearchは配列の大きさ固定っぽくてrehashしてくれなさそうだったのでとりあえず利用を見送った。
ここで、glib使えばよさそうかなーってアタリをつけたので、glibのハッシュテーブルについて書いてある記事を3つほどメモ。
hsearchのテストコード。
//! gcc -o hsearch.bin hsearch.c -W -Wall -O3 -std=gnu99 #define _GNU_SOURCE #include <stdio.h> #include <stdint.h> #include <stdlib.h> #include <stdbool.h> #include <search.h> static char *keys[] = { "aaaa", "bbbb", "cccc", "dddd", "eeee", "ffff", "gggg", "hhhh", "iiii", "jjjj", "kkkk", "llll", "mmmm", "nnnn", "oooo", "pppp", "qqqq", "rrrr", "ssss", "tttt", "uuuu", "vvvv", "wwww", "xxxx", "yyyy", "zzzz"}; #define hsearch_errproc( search ) { \ if ( search == 0 ) { \ fprintf( stderr, "hsearch is failed\n" ); \ perror( "hsearch" ); \ exit( 1 ); \ } \ } int main( void ) { ENTRY e, *ep; struct hsearch_data htab = {0}; if ( !hcreate_r( 20, &htab ) ) { fprintf( stderr, "htab create is failed\n" ); exit( 1 ); } /* insert data into table */ for ( int i = 0; i < 26; i++ ) { printf( "%d\n", i ); e.key = keys[i]; e.data = (void*)i; /* hsearch_errproc( hsearch_r( e, ENTER, &ep, &htab ) ); */ hsearch_errproc( hsearch_r( e, ENTER, &ep, &htab ) ); } hdestroy_r( &htab ); return 0; }
glibのGHashTableのテストコード。
//! gcc -o ghash.bin ghash.c -W -Wall -O3 -std=gnu99 -lglib-2.0 -I/usr/include/glib-2.0 -I/usr/lib/i386-linux-gnu/glib-2.0/include #include <stdio.h> #include <stdint.h> #include <stdlib.h> #include <stdbool.h> #include <glib-2.0/glib.h> #include <string.h> static char *keys[] = { "aaaa", "bbbb", "cccc", "dddd", "eeee", "ffff", "gggg", "hhhh", "iiii", "jjjj", "kkkk", "llll", "mmmm", "nnnn", "oooo", "pppp", "qqqq", "rrrr", "ssss", "tttt", "uuuu", "vvvv", "wwww", "xxxx", "yyyy", "zzzz"}; void destroy_key( gpointer key ) { g_print( "destroy_key: %s\n", (char *)key ); g_free( key ); } void destroy_val( gpointer val ) { g_print( "destroy_val: %d\n", *(int*)val ); g_free( val ); } void print_hash( gpointer key, gpointer val, __attribute__((unused)) gpointer user_data ) { g_print( "%s: %d\n", (char *)key, *(int*)val ); } int main( void ) { GHashTable *htab = g_hash_table_new_full( g_str_hash, g_str_equal, destroy_key, destroy_val ); char *key; int *val; for ( int i = 0; i < 26; i++ ) { key = strdup( keys[i] ); val = g_new( int, 1 ); *val = i; g_print( "insert: %s, %d\n", key, *val ); g_hash_table_insert( htab, key, val ); } g_print( "----\n" ); g_hash_table_foreach( htab, print_hash, NULL ); g_print( "----\n" ); g_hash_table_remove( htab, keys[0] ); g_hash_table_foreach( htab, print_hash, NULL ); g_print( "----\n" ); g_hash_table_destroy( htab ); return 0; }