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
|
/*
* Nsock regression test suite
* Same license as nmap -- see https://nmap.org/book/man-legal.html
*/
#include "test-common.h"
#include "../src/gh_heap.h"
#include <stdint.h>
#include <time.h>
#define HEAP_COUNT 3
struct testitem {
int val;
gh_hnode_t node;
};
static int hnode_int_cmp(gh_hnode_t *n1, gh_hnode_t *n2) {
struct testitem *a;
struct testitem *b;
a = container_of(n1, struct testitem, node);
b = container_of(n2, struct testitem, node);
return (a->val < b->val);
}
static gh_hnode_t *mknode(int val) {
struct testitem *item;
item = calloc(1, sizeof(struct testitem));
assert(item != NULL);
item->val = val;
gh_hnode_invalidate(&item->node);
return &item->node;
}
static int node2int(gh_hnode_t *hnode) {
struct testitem *item;
item = container_of(hnode, struct testitem, node);
return item->val;
}
static int ghheap_ordering(void *tdata) {
gh_heap_t heap;
int i, n, k;
gh_heap_init(&heap, hnode_int_cmp);
for (i = 25000; i < 50000; i++)
gh_heap_push(&heap, mknode(i));
for (i = 24999; i >= 0; i--)
gh_heap_push(&heap, mknode(i));
for (i = 25000; i < 50000; i++)
gh_heap_push(&heap, mknode(i));
n = -1;
do {
gh_hnode_t *current;
current = gh_heap_pop(&heap);
assert(!gh_hnode_is_valid(current));
k = node2int(current);
if (k < n)
return -EINVAL;
n = k;
free(container_of(current, struct testitem, node));
} while (gh_heap_count(&heap) > 0);
gh_heap_free(&heap);
return 0;
}
static int ghheap_stress(void *tdata) {
gh_heap_t heaps[HEAP_COUNT];
int i, num;
for (i = 0; i < HEAP_COUNT; i++)
gh_heap_init(&heaps[i], hnode_int_cmp);
for (num = 25000; num < 50000; num++) {
for (i = 0; i < HEAP_COUNT; i++) {
gh_heap_push(&heaps[i], mknode(num));
}
}
for (num = 24999; num >= 0; num--) {
for (i = 0; i < HEAP_COUNT; i++) {
gh_heap_push(&heaps[i], mknode(num));
}
}
for (num = 0; num < 50000; num++) {
for (i = 0; i < HEAP_COUNT; i++) {
int r_min, r_pop;
gh_hnode_t *hnode;
r_min = node2int(gh_heap_min(&heaps[i]));
hnode = gh_heap_pop(&heaps[i]);
r_pop = node2int(hnode);
if (r_min != r_pop) {
fprintf(stderr, "Bogus min/pop return values (%d != %d)\n", r_min, r_pop);
return -EINVAL;
}
if (r_min != num) {
fprintf(stderr, "Bogus return value %d when expected %d\n", r_min, num);
return -EINVAL;
}
free(container_of(hnode, struct testitem, node));
}
}
for (i = 0; i < HEAP_COUNT; i++) {
void *ret;
ret = gh_heap_pop(&heaps[i]);
if (ret != NULL) {
fprintf(stderr, "Ret is bogus for heap %d\n", i);
return -EINVAL;
}
}
for (i = 0; i < HEAP_COUNT; i++)
gh_heap_free(&heaps[i]);
return 0;
}
const struct test_case TestGHHeaps = {
.t_name = "test nsock internal ghheaps",
.t_setup = NULL,
.t_run = ghheap_stress,
.t_teardown = NULL
};
const struct test_case TestHeapOrdering = {
.t_name = "test heaps conditions",
.t_setup = NULL,
.t_run = ghheap_ordering,
.t_teardown = NULL
};
|
