1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
|
#ifndef __HASHMAP__
#define __HASHMAP__
#include <openssl/sha.h>
#include <string.h>
#include "circulardoublelinkedlist.h"
#include "util.h"
struct ht_item {
char *hash;
void *data;
unsigned int data_length;
struct list list;
};
struct hashtable {
struct ht_item **begin;
unsigned int length;
unsigned int hash_length;
void (*hash_function)(void *data, unsigned int data_length, char *res);
};
int __ht_init(struct hashtable *ht, unsigned int number_elem,
unsigned int hash_length, void (*func)(void *data,
unsigned int data_length, char *res))
{
ht->begin = xmalloc(sizeof(struct ht_item)*number_elem);
ht->length = number_elem;
ht->hash_length = hash_length;
ht->hash_function = func;
}
void compute_hash_sha1(void *data, unsigned int data_length, char *res)
{
SHA_CTX sha1;
SHA1_Init(&sha1);
SHA1_Update(&sha1, data, data_length);
SHA1_Final(res, &sha1);
}
int ht_init_sha1(struct hashtable *ht)
{
__ht_init(ht, 300, 20, compute_hash_sha1);
}
void *ht_is_in_list(struct list *list, char *hash, int hash_length)
{
struct list *head, *iter;
struct ht_item *res = NULL;
head = list;
res = CONTAINER_OF(head, struct ht_item, list);
if(memcmp(res->hash, hash, hash_length) == 0)
return res->data;
LIST_FOR_EACH(iter,head) {
res = CONTAINER_OF(iter, struct ht_item, list);
if(memcmp(res->hash, hash, hash_length) == 0)
return res->data;
}
return NULL;
}
void ht_add(struct hashtable *ht, void *data, unsigned int data_length,
void *key, unsigned int key_length)
{
unsigned long index;
struct ht_item *new_elem = xmalloc(sizeof(struct ht_item));
new_elem->hash = xmalloc(ht->hash_length);
new_elem->data = xmalloc(data_length);
memcpy(new_elem->data, data, data_length);
new_elem->data_length = data_length;
LIST_INIT(&new_elem->list);
ht->hash_function(key, key_length, new_elem->hash);
memcpy(&index, new_elem->hash, sizeof(unsigned long));
index = index % ht->length;
if(ht->begin[index] == NULL) {
ht->begin[index] = new_elem;
return;
}
if(ht_is_in_list(&(ht->begin[index]->list), new_elem->hash,
ht->hash_length) == NULL) {
list_insert_after(&(ht->begin[index]->list), &new_elem->list);
printf("kollision\n");
return;
}
}
void *ht_get(struct hashtable *ht, void *key, unsigned int key_length)
{
char *hash = xmalloc(ht->hash_length);
unsigned long index;
ht->hash_function(key, key_length, hash);
memcpy(&index, hash, sizeof(unsigned long));
index = index % ht->length;
return ht_is_in_list(&(ht->begin[index]->list), hash, ht->hash_length);
}
#endif
|
