test_attq.c revision fb3e20e0 
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#ifdef _MSC_VER
119    prev = 0;
120#endif
121    for (i = 0; i < sizeof(curiosity); ++i)
122    {
123        next_attq = lsquic_attq_next(q);
124        assert(next_attq);
125        t = next_attq->ae_adv_time;
126        if (i > 0)
127            assert(t >= prev);
128        prev = t;
129        conn = lsquic_attq_pop(q, ~0ULL);
130        assert(conn);
131    }
132
133    next_attq = lsquic_attq_next(q);
134    assert(!next_attq);
135    conn = lsquic_attq_pop(q, ~0ULL);
136    assert(!conn);
137
138    free(conns);
139    lsquic_attq_destroy(q);
140}
141
142
143/* Filter up */
144static void
145test_attq_removal_1 (void)
146{
147    struct attq *q;
148    struct lsquic_conn *conns;
149
150    q = lsquic_attq_create();
151    conns = calloc(6, sizeof(conns[0]));
152
153    lsquic_attq_add(q, &conns[0], 1, 0);
154    lsquic_attq_add(q, &conns[1], 4, 0);
155    lsquic_attq_add(q, &conns[2], 2, 0);
156    lsquic_attq_add(q, &conns[3], 5, 0);
157    lsquic_attq_add(q, &conns[4], 6, 0);
158    lsquic_attq_add(q, &conns[5], 3, 0);
159
160    lsquic_attq_remove(q, &conns[3]);
161
162    free(conns);
163    lsquic_attq_destroy(q);
164}
165
166
167/* Filter down */
168static void
169test_attq_removal_2 (void)
170{
171    struct attq *q;
172    struct lsquic_conn *conns;
173
174    q = lsquic_attq_create();
175    conns = calloc(9, sizeof(conns[0]));
176
177    lsquic_attq_add(q, &conns[0], 1, 0);
178    lsquic_attq_add(q, &conns[1], 5, 0);
179    lsquic_attq_add(q, &conns[2], 6, 0);
180    lsquic_attq_add(q, &conns[3], 9, 0);
181    lsquic_attq_add(q, &conns[4], 11, 0);
182    lsquic_attq_add(q, &conns[5], 8, 0);
183    lsquic_attq_add(q, &conns[6], 15, 0);
184    lsquic_attq_add(q, &conns[7], 17, 0);
185    lsquic_attq_add(q, &conns[8], 21, 0);
186
187    lsquic_attq_remove(q, &conns[1]);
188
189    free(conns);
190    lsquic_attq_destroy(q);
191}
192
193
194/* Filter up */
195static void
196test_attq_removal_3 (void)
197{
198    struct attq *q;
199    struct lsquic_conn *conns;
200
201    q = lsquic_attq_create();
202    conns = calloc(9, sizeof(conns[0]));
203
204    lsquic_attq_add(q, &conns[0], 1, 0);
205    lsquic_attq_add(q, &conns[1], 9, 0);
206    lsquic_attq_add(q, &conns[2], 22, 0);
207    lsquic_attq_add(q, &conns[3], 17, 0);
208    lsquic_attq_add(q, &conns[4], 11, 0);
209    lsquic_attq_add(q, &conns[5], 33, 0);
210    lsquic_attq_add(q, &conns[6], 27, 0);
211    lsquic_attq_add(q, &conns[7], 21, 0);
212    lsquic_attq_add(q, &conns[8], 19, 0);
213
214    lsquic_attq_remove(q, &conns[1]);
215
216    free(conns);
217    lsquic_attq_destroy(q);
218}
219
220
221int
222main (void)
223{
224    test_attq_ordering(SORT_NONE);
225    test_attq_ordering(SORT_ASC);
226    test_attq_ordering(SORT_DESC);
227    test_attq_removal_1();
228    test_attq_removal_2();
229    test_attq_removal_3();
230    return 0;
231}
232