File size: 3,197 Bytes
e05eed1 98a67a0 |
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 151 152 153 154 155 156 157 158 |
// SPDX-FileCopyrightText: Copyright (c) 2025, NVIDIA CORPORATION & AFFILIATES. All rights reserved.
// SPDX-License-Identifier: Apache-2.0
#pragma once
#include <cstdlib>
#include <memory>
#include <vector>
#include <unordered_map>
#include <list>
typedef int32_t token_t;
class Prefix;
// typedef std::shared_ptr<Prefix> PrefixPtr;
class Prefix
{
public:
token_t Token;
Prefix *Parent;
Prefix(token_t token = 0 /* blank */, Prefix *parent = nullptr)
: Token(token), Parent(parent)
{}
std::vector<token_t> ToList() const;
size_t size() const;
};
///// Borrowed from Boost libraries
template<typename T>
void hash_combine(size_t & seed, T const& v)
{
seed ^= std::hash<T>()(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
/////
namespace std {
template<>
struct hash<Prefix*>
{
size_t operator()(const Prefix *p) const noexcept
{
size_t seed = 0;
while (p) {
if (p->Token != 0) {
hash_combine(seed, p->Token);
}
p = p->Parent;
}
return seed;
}
};
template<>
struct hash<tuple<Prefix*, token_t>>
{
size_t operator()(const tuple<Prefix*, token_t> &t) const noexcept
{
size_t seed = 0;
hash_combine(seed, get<0>(t));
hash_combine(seed, get<1>(t));
return seed;
}
};
template<>
struct equal_to<Prefix*>
{
bool operator()(const Prefix *a, const Prefix *b) const noexcept
{
while (a != nullptr && b != nullptr) {
if (a->Token != b->Token) {
return false;
}
a = a->Parent;
b = b->Parent;
}
// If one chain is shorter than the other
return a == b;
}
};
}
inline size_t Prefix::size() const
{
size_t ret = 0;
auto p = this;
while (p != nullptr) {
ret += 1;
p = p->Parent;
}
return ret;
}
class PrefixAllocator
{
public:
PrefixAllocator() = default;
~PrefixAllocator();
template<typename ...Args>
Prefix *GetPrefix(Args&& ...ctorArgs);
private:
void AllocateNextBuffer();
std::list<Prefix*> m_buffers;
size_t m_allocSize = 0;
size_t m_currOff = 0;
};
inline PrefixAllocator::~PrefixAllocator()
{
for (auto p : m_buffers) {
// Prefix is a POD, and are allocated without initializing
// to prevent redundant work upfront
// delete[] p;
free(p);
}
}
inline void PrefixAllocator::AllocateNextBuffer()
{
size_t nextSize = m_allocSize == 0 ? 1000 : 2 * m_allocSize;
// Using malloc here to prevent the ctor of Prefix being called for each item.
// Instead, the ctor will be called upon first access using GetPrefix
auto pBuff = reinterpret_cast<Prefix*>(malloc(sizeof(Prefix) * nextSize));
m_buffers.push_back(pBuff);
m_allocSize = nextSize;
m_currOff = 0;
}
template<typename ...Args>
Prefix *PrefixAllocator::GetPrefix(Args&& ...ctorArgs)
{
if (m_currOff == m_allocSize) {
AllocateNextBuffer();
}
auto buff = m_buffers.back() + m_currOff;
auto ret = new (buff) Prefix(std::forward<Args>(ctorArgs)...);
++m_currOff;
return ret;
}
|