hackney

3.0.0

4.7.2 4.7.1 4.7.0 4.6.1 4.6.0 4.5.2 4.5.1 4.5.0 4.4.5 4.4.3 4.4.2 4.4.1 4.4.0 4.3.0 4.2.3 4.2.2 4.2.1 4.2.0 4.1.0 4.0.3 4.0.2 4.0.1 4.0.0 3.2.1 3.2.0 3.1.2 3.1.1 3.1.0 3.0.3 3.0.2 3.0.1 3.0.0 retired 2.0.1 2.0.0 2.0.0-beta.1 1.25.0 1.24.1 1.24.0 1.23.0 1.22.0 1.21.0 1.20.1 1.20.0 1.19.1 1.19.0 1.18.2 1.18.1 1.18.0 1.17.4 1.17.3 1.17.2 1.17.1 1.17.0 1.16.0 1.15.2 1.15.1 1.15.0 1.14.3 1.14.2 1.14.0 1.13.0 1.12.1 1.12.0 1.11.0 1.10.1 1.10.0 1.9.0 1.8.6 1.8.5 1.8.4 1.8.3 1.8.2 1.8.0 1.7.1 1.7.0 1.6.6 retired 1.6.5 1.6.4 retired 1.6.3 1.6.2 1.6.1 1.6.0 1.5.7 1.5.6 1.5.5 1.5.4 1.5.3 1.5.2 1.5.1 1.5.0 1.4.10 1.4.8 1.4.7 1.4.6 1.4.5 1.4.4 1.4.3 1.4.2 1.4.1 1.4.0 1.3.2 1.3.1 1.3.0 1.2.0 1.1.0 1.0.6 1.0.5 1.0.2 1.0.1 0.15.2 0.15.0 0.14.3 0.14.2 0.14.1 0.14.0 0.13.1

Simple HTTP client with HTTP/1.1, HTTP/2, and HTTP/3 support

Retired package: Release invalid - Use 3.0.1 instead

Security advisory: This version has known vulnerabilities. View advisories

HexDocs

Current section

Files

Jump to

Readme 116 Versions 6 Dependencies Dependants 12 Advisories Files Activity

hackney c_src lsquic src liblsquic lsquic_set.c

Raw

c_src/lsquic/src/liblsquic/lsquic_set.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;
}

Operator	Description	Example
name:	Match package name. Supports * wildcards and repo/package form	name:phx* or name:hexpm/phoenix
description:	Full-text search of package descriptions	description:auth
depends:	Packages depending on a given package. Supports repo:package form	depends:ecto or depends:hexpm:ecto
build_tool:	Filter by build tool	build_tool:mix
updated_after:	Packages updated after an ISO8601 datetime	updated_after:2025-01-01T00:00:00Z
extra:	Match custom metadata (key,value). Nested keys are separated by commas	extra:license,MIT