openssl哈希表

一 哈希表

        在一般的数据结构如线性表和树中，记录在结构中的相对位置是与记录的关键字之间不存在确定的关系，在结构中查找记录时需进行一系列的关键字比较。这一类查找方法建立在“比较”的基础上，查找的效率与比较次数密切相关。理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立确定的对应关系，使每个关键字和结构中一个唯一的存储位置相对应。在查找时，只需根据这个对应关系找到给定值。这种对应关系既是哈希函数，按这个思想建立的表为哈希表。

        哈希表存在冲突现象：不同的关键字可能得到同一哈希地址。在建造哈希表时不仅要设定一个好的哈希函数，而且要设定一种处理冲突的方法。

 

二 哈希表数据结构

        openssl函数使用哈希表来加快查询操作，并能存放任意形式的数据，比如配置文件的读取、内存分配中被分配内存的信息等。其源码在crypto/lhash目录下。

        openssl中的哈希表数据结构在lhash.h中定义。

1. typedef struct lhash_node_st
   {
       void *data;
       struct lhash_node_st *next;
   #ifndef OPENSSL_NO_HASH_COMP
       unsigned long hash;
   #endif
   }LHASH_NODE;

    

本结构是一个单链表。

data：用于存放数据地址。

next：为下一个数据地址。

hash：为数据哈希计算值。

 

typedefstruct lhash_st
{
	LHASH_NODE **b;
 	LHASH_COMP_FN_TYPE comp;
 	LHASH_HASH_FN_TYPE hash;
	unsigned	int num_nodes;
	unsigned	int num_alloc_nodes;
	unsigned	int p;
	unsigned	int pmax;
	unsigned	long up_load;/* load times 256 */
	unsigned	long down_load;/* load times 256 */
	unsigned	long num_items;
	unsigned	long num_expands;
	unsigned	long num_expand_reallocs;
	unsigned	long num_contracts;
	unsigned	long num_contract_reallocs;
	unsigned	long num_hash_calls;
	unsigned	long num_comp_calls;
	unsigned	long num_insert;
	unsigned	long num_replace;
	unsigned	long num_delete;
	unsigned	long num_no_delete;
	unsigned	long num_retrieve;
	unsigned	long num_retrieve_miss;
	unsigned	long num_hash_comps;
	int error;
}LHASH;

 

b指针数组用于存放所有的数据，数组中的每一个值为数据链表的头指针。

comp用于存放数据比较函数地址。

hash用于存放计算哈希值函数的地址。

num_nodes为链表个数。

num_alloc_nodes为b分配空间的大小。

三 哈希函数说明

1、LHASH *lh_new(LHASH_HASH_FN_TYPE h, LHASH_COMP_FN_TYPE c)

功能：生成哈希表

源文件：lhash.c

说明：输入参数h为哈希函数，c为比较函数。这两个函数都是回调函数。因为哈希表用于存放任意的数据结构，哈希表存放、查询、删除等操作都需要比较数据和进行哈希运算，而哈希表不知道用户数据如何进行比较，也不知道用户数据结构中需要对哪些关键项进行散列运算。所以，用户必须提供这两个回调函数。

2、void *lh_delete(LHASH *lh, const void *data)

源文件：lhash.c

功能：删除散列表中的一个数据

说明：data为数据结构指针。

3、void lh_doall(LHASH *lh, LHASH_DOALL_FN_TYPE func)

源文件：lhash.c

功能：处理哈希表中的所有数据

说明：func为外部提供的回调函数，本函数遍历所有存储在哈希表中的数据，每个数据被func处理。

4、void lh_doall_arg(LHASH *lh, LHASH_DOALL_ARG_FN_TYPE func, void *arg)

源文件：lhash.c

功能：处理哈希表中所有数据

说明：此参数类似于lh_doall函数，func为外部提供的回调函数，arg为传递给func函数的参数。本函数遍历所有存储在哈希表中的数据，每个数据被func处理。

5、void lh_free(LHASH *lh)

源文件：lhash.c

功能：释放哈希表。

6、void *lh_insert(LHASH *lh, void *data)

源文件：lhash.c

功能：往哈希表中添加数据。

说明：data为需要添加数据结构的指针地址。

7、void *lh_retrieve(LHASH *lh, const void *data)

源文件：lhash.c

功能：查询数据。

说明：从哈希表中查询数据，data为数据结构地址，此数据结构中必须提供关键项(这些关键项对应于用户提供的哈希函数和比较函数)以供查询，如果查询成功，返回数据结构的地址，否则返回NULL。比如SSL握手中服务端查询以前存储的SESSION时，它需要提供其中关键的几项。

SSL_SESSION *ret=NULL,data;

data.ssl_version=s->version;

data.session_id_length=len;

