2021SC@SDUSC
4 hash table
man lhash
4.1 hash table
In general data structures such as linear tables and trees, there is no definite relationship between the relative position of records in the structure and the keywords of records,
A series of keyword comparisons are needed to find records in the structure
This kind of search method is based on "comparison", and the search efficiency is closely related to the number of comparisons.
Ideally, the required records can be found directly, so a definite corresponding relationship must be established between the storage location of the record and its keywords,
Make each keyword correspond to a unique storage location in the structure
When searching, you only need to find the given value according to this correspondence
This correspondence is a hash function, and the table established according to this idea is a hash table.
Hash table conflicts:
Different keywords may get the same hash address.
When building a hash table, we should not only set a good hash function, but also set a method to deal with conflicts.
4.2 hash table data structure
openssl function uses hash table to speed up query operation, and can store any form of data, such as reading configuration file, information of allocated memory in memory allocation, etc. Its source code is in the crypto/lhash directory.
The hash table data structure in openssl is defined in lhash.h as follows:
typedef struct lhash_node_st {
void *data;
struct lhash_node_st *next;
#ifndef OPENSSL_NO_HASH_COMP
unsigned long hash;
#endif
} LHASH_NODE;
This structure is a single linked list.
Where, data is used to store the data address,
Next is the next data address,
Hash calculates the value for the data hash.
typedef struct 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;
Among them,
b pointer array is used to store all data, and each value in the array is the head pointer of the data linked list;
comp is used to store the address of data comparison function;
Hash is used to store the address of the function for calculating the hash value;
num_nodes is the number of linked lists;
num_alloc_nodes the amount of space allocated for b.
The basic structure is shown in the following figure
_images/4_2.png
4.3 function description
-
LHASH *lh_TYPE_new(LHASH_HASH_FN_TYPE h, LHASH_COMP_FN_TYPE c)
Function: generate hash table
Source file: lhash.c
Description: input parameters
h is the hash function,
c is the comparison function.
Both functions are callback functions.
Because hash tables are used to store arbitrary data structures,
Data comparison and hash operation are required for hash table storage, query, deletion and other operations,
The hash table does not know how to compare user data, nor which key items need to be hashed in the user data structure
Therefore, the user must provide these two callback functions. -
void *lh_TYPE_delete(LHASH *lh, const void *data)
Source file: lhash.c
Function: delete a data in hash table
Description: data is a data structure pointer. -
void lh_TYPE_doall(LHASH *lh, LHASH_DOALL_FN_TYPE func)
Source file: lhash.c
Function: process all data in hash table
Description: func is a callback function provided externally. This function traverses all the data stored in the hash table, and each data is processed by func. -
void lh_TYPE_doall_arg(LHASH *lh, LHASH_DOALL_ARG_FN_TYPE func, void *arg)
Source file: lhash.c
Function: process all data in hash table
Description: this parameter is similar to lh_doall function, func is a callback function provided externally,
arg is the parameter passed to func function.
This function traverses all the data stored in the hash table, and each data is processed by func. -
void lh_TYPE_free(LHASH *lh)
Source file: lhash.c
Function: release hash table.
6)void *lh_TYPE_insert(LHASH *lh, void *data)
Source file: lhash.c
Function: add data to hash table.
Note: data is the pointer address of the data structure to be added.
7)void *lh_retrieve(LHASH *lh, const void *data)
Source file: lhash.c
Function: query data.
Note: query data from the hash table. Data is the address of the data structure,
Key items (corresponding to the hash function and comparison function provided by the user) must be provided in this data structure for query,
If the query is successful, the address of the data structure is returned; otherwise, NULL is returned.
For example, when the server queries the previously stored SESSION in the SSL handshake,
It needs to provide several key items:
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)
Source file: lh_stats.c
Function: output the data status under each linked list in the hash table to BIO.
9)void lh_node_stats(const LHASH *lh, FILE *fp)
Source file: lh_stats.c
Function: output the number of data under each linked list in the hash table to FILE.
Description: this function calls lh_node_stats_bio function.
10)void lh_node_usage_stats_bio(const LHASH *lh, BIO *out)
Source file: lh_stats.c
Function: output the usage status of hash table to BIO.
11)void lh_node_usage_stats(const LHASH *lh, FILE *fp)
Source file: lh_stats.c
Function: output the usage status of hash table to FILE
Description: this function calls lh_node_usage_stats_bio function
12)unsigned long lh_num_items(const LHASH *lh)
Source file: lhash. c
Function: get the number of elements in the hash table.
13)void lh_stats_bio(const LHASH *lh, BIO *out)
Source file: lh_stats.c
Function: output hash table statistics to BIO
14)void lh_stats(const LHASH *lh, FILE *fp)
Source file: lh_stats.c
Function: print statistics of hash table. This function calls lh_stats_bio.
15)unsigned long lh_strhash(const char *c)
Source file: lhash.c
Function: calculate text string to hash value.
DEFINE_LHASH_OF(Student);
IMPLEMENT_LHASH_DOALL_ARG(Student, int);
4.4 programming examples
#include <string.h>
#include <openssl/lhash.h>
typedef struct Student_st
{
char name[20];
int age;
char otherInfo[200];
}Student;
static int Student_cmp(const Student *a, const Student *b)
{
const char *namea = a->name;
const char *nameb = b->name;
return strcmp(namea,nameb);
}
/* Print each value*/
static void PrintValue(Student *a)
{
printf("\nname :%s\n",a->name);
printf("age :%d\n",a->age);
printf("otherInfo : %s\n",a->otherInfo);
}
static void PrintValue_arg(Student *a,int *b)
{
int flag = *b;
printf("\n User input parameters are:%d\n",flag);
printf("name :%s\n",a->name);
printf("age :%d\n",a->age);
printf("otherInfo : %s\n",a->otherInfo);
}
DEFINE_LHASH_OF(Student);
IMPLEMENT_LHASH_DOALL_ARG(Student, int);
int main()
{
int flag = 11;
Student s1 = {"zcp",28,"hu bei"},
s2 = {"forxy",28,"no info"},
s3 = {"skp",24,"student"},
s4 = {"zhao_zcp",28,"zcp's name"},
*s5;
Student *data;
LHASH_OF(Student) *h = lh_Student_new(NULL,Student_cmp);
if(h == NULL) {
printf("err.\n");
return -1;
}
data = &s1;
lh_Student_insert(h,data);
data = &s2;
lh_Student_insert(h,data);
data = &s3;
lh_Student_insert(h,data);
data = &s4;
lh_Student_insert(h,data);
/* Print*/
lh_Student_doall(h,PrintValue);
printf("\n\n");
lh_Student_doall_int(h,PrintValue_arg,&flag);
data = lh_Student_retrieve(h,(const void*)"skp");
if(data == NULL) {
printf("can not look up skp!\n");
lh_Student_free(h);
return -1;
}
s5 = data;
printf("\n\nstudent name :%s\n",s5->name);
printf("sutdent age : %d\n",s5->age);
printf("student otherinfo :%s\n",s5->otherInfo);
lh_Student_free(h);
//getchar();
return 0;
}