bg3se/CoreLib/Base/PagedMap.h at main · Norbyte/bg3se · GitHub

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#pragma once

#include <CoreLib/Base/PagedArray.h>

BEGIN_SE()

template <class TKey, class TAllocator = DefaultPagedAllocator>
struct PagedHashSet : protected TAllocator
{
    inline PagedHashSet(uint16_t bitsPerPage, TAllocator const& allocator = TAllocator{})
        : TAllocator(allocator),
        hashLayout_(bitsPerPage),
        keyLayout_(bitsPerPage)
    {}

    int32_t** hash_{ nullptr };
    int32_t** nextIds_{ nullptr };
    TKey** keys_{ nullptr };
    PageLayout hashLayout_;
    PageLayout keyLayout_;
    uint32_t hashSize_{ 0 };
    uint32_t keysSize_{ 0 };

    int find_index(TKey const& key) const
    {
        if (hashSize_ == 0) return -1;

        auto hash = (uint32_t)(HashMapHash(key) % hashSize_);
        auto keyIndex = *hashLayout_.at(hash_, hash);
        while (keyIndex >= 0) {
            auto keyBucket = keyIndex >> keyLayout_.BitsPerPage;
            auto keySlot = keyIndex & (keyLayout_.bucket_size() - 1);
            if (keys_[keyBucket][keySlot] == key) return keyIndex;
            keyIndex = nextIds_[keyBucket][keySlot];
        }

        return -1;
    }

    int insert(TKey const& key)
    {
        auto index = find_index(key);
        if (index != -1) {
            return index;
        }

        auto keyIdx = keysSize_++;

        if (keyIdx >= keyLayout_.capacity()) {
            auto layout = keyLayout_;
            PagedOps<int32_t, TAllocator>::Resize(keyIdx + 1, nextIds_, layout, *this);
            PagedOps<TKey, TAllocator>::Resize(keyIdx + 1, keys_, keyLayout_, *this);
        }

        *keyLayout_.at(keys_, keyIdx) = key;
        *keyLayout_.at(nextIds_, keyIdx) = -1;

        if (hashSize_ >= keysSize_ + (keysSize_ >> 1)) {
            hash_insert(key, keyIdx);
        } else {
            rehash(keysSize_ + (keysSize_ >> 1));
        }

        return (int)keyIdx;
    }

private:
    void hash_insert(TKey const& key, int keyIdx)
    {
        auto hash = (uint32_t)(HashMapHash(key) % hashSize_);
        auto prevKeyIdx = *hashLayout_.at(hash_, hash);
        if (prevKeyIdx < 0) {
            prevKeyIdx = -2 - (int)hash;
        }

        *keyLayout_.at(nextIds_, keyIdx) = prevKeyIdx;
        *hashLayout_.at(hash_, hash) = keyIdx;
    }

    void rehash(uint32_t size)
    {
        auto hashSize = GetNearestMultiHashMapPrime(size);
        PagedOps<int32_t, TAllocator>::Resize(hashSize, hash_, hashLayout_, *this);
        hashSize_ = hashSize;
        for (uint32_t i = 0; i < hashSize_; i++) {
            *hashLayout_.at(hash_, i) = -1;
        }

        for (uint32_t i = 0; i < keysSize_; i++) {
            hash_insert(*keyLayout_.at(keys_, i), i);
        }
    }
};


template <class TKey, class TValue, class TAllocator = DefaultPagedAllocator>
struct PagedHashMap : public PagedHashSet<TKey, TAllocator>
{
    inline PagedHashMap(uint16_t bitsPerPage, TAllocator const& allocator = TAllocator{})
        : PagedHashSet<TKey, TAllocator>(bitsPerPage, allocator),
        Values(bitsPerPage, allocator)
    {}

    PagedArray<TValue, TAllocator> Values;

    inline TAllocator const& allocator() const
    {
        return static_cast<TAllocator const&>(*this);
    }

    inline TKey const& key_at(uint32_t index) const
    {
        return *this->keyLayout_.at(this->keys_, index);
    }

    inline uint32_t size() const
    {
        return Values.size();
    }

    TValue* find(TKey const& key)
    {
        auto index = this->find_index(key);
        if (index < 0) return nullptr;

        return &Values[index];
    }

    TValue const* find(TKey const& key) const
    {
        auto index = this->find_index(key);
        if (index < 0) return nullptr;

        return &Values[index];
    }

    TValue* add_uninitialized(TKey const& key)
    {
        auto index = this->insert(key);
        return Values.add_uninitialized();
    }

    template <class... Args>
    TValue* add(TKey const& key, Args... args)
    {
        return new (add_uninitialized(key)) TValue(std::forward<Args>(args)...);
    }
};

END_SE()