/src/h2o/deps/quicly/lib/ranges.c

Source (jump to first uncovered line)
/*
 * Copyright (c) 2017 Fastly, Kazuho Oku
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to
 * deal in the Software without restriction, including without limitation the
 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
 * sell copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 * IN THE SOFTWARE.
 */
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include "picotls.h"
#include "quicly/constants.h"
#include "quicly/ranges.h"

#define COPY(dst, src, n)                                                                                                          \
    do {                                                                                                                           \
        size_t _n = (n);                                                                                                           \
        if (_n != 0)                                                                                                               \
            memcpy((dst), (src), sizeof(quicly_range_t) * _n);                                                                     \
    } while (0)
#define MOVE(dst, src, n)                                                                                                          \
    do {                                                                                                                           \
        size_t _n = (n);                                                                                                           \
        if (_n != 0)                                                                                                               \
            memmove((dst), (src), sizeof(quicly_range_t) * _n);                                                                    \
    } while (0)

static int insert_at(quicly_ranges_t *ranges, uint64_t start, uint64_t end, size_t slot)
{
    if (ranges->num_ranges == ranges->capacity) {
        size_t new_capacity = ranges->capacity < 4 ? 4 : ranges->capacity * 2;
        quicly_range_t *new_ranges = malloc(new_capacity * sizeof(*new_ranges));
        if (new_ranges == NULL)
            return PTLS_ERROR_NO_MEMORY;
        COPY(new_ranges, ranges->ranges, slot);
        COPY(new_ranges + slot + 1, ranges->ranges + slot, ranges->num_ranges - slot);
        if (ranges->ranges != &ranges->_initial)
            free(ranges->ranges);
        ranges->ranges = new_ranges;
        ranges->capacity = new_capacity;
    } else {
        MOVE(ranges->ranges + slot + 1, ranges->ranges + slot, ranges->num_ranges - slot);
    }
    ranges->ranges[slot] = (quicly_range_t){start, end};
    ++ranges->num_ranges;
    return 0;
}

void quicly_ranges_drop_by_range_indices(quicly_ranges_t *ranges, size_t begin_range_index, size_t end_range_index)
{
    assert(begin_range_index < end_range_index);

    MOVE(ranges->ranges + begin_range_index, ranges->ranges + end_range_index, ranges->num_ranges - end_range_index);
    ranges->num_ranges -= end_range_index - begin_range_index;
    if (ranges->capacity > 4 && ranges->num_ranges * 3 <= ranges->capacity) {
        size_t new_capacity = ranges->capacity / 2;
        quicly_range_t *new_ranges = realloc(ranges->ranges, new_capacity * sizeof(*new_ranges));
        if (new_ranges != NULL) {
            ranges->ranges = new_ranges;
            ranges->capacity = new_capacity;
        }
    }
}

static inline int merge_update(quicly_ranges_t *ranges, uint64_t start, uint64_t end, size_t slot, size_t end_slot)
{
    if (start < ranges->ranges[slot].start)
        ranges->ranges[slot].start = start;
    ranges->ranges[slot].end = end < ranges->ranges[end_slot].end ? ranges->ranges[end_slot].end : end;

    if (slot != end_slot)
        quicly_ranges_drop_by_range_indices(ranges, slot + 1, end_slot + 1);

    return 0;
}

int quicly_ranges_init_with_range(quicly_ranges_t *ranges, uint64_t start, uint64_t end)
{
    quicly_ranges_init(ranges);
    return insert_at(ranges, start, end, 0);
}

int quicly_ranges_add(quicly_ranges_t *ranges, uint64_t start, uint64_t end)
{
    size_t slot, end_slot;

    assert(start <= end);

    if (start == end)
        return 0;

    if (ranges->num_ranges == 0) {
        return insert_at(ranges, start, end, 0);
    } else if (ranges->ranges[ranges->num_ranges - 1].end < start) {
        return insert_at(ranges, start, end, ranges->num_ranges);
    }

    /* find the slot that should contain `end` */
    for (slot = ranges->num_ranges - 1;; --slot) {
        if (ranges->ranges[slot].start <= end)
            break;
        if (slot == 0)
            return insert_at(ranges, start, end, 0);
    }
    end_slot = slot;

    /* find the slot that should contain `start` */
    do {
        if (ranges->ranges[slot].end == start) {
            return merge_update(ranges, start, end, slot, end_slot);
        } else if (ranges->ranges[slot].end < start) {
            if (slot++ == end_slot) {
                return insert_at(ranges, start, end, slot);
            } else {
                return merge_update(ranges, start, end, slot, end_slot);
            }
        }
    } while (slot-- != 0);

    return merge_update(ranges, start, end, 0, end_slot);
}

