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
|
/* Copyright (C) CZ.NIC, z.s.p.o. and contributors
* SPDX-License-Identifier: GPL-2.0-or-later
* For more information, see <https://www.knot-dns.cz/>
*/
#include <string.h>
#include <tap/basic.h>
#include "libknot/dynarray.h"
#define test_capacity 5
// minimum 3
typedef struct {
int x;
int x2;
} quadrate_t;
knot_dynarray_declare(q, quadrate_t, DYNARRAY_VISIBILITY_STATIC, test_capacity);
knot_dynarray_define(q, quadrate_t, DYNARRAY_VISIBILITY_STATIC);
static q_dynarray_t q_fill(size_t howmany)
{
quadrate_t q = { 0 };
q_dynarray_t qd = { 0 };
for (size_t i = 0; i < howmany; i++) {
q.x2 = q.x * q.x;
q_dynarray_add(&qd, &q);
q.x++;
}
return qd;
}
static void check_arr(q_dynarray_t *q, size_t count, size_t index, const char *msg)
{
quadrate_t *arr = q->arr(q);
ok(arr[index].x == index && arr[index].x2 == index * index,
"%s check: index %zu", msg, index);
size_t i = 0;
knot_dynarray_foreach(q, quadrate_t, p, *q) {
ok(p->x == i && p->x2 == i * i, "%s foreach: index %zu", msg, i);
i++;
}
ok(i == count, "%s foreach: whole array", msg);
}
static size_t q_set_dups(q_dynarray_t *q, double dup_percentage, const quadrate_t *dupval)
{
size_t dup_cnt = 0;
int threshold = (int)(dup_percentage / 100 * ((double)RAND_MAX + 1.0));
knot_dynarray_foreach(q, quadrate_t, item, *q) {
if (rand() < threshold && q_dynarray_memb_cmp(item, dupval) != 0) {
*item = *dupval;
dup_cnt++;
}
}
return dup_cnt;
}
static void check_dups(q_dynarray_t *q, const quadrate_t *dupval,
const size_t expected, const char *msg)
{
size_t cnt = 0;
knot_dynarray_foreach(q, quadrate_t, item, *q) {
if (q_dynarray_memb_cmp(item, dupval) == 0) {
cnt++;
}
}
ok(cnt == expected, "duplicate items: %s", msg);
}
int main(int argc, char *argv[])
{
plan_lazy();
// first fill
q_dynarray_t q = q_fill(test_capacity - 1);
check_arr(&q, test_capacity - 1, test_capacity - 3, "initial");
q_dynarray_free(&q);
// second fill
q = q_fill(test_capacity + 3);
check_arr(&q, test_capacity + 3, test_capacity + 1, "second");
q_dynarray_free(&q);
// third fill
q = q_fill(test_capacity * 5);
check_arr(&q, test_capacity * 5, test_capacity * 4, "third");
q_dynarray_free(&q);
// duplicate items removal test
q = q_fill(test_capacity * 10);
quadrate_t dup_item = { .x = 0, .x2 = 0 }; // matches the first item
size_t dups = q_set_dups(&q, 50, &dup_item);
ok(q.size == test_capacity * 10, "duplicate items: created");
check_dups(&q, &dup_item, dups + 1, "created all");
q_dynarray_remove(&q, &dup_item);
ok(q.size == test_capacity * 10 - dups - 1, "duplicate items: removed");
check_dups(&q, &dup_item, 0, "removed all");
q_dynarray_free(&q);
// binary search removal test
q = q_fill(test_capacity * 10);
for (int i = 0; i < test_capacity * 10; i++) {
quadrate_t qu = { i, i * i };
if ((qu.x % 2) == 0) {
q_dynarray_remove(&q, &qu);
}
}
q_dynarray_sort(&q);
for (int i = 0; i < test_capacity * 10; i++) {
quadrate_t qu = { i, i * i };
int present = (q_dynarray_bsearch(&q, &qu) != NULL ? 1 : 0);
ok(present == (i % 2), "presence in sorted array %d", i);
}
q_dynarray_free(&q);
return 0;
}
|
