lbug 0.16.1

An in-process property graph database management system built for query speed and scalability
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

#pragma once

#include <array>
#include <cstdint>
#include <cstring>
#include <type_traits>

#include "common/assert.h"
#include "common/constants.h"
#include "common/types/types.h"
#include <bit>

namespace lbug {
namespace storage {

using entry_pos_t = uint8_t;
using slot_id_t = uint64_t;

class SlotHeader {
public:
    static const entry_pos_t INVALID_ENTRY_POS = UINT8_MAX;
    static const slot_id_t INVALID_OVERFLOW_SLOT_ID = UINT64_MAX;
    // For a header of 32 bytes.
    // This is smaller than the possible number of entries with an 1-byte key like uint8_t,
    // but the additional size would limit the number of entries for 8-byte keys, so we
    // instead restrict the capacity to 20
    static constexpr uint8_t FINGERPRINT_CAPACITY = 20;

    SlotHeader() : fingerprints{}, validityMask{0}, nextOvfSlotId{INVALID_OVERFLOW_SLOT_ID} {}

    void reset() {
        validityMask = 0;
        nextOvfSlotId = INVALID_OVERFLOW_SLOT_ID;
    }

    inline bool isEntryValid(uint32_t entryPos) const {
        return validityMask & ((uint32_t)1 << entryPos);
    }
    inline void setEntryValid(entry_pos_t entryPos, uint8_t fingerprint) {
        validityMask |= ((uint32_t)1 << entryPos);
        fingerprints[entryPos] = fingerprint;
    }
    inline void setEntryInvalid(entry_pos_t entryPos) {
        validityMask &= ~((uint32_t)1 << entryPos);
    }

    inline entry_pos_t numEntries() const { return std::popcount(validityMask); }

public:
    std::array<uint8_t, FINGERPRINT_CAPACITY> fingerprints;
    uint32_t validityMask;
    slot_id_t nextOvfSlotId;
};
static_assert(std::has_unique_object_representations_v<SlotHeader>);

template<typename T>
struct SlotEntry {
    SlotEntry(T _key, common::offset_t _value) : key{std::move(_key)}, value{_value} {
        // Zero padding, if any
        if constexpr (sizeof(T) + sizeof(common::offset_t) < sizeof(SlotEntry<T>)) {
            auto padding = sizeof(SlotEntry<T>) - sizeof(T) - sizeof(common::offset_t);
            memset(reinterpret_cast<uint8_t*>(&key) + sizeof(T), 0, padding);
            // Assumes that all the padding follows the key
            DASSERT((std::byte*)&key + sizeof(key) + padding == (std::byte*)&value);
        }
    }
    SlotEntry() : SlotEntry(T{}, 0) {}

    T key;
    common::offset_t value;
};

template<typename T>
static constexpr uint8_t getSlotCapacity() {
    return std::min((common::HashIndexConstants::SLOT_CAPACITY_BYTES - sizeof(SlotHeader)) /
                        sizeof(SlotEntry<T>),
        static_cast<size_t>(SlotHeader::FINGERPRINT_CAPACITY));
}

template<typename T>
struct Slot {
    Slot() : header{}, entries{} {}
    SlotHeader header;
    std::array<SlotEntry<T>, getSlotCapacity<T>()> entries;
};

} // namespace storage
} // namespace lbug