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 #include "ngtcp2_range.h"
27
28 #include <string.h>
29 #include <assert.h>
30
ngtcp2_gaptr_init(ngtcp2_gaptr * gaptr,const ngtcp2_mem * mem)31 int ngtcp2_gaptr_init(ngtcp2_gaptr *gaptr, const ngtcp2_mem *mem) {
32 int rv;
33 ngtcp2_range range = {0, UINT64_MAX};
34
35 rv = ngtcp2_ksl_init(&gaptr->gap, ngtcp2_ksl_range_compar,
36 sizeof(ngtcp2_range), mem);
37 if (rv != 0) {
38 return rv;
39 }
40
41 rv = ngtcp2_ksl_insert(&gaptr->gap, NULL, &range, NULL);
42 if (rv != 0) {
43 ngtcp2_ksl_free(&gaptr->gap);
44 return rv;
45 }
46
47 gaptr->mem = mem;
48
49 return 0;
50 }
51
ngtcp2_gaptr_free(ngtcp2_gaptr * gaptr)52 void ngtcp2_gaptr_free(ngtcp2_gaptr *gaptr) {
53 if (gaptr == NULL) {
54 return;
55 }
56
57 ngtcp2_ksl_free(&gaptr->gap);
58 }
59
ngtcp2_gaptr_push(ngtcp2_gaptr * gaptr,uint64_t offset,uint64_t datalen)60 int ngtcp2_gaptr_push(ngtcp2_gaptr *gaptr, uint64_t offset, uint64_t datalen) {
61 int rv;
62 ngtcp2_range k, m, l, r, q = {offset, offset + datalen};
63 ngtcp2_ksl_it it;
64
65 it = ngtcp2_ksl_lower_bound_compar(&gaptr->gap, &q,
66 ngtcp2_ksl_range_exclusive_compar);
67
68 for (; !ngtcp2_ksl_it_end(&it);) {
69 k = *(ngtcp2_range *)ngtcp2_ksl_it_key(&it);
70 m = ngtcp2_range_intersect(&q, &k);
71 if (!ngtcp2_range_len(&m)) {
72 break;
73 }
74
75 if (ngtcp2_range_eq(&k, &m)) {
76 ngtcp2_ksl_remove_hint(&gaptr->gap, &it, &it, &k);
77 continue;
78 }
79 ngtcp2_range_cut(&l, &r, &k, &m);
80 if (ngtcp2_range_len(&l)) {
81 ngtcp2_ksl_update_key(&gaptr->gap, &k, &l);
82
83 if (ngtcp2_range_len(&r)) {
84 rv = ngtcp2_ksl_insert(&gaptr->gap, &it, &r, NULL);
85 if (rv != 0) {
86 return rv;
87 }
88 }
89 } else if (ngtcp2_range_len(&r)) {
90 ngtcp2_ksl_update_key(&gaptr->gap, &k, &r);
91 }
92 ngtcp2_ksl_it_next(&it);
93 }
94 return 0;
95 }
96
ngtcp2_gaptr_first_gap_offset(ngtcp2_gaptr * gaptr)97 uint64_t ngtcp2_gaptr_first_gap_offset(ngtcp2_gaptr *gaptr) {
98 ngtcp2_ksl_it it = ngtcp2_ksl_begin(&gaptr->gap);
99 ngtcp2_range r = *(ngtcp2_range *)ngtcp2_ksl_it_key(&it);
100 return r.begin;
101 }
102
ngtcp2_gaptr_get_first_gap_after(ngtcp2_gaptr * gaptr,uint64_t offset)103 ngtcp2_ksl_it ngtcp2_gaptr_get_first_gap_after(ngtcp2_gaptr *gaptr,
104 uint64_t offset) {
105 ngtcp2_range q = {offset, offset + 1};
106 return ngtcp2_ksl_lower_bound_compar(&gaptr->gap, &q,
107 ngtcp2_ksl_range_exclusive_compar);
108 }
109
ngtcp2_gaptr_is_pushed(ngtcp2_gaptr * gaptr,uint64_t offset,uint64_t datalen)110 int ngtcp2_gaptr_is_pushed(ngtcp2_gaptr *gaptr, uint64_t offset,
111 uint64_t datalen) {
112 ngtcp2_range q = {offset, offset + datalen};
113 ngtcp2_ksl_it it = ngtcp2_ksl_lower_bound_compar(
114 &gaptr->gap, &q, ngtcp2_ksl_range_exclusive_compar);
115 ngtcp2_range k = *(ngtcp2_range *)ngtcp2_ksl_it_key(&it);
116 ngtcp2_range m = ngtcp2_range_intersect(&q, &k);
117 return ngtcp2_range_len(&m) == 0;
118 }
119
ngtcp2_gaptr_drop_first_gap(ngtcp2_gaptr * gaptr)120 void ngtcp2_gaptr_drop_first_gap(ngtcp2_gaptr *gaptr) {
121 ngtcp2_ksl_it it = ngtcp2_ksl_begin(&gaptr->gap);
122 ngtcp2_range r;
123
124 assert(!ngtcp2_ksl_it_end(&it));
125
126 r = *(ngtcp2_range *)ngtcp2_ksl_it_key(&it);
127
128 ngtcp2_ksl_remove_hint(&gaptr->gap, NULL, &it, &r);
129 }
130