File obstackheap.h¶
File List > cubrid > src > heaplayers > heaps > special > obstackheap.h
Go to the documentation of this file
/* -*- C++ -*- */
/*
Heap Layers: An Extensible Memory Allocation Infrastructure
Copyright (C) 2000-2020 by Emery Berger
http://www.emeryberger.com
emery@cs.umass.edu
Heap Layers is distributed under the terms of the Apache 2.0 license.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
*/
// An "Obstack".
#ifndef HL_OBSTACKHEAP_H
#define HL_OBSTACKHEAP_H
#include <assert.h>
#include <new>
#include "utility/align.h"
namespace HL {
template <int ChunkSize, class SuperHeap>
class ObstackHeap : public SuperHeap {
private:
int m_chkSize;
public:
enum { Alignment = sizeof(double) };
ObstackHeap()
{
currentChunk = NULL;
m_chkSize = ChunkSize;
if (m_chkSize > 0)
{
// Get one chunk and set the current position marker.
currentChunk = makeChunk (NULL, m_chkSize);
currentBase = nextPos = (char *) (currentChunk + 1);
assert (isValid ());
}
}
~ObstackHeap() {
// Free every chunk.
assert (isValid());
ChunkHeader * ch = currentChunk;
while (ch != NULL) {
ChunkHeader * pch = ch->getPrevChunk();
// cout << "Freeing chunk " << ch << endl;
SuperHeap::free (ch);
ch = pch;
}
}
inline void reset (const int chkSize)
{
m_chkSize = chkSize;
if (m_chkSize > 0 && currentChunk == NULL)
{
// Get one chunk and set the current position marker.
currentChunk = makeChunk (NULL, m_chkSize);
currentBase = nextPos = (char *) (currentChunk + 1);
assert (isValid ());
}
}
// "Grow" the current object.
// Returns a point in the object just before the current "grow".
inline void * grow (size_t sz) {
// If we've grown beyond the confines of this chunk,
// get a new one.
assert (isValid());
if ((int) ((char *) currentChunk->getLimit() - (char *) nextPos) < sz) {
ChunkHeader * newCurrent = copyToNew(sz);
if (newCurrent == NULL)
return NULL;
#if 0
// Now delete the previous chunk if this was the only object in it.
if (deleteChunk != NULL) {
SuperHeap::free (deleteChunk);
}
#endif
assert (isValid());
}
assert (((int) ((char *) currentChunk->getLimit() - (char *) nextPos) >= sz));
assert ((char *) (sz + nextPos) <= currentChunk->getLimit());
// Bump the pointer for the next object.
void * prevNextPos = nextPos;
nextPos += sz;
assert (isValid());
return prevNextPos;
}
inline void * malloc (size_t sz) {
assert (isValid());
if (currentChunk == NULL) {
return NULL;
}
//sz = align(sz > 0 ? sz : 1);
// If this object can't fit in the current chunk,
// get another one.
if ((ptrdiff_t) ((char *) currentChunk->getLimit() - (char *) nextPos) < (ptrdiff_t) sz) {
// Allocate a chunk that's large enough to hold the requested size.
currentChunk = makeChunk (currentChunk, sz);
if (currentChunk == NULL) {
return NULL;
}
currentBase = nextPos = (char *) (currentChunk + 1);
assert (isValid());
}
assert (((ptrdiff_t) ((char *) currentChunk->getLimit() - (char *) nextPos) >= (ptrdiff_t) sz));
assert ((char *) (sz + nextPos) <= currentChunk->getLimit());
// Bump the pointers forward.
currentBase = nextPos;
nextPos += sz;
void * ptr = currentBase;
finalize();
assert (isValid());
return (void *) ptr;
}
// Free everything allocated "after" ptr.
// NB: Freeing NULL safely empties the entire obstack.
inline void free (void * ptr) {
assert (isValid());
// Free every chunk until we find the one that this pointer is in.
// Then reset the current position to ptr.
while (currentChunk != NULL &&
(((char *) currentChunk > (char *) ptr) ||
((char *) currentChunk->getLimit() < (char *) ptr))) {
ChunkHeader * pch = currentChunk;
currentChunk = currentChunk->getPrevChunk();
SuperHeap::free (pch);
}
if (currentChunk != NULL) {
currentBase = nextPos = (char *) ptr;
assert (isValid());
} else {
if (ptr != NULL) {
// Something bad has happened -- we tried to free an item that
// wasn't in any chunk.
abort();
} else {
// Get one chunk.
currentChunk = makeChunk (NULL, m_chkSize);
currentBase = nextPos = (char *) (currentChunk + 1);
assert (isValid());
}
}
}
inline void * getObjectBase() {
assert (isValid());
return currentBase;
}
inline void finalize() {
assert (isValid());
nextPos = (char *) HL::align<Alignment> ((size_t) nextPos);
currentBase = nextPos;
assert (isValid());
}
private:
inline int objectSize() {
int diff = (int) (nextPos - currentBase);
assert (diff >= 0);
return diff;
}
int isValid() {
// Verify class invariants.
#ifndef NDEBUG
bool c1 = (currentBase <= nextPos);
assert (c1);
bool c2 = (nextPos <= currentChunk->getLimit());
assert (c2);
bool c3 = ((char *) currentChunk <= currentChunk->getLimit());
assert (c3);
bool c4 = ((char *) currentChunk <= currentBase);
assert (c4);
bool c5 = (currentChunk != currentChunk->getPrevChunk());
assert (c5);
bool c6 = (objectSize() >= 0);
assert (c6);
return (c1 && c2 && c3 && c4 && c5 && c6);
#else
return 1;
#endif
}
// The header for every chunk.
class ChunkHeader {
public:
inline ChunkHeader (ChunkHeader * prev, size_t sz)
: _pastEnd ((char *) (this + 1) + sz),
_prevChunk (prev)
{}
// Return the end of the current chunk.
inline char * getLimit() { return _pastEnd; }
// Return the previous chunk.
inline ChunkHeader * getPrevChunk() { return _prevChunk; }
private:
// Just past the end of this chunk.
char * _pastEnd;
// Address of prior chunk.
ChunkHeader * _prevChunk;
};
// Make a new chunk of at least sz bytes.
inline ChunkHeader * makeChunk (ChunkHeader * ch, size_t sz) {
// Round up the allocation size to at least one chunk.
size_t allocSize
= HL::align<Alignment>((sz > m_chkSize - sizeof(ChunkHeader)) ? sz : m_chkSize - sizeof(ChunkHeader));
// Make a new chunk.
void * ptr = SuperHeap::malloc (sizeof(ChunkHeader) + allocSize);
if (ptr == NULL) {
return NULL;
}
ChunkHeader * newChunk
= new (ptr) ChunkHeader (ch, allocSize);
return newChunk;
}
// Copy the current object to a new chunk.
// sz = the minimum amount of extra space we need.
inline ChunkHeader * copyToNew (size_t sz) {
size_t obj_size = objectSize();
size_t new_size = obj_size + sz + (obj_size >> 3) + 100;
//size_t new_size = 2 * (obj_size + sz);
ChunkHeader * newChunk;
#if 0
// This variable will hold the chunk to be deleted (if any).
ChunkHeader * deleteChunk = NULL;
// If this object was the only one in the chunk,
// link back past this chunk.
if (currentBase == (char *) (currentChunk + 1)) {
newChunk = makeChunk (currentChunk->getPrevChunk(), new_size);
deleteChunk = currentChunk;
} else {
newChunk = makeChunk (currentChunk, new_size);
}
#else
newChunk = makeChunk (currentChunk, new_size);
#endif
if (newChunk == NULL) {
currentChunk = NULL;
return NULL;
}
// Copy the current object to the new chunk.
memcpy ((char *) (newChunk + 1), currentBase, obj_size);
currentChunk = newChunk;
currentBase = (char *) (currentChunk + 1);
nextPos = currentBase + obj_size;
#if 0
if (deleteChunk != NULL) {
SuperHeap::free (deleteChunk);
}
#endif
return currentChunk;
}
// Current position in the current chunk.
char * currentBase;
// Where to add the next character to the current object.
char * nextPos;
// My current chunk.
ChunkHeader * currentChunk;
};
}
#endif