免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12下一页
最近访问板块 发新帖
查看: 7290 | 回复: 13

[C] 如何建立hash表 [复制链接]

论坛徽章:
0
发表于 2011-09-03 13:17 |显示全部楼层
1.        建立2个hash数组:hash_lan,hash_wan,数组中的每个元素维护一张结构体链表头,结构体中必须的元素:source_ip,source_port,nat_ip,nat_port
2.        外出数据包 Hash 表创建:
Unsigned short    hash_create_and _find(unsigned   int source_ip,  unsigned short    source_port,   unsigned int    nat_ip);
以 source_ip,source_port 计算hash值,以该值为索引取得hash_lan中的一张结构体链表头,以 source_ip,source_port检索该结构体链表,若有匹配的,则返回结构体中的nat_port值;若无则新建结构体,在其中保存source_ip,source_port,nat_ip及新分配的nat_port值,并将该结构体插入链表中,再以nat_port,nat_ip计算hash值,在hash_out中获取一张结构体链表头,新建结构体,在其中保存source_ip,source_port,nat_ip及nat_port值并将该结构体插入链表中。


这个比较急啊,请哪位老兄帮一下

论坛徽章:
0
发表于 2011-09-03 14:15 |显示全部楼层
本帖最后由 ChiyuT 于 2011-09-03 14:26 编辑

回复 1# cuiwei000

凑合看一下吧。
  1. typedef struct item {
  2.         unsigned int source_ip;
  3.         unsigned short source_port;
  4.         unsigned int nat_ip;
  5.         unsigned short nat_port;
  6.         struct item * next;
  7. } Item;

  8. Item hash_lan[HASH_LAN_LEN];
  9. Item hash_wan[HASH_WAN_LEN];

  10. unsigned short hash_create_and_find(unsigned int source_ip, unsigned short source_port, unsigned int nat_ip)
  11. {
  12.         int key;
  13.         Item * prev, * cur;

  14.         key = xxx_hash(source_ip, source_port);

  15.         cur = &(hash_lan[key]);
  16.        
  17.         while (cur) {
  18.                 if (cur->source_ip == source_ip && cur->source_port == source_port) {
  19.                         return cur->nat_port;
  20.                 }
  21.                 prev = cur;
  22.                 cur = cur->next;
  23.         }
  24.        
  25.         if ((cur = (Item *)malloc(sizeof(Item))) == NULL) {
  26.                 ;
  27.         }
  28.         cur->source_ip = source_ip;
  29.         cur->source_port = source_port;
  30.         cur->nat_ip = nat_ip;
  31.         cur->next = NULL;
  32.         prev->next = cur;

  33.         key = yyy_hash(nat_port, nat_ip);
  34.         prev = &(hash_wan[key]);
  35.        
  36.         if ((cur = (Item *)malloc(sizeof(Item))) == NULL) {
  37.                ;
  38.         }
  39.         cur->source_ip = source_ip;
  40.         cur->source_port = source_port;
  41.         cur->nat_port = nat_port;
  42.         cur->next = NULL;

  43.         while (prev->next) {
  44.                 prev = prev->next;
  45.         }

  46.         prev->next = cur;
  47.        
  48.         return nat_port;
  49. }
复制代码

论坛徽章:
0
发表于 2011-09-03 14:29 |显示全部楼层
大哥 太感谢你了,

论坛徽章:
0
发表于 2011-09-03 14:32 |显示全部楼层
大哥 太感谢你了,

论坛徽章:
0
发表于 2011-09-03 14:33 |显示全部楼层
key=xxx_hash(source_ip,source_port);
这个函数在哪里啊

论坛徽章:
0
发表于 2011-09-03 14:38 |显示全部楼层
3.        输入数据包hash搜索:
int    hash_find(unsigned int*    source_ip,  unsigned short*    source_port,   unsigned int      nat_ip,   unsigned short     nat_port);
以 nat_port,nat_ip计算hash值,以该值为索引取得hash_wan中的一张结构体链表头,以 nat_port,nat_ip检索该结构体链表,若有匹配的,则在source_ip、source_port 指针中存放该结构体中的source_ip,source_port值,且返回值为0;如没有匹配的则返回  -1,且source_ip、source_port 指针为NULL;
第3部分怎么写啊,大哥

论坛徽章:
0
发表于 2011-09-03 14:41 |显示全部楼层
key=xxx_hash(source_ip,source_port);
这个函数在哪里啊
cuiwei000 发表于 2011-09-03 14:33


这个是hash函数啊,你自己去查找一个合适你的要求的。

论坛徽章:
0
发表于 2011-09-03 14:43 |显示全部楼层
本帖最后由 ChiyuT 于 2011-09-03 14:46 编辑
3.        输入数据包hash搜索:
int    hash_find(unsigned int*    source_ip,  unsigned short*    source_por ...
cuiwei000 发表于 2011-09-03 14:38


这个就跟刚才那个一样了吧。几乎同样的操作。也就是先计算hash得到key,然后遍历一下链表即可。

论坛徽章:
0
发表于 2011-09-03 15:42 |显示全部楼层
谢谢ChiyuT!

论坛徽章:
0
发表于 2011-09-03 16:37 |显示全部楼层
ChiyuT大哥您有skepy吗,我刚进入linux c开发,是个菜鸟,以后还要向您多多请教
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP