-
Notifications
You must be signed in to change notification settings - Fork 0
/
HashTable.cpp
140 lines (108 loc) · 2.22 KB
/
HashTable.cpp
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
#include<iostream>
using namespace std;
void mstrcpy(char *dst, const char *src) {
int pos = 0;
while (dst[pos] = src[pos]) {
pos++;
}
}
int mstrcmp(const char *str1, const char* str2) {
int pos = 0;
while (str1[pos]) {
if (str1[pos] != str2[pos])
break;
pos++;
}
return str1[pos] - str2[pos];
}
#define MAX_TABLE 100007
#define MAX_DATA 50000
struct Table {
char name[20];
int id;
};
struct Node {
Node *prev;
Node *next;
Table *table;
};
Node hashTable[MAX_TABLE];
Node arrNode[MAX_DATA];
Table arrTable[MAX_DATA];
int tCnt, nCnt;
Table *newTable() {
Table *table = &arrTable[tCnt++];
return table;
}
Node *newNode() {
Node *node = &arrNode[nCnt++];
node->prev = 0;
node->next = 0;
node->table = 0;
return node;
}
unsigned long myhash(const char *str)
{
unsigned long hash = 5381;
int c;
while (c = *str++)
{
hash = (((hash << 5) + hash) + c) % MAX_TABLE;
}
return hash % MAX_TABLE;
}
void initMemory() {
nCnt = 0, tCnt = 0;
for (register int i = 0; i < MAX_TABLE; i++) {
hashTable[i].next = 0;
hashTable[i].prev = 0;
hashTable[i].table = 0;
}
}
void addHashTable(const char *str, const int id) {
Table *table = newTable();
table->id = id;
mstrcpy(table->name, str);
Node *node = newNode();
node->table = table;
int hashKey = myhash(str);
Node *head = hashTable[hashKey].next;
node->prev = &hashTable[hashKey];
node->next = head;
if (head != 0) head->prev = node;
hashTable[hashKey].next = node;
}
int modifyHashTable(const char *str, const int fixID) {
int hashKey = myhash(str);
Node *node = hashTable[hashKey].next;
while (node) {
Node *next = node->next;
if (!mstrcmp(str, node->table->name)) {
node->table->id = fixID;
return 1;
}
node = next;
}
return 0;
}
void deleteHashTable(const char *str) {
int hashKey = myhash(str);
Node *node = hashTable[hashKey].next;
while (node) {
Node *next = node->next;
if (!mstrcmp(str, node->table->name)) {
// deleteNode
if (node->next != 0) node->next->prev = node->prev;
if (node->prev != 0) node->prev->next = node->next;
}
node = next;
}
}
int main() {
addHashTable("gogo", 1);
addHashTable("gogo", 2);
addHashTable("abc", 10);
modifyHashTable("abc", 4);
deleteHashTable("gogo");
return 0;
}