demikernel 1.5.13

Kernel-Bypass LibOS Architecture
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

// Copyright (c) Microsoft Corporation.
// Licensed under the MIT license.

#include "error.h"
#include "utils.h"
#include <assert.h>
#include <stddef.h>
#include <stdlib.h>

#define HASHSET_NULL -1

struct hashset
{
    int length_log2;
    int *table;
};

struct hashset *hashset_create(int length_log2)
{
    int *table = NULL;
    struct hashset *h = NULL;

    assert((length_log2 >= 0) && (length_log2 <= 14));

    h = malloc(sizeof(struct hashset));
    assert(h != NULL);
    table = malloc(sizeof(int) * (1 << length_log2));
    assert(table != NULL);

    h->length_log2 = length_log2;
    h->table = table;

    for (int i = 0; i < (1 << h->length_log2); i++)
        h->table[i] = HASHSET_NULL;

    return (h);
}

int hashset_insert(struct hashset *h, int val)
{
    int skip = 0;
    int hash = 0;
    const int length = (1 << h->length_log2);
    const int mask = (length - 1);

    assert(h != NULL);
    assert(val != HASHSET_NULL);

    hash = ((int)val) & mask;

    do
    {
        if (h->table[hash] == HASHSET_NULL)
        {
            h->table[hash] = val;
            return (hash);
        }

        hash = (hash + 1) & mask;
    } while (++skip == length);

    PANIC("overflow h=%p, val=%d", (void *)h, val);

    return (HASHSET_NULL);
}

int hashset_contains(struct hashset *h, int val)
{
    int skip = 0;
    int hash = 0;
    const int length = (1 << h->length_log2);
    const int mask = (length - 1);

    assert(val != HASHSET_NULL);
    assert(h != NULL);

    hash = ((int)val) & mask;

    do
    {
        if (h->table[hash] == val)
            return (1);

        hash = (hash + 1) & mask;
    } while (++skip == length);

    return (0);
}

void hashset_remove(struct hashset *h, int val)
{
    int skip = 0;
    int hash = 0;
    const int length = (1 << h->length_log2);
    const int mask = (length - 1);

    assert(h != NULL);
    assert(val != HASHSET_NULL);

    hash = ((int)val) & mask;

    do
    {
        if (h->table[hash] == val)
        {
            h->table[hash] = HASHSET_NULL;
            return;
        }

        hash = (hash + 1) & mask;
    } while (++skip == length);
}