/* -*- C++ -*- */

/*

  Heap Layers: An Extensible Memory Allocation Infrastructure
  
  Copyright (C) 2000-2003 by Emery Berger
  http://www.cs.umass.edu/~emery
  emery@cs.umass.edu
  
  This program is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation; either version 2 of the License, or
  (at your option) any later version.
  
  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.
  
  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

*/

// An "Obstack".

#ifndef _HLOBSTACK_H_
#define _HLOBSTACK_H_

#ifdef __cplusplus

#include <assert.h>
#include <new>
#include <string.h>

namespace HL {

template <int ChunkSize, class SuperHeap>
class ObstackHeap : public SuperHeap {
private:
  int chkSize;
public:

  ObstackHeap (void)
  {
    currentChunk = NULL;
    chkSize = ChunkSize;

    if (chkSize > 0)
      {
        // Get one chunk and set the current position marker.
        currentChunk = makeChunk (NULL, chkSize);
        currentBase = nextPos = (char *) (currentChunk + 1);
        assert (isValid());
      }
  }

  ~ObstackHeap (void) {
    // 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_) {
    chkSize = chkSize_;
    if (chkSize > 0 && currentChunk == NULL)
      {
        // Get one chunk and set the current position marker.
        currentChunk = makeChunk (NULL, chkSize);
        currentBase = nextPos = (char *) (currentChunk + 1);
        assert (isValid());
      } 
  }

#if 0 /* DO NOT DELETE ME FOR FUTURE USE */
  inline void clear (void) {
    // 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;
    }

    currentChunk = NULL;
    if (chkSize > 0)
      {
        // Get one chunk and set the current position marker.
        currentChunk = makeChunk (NULL, chkSize);
        currentBase = nextPos = (char *) (currentChunk + 1);
        assert (isValid());
      }
  }
#else
  inline void clear (void) {
    // Free every chunk except the last one
    assert (isValid());
    ChunkHeader * ch, * pch;
    for (ch = currentChunk, pch = (ch) ? ch->getPrevChunk() : NULL;
         pch != NULL;
         ch = pch, pch = (ch) ? ch->getPrevChunk() : NULL) {
      // cout << "Freeing chunk " << ch << endl;
      SuperHeap::free (ch);
    }
    // Reset the last chunk
    currentChunk = ch;
    if (currentChunk != NULL) {
      currentBase = nextPos = (char *) (currentChunk + 1);
    } else {
      if (chkSize > 0)
        {
          // Get one chunk and set the current position marker.
          currentChunk = makeChunk (NULL, chkSize);
          currentBase = nextPos = (char *) (currentChunk + 1);
          assert (isValid());
        }
    }
  }
#endif

  // "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 ((int) ((char *) currentChunk->getLimit() - (char *) nextPos) < 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 (((int) ((char *) currentChunk->getLimit() - (char *) nextPos) >= 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, chkSize);
	currentBase = nextPos = (char *) (currentChunk + 1);
	assert (isValid());
      }
    }
  }


  inline void * getObjectBase (void) {
    assert (isValid());
    return currentBase;
  }


  inline void finalize (void) {
    assert (isValid());
    nextPos = (char *) align((int) nextPos);
    currentBase = nextPos;
    assert (isValid());
  }


private:


  inline int objectSize (void) {
    int diff = (int) (nextPos - currentBase);
    assert (diff >= 0);
    return diff;
  }


  int isValid (void) {
    // 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 (void) { return _pastEnd; }

    // Return the previous chunk.
    inline ChunkHeader * getPrevChunk (void) { return _prevChunk; }

  private:
    // Just past the end of this chunk.
    char * _pastEnd;

    // Address of prior chunk.
    ChunkHeader * _prevChunk;
  };


  inline static size_t align (int sz) {
    return (sz + (sizeof(double) - 1)) & ~(sizeof(double) - 1);
  }

  // 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
      = align((sz > chkSize - sizeof(ChunkHeader)) ? sz : 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 // __cplusplus

#endif // _HLOBSTACK_H_