372 lines
8.6 KiB
C
372 lines
8.6 KiB
C
/* Copyright (c) 2017 - 2022 LiteSpeed Technologies Inc. See LICENSE. */
|
|
/*
|
|
* lsquic_set.c -- A set implementation.
|
|
*
|
|
* Deleting from a set is not supported. Implemented as a sorted array.
|
|
* Optimized for reading. Insertion may trigger realloc, memmove, or
|
|
* both.
|
|
*/
|
|
|
|
#include <assert.h>
|
|
#include <errno.h>
|
|
#include <limits.h>
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
|
|
#include "lsquic_set.h"
|
|
|
|
|
|
struct lsquic_set32_elem
|
|
{
|
|
uint32_t low, high;
|
|
};
|
|
|
|
|
|
void
|
|
lsquic_set32_init (struct lsquic_set32 *set)
|
|
{
|
|
memset(set, 0, sizeof(*set));
|
|
}
|
|
|
|
|
|
void
|
|
lsquic_set32_cleanup (struct lsquic_set32 *set)
|
|
{
|
|
free(set->elems);
|
|
}
|
|
|
|
|
|
static int
|
|
lsquic_set32_insert_set_elem (struct lsquic_set32 *set, int i, uint32_t value)
|
|
{
|
|
struct lsquic_set32_elem *elems;
|
|
|
|
if (set->n_elems == INT_MAX)
|
|
{
|
|
errno = EOVERFLOW;
|
|
return -1;
|
|
}
|
|
|
|
if (set->n_alloc == set->n_elems)
|
|
{
|
|
if (set->n_alloc)
|
|
set->n_alloc *= 2;
|
|
else
|
|
set->n_alloc = 4;
|
|
elems = realloc(set->elems, sizeof(set->elems[0]) * set->n_alloc);
|
|
if (!elems)
|
|
return -1;
|
|
set->elems = elems;
|
|
}
|
|
if (i < set->n_elems)
|
|
memmove(&set->elems[i + 1], &set->elems[i],
|
|
(set->n_elems - i) * sizeof(set->elems[i]));
|
|
set->elems[i].low = set->elems[i].high = value;
|
|
++set->n_elems;
|
|
return 0;
|
|
}
|
|
|
|
|
|
static void
|
|
lsquic_set32_merge_set_elems (struct lsquic_set32 *set, int i)
|
|
{
|
|
assert(i >= 0);
|
|
assert(i < set->n_elems - 1);
|
|
assert(set->elems[i].high + 1 == set->elems[i + 1].low);
|
|
set->elems[i].high = set->elems[i + 1].high;
|
|
if (i < set->n_elems - 2)
|
|
memmove(&set->elems[i + 1], &set->elems[i + 2],
|
|
(set->n_elems - i - 2) * sizeof(set->elems[i]));
|
|
--set->n_elems;
|
|
}
|
|
|
|
|
|
#ifndef NDEBUG
|
|
static void
|
|
lsquic_set32_check_elems_sorted (const struct lsquic_set32 *set)
|
|
{
|
|
int i;
|
|
for (i = 0; i < set->n_elems; ++i)
|
|
{
|
|
assert(set->elems[i].low <= set->elems[i].high);
|
|
if (i > 0)
|
|
assert(set->elems[i - 1].high + 1 < set->elems[i].low);
|
|
}
|
|
}
|
|
#endif
|
|
|
|
|
|
int
|
|
lsquic_set32_add (struct lsquic_set32 *set, uint32_t value)
|
|
{
|
|
if (value < 64)
|
|
{
|
|
set->lowset |= 1ULL << value;
|
|
return 0;
|
|
}
|
|
|
|
int low, high, i;
|
|
|
|
if (set->n_elems > 0)
|
|
{
|
|
low = 0, high = set->n_elems - 1;
|
|
do
|
|
{
|
|
i = low + (high - low) / 2;
|
|
if (set->elems[i].low <= value && set->elems[i].high >= value)
|
|
return 0;
|
|
else if (set->elems[i].high < value)
|
|
low = i + 1;
|
|
else
|
|
high = i - 1;
|
|
}
|
|
while (low <= high);
|
|
|
|
if (value < set->elems[i].low)
|
|
{
|
|
if (set->elems[i].low - 1 == value)
|
|
{
|
|
set->elems[i].low = value;
|
|
if (i > 0 && set->elems[i - 1].high + 1 == value)
|
|
lsquic_set32_merge_set_elems(set, i - 1);
|
|
}
|
|
else if (i > 0 && set->elems[i - 1].high + 1 == value)
|
|
set->elems[i - 1].high = value;
|
|
else if (0 != lsquic_set32_insert_set_elem(set, i, value))
|
|
return -1;
|
|
}
|
|
else
|
|
{
|
|
assert(value > set->elems[i].high);
|
|
if (set->elems[i].high + 1 == value)
|
|
{
|
|
set->elems[i].high = value;
|
|
if (i + 1 < set->n_elems && set->elems[i + 1].low - 1== value)
|
|
lsquic_set32_merge_set_elems(set, i);
|
|
}
|
|
else if (i + 1 < set->n_elems && set->elems[i + 1].low - 1 == value)
|
|
set->elems[i + 1].low = value;
|
|
else if (0 != lsquic_set32_insert_set_elem(set, i + 1, value))
|
|
return 0;
|
|
}
|
|
}
|
|
else
|
|
{
|
|
assert(NULL == set->elems);
|
|
if (0 != lsquic_set32_insert_set_elem(set, 0, value))
|
|
return -1;
|
|
}
|
|
#ifndef NDEBUG
|
|
lsquic_set32_check_elems_sorted(set);
|
|
#endif
|
|
return 0;
|
|
}
|
|
|
|
|
|
int
|
|
lsquic_set32_has (const struct lsquic_set32 *set, uint32_t value)
|
|
{
|
|
if (value < 64)
|
|
{
|
|
return !!(set->lowset & (1ULL << value));
|
|
}
|
|
|
|
int low, high, i;
|
|
|
|
low = 0, high = set->n_elems - 1;
|
|
while (low <= high)
|
|
{
|
|
i = low + (high - low) / 2;
|
|
if (set->elems[i].low <= value && set->elems[i].high >= value)
|
|
return 1;
|
|
else if (set->elems[i].high < value)
|
|
low = i + 1;
|
|
else
|
|
high = i - 1;
|
|
}
|
|
|
|
return 0;
|
|
}
|
|
|
|
|
|
/* ******* ******* ******** *******
|
|
*
|
|
* The following code is a set of two replacements:
|
|
*
|
|
* :.,$s/lsquic_set32/lsquic_set64/g
|
|
* :.,$s/uint32_t/uint64_t/g
|
|
*/
|
|
struct lsquic_set64_elem
|
|
{
|
|
uint64_t low, high;
|
|
};
|
|
|
|
|
|
void
|
|
lsquic_set64_init (struct lsquic_set64 *set)
|
|
{
|
|
memset(set, 0, sizeof(*set));
|
|
}
|
|
|
|
|
|
void
|
|
lsquic_set64_cleanup (struct lsquic_set64 *set)
|
|
{
|
|
free(set->elems);
|
|
}
|
|
|
|
|
|
static int
|
|
lsquic_set64_insert_set_elem (struct lsquic_set64 *set, int i, uint64_t value)
|
|
{
|
|
struct lsquic_set64_elem *elems;
|
|
|
|
if (set->n_elems == INT_MAX)
|
|
{
|
|
errno = EOVERFLOW;
|
|
return -1;
|
|
}
|
|
|
|
if (set->n_alloc == set->n_elems)
|
|
{
|
|
if (set->n_alloc)
|
|
set->n_alloc *= 2;
|
|
else
|
|
set->n_alloc = 4;
|
|
elems = realloc(set->elems, sizeof(set->elems[0]) * set->n_alloc);
|
|
if (!elems)
|
|
return -1;
|
|
set->elems = elems;
|
|
}
|
|
if (i < set->n_elems)
|
|
memmove(&set->elems[i + 1], &set->elems[i],
|
|
(set->n_elems - i) * sizeof(set->elems[i]));
|
|
set->elems[i].low = set->elems[i].high = value;
|
|
++set->n_elems;
|
|
return 0;
|
|
}
|
|
|
|
|
|
static void
|
|
lsquic_set64_merge_set_elems (struct lsquic_set64 *set, int i)
|
|
{
|
|
assert(i >= 0);
|
|
assert(i < set->n_elems - 1);
|
|
assert(set->elems[i].high + 1 == set->elems[i + 1].low);
|
|
set->elems[i].high = set->elems[i + 1].high;
|
|
if (i < set->n_elems - 2)
|
|
memmove(&set->elems[i + 1], &set->elems[i + 2],
|
|
(set->n_elems - i - 2) * sizeof(set->elems[i]));
|
|
--set->n_elems;
|
|
}
|
|
|
|
|
|
#ifndef NDEBUG
|
|
static void
|
|
lsquic_set64_check_elems_sorted (const struct lsquic_set64 *set)
|
|
{
|
|
int i;
|
|
for (i = 0; i < set->n_elems; ++i)
|
|
{
|
|
assert(set->elems[i].low <= set->elems[i].high);
|
|
if (i > 0)
|
|
assert(set->elems[i - 1].high + 1 < set->elems[i].low);
|
|
}
|
|
}
|
|
#endif
|
|
|
|
|
|
int
|
|
lsquic_set64_add (struct lsquic_set64 *set, uint64_t value)
|
|
{
|
|
if (value < 64)
|
|
{
|
|
set->lowset |= 1ULL << value;
|
|
return 0;
|
|
}
|
|
|
|
int low, high, i;
|
|
|
|
if (set->n_elems > 0)
|
|
{
|
|
low = 0, high = set->n_elems - 1;
|
|
do
|
|
{
|
|
i = low + (high - low) / 2;
|
|
if (set->elems[i].low <= value && set->elems[i].high >= value)
|
|
return 0;
|
|
else if (set->elems[i].high < value)
|
|
low = i + 1;
|
|
else
|
|
high = i - 1;
|
|
}
|
|
while (low <= high);
|
|
|
|
if (value < set->elems[i].low)
|
|
{
|
|
if (set->elems[i].low - 1 == value)
|
|
{
|
|
set->elems[i].low = value;
|
|
if (i > 0 && set->elems[i - 1].high + 1 == value)
|
|
lsquic_set64_merge_set_elems(set, i - 1);
|
|
}
|
|
else if (i > 0 && set->elems[i - 1].high + 1 == value)
|
|
set->elems[i - 1].high = value;
|
|
else if (0 != lsquic_set64_insert_set_elem(set, i, value))
|
|
return -1;
|
|
}
|
|
else
|
|
{
|
|
assert(value > set->elems[i].high);
|
|
if (set->elems[i].high + 1 == value)
|
|
{
|
|
set->elems[i].high = value;
|
|
if (i + 1 < set->n_elems && set->elems[i + 1].low - 1== value)
|
|
lsquic_set64_merge_set_elems(set, i);
|
|
}
|
|
else if (i + 1 < set->n_elems && set->elems[i + 1].low - 1 == value)
|
|
set->elems[i + 1].low = value;
|
|
else if (0 != lsquic_set64_insert_set_elem(set, i + 1, value))
|
|
return 0;
|
|
}
|
|
}
|
|
else
|
|
{
|
|
assert(NULL == set->elems);
|
|
if (0 != lsquic_set64_insert_set_elem(set, 0, value))
|
|
return -1;
|
|
}
|
|
#ifndef NDEBUG
|
|
lsquic_set64_check_elems_sorted(set);
|
|
#endif
|
|
return 0;
|
|
}
|
|
|
|
|
|
int
|
|
lsquic_set64_has (const struct lsquic_set64 *set, uint64_t value)
|
|
{
|
|
if (value < 64)
|
|
{
|
|
return !!(set->lowset & (1ULL << value));
|
|
}
|
|
|
|
int low, high, i;
|
|
|
|
low = 0, high = set->n_elems - 1;
|
|
while (low <= high)
|
|
{
|
|
i = low + (high - low) / 2;
|
|
if (set->elems[i].low <= value && set->elems[i].high >= value)
|
|
return 1;
|
|
else if (set->elems[i].high < value)
|
|
low = i + 1;
|
|
else
|
|
high = i - 1;
|
|
}
|
|
|
|
return 0;
|
|
}
|
|
|
|
|