I've written a code that accumulates unnecessary memory space and gives it back when needed, organizing it as a stack (customers' requirements are strange).
void* stack = nullptr;
template <typename P>
void push(P* p) {
// reinterpret memory space of *p as a storage for the address of the top element of the stack;
*reinterpret_cast<void**>(p) = stack;
// now *p is the top element, so update stack to point to *p;
stack = p;
}
template <typename P>
P* pop() {
if (stack == nullptr) throw;
// get the address of the top element
P* p = static_cast<P*>(stack);
// now stack should point to the next element after *p, which address is stored in *p's memory space
stack = *reinterpret_cast<void**>(stack);
return p;
}
stack is a pointer to the top element. When a new memory space is pushed its first 8 bytes are used for storing the address of the previous element, stack is updated. A simple stack chain.
While I was trying to achieve this behavior the compiler often said this (I know that some memory manipulations are illegal):
assignment to cast is illegal, lvalue casts are not supported
I want to know whether my implementation is legal now or not?
#include <iostream>
#include <bitset>
constexpr size_t bytes_8 = 8 * 8;
constexpr size_t bytes_20 = 8 * 20;
constexpr size_t bytes_50 = 8 * 50;
// we assume that std::bitset holds its data contigiously in the beginning
struct A {
std::bitset<bytes_8> bits;
};
struct B {
std::bitset<bytes_20> bits;
};
struct C {
std::bitset<bytes_50> bits;
};
int main() {
// Imagine they were allocated on heap:
A a; B b; C c;
std::cout << "Addresses" << '\n'
<< "a: " << &a << "\t"
<< "b: " << &b << "\t"
<< "c: " << &c
<< std::endl << std::endl << std::endl;
push<A>(&a);
std::cout << "---------- push<A>(&a) ----------\n"
<< "'a' is the top element (and the only one), so 'stack' points to it,\n"
<< "meanwhile 'a' stores the address of the previous element (none)\n\n"
<< "stack: " << stack << "\ta.bits: " << std::hex << a.bits.to_ullong()
<< std::endl << std::endl;
push<B>(&b);
std::cout << "---------- push<B>(&b) ----------\n"
<< "now 'b' is the top element, so 'stack' updates to point to it,\n"
<< "'b' stores the address of the previous element (a)\n\n"
<< "stack: " << stack << "\tb.bits: " << std::hex << b.bits.to_ullong()
<< std::endl << std::endl;
push<C>(&c);
std::cout << "---------- push<C>(&c) ----------\n"
<< "finally 'c' is the top element and 'stack' points to it,\n"
<< "'c' stores the address of the previous element (b)\n\n"
<< "stack: " << stack << "\tc.bits: " << std::hex << c.bits.to_ullong()
<< std::endl << std::endl << std::endl;
auto p1 = pop<C>();
std::cout << "---------- pop<C>() ----------\n"
<< "'b' is the top element and the next one after it is 'a'\n\n"
<< "ret: " << p1 << "\nstack: " << stack << "\tb.bits: " << std::hex << b.bits.to_ullong()
<< std::endl << std::endl;
auto p2 = pop<B>();
std::cout << "---------- pop<B>() ----------\n"
<< "'a' is the top element and the last one in the stack\n\n"
<< "ret: " << p2 << "\nstack: " << stack << "\ta.bits: " << std::hex << a.bits.to_ullong()
<< std::endl << std::endl;
auto p3 = pop<A>();
std::cout << "---------- pop<A>() ----------\n"
<< "the stack is empty\n\n"
<< "ret: " << p3 << "\nstack: " << "0x" << stack
<< std::endl << std::endl;
return 0;
}
Addresses
a: 0x7fffffffdc20 b: 0x7fffffffdc40 c: 0x7fffffffdc60
---------- push<A>(&a) ----------
'a' is the top element (and the only one), so 'stack' points to it,
meanwhile 'a' stores the address of the previous element (none)
stack: 0x7fffffffdc20 a.bits: 0
---------- push<B>(&b) ----------
now 'b' is the top element, so 'stack' updates to point to it,
'b' stores the address of the previous element (a)
stack: 0x7fffffffdc40 b.bits: 7fffffffdc20
---------- push<C>(&c) ----------
finally 'c' is the top element and 'stack' points to it,
'c' stores the address of the previous element (b)
stack: 0x7fffffffdc60 c.bits: 7fffffffdc40
---------- pop<C>() ----------
'b' is the top element and the next one after it is 'a'
ret: 0x7fffffffdc60
stack: 0x7fffffffdc40 b.bits: 7fffffffdc20
---------- pop<B>() ----------
'a' is the top element and the last one in the stack
ret: 0x7fffffffdc40
stack: 0x7fffffffdc20 a.bits: 0
---------- pop<A>() ----------
the stack is empty
ret: 0x7fffffffdc20
stack: 0x0
You can re-use the storage of objects once their lifetime ends, but you really should track the sizes.
struct frame {
frame * ptr;
std::size_t size;
};
frame* stack = nullptr;
template <typename P>
requires sizeof(P) >= sizeof frame
void push(P* obj) {
p->~P();
stack = new(p) frame{ stack, sizeof(P) };
}
template <typename P, typename... Args>
P* pop(Args&&... args) {
if (stack == nullptr || stack->size != sizeof(P)) throw std::bad_alloc{};
frame * top = stack;
stack = stack->ptr;
top->~frame();
return new(top) P(std::forward<Args>(args)...);
}
But even if you do this, I would profile whether this scheme has any improvement over normal allocations. Most likely, you are adding a whole pile of restrictions to how you can allocate, for a negligible or possibly negative performance benefit.