/* Copyright (C) Information Equipment co.,LTD All rights reserved. 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 **head; 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); s_hash_node = s_hash->head[s_hash->index(s_key, s_hash->table_count)]; 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->head[s_index] = s_hash_node; 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; s_hash_node = s_hash->head[s_index]; 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 */ s_hash->head = (struct ts_mzapi_hash_node **)malloc(s_hash->table_size); /* 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->add = __mzhash_add__; s_hash->del = __mzhash_del__; s_hash->info = __mzhash_info__; /* initialize hash table */ if(s_hash->head != ((struct ts_mzapi_hash_node **)0)) { 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); if(s_hash->head != ((struct ts_mzapi_hash_node **)0)) { for(s_index = 0;s_index < s_hash->table_count;s_index++) { while(s_hash->head[s_index] != ((struct ts_mzapi_hash_node *)0)) { s_prev_node = s_hash->head[s_index]; s_hash->head[s_index] = s_hash->head[s_index]->next; free((void *)s_prev_node); } } free((void *)s_hash->head); } 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)); } else (void)fprintf(stdout, "not found.\n"); (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 */
Copyrights © - Joinc, All Rights Reserved. Inherited From - Yundream Rebranded By - Joonphil
설명
사용방법
코드
변경사항
2004/01/08
Recent Posts
Archive Posts
Tags