1 #include <string.h>
2 #include "simpleht.h"
3
4 typedef struct _Sht_Slot{
5 int32_t Next;
6 } Sht_Slot;
7
8 static const Sht_Slot EmptySlot = {-1};
9
SimpleHT_Init(SimpleHT * ht,int DataLength,size_t MaxLoadFactor,int (* HashFunction)(const char *,int))10 int SimpleHT_Init(SimpleHT *ht, int DataLength, size_t MaxLoadFactor, int (*HashFunction)(const char *, int))
11 {
12 int loop;
13
14 if( Array_Init(&(ht->Slots), sizeof(Sht_Slot), 7, FALSE, NULL) != 0 )
15 {
16 return -1;
17 }
18
19 for( loop = 0; loop != 7; ++loop )
20 {
21 Array_PushBack(&(ht->Slots), &EmptySlot, NULL);
22 }
23
24 if( Array_Init(&(ht->Nodes), sizeof(Sht_NodeHead) + DataLength, 0, FALSE, NULL) != 0 )
25 {
26 return -2;
27 }
28
29 ht->MaxLoadFactor = MaxLoadFactor;
30 ht->LeftSpace = 7 * MaxLoadFactor;
31 ht->HashFunction = HashFunction;
32
33 return 0;
34 }
35
SimpleHT_RemoveFromSlot(SimpleHT * ht,int Slot,int * NodeSubscript)36 static Sht_NodeHead *SimpleHT_RemoveFromSlot(SimpleHT *ht, int Slot, int *NodeSubscript)
37 {
38 int NumberOfSlots_New = Array_GetUsed(&(ht->Slots));
39
40 Sht_Slot *TheSlot;
41 Sht_NodeHead *FirstNode = NULL;
42 Sht_NodeHead *SecondNode = NULL;
43
44 TheSlot = Array_GetBySubscript(&(ht->Slots), Slot);
45 if( TheSlot == NULL )
46 {
47 return NULL;
48 }
49
50 FirstNode = Array_GetBySubscript(&(ht->Nodes), TheSlot->Next);
51 if( FirstNode == NULL )
52 {
53 return NULL;
54 }
55
56 if( FirstNode->HashValue % NumberOfSlots_New != Slot )
57 {
58 *NodeSubscript = TheSlot->Next;
59 TheSlot->Next = FirstNode->Next;
60 return FirstNode;
61 } else {
62 *NodeSubscript = FirstNode->Next;
63 SecondNode = Array_GetBySubscript(&(ht->Nodes), FirstNode->Next);
64 while( SecondNode != NULL )
65 {
66 if( SecondNode->HashValue % NumberOfSlots_New != Slot )
67 {
68 FirstNode->Next = SecondNode->Next;
69 return SecondNode;
70 }
71
72 FirstNode = SecondNode;
73 *NodeSubscript = SecondNode->Next;
74 SecondNode = Array_GetBySubscript(&(ht->Nodes), SecondNode->Next);
75 }
76 return NULL;
77 }
78 }
79
SimpleHT_AddToSlot(SimpleHT * ht,Sht_NodeHead * Node,int NodeSubscript)80 static int SimpleHT_AddToSlot(SimpleHT *ht, Sht_NodeHead *Node, int NodeSubscript)
81 {
82 int NumberOfSlots = Array_GetUsed(&(ht->Slots));
83 Sht_Slot *TheSlot;
84
85 TheSlot = Array_GetBySubscript(&(ht->Slots), Node->HashValue % NumberOfSlots);
86 if( TheSlot == NULL )
87 {
88 return -1;
89 }
90
91 Node->Next = TheSlot->Next;
92 TheSlot->Next = NodeSubscript;
93
94 return 0;
95 }
96
SimpleHT_Expand(SimpleHT * ht)97 static int SimpleHT_Expand(SimpleHT *ht)
98 {
99 int NumberOfSlots_Old = Array_GetUsed(&(ht->Slots));
100 Sht_NodeHead *Itr = NULL;
101 int ItrSubscript = 0;
102 int loop;
103
104 for( loop = 0; loop < NumberOfSlots_Old; ++loop )
105 {
106 if( Array_PushBack(&(ht->Slots), &EmptySlot, NULL) < 0 )
107 {
108 return -1;
109 }
110 }
111
112 for( loop = 0; loop < NumberOfSlots_Old; ++loop )
113 {
114 Itr = SimpleHT_RemoveFromSlot(ht, loop, &ItrSubscript);
115 while( Itr != NULL )
116 {
117 SimpleHT_AddToSlot(ht, Itr, ItrSubscript);
118 Itr = SimpleHT_RemoveFromSlot(ht, loop, &ItrSubscript);
119 }
120 }
121
122 return 0;
123 }
124
SimpleHT_Add(SimpleHT * ht,const char * Key,int KeyLength,const char * Data,int * HashValue)125 const char *SimpleHT_Add(SimpleHT *ht, const char *Key, int KeyLength, const char *Data, int *HashValue)
126 {
127 Sht_NodeHead *New;
128 int NewSubscript;
129
130 if( ht->LeftSpace == 0 )
131 {
132 int NumberOfSlots_Old = Array_GetUsed(&(ht->Slots));
133
134 if( SimpleHT_Expand(ht) != 0 )
135 {
136 return NULL;
137 }
138
139 ht->LeftSpace = NumberOfSlots_Old * ht->MaxLoadFactor;
140 }
141
142 NewSubscript = Array_PushBack(&(ht->Nodes), NULL, NULL);
143 if( NewSubscript < 0 )
144 {
145 return NULL;
146 }
147
148 New = Array_GetBySubscript(&(ht->Nodes), NewSubscript);
149
150 if( HashValue == NULL )
151 {
152 New->HashValue = (ht->HashFunction)(Key, KeyLength);
153 } else {
154 New->HashValue = *HashValue;
155 }
156
157 memcpy(New + 1, Data, ht->Nodes.DataLength - sizeof(Sht_NodeHead));
158
159 SimpleHT_AddToSlot(ht, New, NewSubscript);
160
161 --(ht->LeftSpace);
162
163 return (const char *)(New + 1);
164 }
165
SimpleHT_Find(SimpleHT * ht,const char * Key,int KeyLength,int * HashValue,const char * Start)166 const char *SimpleHT_Find(SimpleHT *ht, const char *Key, int KeyLength, int *HashValue, const char *Start)
167 {
168 int NumberOfSlots = Array_GetUsed(&(ht->Slots));
169 int SlotNumber;
170 Sht_Slot *TheSlot;
171 Sht_NodeHead *Node;
172
173 if( NumberOfSlots <= 0 )
174 {
175 return NULL;
176 }
177
178 if( Start != NULL )
179 {
180 Node = Array_GetBySubscript(&(ht->Nodes), (((Sht_NodeHead *)Start) - 1)->Next);
181 } else {
182 if( HashValue == NULL )
183 {
184 SlotNumber = (ht->HashFunction)(Key, KeyLength) % NumberOfSlots;
185 } else {
186 SlotNumber = (*HashValue) % NumberOfSlots;
187 }
188
189 TheSlot = Array_GetBySubscript(&(ht->Slots), SlotNumber);
190 if( TheSlot == NULL )
191 {
192 return NULL;
193 }
194
195 Node = Array_GetBySubscript(&(ht->Nodes), TheSlot->Next);
196 }
197
198 if( Node == NULL )
199 {
200 return NULL;
201 }
202
203 return (const char *)(Node + 1);
204
205 }
206
SimpleHT_Enum(SimpleHT * ht,int32_t * Start)207 const char *SimpleHT_Enum(SimpleHT *ht, int32_t *Start)
208 {
209 Array *Nodes = &(ht->Nodes);
210 Sht_NodeHead *Node;
211
212 Node = Array_GetBySubscript(Nodes, *Start);
213
214 if( Node != NULL )
215 {
216 ++(*Start);
217 return (const char *)(Node + 1);
218 } else {
219 return NULL;
220 }
221 }
222
SimpleHT_Free(SimpleHT * ht)223 void SimpleHT_Free(SimpleHT *ht)
224 {
225 Array_Free(&(ht->Slots));
226 Array_Free(&(ht->Nodes));
227 }
228