注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Code@Pig Home

喜欢背着一袋Code傻笑的Pig .. 忧美.欢笑.记忆.忘却 .之. 角落

 
 
 

日志

 
 

[avro-c] 神奇的 general hashtable  

2011-02-14 15:42:35|  分类: serialize_avro |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
在 avro-c 代码中看到 st.h / st.c 这个 hashtable 实现。很精巧,同时包容了int、string作为key的情况,也可以自己定制特殊的 key 格式。

但最有趣的是这段注释,1989年的作品!Peter Moore 是哪位大神,google不出来,没有详细考证,无限敬仰之。
/*
 * This is a public domain general purpose hash table package written by
 * Peter Moore @ UCB. 
 */

/*
 * @(#) st.h 5.1 89/12/14 
 */
并且这个 hashtable 被用于很多地方,比如 ruby。

以后我都不需要自己实现 hashtable (c version) 了。好,来看看这个 hashtable 如何使用:
--------------------------------------------------------------------------------------------------
#include "st.h"
#include <stdlib.h>
#include <stdio.h>

int
numtable_print(int key, int value, void *hint)
{
    printf("hint:%s, key:%d, value:%d\n", (const char *)hint, key, value);
    return ST_CONTINUE;
}

void
numtable_test()
{
    int r;
    int key, value;
    st_table *numtable;

    numtable = st_init_numtable();

    // st_insert()
    //   0 - create a new key/value
    //   1 - key exists, value updated
    r = st_insert(numtable, 1, 10);
    printf("st_insert(1, 10), r = %d\n", r);
    r = st_insert(numtable, 1, 11);
    printf("st_insert(1, 11), r = %d\n", r);

    st_insert(numtable, 2, 20);

    // st_lookup()
    //   0 - not found
    //   1 - found, value is usable
    r = st_lookup(numtable, 1, &value);
    printf("st_lookup(1) = %d, r = %d\n", value, r);

    // st_delete()
    //   0 - key not found
    //   1 - delete ok, value is the value of the key deleted
    key = 2;
    r = st_delete(numtable, &key, &value);
    printf("st_delete(2) = %d, r = %d\n", value, r);

    // st_foreach()
    //   0 - succeed
    //   1 - call func with error, notice
    r = st_foreach(numtable, numtable_print, "numtable");
    printf("st_foreach(), r = %d\n", r);

    st_free_table(numtable);
}


int
strtable_print(const char *key, int value, void *hint)
{
    printf("hint:%s, key:%s, value:%d\n", (const char *)hint, key, value);
    return ST_CONTINUE;
}

void
strtable_test()
{
    int r;
    const char *key;
    int value;
    st_table *strtable;

    strtable = st_init_strtable();

    // st_insert()
    r = st_insert(strtable, "key1", 10);
    printf("st_insert(\"key1\", 10), r = %d\n", r);
    r = st_insert(strtable, "key1", 11);
    printf("st_insert(\"key1\", 11), r = %d\n", r);

    st_insert(strtable, "key2", 20);

    // st_lookup()
    r = st_lookup(strtable, "key1", &value);
    printf("st_lookup(\"key1\") = %d, r = %d\n", value, r);

    // st_delete()
    key = "key2";
    r = st_delete(strtable, &key, &value);
    printf("st_delete(2) = %d, r = %d\n", value, r);

    // st_foreach()
    r = st_foreach(strtable, strtable_print, "strtable");
    printf("st_foreach(), r = %d\n", r);

    st_free_table(strtable);
}

int main()
{
    numtable_test();
    strtable_test();
    return 0;
}
--------------------------------------------------------------------------------------------------
$ ./a.out 
st_insert(1, 10), r = 0
st_insert(1, 11), r = 1
st_lookup(1) = 11, r = 1
st_delete(2) = 20, r = 1
hint:numtable, key:1, value:11
st_foreach(), r = 0

st_insert("key1", 10), r = 0
st_insert("key1", 11), r = 1
st_lookup("key1") = 11, r = 1
st_delete(2) = 20, r = 1
hint:strtable, key:key1, value:11
st_foreach(), r = 0
--------------------------------------------------------------------------------------------------

编译会有一些 warning,恩,这很正常。

通过 st_hash_type{} 还可以定制特制版的 hashtable。cooool~
struct st_hash_type {
    int (*compare) ();
    int (*hash) ();
};
st_table *st_init_table(struct st_hash_type *);

此 hashtable 的详细结构分析,参见:
  评论这张
 
阅读(1380)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017