CLOSE

Recommanded Free YOUTUBE Lecture: <% selectedImage[1] %>
1. hash
2. hash의 개념을 이해하기 위한 코드
3. [yundream]
4. Version 0.2
5. 2004/01/09

### 설명

• 원문 : http://minzkn.wowdns.com:2744/phpBB2/viewtopic.php?t=438

### 사용방법

주어진 데이터를 얼마나 효율적인 구조로 인덱스 할것인가에 대한 생각을 하면서 직접 테스트 해보시길.

### 코드

```/*
Code by JaeHyuk Cho <mailto:minzkn@infoeq.com>
CVSTAG="\$Header: /usr/local/mutihost/joinc/modules/moniwiki/data/text/RCS/Code_2fC_2fmz_5fhash,v 1.1 2007/01/09 02:46:10 root Exp root \$"
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#define mzapi_export
#define mzapi_fastcall

typedef unsigned long t_mzapi_crc32;
typedef void * t_mzapi_vector;
#define t_mzapi_hash_key t_mzapi_crc32

struct ts_mzapi_hash_node
{
struct ts_mzapi_hash_node *prev;
struct ts_mzapi_hash_node *next;
t_mzapi_hash_key key;
t_mzapi_vector vector;
};

struct ts_mzapi_hash
{
int table_count;
size_t table_size;
t_mzapi_hash_key seed;
struct ts_mzapi_hash_node **tail;
/* member function */
t_mzapi_hash_key (mzapi_fastcall * function)(struct ts_mzapi_hash *, const void *, size_t);
int (mzapi_fastcall * index)(t_mzapi_hash_key, int);
struct ts_mzapi_hash_node * (mzapi_fastcall * search_by_key)(struct ts_mzapi_hash *, t_mzapi_hash_key);
struct ts_mzapi_hash_node * (mzapi_fastcall * next_search)(struct ts_mzapi_hash *, struct ts_mzapi_hash_node *);
struct ts_mzapi_hash_node * (mzapi_fastcall * prev_search)(struct ts_mzapi_hash *, struct ts_mzapi_hash_node *);
struct ts_mzapi_hash_node * (mzapi_fastcall * add)(struct ts_mzapi_hash *, t_mzapi_hash_key, t_mzapi_vector);
int (mzapi_fastcall * del)(struct ts_mzapi_hash *, struct ts_mzapi_hash_node *);
int (mzapi_fastcall * info)(struct ts_mzapi_hash *);
};

static t_mzapi_crc32 (mzapi_fastcall __mzhash_crc32__)(t_mzapi_crc32 s_crc32, unsigned char *s_buffer, int s_size);
static t_mzapi_hash_key (mzapi_fastcall __mzhash_function__)(struct ts_mzapi_hash *s_hash, const void *s_data, size_t s_size);
static int (mzapi_fastcall __mzhash_index__)(t_mzapi_hash_key s_key, int s_table_count);
static struct ts_mzapi_hash_node * (mzapi_fastcall __mzhash_search_by_key__)(struct ts_mzapi_hash *s_hash, t_mzapi_hash_key s_key);
static struct ts_mzapi_hash_node * (mzapi_fastcall __mzhash_next_search__)(struct ts_mzapi_hash *s_hash, struct ts_mzapi_hash_node *s_hash_node);
static struct ts_mzapi_hash_node * (mzapi_fastcall __mzhash_prev_search__)(struct ts_mzapi_hash *s_hash, struct ts_mzapi_hash_node *s_hash_node);
static struct ts_mzapi_hash_node * (mzapi_fastcall __mzhash_add__)(struct ts_mzapi_hash *s_hash, t_mzapi_hash_key s_key, t_mzapi_vector s_vector);
static int (mzapi_fastcall __mzhash_del__)(struct ts_mzapi_hash *s_hash, struct ts_mzapi_hash_node *s_hash_node);
static int (mzapi_fastcall __mzhash_info__)(struct ts_mzapi_hash *s_hash);

mzapi_export struct ts_mzapi_hash * (mzapi_fastcall mzapi_open_hash)(int s_table_count);
mzapi_export struct ts_mzapi_hash * (mzapi_fastcall mzapi_close_hash)(struct ts_mzapi_hash *s_hash);

static t_mzapi_crc32 (mzapi_fastcall __mzhash_crc32__)(t_mzapi_crc32 s_crc32, unsigned char *s_buffer, int s_size)
{
static t_mzapi_crc32 sg_crc32_table[ 1 << 8 ];
static int sg_given_crc32_table = 0;
t_mzapi_crc32 s_value;
int s_index, s_sub_index;
if(sg_given_crc32_table == 0)
{ /* make crc32 table */
sg_given_crc32_table = 1;
for(s_index = 0;s_index < (sizeof(sg_crc32_table) / sizeof(t_mzapi_crc32));s_index++)
{
s_value = (t_mzapi_crc32)s_index;
for(s_sub_index = 0;s_sub_index < 8;s_sub_index++)
{
if(s_value & 0x00000001ul)s_value = 0xedb88320ul ^ (s_value >> 1);
else s_value >>= 1;
}
sg_crc32_table[s_index] = s_value;
}
}
s_value = s_crc32 ^ ((t_mzapi_crc32)0xfffffffful);
for(s_index = 0;s_index < s_size;s_index++)s_value = sg_crc32_table[(s_value ^ ((t_mzapi_crc32)s_buffer[s_index])) & ((t_mzapi_crc32)0x000000fful)] ^ (s_value >> 8);
return(s_value ^ ((t_mzapi_crc32)0xfffffffful));
}

static t_mzapi_hash_key (mzapi_fastcall __mzhash_function__)(struct ts_mzapi_hash *s_hash, const void *s_data, size_t s_size)
{
return((t_mzapi_hash_key)__mzhash_crc32__((s_hash != ((struct ts_mzapi_hash *)0)) ? s_hash->seed : ((t_mzapi_hash_key)0), (unsigned char *)s_data, s_size));
}

static int (mzapi_fastcall __mzhash_index__)(t_mzapi_hash_key s_key, int s_table_count)
{
return((int)(s_key % ((t_mzapi_hash_key)s_table_count)));
}

static struct ts_mzapi_hash_node * (mzapi_fastcall __mzhash_search_by_key__)(struct ts_mzapi_hash *s_hash, t_mzapi_hash_key s_key)
{
struct ts_mzapi_hash_node *s_hash_node;
if(s_hash == ((struct ts_mzapi_hash *)0))return((struct ts_mzapi_hash_node *)0);
while(s_hash_node != ((struct ts_mzapi_hash_node *)0))
{
if(s_hash_node->key == s_key)break;
s_hash_node = s_hash_node->next;
}
return(s_hash_node);
}

static struct ts_mzapi_hash_node * (mzapi_fastcall __mzhash_next_search__)(struct ts_mzapi_hash *s_hash, struct ts_mzapi_hash_node *s_hash_node)
{
t_mzapi_hash_key s_key;
if(s_hash_node != ((struct ts_mzapi_hash_node *)0))
{
s_key = s_hash_node->key;
s_hash_node = s_hash_node->next;
while(s_hash_node != ((struct ts_mzapi_hash_node *)0))
{
if(s_hash_node->key == s_key)break;
s_hash_node = s_hash_node->next;
}
}
return(s_hash_node);
}

static struct ts_mzapi_hash_node * (mzapi_fastcall __mzhash_prev_search__)(struct ts_mzapi_hash *s_hash, struct ts_mzapi_hash_node *s_hash_node)
{
t_mzapi_hash_key s_key;
if(s_hash_node != ((struct ts_mzapi_hash_node *)0))
{
s_key = s_hash_node->key;
s_hash_node = s_hash_node->prev;
while(s_hash_node != ((struct ts_mzapi_hash_node *)0))
{
if(s_hash_node->key == s_key)break;
s_hash_node = s_hash_node->prev;
}
}
return(s_hash_node);
}

static struct ts_mzapi_hash_node * (mzapi_fastcall __mzhash_add__)(struct ts_mzapi_hash *s_hash, t_mzapi_hash_key s_key, t_mzapi_vector s_vector)
{
struct ts_mzapi_hash_node *s_hash_node;
int s_index;
if(s_hash == ((struct ts_mzapi_hash *)0))return((struct ts_mzapi_hash_node *)0);
s_hash_node = (struct ts_mzapi_hash_node *)malloc((size_t)sizeof(struct ts_mzapi_hash_node));
if(s_hash_node != ((struct ts_mzapi_hash_node *)0))
{
s_hash_node->key = s_key;
s_hash_node->vector = s_vector;
s_index = s_hash->index(s_key, s_hash->table_count);
if(s_hash->tail[s_index] == ((struct ts_mzapi_hash_node *)0))
{
s_hash_node->prev = s_hash_node->next = (struct ts_mzapi_hash_node *)0;
s_hash->tail[s_index] = s_hash_node;
}
else
{
s_hash_node->prev = s_hash->tail[s_index];
s_hash_node->next = (struct ts_mzapi_hash_node *)0;
s_hash->tail[s_index]->next = s_hash_node;
s_hash->tail[s_index] = s_hash_node;
}
}
return(s_hash_node);
}

static int (mzapi_fastcall __mzhash_del__)(struct ts_mzapi_hash *s_hash, struct ts_mzapi_hash_node *s_hash_node)
{
int s_index;
if(s_hash == ((struct ts_mzapi_hash *)0))return(-1);
if(s_hash_node == ((struct ts_mzapi_hash_node *)0))return(0);
s_index = s_hash->index(s_hash_node->key, s_hash->table_count);
if(s_hash_node->prev == ((struct ts_mzapi_hash_node *)0))s_hash->head[s_index] = s_hash_node->next;
else s_hash_node->prev->next = s_hash_node->next;
if(s_hash_node->next == ((struct ts_mzapi_hash_node *)0))s_hash->tail[s_index] = s_hash_node->prev;
else s_hash_node->next->prev = s_hash_node->prev;
free((void *)s_hash_node);
return(1);
}

static int (mzapi_fastcall __mzhash_info__)(struct ts_mzapi_hash *s_hash)
{
int s_index;
int s_hash_count;
struct ts_mzapi_hash_node *s_hash_node;
if(s_hash == ((struct ts_mzapi_hash *)0))return(-1);
(void)fprintf(stdout,
"\nhash info\n=========\n\n"
"table_count = %d\n"
"table_size  = %lu\n"
"seed        = %08lXH\n\n",
s_hash->table_count,
(unsigned long)s_hash->table_size,
(unsigned long)s_hash->seed);
for(s_index = 0;s_index < s_hash->table_count;s_index++)
{
s_hash_count = 0;
while(s_hash_node != ((struct ts_mzapi_hash_node *)0))
{
s_hash_count++;
s_hash_node = s_hash_node->next;
}
(void)fprintf(stdout, " [%5d] hash_nodes=%d\n", s_index, s_hash_count);
}
(void)fputs("\nEnd of hash info.\n", stdout);
return(1);
}

struct ts_mzapi_hash * (mzapi_fastcall mzapi_open_hash)(int s_table_count)
{
struct ts_mzapi_hash *s_hash;
int s_index;
s_hash = (struct ts_mzapi_hash *)malloc((size_t)sizeof(struct ts_mzapi_hash));
if(s_hash != ((struct ts_mzapi_hash *)0))
{
if(s_table_count <= 0)s_table_count = 256; /* default */
s_hash->table_count   = s_table_count;
s_hash->table_size    = (size_t)(s_hash->table_count * sizeof(struct ts_mzapi_hash_node *));
s_hash->seed          = (t_mzapi_hash_key)0; /* default seed key */
/* mapping member function */
s_hash->function      = __mzhash_function__;
s_hash->index         = __mzhash_index__;
s_hash->search_by_key = __mzhash_search_by_key__;
s_hash->next_search   = __mzhash_next_search__;
s_hash->prev_search   = __mzhash_prev_search__;
s_hash->del           = __mzhash_del__;
s_hash->info          = __mzhash_info__;
/* initialize hash table */
{
for(s_index = 0;s_index < s_hash->table_count;s_index++)s_hash->head[s_index] = (struct ts_mzapi_hash_node *)0;
s_hash->tail = (struct ts_mzapi_hash_node **)malloc(s_hash->table_size);
if(s_hash->tail != ((struct ts_mzapi_hash_node **)0))
{
for(s_index = 0;s_index < s_hash->table_count;s_index++)s_hash->tail[s_index] = (struct ts_mzapi_hash_node *)0;
/* ok */
}
else s_hash = mzapi_close_hash(s_hash);
}
else
{
s_hash->tail = (struct ts_mzapi_hash_node **)0;
s_hash = mzapi_close_hash(s_hash);
}
}
return(s_hash);
}

struct ts_mzapi_hash * (mzapi_fastcall mzapi_close_hash)(struct ts_mzapi_hash *s_hash)
{
int s_index;
struct ts_mzapi_hash_node *s_prev_node;
if(s_hash != ((struct ts_mzapi_hash *)0))
{
if(s_hash->tail != ((struct ts_mzapi_hash_node **)0))free((void *)s_hash->tail);
{
for(s_index = 0;s_index < s_hash->table_count;s_index++)
{
{
free((void *)s_prev_node);
}
}
}
free((void *)s_hash);
}
return((struct ts_mzapi_hash *)0);
}

#if 1 /* simple test code -------------------------------------------------- */
struct ts_data
{
struct ts_data *next;
int index;
size_t size;
void *ptr;
};

static struct ts_data * test_data(FILE *s_file)
{
struct ts_data *s_data, *s_last, *s_new;
unsigned char s_buffer[ 32 << 10 ];
char *s_line;
size_t s_len;
int s_index = 0;
s_data = s_last = (struct ts_data *)0;
do
{ /* indexing from stdin */
s_line = fgets((char *)(&s_buffer[0]), sizeof(s_buffer), stdin);
if(s_line == (char *)0)break;
s_index++;
s_len = strlen(s_line);
while(s_len > 0)
{ /* strip \n */
if(s_line[s_len - 1] == '\n')s_line[--s_len] = '\0';
else break;
}
s_new = (struct ts_data *)malloc((size_t)sizeof(struct ts_data));
if(s_new != ((struct ts_data *)0))
{
s_new->index = s_index;
s_new->size = s_len;
s_new->ptr = (void *)malloc(s_new->size + ((size_t)1));
if(s_new->ptr != ((void *)0))(void)strcpy((char *)s_new->ptr, s_line);
s_new->next = (struct ts_data *)0;
if(s_last == ((struct ts_data *)0))s_data = s_new;
else s_last->next = s_new;
s_last = s_new;
}
}while(1);
return(s_data);
}

static void free_data(struct ts_data *s_data)
{
struct ts_data *s_prev;
while(s_data != ((struct ts_data *)0))
{
s_prev = s_data;
s_data = s_data->next;
if(s_prev->ptr != ((void *)0))free(s_prev->ptr);
free((void *)s_prev);
}
}

int (main)(int s_argc, char **s_argv)
{
struct ts_mzapi_hash *s_hash;
struct ts_mzapi_hash_node *s_hash_node;
struct ts_data *s_data;
struct ts_data *s_temp;
int s_arg_index;
if(s_argc <= 1) (void)fprintf(stdout, "usage: %s <keyword> [...]\n", s_argv[0]);
else
{
s_hash = mzapi_open_hash(128 /* table_count */);
if(s_hash != ((struct ts_mzapi_hash *)0))
{
s_data = test_data(stdin);
if(s_data != ((struct ts_data *)0))
{
/* indexing hash */
(void)fprintf(stdout, "enter: index\n");
s_temp = s_data;
while(s_temp != ((struct ts_data *)0))
{
s_hash_node = s_hash->add(s_hash, s_hash->function(s_hash, s_temp->ptr, s_temp->size), (t_mzapi_vector)s_temp);
if(s_hash_node != ((struct ts_mzapi_hash_node *)0))
(void)fprintf(stdout, " indexing [key=%08lXH, line=%d] \"%s\"\n", (unsigned long)s_hash_node->key, s_temp->index, (char *)s_temp->ptr);
s_temp = s_temp->next;
}
(void)fprintf(stdout, "leave: index\n");

#if 1 /* hash view */
s_hash->info(s_hash);
#endif
(void)fprintf(stdout, "\n");

for(s_arg_index = 1;s_arg_index < s_argc;s_arg_index++)
{
/* search */
(void)fprintf(stdout, "enter: search[%d] \"%s\"\n", s_arg_index, s_argv[s_arg_index]);
s_hash_node = s_hash->search_by_key(s_hash, s_hash->function(s_hash, (void *)s_argv[s_arg_index], (size_t)strlen(s_argv[s_arg_index]))); /* first search */
if(s_hash_node != ((struct ts_mzapi_hash_node *)0))
{
do
{
s_temp = (struct ts_data *)s_hash_node->vector;
(void)fprintf(stdout, " line=%d, \"%s\"\n", s_temp->index, (char *)s_temp->ptr);
s_hash_node = s_hash->next_search(s_hash, s_hash_node);
}while(s_hash_node != ((struct ts_mzapi_hash_node *)0));
}
(void)fprintf(stdout, "leave: search[%d] \"%s\"\n\n", s_arg_index, s_argv[s_arg_index]);
}

free_data(s_data);
}
else (void)fprintf(stdout, "no data\n");
(void)mzapi_close_hash(s_hash);
}
}
return(0);
}
#endif

/* vim: set expandtab: */
/* End of source */```