Hash Table in C

Hash Table應該上計概或資料結構的時候都會講到, 一般的用法就是傳入一個Key, 透過查表, 回傳相對應的Value.
看看wiki上"Hash table"的解釋, 感覺實做上似乎不是那麼容易, 尤其是hash function的設計, 但多數的程式語言, 如perl, java, c#, 都提供了hash相關的library. 在linux下, 也有一系列的"hash table management" APIs.

以下提供一個簡單的範例
my_hash.c

#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <search.h>

typedef struct _node_t
{
    char key[16];
    char value[16];
}node_t;

static node_t *node_list = NULL;

static struct hsearch_data htab;

void set_node(char *name, char *value)
{
    ENTRY e, *ep;

    memset(&e, 0, sizeof(ENTRY));
    e.key = name;

    hsearch_r(e, FIND, &ep, &htab);
    if(ep)
        ep->data = value;
    else
    {
        e.data = value;
        hsearch_r(e, ENTER, &ep, &htab);
    }
}

void get_node(char *name, char *buf)
{
    ENTRY e={NULL,NULL}, *ep;

    e.key = name;
    hsearch_r(e, FIND, &ep, &htab);

    if (ep && ep->data)
        strcpy(buf, ep->data);
    else
        strcpy(buf, "");
}

void release_htab()
{
    if (node_list) free(node_list);
    hdestroy_r(&htab);
}

void create_htab(char *fpath)
{
    FILE *fp = NULL;
    int nel=0;   

    fp = fopen(fpath, "r");
    if (!fp)
    {
        CM_DBG("Cannot open %s\n", fpath);
        return;
    }

    release_htab();

    // Get the total number
    while(!feof(fp) && fgets(str, BUF_SIZE, fp))
    {
        nel++;
    }

    if(!hcreate_r(nel, &htab))
        return;

    node_list = malloc(sizeof(node_t)*nel);
    memset(node_list, 0, (sizeof(node_t)*nel));

    rewind(fp);

    char str[256] = {0};
    char *ptr=NULL, *saveptr=NULL;
    node_t *p_node = NULL;
    int i = 0;

    while(!feof(fp) && fgets(str, BUF_SIZE, fp))
    {
        p_node = (node_t *)(node_list+i);

        //The string format: Name,PhoneNo
        ptr = strtok_r(str, ",", &saveptr);        // Name
        if (ptr)
            strcpy(p_node->key, ptr);
        else
            continue;

        ptr = strtok_r(NULL, ",\n", &saveptr);    // Phone No
        if (ptr)
            strcat(p_node->value, ptr);
        else
            continue;

        set_node(p_node->key, p_node->value);    //Put into hash table
        i++;
    }
}

其中, 要注意的地方在於, 塞hash table時, 需要動態配置記憶體空間來儲存值組(key, value), 但hdestroy並不會釋放動態配置的記憶體空間, 使用者需要自己free. 在範例程式中, 單純開了一個大塊的空間去存值, 但比較好的作法,可能是用linked list去紀錄各個值組, 這樣比較不用怕浪費太多記憶體空間或是buffer不夠大的問題.

參考資料：
[1] hsearch_r.c