-
Notifications
You must be signed in to change notification settings - Fork 1
/
hashtable.c
132 lines (119 loc) · 3.18 KB
/
hashtable.c
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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
/*****************************************************
* Hash Table Implementation *
* Author: Michael P. Nitowski <mpnitowski@gmail.com> *
* License: MIT License *
******************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "hash.h"
#include "strdup.h"
#include "hashtable.h"
static HASHTABLE hashtable_fill(size_t size, HASHTABLE ht)
{
int i;
for(i = 0; i < size; i++) {
HASHTABLE_ENTRY entry;
entry.value = "";
entry.key = "";
entry.hash = -1;
ht.table[i] = entry;
}
return ht;
}
HASHTABLE hashtable_init(size_t size)
{
HASHTABLE ht;
ht.size = size;
ht.count = (int*)malloc(sizeof(int));
*(ht.count) = 0;
ht.table = (HASHTABLE_ENTRY*)malloc(sizeof(HASHTABLE_ENTRY) * size);
return hashtable_fill(size, ht);
}
unsigned long hashtable_hash(char *str)
{
return hash((unsigned char*)str);
}
static int hashtable_probe(int ht_key, char *key, HASHTABLE ht)
{
if(strcmp(ht.table[ht_key].key, "") && strcmp(ht.table[ht_key].key, key)) {
ht_key = (ht_key + 1) % ht.size;
while(strcmp(ht.table[ht_key].key, "")
&& strcmp(ht.table[ht_key].key, key))
ht_key = (ht_key + 1) % ht.size;
}
return ht_key;
}
HASHTABLE_ENTRY hashtable_get(char *key, HASHTABLE ht)
{
unsigned long hash;
int ht_key;
hash = hashtable_hash(key);
ht_key = hashtable_probe(hash % ht.size, key, ht);
return ht.table[ht_key];
}
bool hashtable_exists(char *key, HASHTABLE ht)
{
return hashtable_get(key, ht).hash != -1;
}
bool hashtable_put(char *key, char *value, HASHTABLE ht)
{
if(*(ht.count) >= ht.size - 1) return 0;
HASHTABLE_ENTRY entry;
unsigned long hash;
int ht_key;
hash = hashtable_hash(key);
entry.key = strdup(key);
entry.value = strdup(value);
ht_key = hashtable_probe(hash % ht.size, key, ht);
entry.hash = ht_key;
if(ht.table[ht_key].hash == -1) *(ht.count) = *(ht.count) + 1;
ht.table[ht_key] = entry;
return 1;
}
char *hashtable_getv(char *key, HASHTABLE ht)
{
return hashtable_get(key, ht).value;
}
bool hashtable_remove(char *key, HASHTABLE ht)
{
HASHTABLE_ENTRY entry = hashtable_get(key, ht);
if(entry.hash == -1) return 0;
int hash = entry.hash;
entry.hash = -1;
entry.value = "";
entry.key = "";
ht.table[hash] = entry;
return 1;
}
void hashtable_deinit(HASHTABLE *ht)
{
free(ht->count);
ht->count = NULL;
free(ht->table);
ht->table = NULL;
}
void hashtable_print(HASHTABLE ht, bool all)
{
int i;
for(i = 0; i < ht.size; i++) {
HASHTABLE_ENTRY entry = ht.table[i];
if(all < 1) {
if(entry.hash == -1) continue;
}
printf("%d : %s : %s\n", entry.hash, entry.key, entry.value);
}
}
void hashtable_resize(size_t size, HASHTABLE *ht)
{
HASHTABLE new = hashtable_init(size);
int i;
for(i = 0; i < ht->size; i++) {
HASHTABLE_ENTRY entry = ht->table[i];
if(entry.hash == -1) continue;
hashtable_put(entry.key, entry.value, new);
}
hashtable_deinit(ht);
*ht = new;
}