int quicly_ranges_subtract(quicly_ranges_t *ranges, uint64_t start, uint64_t end)
{
    size_t shrink_from, slot;

    assert(start <= end);

    if (start == end)
        return 0;

    if (ranges->num_ranges == 0) {
        return 0;
    } else if (end <= ranges->ranges[0].start) {
        return 0;
    } else if (ranges->ranges[ranges->num_ranges - 1].end <= start) {
        return 0;
    }

    /* find the first overlapping slot */
    for (slot = 0; ranges->ranges[slot].end < start; ++slot)
        ;

    if (end <= ranges->ranges[slot].end) {
        /* first overlapping slot is the only slot that we will ever modify */
        if (end <= ranges->ranges[slot].start)
            return 0;
        if (start <= ranges->ranges[slot].start) {
            ranges->ranges[slot].start = end;
        } else if (end == ranges->ranges[slot].end) {
            ranges->ranges[slot].end = start;
        } else {
            /* split */
            int ret;
            if ((ret = insert_at(ranges, end, ranges->ranges[slot].end, slot + 1)) != 0)
                return ret;
            ranges->ranges[slot].end = start;
            return 0;
        }
        /* remove the slot if the range has become empty */
        if (ranges->ranges[slot].start == ranges->ranges[slot].end)
            quicly_ranges_drop_by_range_indices(ranges, slot, slot + 1);
        return 0;
    }

    /* specified region covers multiple slots */
    if (start <= ranges->ranges[slot].start) {
        shrink_from = slot;
    } else {
        ranges->ranges[slot].end = start;
        shrink_from = slot + 1;
    }

    /* find the last overlapping slot */
    for (++slot; slot != ranges->num_ranges; ++slot) {
        if (end <= ranges->ranges[slot].start)
            break;
        if (end < ranges->ranges[slot].end) {
            ranges->ranges[slot].start = end;
            break;
        }
    }

    /* remove shrink_from..slot */
    if (shrink_from != slot)
        quicly_ranges_drop_by_range_indices(ranges, shrink_from, slot);

    return 0;
}

Coverage Report

Created: 2025-06-22 06:18