memcpy(data.session_id,session_id,len);

ret=(SSL_SESSION *)lh_retrieve(s->ctx->sessions,&data);

8、void lh_node_stats_bio(const LHASH *lh, BIO *out)

源文件：lh_stats.c

功能：将哈希表中每个链表下的数据状态输出到BIO中。

9、void lh_node_stats(const LHASH *lh, FILE *fp)

源文件：lh_stats.c

功能：将哈希表中每个链表下数据到输出到FILE中。

说明：此函数调用了lh_node_stats_bio函数。

10、void lh_node_usage_stats_bio(const LHASH *lh, BIO *out)

源文件：lh_stats.c

功能：将哈希表的使用状态输出到BIO中。

11、void lh_node_usage_stats(const LHASH *lh, FILE *fp)

源文件：lh_stats.c

功能：将哈希表的使用状态输出到FILE中。

说明：此函数调用了lh_node_usage_stats_bio函数

12、unsigned long lh_num_items(const LHASH *lh)

源文件：lhash.c

功能：获取哈希表中元素的个数。

13、void lh_stats_bio(const LHASH *lh, BIO *out)

源文件：lh_stats.c

功能：输出哈希表统计信息到BIO中。

14、void lh_stats(const LHASH *lh, FILE *fp)

源文件：lh_stats.c

功能：打印哈希表的统计信息，此函数调用了lh_stats_bio。

15、unsigned long lh_strhash(const char *c)

源文件：lhash.c

 

四 实例

1. #include<string.h>
2. #include<openssl/lhash.h>
4. typedefstructStudent_st
5. {
6. char name[20];
7. int age;
8. char otherInfo[200];
9. }Student;
11. staticintStudent_cmp(constvoid*a,constvoid*b)
12. {
13. char*namea=((Student*)a)->name;
14. char*nameb=((Student*)b)->name;
15. return strcmp(namea,nameb);
16. }
18. /* 打印每个值*/
19. staticvoidPrintValue(Student*a)
20. {
21. printf("name :%s\n",a->name);
22. printf("age :%d\n",a->age);
23. printf("otherInfo : %s\n",a->otherInfo);
24. }
26. staticvoidPrintValue_arg(Student*a,void*b)
27. {
28. int flag=0;
30. flag=*(int*)b;
31. printf("用户输入参数为:%d\n",flag);
32. printf("name :%s\n",a->name);
33. printf("age :%d\n",a->age);
34. printf("otherInfo : %s\n",a->otherInfo);
35. }
37. int main()
38. {
39. int flag=11;
40. _LHASH *h;
41. Student s1={"zcp",28,"hu bei"},
42. s2={"forxy",28,"no info"},
43. s3={"skp",24,"student"},
44. s4={"zhao_zcp",28,"zcp's name"},
45. *s5;
46. void*data;
48. /*创建哈希表*/
49. h=lh_new(NULL,Student_cmp);
50. if(h==NULL)
51. {
52. printf("err.\n");
53. return-1;
54. }
55. /*将数据插入哈希表*/
56. data=&s1;
57. lh_insert(h,data);
58. data=&s2;
59. lh_insert(h,data);
60. data=&s3;
61. lh_insert(h,data);
62. data=&s4;
63. lh_insert(h,data);
65. /*遍历打印*/
66. lh_doall(h,PrintValue);
67. lh_doall_arg(h,PrintValue_arg,(void*)(&flag));
69. /*查找数据*/
70. data=lh_retrieve(h,(constvoid*)"skp");
71. if(data==NULL)
72. {
73. printf("can not find skp!\n");
74. lh_free(h);
75. return-1;
76. }
77. else
78. {
79. s5=data;
80. printf("\n\nstudent name : %s\n",s5->name);
81. printf("sutdent age : %d\n",s5->age);
82. printf("student otherinfo : %s\n",s5->otherInfo);
83. lh_free(h);
84. }
86. getchar();
87. return0;
88. }

编译与运行

1. [root@localhost ~]# cd /
2. [root@localhost /]# cd openssl-1.1.0c/test
3. [root@localhost test]# gcc example2.c -o example2 -L/usr/lib -lssl -lcrypto
4. [root@localhost test]# ./example2 name :zhao_zcp age :28 otherInfo : zcp's name name :skp age :24 otherInfo : student name :forxy age :28 otherInfo : no info name :zcp age :28 otherInfo : hu bei 用户输入参数为:11 name :zhao_zcp age :28 otherInfo : zcp's name 用户输入参数为:11 name :skp age :24 otherInfo : student 用户输入参数为:11 name :forxy age :28 otherInfo : no info 用户输入参数为:11 name :zcp age :28 otherInfo : hu bei student name : skp sutdent age : 24 student otherinfo : student