1 /*
2 * ngtcp2
3 *
4 * Copyright (c) 2017 ngtcp2 contributors
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining
7 * a copy of this software and associated documentation files (the
8 * "Software"), to deal in the Software without restriction, including
9 * without limitation the rights to use, copy, modify, merge, publish,
10 * distribute, sublicense, and/or sell copies of the Software, and to
11 * permit persons to whom the Software is furnished to do so, subject to
12 * the following conditions:
13 *
14 * The above copyright notice and this permission notice shall be
15 * included in all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
19 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
21 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
22 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
23 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
24 */
25 #include "ngtcp2_gaptr.h"
26
27 #include <string.h>
28 #include <assert.h>
29
ngtcp2_gaptr_init(ngtcp2_gaptr * gaptr,const ngtcp2_mem * mem)30 void ngtcp2_gaptr_init(ngtcp2_gaptr *gaptr, const ngtcp2_mem *mem) {
31 ngtcp2_ksl_init(&gaptr->gap, ngtcp2_ksl_range_compar, sizeof(ngtcp2_range),
32 mem);
33
34 gaptr->mem = mem;
35 }
36
gaptr_gap_init(ngtcp2_gaptr * gaptr)37 static int gaptr_gap_init(ngtcp2_gaptr *gaptr) {
38 ngtcp2_range range = {0, UINT64_MAX};
39 int rv;
40
41 rv = ngtcp2_ksl_insert(&gaptr->gap, NULL, &range, NULL);
42 if (rv != 0) {
43 return rv;
44 }
45
46 return 0;
47 }
48
ngtcp2_gaptr_free(ngtcp2_gaptr * gaptr)49 void ngtcp2_gaptr_free(ngtcp2_gaptr *gaptr) {
50 if (gaptr == NULL) {
51 return;
52 }
53
54 ngtcp2_ksl_free(&gaptr->gap);
55 }
56
ngtcp2_gaptr_push(ngtcp2_gaptr * gaptr,uint64_t offset,uint64_t datalen)57 int ngtcp2_gaptr_push(ngtcp2_gaptr *gaptr, uint64_t offset, uint64_t datalen) {
58 int rv;
59 ngtcp2_range k, m, l, r, q = {offset, offset + datalen};
60 ngtcp2_ksl_it it;
61
62 if (ngtcp2_ksl_len(&gaptr->gap) == 0) {
63 rv = gaptr_gap_init(gaptr);
64 if (rv != 0) {
65 return rv;
66 }
67 }
68
69 it = ngtcp2_ksl_lower_bound_compar(&gaptr->gap, &q,
70 ngtcp2_ksl_range_exclusive_compar);
71
72 for (; !ngtcp2_ksl_it_end(&it);) {
73 k = *(ngtcp2_range *)ngtcp2_ksl_it_key(&it);
74 m = ngtcp2_range_intersect(&q, &k);
75 if (!ngtcp2_range_len(&m)) {
76 break;
77 }
78
79 if (ngtcp2_range_eq(&k, &m)) {
80 ngtcp2_ksl_remove_hint(&gaptr->gap, &it, &it, &k);
81 continue;
82 }
83 ngtcp2_range_cut(&l, &r, &k, &m);
84 if (ngtcp2_range_len(&l)) {
85 ngtcp2_ksl_update_key(&gaptr->gap, &k, &l);
86
87 if (ngtcp2_range_len(&r)) {
88 rv = ngtcp2_ksl_insert(&gaptr->gap, &it, &r, NULL);
89 if (rv != 0) {
90 return rv;
91 }
92 }
93 } else if (ngtcp2_range_len(&r)) {
94 ngtcp2_ksl_update_key(&gaptr->gap, &k, &r);
95 }
96 ngtcp2_ksl_it_next(&it);
97 }
98 return 0;
99 }
100
ngtcp2_gaptr_first_gap_offset(ngtcp2_gaptr * gaptr)101 uint64_t ngtcp2_gaptr_first_gap_offset(ngtcp2_gaptr *gaptr) {
102 ngtcp2_ksl_it it;
103 ngtcp2_range r;
104
105 if (ngtcp2_ksl_len(&gaptr->gap) == 0) {
106 return 0;
107 }
108
109 it = ngtcp2_ksl_begin(&gaptr->gap);
110 r = *(ngtcp2_range *)ngtcp2_ksl_it_key(&it);
111
112 return r.begin;
113 }
114
ngtcp2_gaptr_get_first_gap_after(ngtcp2_gaptr * gaptr,uint64_t offset)115 ngtcp2_range ngtcp2_gaptr_get_first_gap_after(ngtcp2_gaptr *gaptr,
116 uint64_t offset) {
117 ngtcp2_range q = {offset, offset + 1};
118 ngtcp2_ksl_it it;
119
120 if (ngtcp2_ksl_len(&gaptr->gap) == 0) {
121 ngtcp2_range r = {0, UINT64_MAX};
122 return r;
123 }
124
125 it = ngtcp2_ksl_lower_bound_compar(&gaptr->gap, &q,
126 ngtcp2_ksl_range_exclusive_compar);
127
128 assert(!ngtcp2_ksl_it_end(&it));
129
130 return *(ngtcp2_range *)ngtcp2_ksl_it_key(&it);
131 }
132
ngtcp2_gaptr_is_pushed(ngtcp2_gaptr * gaptr,uint64_t offset,uint64_t datalen)133 int ngtcp2_gaptr_is_pushed(ngtcp2_gaptr *gaptr, uint64_t offset,
134 uint64_t datalen) {
135 ngtcp2_range q = {offset, offset + datalen};
136 ngtcp2_ksl_it it;
137 ngtcp2_range k;
138 ngtcp2_range m;
139
140 if (ngtcp2_ksl_len(&gaptr->gap) == 0) {
141 return 0;
142 }
143
144 it = ngtcp2_ksl_lower_bound_compar(&gaptr->gap, &q,
145 ngtcp2_ksl_range_exclusive_compar);
146 k = *(ngtcp2_range *)ngtcp2_ksl_it_key(&it);
147 m = ngtcp2_range_intersect(&q, &k);
148
149 return ngtcp2_range_len(&m) == 0;
150 }
151
ngtcp2_gaptr_drop_first_gap(ngtcp2_gaptr * gaptr)152 void ngtcp2_gaptr_drop_first_gap(ngtcp2_gaptr *gaptr) {
153 ngtcp2_ksl_it it;
154 ngtcp2_range r;
155
156 if (ngtcp2_ksl_len(&gaptr->gap) == 0) {
157 return;
158 }
159
160 it = ngtcp2_ksl_begin(&gaptr->gap);
161
162 assert(!ngtcp2_ksl_it_end(&it));
163
164 r = *(ngtcp2_range *)ngtcp2_ksl_it_key(&it);
165
166 ngtcp2_ksl_remove_hint(&gaptr->gap, NULL, &it, &r);
167 }
168