-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathhash_table.h
More file actions
218 lines (171 loc) · 5.06 KB
/
hash_table.h
File metadata and controls
218 lines (171 loc) · 5.06 KB
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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
/*
* Implements harsh table data structure
*/
// TODO: how to handle redundant key
// TODO: how about double linked list for hash list?
// data structure for hash table
// each key is mapped to a linked list
//hash node holds <key, value> pair
typedef struct hash_node {
DataType key;
DataType value;
struct hash_node* next;
}__attribute__((packed)) HashNode;
typedef struct hash_table {
int hashSize;
HashNode* htNodeHead; // point to node head for each list of ht entry
} HashTable;
typedef struct hash_list{
HashNode* listHead;
} HashList;
// create a hash node
HashNode* ht_CreateNode(DataType key, DataType value)
{
HashNode* node = malloc(sizeof(HashNode));
node-> key = key;
node-> value = value;
node-> next = NULL;
return node;
}
// create hash table given table size
void ht_Create(HashTable* hashTable, int hashSize)
{
int i;
HashNode* p = malloc(hashSize*sizeof(HashNode));
printf("HashTable allocated at %p \n", p);
printf("Size_HashNode %d = size_NodePtr %d + 2*size_Data %d \n",
sizeof(HashNode), sizeof(HashNode*), 2*sizeof(DataType) );
hashTable->hashSize = hashSize;
hashTable->htNodeHead = p; // node head for first list in HT
for(i = 0; i<hashSize; i++){
p = (HashNode*)(hashTable->htNodeHead+i);
p->next = NULL;
p->key = 0; // TODO: first node is always dummy now.
p->value = 0;
printf("Initializing node %d at %p \n", i, p);
}
}
// hash function: given key, find index
static unsigned int ht_HashFunction(HashTable* hashTable, DataType key)
{
unsigned int index = key % hashTable->hashSize;
return index;
}
// given a hash node, create hash list
static HashList* hashList_CreateList(HashNode* hashNode)
{
HashList* hashList = malloc(sizeof(HashList));
hashList->listHead = hashNode;
return hashList;
}
// get the last node of the hash list
static HashNode* hashList_GetTail(HashList* hashList)
{
HashNode* p = hashList->listHead;
while (p->next!=NULL){
p = p->next;
}
return p;
}
// insert value into tail of hash list
static void hashList_Add(HashList* hashList, DataType key, DataType value)
{
HashNode* newNode = ht_CreateNode(key, value);
HashNode* p = hashList_GetTail(hashList);
p->next = newNode;
}
// print the entire list
static void hashList_PrintList(HashList* list)
{
HashNode* p = list->listHead;
int i = 0;
while (p!=NULL){
printf("Node %d key: %d value: %d ", i, p->key, p->value);
printf("---Node %d address: %p \n", i, p);
p = p->next;
i++;
}
}
// insert into table: given <key, value>, insert into hash table.
void ht_Insert(HashTable* hashTable, DataType key, DataType value)
{
unsigned int index = ht_HashFunction(hashTable, key);
HashNode* p = (hashTable->htNodeHead+index);
// here we append new data directly to linked list created
HashList* hashList = hashList_CreateList(p);
hashList_Add(hashList, key, value);
printf("\nData with <key, val> <%d, %d> is inserted to %dth list. \n",
key, value, index);
hashList_PrintList(hashList);
}
// search for an element: given key, return pt to hash node
HashNode* ht_Search(HashTable* hashTable, DataType key)
{
unsigned int index = ht_HashFunction(hashTable, key);
HashNode* p = (hashTable->htNodeHead+index);
HashNode* result = NULL;
p = p->next;
while(p){
if(p->key==key) {
result = p;
break;
}
p = p->next;
}
if(result)
printf("Data with key %d is found with value %d. \n",
key, result->value);
else printf("Key %d not found. \n", key);
return result;
}
// delete tail node of list corresponding to key
static void hashList_DeleteTail(HashTable* hashTable, DataType key)
{
unsigned int index = ht_HashFunction(hashTable, key);
printf("Deleting tail node. \n");
HashNode* prev = (hashTable->htNodeHead+index);
HashNode* p = prev->next;
while(p->next){
prev = p;
p = p->next;
}
prev->next = NULL;
free(p);
}
// Delete a node given its key: return TRUE if node found and deleted
int ht_Delete(HashTable* hashTable, DataType key)
{
HashNode* p;
HashNode* q;
q = ht_Search(hashTable, key);// note that q can never be the dummy list head
if(q) {
p = q->next;
if(p){
// not tail node
q->key = p->key;
q->value = p->value;
q->next = p->next;
free(p);
} else{
// tail node of list
hashList_DeleteTail(hashTable, key);
}
printf("Node with key %d deleted.\n", key);
return 1;
} else {
printf("Key %d not found. \n", key);
return 0;
}
}
// print entire hash table
void ht_PrintTable(HashTable* hashTable, DataType key)
{
unsigned int index = ht_HashFunction(hashTable, key);
HashNode* p = (hashTable->htNodeHead+index);
printf("List correspoding to key %d", key);
while(p){
printf("-<%d, %d>-", p->key, p->value);
p = p->next;
}
printf("\n");
}