-
Notifications
You must be signed in to change notification settings - Fork 0
/
tests.c
367 lines (321 loc) · 9.59 KB
/
tests.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
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
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
/*
* CS 261 Data Structures
* Assignment 5
*/
#include "CuTest.h"
#include "hashMap.h"
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <string.h>
// --- Test Helpers ---
typedef struct HistLink HistLink;
typedef struct Histogram Histogram;
struct HistLink
{
char* key;
int count;
HistLink* next;
};
struct Histogram
{
HistLink* head;
int size;
};
void histInit(Histogram* hist)
{
hist->head = NULL;
hist->size = 0;
}
void histCleanUp(Histogram* hist)
{
HistLink* link = hist->head;
while (link != NULL)
{
HistLink* next = link->next;
free(link);
link = next;
}
}
void histAdd(Histogram* hist, char* key)
{
HistLink* link = hist->head;
while (link != NULL)
{
if (strcmp(key, link->key) == 0 )
{
link->count++;
return;
}
link = link->next;
}
link = malloc(sizeof(HistLink));
link->key = key;
link->count = 1;
link->next = hist->head;
hist->head = link;
hist->size++;
}
/**
* Counts the number of times each key appears in the table.
* @param hist
* @param map
*/
void histFromTable(Histogram* hist, HashMap* map)
{
histInit(hist);
for (int i = 0; i < map->capacity; i++)
{
HashLink* link = map->table[i];
while (link != NULL)
{
histAdd(hist, link->key);
link = link->next;
}
}
}
/**
* Asserts that each key is unique (count is 1 for each key).
* @param test
* @param hist
*/
void assertHistCounts(CuTest* test, Histogram* hist)
{
HistLink* link = hist->head;
while (link != NULL)
{
CuAssertIntEquals(test, 1, link->count);
link = link->next;
}
}
// --- Hash Map tests ---
/*
* Test cases:
* - At most one link in each bucket under threshold.
* - At most one link in each bucket over threshold.
* - Multiple links in some buckets under threshold.
* - Multiple links in some buckets over threshold.
* - Multiple links in some buckets over threshold with duplicates.
*/
/**
* Tests all hash map functions after adding and removing all of the given keys
* and values.
* @param test
* @param links The key-value pairs to be added and removed.
* @param notKeys Some keys not in the table to test contains and get.
* @param numLinks The number of key-value pairs to be added and removed.
* @param numNotKeys The number of keys not in the table.
* @param numBuckets The initial number of buckets (capacity) in the table.
*/
void testCase(CuTest* test, HashLink* links, const char** notKeys, int numLinks,
int numNotKeys, int numBuckets)
{
HashMap* map = hashMapNew(numBuckets);
Histogram hist;
// Add links
for (int i = 0; i < numLinks; i++)
{
hashMapPut(map, links[i].key, links[i].value);
}
// Print table
printf("\nAfter adding all key-value pairs:");
hashMapPrint(map);
// Check size
CuAssertIntEquals(test, numLinks, hashMapSize(map));
// Check capacity
CuAssertIntEquals(test, map->capacity, hashMapCapacity(map));
// Check empty buckets
int sum = 0;
for (int i = 0; i < map->capacity; i++)
{
if (map->table[i] == NULL)
{
sum++;
}
}
CuAssertIntEquals(test, sum, hashMapEmptyBuckets(map));
// Check table load
CuAssertIntEquals(test, (float)numLinks / map->capacity, hashMapTableLoad(map));
// Check contains and get on valid keys.
for (int i = 0; i < numLinks; i++)
{
CuAssertIntEquals(test, 1, hashMapContainsKey(map, links[i].key));
int* value = hashMapGet(map, links[i].key);
CuAssertPtrNotNull(test, value);
CuAssertIntEquals(test, links[i].value, *value);
}
// Check contains and get on invalid keys.
for (int i = 0; i < numNotKeys; i++)
{
CuAssertIntEquals(test, 0, hashMapContainsKey(map, notKeys[i]));
CuAssertPtrEquals(test, NULL, hashMapGet(map, notKeys[i]));
}
// Check that all links are present and have a unique key.
histFromTable(&hist, map);
CuAssertIntEquals(test, numLinks, hist.size);
assertHistCounts(test, &hist);
histCleanUp(&hist);
// Remove keys
for (int i = 0; i < numLinks; i++)
{
hashMapRemove(map, links[i].key);
}
// Print table
printf("\nAfter removing all key-value pairs:");
hashMapPrint(map);
// Check size
CuAssertIntEquals(test, 0, hashMapSize(map));
// Check capacity
CuAssertIntEquals(test, map->capacity, hashMapCapacity(map));
// Check empty buckets
CuAssertIntEquals(test, map->capacity, hashMapEmptyBuckets(map));
// Check table load
CuAssertIntEquals(test, 0, hashMapTableLoad(map));
// Check contains and get on valid keys.
for (int i = 0; i < numLinks; i++)
{
CuAssertIntEquals(test, 0, hashMapContainsKey(map, links[i].key));
CuAssertPtrEquals(test, NULL, hashMapGet(map, links[i].key));
}
// Check contains and get on invalid keys.
for (int i = 0; i < numNotKeys; i++)
{
CuAssertIntEquals(test, 0, hashMapContainsKey(map, notKeys[i]));
CuAssertPtrEquals(test, NULL, hashMapGet(map, notKeys[i]));
}
// Check that there are no links in the table.
histFromTable(&hist, map);
CuAssertIntEquals(test, 0, hist.size);
assertHistCounts(test, &hist);
histCleanUp(&hist);
hashMapDelete(map);
}
/**
* Tests hash map functions for a table with no more than one link
* in each bucket and without hitting the table load threshold.
* @param test
*/
void testSingleUnder(CuTest* test)
{
printf("\n--- Testing single-link chains under threshold ---\n");
HashLink links[] = {
{ .key = "a", .value = 0, .next = NULL },
{ .key = "c", .value = 1, .next = NULL },
{ .key = "d", .value = 2, .next = NULL },
{ .key = "f", .value = 3, .next = NULL },
{ .key = "g", .value = 4, .next = NULL }
};
const char* notKeys[] = { "b", "e", "h" };
testCase(test, links, notKeys, 5, 3, 10);
}
/**
* Tests hash map functions for a table with no more than one link
* in each bucket while hitting the table load threshold.
* @param test
*/
void testSingleOver(CuTest* test)
{
printf("\n--- Testing single-link chains over threshold ---\n");
HashLink links[] = {
{ .key = "a", .value = 0, .next = NULL },
{ .key = "c", .value = 1, .next = NULL },
{ .key = "d", .value = 2, .next = NULL },
{ .key = "f", .value = 3, .next = NULL },
{ .key = "g", .value = 4, .next = NULL }
};
const char* notKeys[] = { "b", "e", "h" };
testCase(test, links, notKeys, 5, 3, 1);
}
/**
* Tests hash map functions for a table with 2+ links in some buckets without
* hitting the table load threshold.
* @param test
*/
void testMultipleUnder(CuTest* test)
{
printf("\n--- Testing multiple-link chains under threshold ---\n");
HashLink links[] = {
{ .key = "ab", .value = 0, .next = NULL },
{ .key = "c", .value = 1, .next = NULL },
{ .key = "ba", .value = 2, .next = NULL },
{ .key = "f", .value = 3, .next = NULL },
{ .key = "gh", .value = 4, .next = NULL }
};
const char* notKeys[] = { "b", "e", "hg" };
testCase(test, links, notKeys, 5, 3, 10);
}
/**
* Tests hash map functions for a table with 2+ links in some buckets while
* hitting the table load threshold.
* @param test
*/
void testMultipleOver(CuTest* test)
{
printf("\n--- Testing multiple-link chains over threshold ---\n");
HashLink links[] = {
{ .key = "ab", .value = 0, .next = NULL },
{ .key = "c", .value = 1, .next = NULL },
{ .key = "ba", .value = 2, .next = NULL },
{ .key = "f", .value = 3, .next = NULL },
{ .key = "gh", .value = 4, .next = NULL }
};
const char* notKeys[] = { "b", "e", "hg" };
testCase(test, links, notKeys, 5, 3, 1);
}
/**
* Tests that values are updated when inserting with a key already in the table.
* Also tests that keys remain unique after insertion (no duplicate links).
* @param test
*/
void testValueUpdate(CuTest* test)
{
int numLinks = 5;
printf("\n--- Testing value updates ---\n");
HashLink links[] = {
{ .key = "ab", .value = 0, .next = NULL },
{ .key = "c", .value = 1, .next = NULL },
{ .key = "ba", .value = 2, .next = NULL },
{ .key = "ab", .value = 3, .next = NULL },
{ .key = "gh", .value = 4, .next = NULL }
};
HashMap* map = hashMapNew(1);
// Add links
for (int i = 0; i < numLinks; i++)
{
hashMapPut(map, links[i].key, links[i].value);
}
// Print table
printf("\nAfter adding all key-value pairs:");
hashMapPrint(map);
int* value = hashMapGet(map, "ab");
CuAssertPtrNotNull(test, value);
CuAssertIntEquals(test, 3, *value);
Histogram hist;
histFromTable(&hist, map);
CuAssertIntEquals(test, numLinks - 1, hist.size);
assertHistCounts(test, &hist);
histCleanUp(&hist);
hashMapDelete(map);
}
// --- Test Suite ---
void addAllTests(CuSuite* suite)
{
SUITE_ADD_TEST(suite, testSingleUnder);
SUITE_ADD_TEST(suite, testSingleOver);
SUITE_ADD_TEST(suite, testMultipleUnder);
SUITE_ADD_TEST(suite, testMultipleOver);
SUITE_ADD_TEST(suite, testValueUpdate);
}
int main()
{
CuSuite* suite = CuSuiteNew();
addAllTests(suite);
CuSuiteRun(suite);
CuString* output = CuStringNew();
CuSuiteSummary(suite, output);
CuSuiteDetails(suite, output);
printf("\n%s\n", output->buffer);
CuStringDelete(output);
CuSuiteDelete(suite);
return 0;
}