#pragma once
#ifndef __AUTO_FREE_LIST__
#define __AUTO_FREE_LIST__
#include "Configuration.h"
#include "Definitions.h"
#include "Range.h"
namespace Auto {
class Subzone;
class FreeListNode : public Preallocated {
private:
FreeListNode *_prev; FreeListNode *_next; usword_t _size; bool _purged;
static FreeListNode *flip(FreeListNode *node) { return (FreeListNode *)(uintptr_t(node) ^ all_ones); }
public:
FreeListNode(FreeListNode *prev, FreeListNode *next, usword_t size) {
set_prev(prev);
set_next(next);
set_size(size);
if (size >= allocate_quantum_medium) _purged = false;
}
FreeListNode() {
set_prev(NULL);
set_next(NULL);
ASSERTION(size() == size_again());
}
FreeListNode *prev() const { return flip(_prev); }
FreeListNode *next() const { return flip(_next); }
usword_t size() const { return _size; }
usword_t size_again() { return *(usword_t *)displace(this, _size - sizeof(usword_t)); }
void set_prev(FreeListNode *prev) { _prev = flip(prev); }
void set_next(FreeListNode *next) { _next = flip(next); }
bool is_purged() const { ASSERTION(_size >= allocate_quantum_medium); return _purged; }
void set_purged(bool purged) { ASSERTION(_size >= allocate_quantum_medium); _purged = purged; }
void validate() { ASSERTION(size() == size_again()); }
void *address() const { return (void *)this; }
void set_size(usword_t size) {
_size = size;
*(usword_t *)displace(this, _size - sizeof(usword_t)) = size;
}
FreeListNode *prior_node() {
usword_t *end_size = (usword_t *)displace(this, -sizeof(usword_t));
return (FreeListNode *)displace(this, -(*end_size));
}
void *next_block() { return displace(this, _size); }
Range purgeable_range() {
Range r(align_up(displace(this, sizeof(FreeListNode))), align_down(displace(this, _size - sizeof(usword_t) - 1)));
return r;
}
};
class FreeList {
private:
FreeListNode *_head; FreeListNode *_tail;
public:
FreeList()
: _head(NULL), _tail(NULL)
{}
FreeListNode *head() const { return _head; }
FreeListNode *pop() {
FreeListNode *node = _head;
if (node) {
_head = node->next();
if (_head) {
_head->set_prev(NULL);
} else {
_tail = NULL;
}
}
return node;
}
void push(void *address, usword_t size) {
FreeListNode *node = new(address) FreeListNode(NULL, _head, size);
if (_head) {
_head->set_prev(node);
} else {
_tail = node;
}
_head = node;
}
void append(FreeListNode *node) {
node->set_prev(_tail);
if (!_head) {
_head = node;
} else {
_tail->set_next(node);
}
_tail = node;
}
void remove(FreeListNode *node) {
FreeListNode *prev = node->prev();
if (prev) {
FreeListNode *next = node->next();
prev->set_next(next);
if (next) {
next->set_prev(prev);
} else {
_tail = prev;
}
} else {
pop();
}
}
void insert(void *address, usword_t size) {
FreeListNode *prevNode = NULL, *nextNode = _head;
while (nextNode != NULL) {
if (uintptr_t(address) < uintptr_t(nextNode)) break;
prevNode = nextNode;
nextNode = nextNode->next();
}
FreeListNode *node = new(address) FreeListNode(prevNode, nextNode, size);
if (nextNode) nextNode->set_prev(node);
if (prevNode) prevNode->set_next(node);
if (_head == nextNode) _head = node;
if (_tail == prevNode) _tail = node;
}
void reset() {
_head = NULL;
_tail = NULL;
}
};
};
#endif // __AUTO_FREE_LIST__