/*
 * MemDebug.cpp
 *
 *  Created on: Apr 28, 2010
 *      Author: crueger
 */

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <boost/thread.hpp>

using namespace std;

#ifndef NDBEGUG
#ifndef NO_MEMDEBUG

namespace Memory {

  // This struct is added before each memory chunk
  // and contains tracking information. Anything used
  // to track memory cannot use any dynamic memory, so
  // we have to resort to classic C-idioms here.
  // This struct also contains pointers to the next
  // an previous chunks to allow fast traversion of
  // all allocated memory blocks
  struct entry_t {
    // we seperate the tracking info from the rest
    // A checksum will be calculated for this part of
    // the struct, so the information in here should
    // not change during the lifetime of the memory
    struct info_t {
      enum {length = 64};
      char file[length+1];
      int line;
      size_t nbytes;
      bool isUsed;
      void *location;
    } info;
    bool isIgnored;
    char checksum;
    entry_t *prev;
    entry_t *next;
  };

  boost::mutex memorylock;

  // start and end of the doubly-linked list
  entry_t *begin=0;
  entry_t *end=0;

  // current amount of allocated memory
  size_t state = 0;
  // maximum amount of allocated memory
  size_t max = 0;
  // number of allocations that have been done so far
  unsigned int allocs = 0;


  // this sets the alignment of the returned memory block
  // malloc guarantees an alignment at the 8 byte border,
  // so we just do the same
  const int alignment = 8;

  // calculates a simple checksum for the info block
  // the checksum is used to find memory corruptions
  inline char calcChecksum(entry_t::info_t *info){
    char *buffer = (char*)info;
    char checksum =0;
    for(size_t i=0;i<sizeof(entry_t::info_t);i++){
      checksum+=buffer[i];
    }
    return checksum;
  }

  // gets the next alignet point which is greater than nbytes
  // this function is only called a fixed number of times, so
  // there is no need to optimize
  inline size_t doAlign(size_t nbytes){
    int nonaligned = nbytes % alignment;
    if(nonaligned) {
     return(nbytes - nonaligned + alignment);
    }
    else{
      return nbytes;
    }
  }

  // Output some state information
  void getState(){
    cout << "Maximum allocated Memory: " << max << " bytes" << endl;
    cout << "Currently allocated Memory: " << state <<" bytes" << endl;
    cout << allocs << " allocated chunks total" << endl;

    // simple traversal of the chunk list
    for(entry_t *pos=begin;pos;pos=pos->next){
      cout << "\nChunk of " << pos->info.nbytes << " bytes" << " still available" << endl;
      cout << "Chunk reserved at: " << pos->info.file << ":" << pos->info.line << endl;
    }
  }

  // Deletes an entry from the linked list
  void deleteEntry(entry_t *entry){
    if(entry->isIgnored)
      return;

    if(entry->prev){
      entry->prev->next = entry->next;
    }
    else{
      // this node was the beginning of the list
      begin = entry->next;
    }

    if(entry->next){
      entry->next->prev = entry->prev;
    }
    else{
      // this node was the end of the list
      end = entry->prev;
    }
    entry->isIgnored = true;
    Memory::state  -= entry->info.nbytes;
  }

  void _ignore(void *ptr){
    // just deletes the node from the list, but leaves the info intact
    static const size_t entrySpace = Memory::doAlign(sizeof(Memory::entry_t));
    entry_t *entry = (Memory::entry_t*)((char*)ptr-entrySpace);
    deleteEntry(entry);
  }
}

void *operator new(size_t nbytes,const char* file, int line) throw(std::bad_alloc) {

  // we need to lock, so that no one changes the linked list while we are here
  boost::mutex::scoped_lock guard(Memory::memorylock);

  // to avoid allocations of 0 bytes if someone screws up
  // allocation with 0 byte size are undefined behavior, so we are
  // free to handle it this way
  if(!nbytes) {
    nbytes = 1;
  }

  // get the size of the entry, including alignment
  static const size_t entrySpace = Memory::doAlign(sizeof(Memory::entry_t));

  void *res;
  if(!(res=malloc(entrySpace + nbytes))){
    // new must throw, when space is low
    throw std::bad_alloc();
  }

  // we got the space, so update the global info
  Memory::state += nbytes;
  if(Memory::state>Memory::max){
    Memory::max = Memory::state;
  }
  Memory::allocs++;

  // build the entry in front of the space
  Memory::entry_t *entry = (Memory::entry_t*) res;
  memset(res,0,entrySpace);
  entry->info.nbytes = nbytes;
  entry->info.isUsed = true;
  strncpy(entry->info.file,file,Memory::entry_t::info_t::length);
  entry->info.file[Memory::entry_t::info_t::length] = '\0';
  entry->info.line=line;
  // the space starts behind the info
  entry->info.location = (char*)res + entrySpace;

  // add the entry at the end of the list
  entry->next=0;            // the created block is last in the list
  entry->prev=Memory::end;  // the created block is last in the list
  if(!Memory::begin){
    // the list was empty... start a new one
    Memory::begin=entry;
  }
  else {
    // other blocks present... we can add to the last one
    Memory::end->next=entry;
  }
  Memory::end=entry;

  // get the checksum...
  entry->checksum = Memory::calcChecksum(&entry->info);
  // this will be set to true, when the block is removed from
  // the list for any reason
  entry->isIgnored = false;

  // ok, space is prepared... the user can have it.
  // the rest (constructor, deleting when something is thrown etc)
  // is handled automatically
  return entry->info.location;
}

void *operator new(size_t nbytes) throw(std::bad_alloc) {
  // Just forward to the other operator, when we do not know from
  // where the allocation came
  return operator new(nbytes,"Unknown",0);
}

void *operator new[] (size_t nbytes,const char* file, int line) throw(std::bad_alloc) {
  // The difference between new and new[] is just for compiler bookkeeping.
  return operator new(nbytes,file,line);
}

void *operator new[] (size_t nbytes) throw(std::bad_alloc) {
  // Forward again
  return operator new[] (nbytes,"Unknown",0);
}

void operator delete(void *ptr) throw() {
  if(!ptr){
    cerr << "Warning: Deleting NULL pointer" << endl;
    return;
  }

  // we need to lock, so the linked list does not changed while we are in here
  boost::mutex::scoped_lock guard(Memory::memorylock);

  // get the size for the entry, including alignment
  static const size_t entrySpace = Memory::doAlign(sizeof(Memory::entry_t));

  // get the position for the entry from the pointer the user gave us
  Memory::entry_t *entry = (Memory::entry_t*)((char*)ptr-entrySpace);

  // let's see if the checksum is still matching
  if(Memory::calcChecksum(&entry->info)!=entry->checksum){
    cerr << "Possible memory corruption detected!" << endl;
    cerr << "Trying to recover allocation information..." << endl;
    cerr << "Memory was allocated at " << entry->info.file << ":" << entry->info.line << endl;
    terminate();
  }

  // this will destroy the checksum, so double deletes are caught
  entry->info.isUsed = false;
  Memory::deleteEntry(entry);

  // delete the space reserved by malloc
  free((char*)ptr-entrySpace);
}

// operator that is called when the constructor throws
// do not call manually
void operator delete(void *ptr,const char*, int) throw() {
  operator delete(ptr);
}

void operator delete[](void *ptr){
  // again difference between delete and delete[] is just in compiler bookkeeping
  operator delete(ptr);
}

// and another operator that can be called when a constructor throws
void operator delete[](void *ptr,const char*, int) throw(){
  operator delete(ptr);
}
#endif
#endif