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
|
#include <assert.h>
#include <sys/time.h>
#include <stdio.h>
//#define INT_SET_PRIVATE
#ifdef INT_SET_PRIVATE
/* Make all hash functions private to this module for better
* performance. This may not be necessary depending on compiler
* optimizations. clang 4.2 -O3 benefits while -O4 figures it and get
* same speed with external linkage. */
#define HT_PRIVATE
#include "int_set.h"
#include "ptr_set.c"
#undef HT_PRIVATE
#else
/* Use external linkage. Link with ptr_set.c which int_set depends upon. */
#include "int_set.h"
#endif
struct timeval time_diff(struct timeval start, struct timeval end)
{
struct timeval temp;
if ((end.tv_usec-start.tv_usec)<0) {
temp.tv_sec = end.tv_sec-start.tv_sec-1;
temp.tv_usec = 1000000+end.tv_usec-start.tv_usec;
} else {
temp.tv_sec = end.tv_sec-start.tv_sec;
temp.tv_usec = end.tv_usec-start.tv_usec;
}
return temp;
}
double elapsed_ms(struct timeval td)
{
return (double)td.tv_sec * 1000 + (double)td.tv_usec / 1000;
}
void test_int_set()
{
int i, x;
const int N = 1000000;
//const int N = 1000;
int_set_t ht = {0};
int_set_t *S = &ht;
double ms, nsop, opms;
struct timeval t1, t2, td;
for (i = 1; i <= N; ++i) {
int_set_add(S, i);
assert(int_set_exists(S, i));
}
assert(int_set_count(S) == N);
for (i = 1; i <= N; ++i) {
assert(int_set_exists(S, i));
}
gettimeofday(&t1, 0);
for (x = 0, i = 1; i <= N; ++i) {
x += int_set_exists(S, i);
}
gettimeofday(&t2, 0);
td = time_diff(t1, t2);
ms = elapsed_ms(td);
nsop = ms * 1000000 / x;
opms = (double)x / ms;
printf("%d out of %d keys found in time %0.03f ms or %0.01f ns per op\n",
x, N, ms, nsop);
printf("ops / ms: %0.0f\n", opms);
for (i = 1; i <= N; ++i) {
assert(int_set_count(S) == N - i + 1);
assert(int_set_exists(S, i));
int_set_remove(S, i);
assert(!int_set_exists(S, i));
}
assert(int_set_count(S) == 0);
}
int main(int argc, char *argv[])
{
test_int_set();
return 0;
}
|