Line	Count	Source (jump to first uncovered line)
1		/*
2		* Copyright (c) 2017 Fastly, Kazuho Oku
3		*
4		* Permission is hereby granted, free of charge, to any person obtaining a copy
5		* of this software and associated documentation files (the "Software"), to
6		* deal in the Software without restriction, including without limitation the
7		* rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
8		* sell copies of the Software, and to permit persons to whom the Software is
9		* furnished to do so, subject to the following conditions:
10		*
11		* The above copyright notice and this permission notice shall be included in
12		* all copies or substantial portions of the Software.
13		*
14		* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15		* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16		* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17		* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18		* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
19		* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
20		* IN THE SOFTWARE.
21		*/
22		#include <assert.h>
23		#include <stdlib.h>
24		#include <string.h>
25		#include "picotls.h"
26		#include "quicly/constants.h"
27		#include "quicly/ranges.h"
28
29		#define COPY(dst, src, n) \
30	0	do { \
31	0	size_t _n = (n); \
32	0	if (_n != 0) \
33	0	memcpy((dst), (src), sizeof(quicly_range_t) * _n); \
34	0	} while (0)
35		#define MOVE(dst, src, n) \
36	0	do { \
37	0	size_t _n = (n); \
38	0	if (_n != 0) \
39	0	memmove((dst), (src), sizeof(quicly_range_t) * _n); \
40	0	} while (0)
41
42		static int insert_at(quicly_ranges_t *ranges, uint64_t start, uint64_t end, size_t slot)
43	0	{
44	0	if (ranges->num_ranges == ranges->capacity) {
45	0	size_t new_capacity = ranges->capacity < 4 ? 4 : ranges->capacity * 2;
46	0	quicly_range_t new_ranges = malloc(new_capacity sizeof(*new_ranges));
47	0	if (new_ranges == NULL)
48	0	return PTLS_ERROR_NO_MEMORY;
49	0	COPY(new_ranges, ranges->ranges, slot);
50	0	COPY(new_ranges + slot + 1, ranges->ranges + slot, ranges->num_ranges - slot);
51	0	if (ranges->ranges != &ranges->_initial)
52	0	free(ranges->ranges);
53	0	ranges->ranges = new_ranges;
54	0	ranges->capacity = new_capacity;
55	0	} else {
56	0	MOVE(ranges->ranges + slot + 1, ranges->ranges + slot, ranges->num_ranges - slot);
57	0	}
58	0	ranges->ranges[slot] = (quicly_range_t){start, end};
59	0	++ranges->num_ranges;
60	0	return 0;
61	0	}
62
63		void quicly_ranges_drop_by_range_indices(quicly_ranges_t *ranges, size_t begin_range_index, size_t end_range_index)
64	0	{
65	0	assert(begin_range_index < end_range_index);
66
67	0	MOVE(ranges->ranges + begin_range_index, ranges->ranges + end_range_index, ranges->num_ranges - end_range_index);
68	0	ranges->num_ranges -= end_range_index - begin_range_index;
69	0	if (ranges->capacity > 4 && ranges->num_ranges * 3 <= ranges->capacity) {
70	0	size_t new_capacity = ranges->capacity / 2;
71	0	quicly_range_t new_ranges = realloc(ranges->ranges, new_capacity sizeof(*new_ranges));
72	0	if (new_ranges != NULL) {
73	0	ranges->ranges = new_ranges;
74	0	ranges->capacity = new_capacity;
75	0	}
76	0	}
77	0	}
78
79		static inline int merge_update(quicly_ranges_t *ranges, uint64_t start, uint64_t end, size_t slot, size_t end_slot)
80	0	{
81	0	if (start < ranges->ranges[slot].start)
82	0	ranges->ranges[slot].start = start;
83	0	ranges->ranges[slot].end = end < ranges->ranges[end_slot].end ? ranges->ranges[end_slot].end : end;
84
85	0	if (slot != end_slot)
86	0	quicly_ranges_drop_by_range_indices(ranges, slot + 1, end_slot + 1);
87
88	0	return 0;
89	0	}
90
91		int quicly_ranges_init_with_range(quicly_ranges_t *ranges, uint64_t start, uint64_t end)
92	0	{
93	0	quicly_ranges_init(ranges);
94	0	return insert_at(ranges, start, end, 0);
95	0	}
96
97		int quicly_ranges_add(quicly_ranges_t *ranges, uint64_t start, uint64_t end)
98	0	{
99	0	size_t slot, end_slot;
100
101	0	assert(start <= end);
102
103	0	if (start == end)
104	0	return 0;
105
106	0	if (ranges->num_ranges == 0) {
107	0	return insert_at(ranges, start, end, 0);
108	0	} else if (ranges->ranges[ranges->num_ranges - 1].end < start) {
109	0	return insert_at(ranges, start, end, ranges->num_ranges);
110	0	}
111
112		/* find the slot that should contain `end` */
113	0	for (slot = ranges->num_ranges - 1;; --slot) {
114	0	if (ranges->ranges[slot].start <= end)
115	0	break;
116	0	if (slot == 0)
117	0	return insert_at(ranges, start, end, 0);
118	0	}
119	0	end_slot = slot;
120
121		/* find the slot that should contain `start` */
122	0	do {
123	0	if (ranges->ranges[slot].end == start) {
124	0	return merge_update(ranges, start, end, slot, end_slot);
125	0	} else if (ranges->ranges[slot].end < start) {
126	0	if (slot++ == end_slot) {
127	0	return insert_at(ranges, start, end, slot);
128	0	} else {
129	0	return merge_update(ranges, start, end, slot, end_slot);
130	0	}
131	0	}
132	0	} while (slot-- != 0);
133
134	0	return merge_update(ranges, start, end, 0, end_slot);
135	0	}
136
137		int quicly_ranges_subtract(quicly_ranges_t *ranges, uint64_t start, uint64_t end)
138	0	{
139	0	size_t shrink_from, slot;
140
141	0	assert(start <= end);
142
143	0	if (start == end)
144	0	return 0;
145
146	0	if (ranges->num_ranges == 0) {
147	0	return 0;
148	0	} else if (end <= ranges->ranges[0].start) {
149	0	return 0;
150	0	} else if (ranges->ranges[ranges->num_ranges - 1].end <= start) {
151	0	return 0;
152	0	}
153
154		/* find the first overlapping slot */
155	0	for (slot = 0; ranges->ranges[slot].end < start; ++slot)
156	0	;
157
158	0	if (end <= ranges->ranges[slot].end) {
159		/* first overlapping slot is the only slot that we will ever modify */
160	0	if (end <= ranges->ranges[slot].start)
161	0	return 0;
162	0	if (start <= ranges->ranges[slot].start) {
163	0	ranges->ranges[slot].start = end;
164	0	} else if (end == ranges->ranges[slot].end) {
165	0	ranges->ranges[slot].end = start;
166	0	} else {
167		/* split */
168	0	int ret;
169	0	if ((ret = insert_at(ranges, end, ranges->ranges[slot].end, slot + 1)) != 0)
170	0	return ret;
171	0	ranges->ranges[slot].end = start;
172	0	return 0;
173	0	}
174		/* remove the slot if the range has become empty */
175	0	if (ranges->ranges[slot].start == ranges->ranges[slot].end)
176	0	quicly_ranges_drop_by_range_indices(ranges, slot, slot + 1);
177	0	return 0;
178	0	}
179
180		/* specified region covers multiple slots */
181	0	if (start <= ranges->ranges[slot].start) {
182	0	shrink_from = slot;
183	0	} else {
184	0	ranges->ranges[slot].end = start;
185	0	shrink_from = slot + 1;
186	0	}
187
188		/* find the last overlapping slot */
189	0	for (++slot; slot != ranges->num_ranges; ++slot) {
190	0	if (end <= ranges->ranges[slot].start)
191	0	break;
192	0	if (end < ranges->ranges[slot].end) {
193	0	ranges->ranges[slot].start = end;
194	0	break;
195	0	}
196	0	}
197
198		/* remove shrink_from..slot */
199	0	if (shrink_from != slot)
200	0	quicly_ranges_drop_by_range_indices(ranges, shrink_from, slot);
201
202	0	return 0;
203	0	}