test_attq.c revision 9a690580 
1/* Copyright (c) 2017 - 2020 LiteSpeed Technologies Inc.  See LICENSE. */
2#include <assert.h>
3#include <stdlib.h>
4#include <sys/queue.h>
5
6#include "lsquic.h"
7#include "lsquic_types.h"
8#include "lsquic_int_types.h"
9#include "lsquic_attq.h"
10#include "lsquic_hash.h"
11#include "lsquic_conn.h"
12
13
14static char curiosity[] =
15    "Dogs say cats love too much, are irresponsible,"
16    "are changeable, marry too many wives,"
17    "desert their children, chill all dinner tables"
18    "with tales of their nine lives."
19    "Well, they are lucky. Let them be"
20    "nine-lived and contradictory,"
21    "curious enough to change, prepared to pay"
22    "the cat price, which is to die"
23    "and die again and again,"
24    "each time with no less pain."
25    "A cat minority of one"
26    "is all that can be counted on"
27    "to tell the truth. And what cats have to tell"
28    "on each return from hell"
29    "is this: that dying is what the living do,"
30    "that dying is what the loving do,"
31    "and that dead dogs are those who do not know"
32    "that dying is what, to live, each has to do."
33    ;
34
35
36static int
37cmp_chars_asc (const void *ap, const void *bp)
38{
39    char a = * (char *) ap;
40    char b = * (char *) bp;
41    return (a > b) - (b > a);
42}
43
44
45static int
46cmp_chars_desc (const void *ap, const void *bp)
47{
48    char a = * (char *) ap;
49    char b = * (char *) bp;
50    return (a < b) - (b < a);
51}
52
53
54enum sort_action { SORT_NONE, SORT_ASC, SORT_DESC, };
55
56static void
57test_attq_ordering (enum sort_action sa)
58{
59    struct attq *q;
60    struct lsquic_conn *conns, *conn;
61    const struct attq_elem *next_attq;
62    lsquic_time_t prev;
63    lsquic_time_t t;
64    unsigned i;
65    int s;
66
67    switch (sa)
68    {
69    case SORT_NONE:
70        break;
71    case SORT_ASC:
72        qsort(curiosity, sizeof(curiosity) *
73            sizeof(curiosity[0]), sizeof(curiosity[0]), cmp_chars_asc);
74        break;
75    case SORT_DESC:
76        qsort(curiosity, sizeof(curiosity) *
77            sizeof(curiosity[0]), sizeof(curiosity[0]), cmp_chars_desc);
78        break;
79    }
80
81    q = lsquic_attq_create();
82
83    for (i = 0; i < sizeof(curiosity); ++i)
84    {
85        unsigned count_before = lsquic_attq_count_before(q, curiosity[i]);
86        assert(count_before == 0);
87    }
88
89    conns = calloc(sizeof(curiosity), sizeof(conns[0]));
90    for (i = 0; i < sizeof(curiosity); ++i)
91    {
92        s = lsquic_attq_add(q, &conns[i], (lsquic_time_t) curiosity[i], 0);
93        assert(s == 0);
94    }
95
96    for (i = 0; i < sizeof(curiosity); ++i)
97        assert(conns[i].cn_attq_elem);
98
99    if (sa == SORT_ASC)
100    {
101        unsigned counts[ sizeof(curiosity) ];
102        unsigned count_before;
103        counts[0] = 0;
104        for (i = 1; i < sizeof(curiosity); ++i)
105        {
106            if (curiosity[i - 1] == curiosity[i])
107                counts[i] = counts[i - 1];
108            else
109                counts[i] = i;
110        }
111        for (i = 1; i < sizeof(curiosity); ++i)
112        {
113            count_before = lsquic_attq_count_before(q, curiosity[i]);
114            assert(count_before == counts[i]);
115        }
116    }
117
118    for (i = 0; i < sizeof(curiosity); ++i)
119    {
120        next_attq = lsquic_attq_next(q);
121        assert(next_attq);
122        t = next_attq->ae_adv_time;
123        if (i > 0)
124            assert(t >= prev);
125        prev = t;
126        conn = lsquic_attq_pop(q, ~0ULL);
127        assert(conn);
128    }
129
130    next_attq = lsquic_attq_next(q);
131    assert(!next_attq);
132    conn = lsquic_attq_pop(q, ~0ULL);
133    assert(!conn);
134
135    free(conns);
136    lsquic_attq_destroy(q);
137}
138
139
140/* Filter up */
141static void
142test_attq_removal_1 (void)
143{
144    struct attq *q;
145    struct lsquic_conn *conns;
146
147    q = lsquic_attq_create();
148    conns = calloc(6, sizeof(conns[0]));
149
150    lsquic_attq_add(q, &conns[0], 1, 0);
151    lsquic_attq_add(q, &conns[1], 4, 0);
152    lsquic_attq_add(q, &conns[2], 2, 0);
153    lsquic_attq_add(q, &conns[3], 5, 0);
154    lsquic_attq_add(q, &conns[4], 6, 0);
155    lsquic_attq_add(q, &conns[5], 3, 0);
156
157    lsquic_attq_remove(q, &conns[3]);
158
159    free(conns);
160    lsquic_attq_destroy(q);
161}
162
163
164/* Filter down */
165static void
166test_attq_removal_2 (void)
167{
168    struct attq *q;
169    struct lsquic_conn *conns;
170
171    q = lsquic_attq_create();
172    conns = calloc(9, sizeof(conns[0]));
173
174    lsquic_attq_add(q, &conns[0], 1, 0);
175    lsquic_attq_add(q, &conns[1], 5, 0);
176    lsquic_attq_add(q, &conns[2], 6, 0);
177    lsquic_attq_add(q, &conns[3], 9, 0);
178    lsquic_attq_add(q, &conns[4], 11, 0);
179    lsquic_attq_add(q, &conns[5], 8, 0);
180    lsquic_attq_add(q, &conns[6], 15, 0);
181    lsquic_attq_add(q, &conns[7], 17, 0);
182    lsquic_attq_add(q, &conns[8], 21, 0);
183
184    lsquic_attq_remove(q, &conns[1]);
185
186    free(conns);
187    lsquic_attq_destroy(q);
188}
189
190
191/* Filter up */
192static void
193test_attq_removal_3 (void)
194{
195    struct attq *q;
196    struct lsquic_conn *conns;
197
198    q = lsquic_attq_create();
199    conns = calloc(9, sizeof(conns[0]));
200
201    lsquic_attq_add(q, &conns[0], 1, 0);
202    lsquic_attq_add(q, &conns[1], 9, 0);
203    lsquic_attq_add(q, &conns[2], 22, 0);
204    lsquic_attq_add(q, &conns[3], 17, 0);
205    lsquic_attq_add(q, &conns[4], 11, 0);
206    lsquic_attq_add(q, &conns[5], 33, 0);
207    lsquic_attq_add(q, &conns[6], 27, 0);
208    lsquic_attq_add(q, &conns[7], 21, 0);
209    lsquic_attq_add(q, &conns[8], 19, 0);
210
211    lsquic_attq_remove(q, &conns[1]);
212
213    free(conns);
214    lsquic_attq_destroy(q);
215}
216
217
218int
219main (void)
220{
221    test_attq_ordering(SORT_NONE);
222    test_attq_ordering(SORT_ASC);
223    test_attq_ordering(SORT_DESC);
224    test_attq_removal_1();
225    test_attq_removal_2();
226    test_attq_removal_3();
227    return 0;
228}
229