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