#include "disk_tools.h"
#include "d_alloc.h"
#include <string>
#include <map>
#include <vector>


using namespace std;

namespace disk_tools {

//d_alloc * global_alloc_ptr = 0;

void d_alloc::insert(d_alloc_node & node) {
   offset_type temp, prev;
   file.seekg(0L, ios::beg);
   file >> temp;
   d_alloc_node n,last;
   last.addr = -1L;
   bool first;
   if(temp != -1L) {
      first = true;
      while(temp != -1L) {
         file.seekg(temp, ios::beg);
         n.load(file);
         if(first) {
            if(node.size <= n.size) {
               file.seekg(0L, ios::beg);
               file << node.addr;
               node.next = temp;
               file.seekg(node.addr);
               node.store(file);
               break;
            }
            first = false;
         }
         else if(node.size <= n.size) {
            last.next = node.addr;
            node.next = n.addr;
            file.seekg(last.addr, ios::beg);
            last.store(file);
            file.seekg(node.addr, ios::beg);
            node.store(file);
            break;
         }
         else if(n.next == -1L) {
            n.next = node.addr;
            node.next = -1L;
            file.seekg(n.addr, ios::beg);
            n.store(file);
            file.seekg(node.addr, ios::beg);
            node.store(file);
            break;
         }
         last = n;
         temp = n.next;
      }
   }
   else {
      file.seekg(0L, ios::beg);
      file << node.addr;
      file.seekg(node.addr, ios::beg);
      node.next = -1L;
      node.store(file);
   }
}


void d_alloc::move_to_alloc_list(offset_type last, d_alloc_node & node)
{
   d_alloc_node n;
   if(last == sizeof(offset_type)) {
      file.seek(sizeof(offset_type));
      file << node.next;
   }
   else {
      file.seek(last);
      n.load(file);
      n.next = node.next;
      file.seek(last);
      n.store(file);
   }
   insert(node);
/*
   file.seek(0L);
   offset_type addr;
   file >> addr;
   node.next = addr;
   file.seek(node.addr);
   node.store(file);
   file.seek(0L);
   file << node.addr;
   //sort();
*/
}

void d_alloc::move_to_dealloc_list(offset_type last, d_alloc_node & node)
{
   d_alloc_node n;
   if(last == 0L) {
      file.seek(0L);
      file << node.next;
   }
   else {
      file.seek(last);
      n.load(file);
      n.next = node.next;
      file.seek(last);
      n.store(file);
   }
   file.seek(sizeof(offset_type));
   offset_type addr;
   file >> addr;
   node.next = addr;
   file.seek(node.addr);
   node.store(file);
   file.seek(sizeof(offset_type));
   file << node.addr;
   //sort();
}

d_alloc::d_alloc(const string & file_name)
{
   file.open(file_name.c_str(), ios::in | ios::binary | ios::out | ios::ate);

   if(file) 
      ;
   else
      throw "unable to open alloc file...";

   file.seekg(0L, ios::beg);

   file.read((char*)&addr, sizeof(offset_type));

   //global_alloc_ptr = this;
}

d_alloc::~d_alloc()
{
   file.close();
}

void d_alloc::swap(d_alloc_node & left, d_alloc_node & right)
{
   offset_type d1 = left.data;
   offset_type sz1 = left.size;
   offset_type d2 = right.data;
   offset_type sz2 = right.size;

   left.data = d2;
   left.size = sz2;
   file.seek(left.addr);
   left.store(file);

   right.data = d1;
   right.size = sz1;
   file.seek(right.addr);
   right.store(file);
}

void d_alloc::sort()
{
   d_alloc_node node1,node2;
   file.seekg(sizeof(offset_type), ios::beg);
   offset_type address;
   file >> address;
   offset_type ptr1,ptr2;

   if(address != -1L ) {
      ptr1 = address;
      while(ptr1 != -1L) {
         file.seek(ptr1);
         node1.load(file);
         ptr2 = ptr1;
         while(ptr2 != -1L) {
            file.seek(ptr2);
            node2.load(file);
            if(node1.addr != node2.addr) {
               if(node1.size > node2.size) {
                  swap(node1,node2);
               }
            }
            ptr2 = node2.next;
         }
         ptr1 = node2.next;
      }
   }
}

void d_alloc::alloc_node(d_alloc_node & node)
{
   offset_type address, address2;
   bool found = false;

   file.seekg(0L, ios::beg);
   file >> address;

   address2 = address;

/*
   while(address != -1L) {
      file.seek(address);
      node.load(file);
      if(node.data == -1L) {
         found = true;
         break;
      }
      address = node.next;
   }
*/

   if(!found) {
      file.seekg(0L, ios::end);
      node.addr = file.tellg();
      node.next = address2;
      node.store(file);
      file.seekg(0L, ios::beg);
      file << node.addr;
   }
}

offset_type d_alloc::allocate(const offset_type & size, bstringstream & buffer)
{
   d_alloc_node node,node2;
   offset_type ret = -1L, off, data,last = sizeof(offset_type);
   file.seekg(sizeof(offset_type), ios::beg);
   file >> addr;

   if(addr != -1L && size >= 0) {
      off = addr; 
      while(off != -1L) { 
      //if(off != -1L) { 
         file.seek(off);
         node.load(file);
         if(node.is_free_node) {
            if(node.size >= size) {
               if(node.size > size) {
                  alloc_node(node2);
                  node2.size = node.size - size;
                  node2.data = node.data + size;
                  node2.is_free_node = 0;
                  node2.next = addr;
                  insert(node2);
                  file.seekg(0L, ios::beg);
                  file << node2.addr;
               }
               else {
                  node.is_free_node = false;
                  file.seek(node.addr);
                  node.store(file);
                  ret = node.data;
                  file.seek(ret);
                  if(buffer.size() != 0) {
                     buffer.write(file);
                  }
                  move_to_alloc_list(last,node);
               }
               //sort();
               break;
            }
         }
         last = off;
         off = node.next;
      }
   }

   if(ret == -1 && size >= 0) {
      file.seek(0L);
      file >> addr;
      file.seekg(0L, ios::end);
      data = file.tellg();
      if(buffer.size() == 0) {
         char * buf = new char[size];
         memset(buf, 0, size);
         file.write(buf, size);
         delete [] buf;
      }
      else {
         buffer.write(file);
      }
      alloc_node(node);
      node.is_free_node = false;
      node.size = size;
      //node.next = addr;
      node.next = -1L;
      node.data = data;
      file.seek(node.addr);
      node.store(file);
      //file.seekg(0L, ios::beg);
      //file << node.addr;
      ret = node.data;
      insert(node);
      //sort();
   }


   return ret;
}

void d_alloc::deallocate(const offset_type & addr)
{
/*
   long_list_type & ll = alloc_map[addr_map[addr]];

   ll.push_back(addr);
*/

   d_alloc_node node;
   offset_type address;
   file.seekg(sizeof(offset_type), ios::beg);
   file >> address;
   offset_type last = 0L;
   while(address != -1) {
      file.seek(address);
      node.load(file);
      if(node.data == addr) {
         node.is_free_node = 1;
         file.seek(node.addr);
         node.store(file); 
         move_to_dealloc_list(last,node);
         break;
      }
      last = address;
      address = node.next;
   }
   //compact();
}

void d_alloc::compact()
{
   d_alloc_node node1, node2, node3;
   offset_type address1, address2 = -1L, prev;
   bool change;

   do {
      change = false;

      file.seekg(sizeof(offset_type), ios::beg);
      file >> address1;

      while(address1 != -1L) {
         file.seek(address1);
         node1.load(file);

         if(node1.is_free_node == false) {
            address1 = node1.next;
            continue;
         }

         if(address2 != -1L)
            prev = address2;

         address2 = address1;

         while(address2 != -1L) {
            file.seek(address2);
            node2.load(file);
 
            if(node2.is_free_node == false) {
               address2 = node2.next;
               continue;
            }

            if((node1.data + node2.size) == node2.data) {
               node1.size += node2.size;
               file.seek(node1.addr);
               node1.store(file);
               node2.is_free_node = true;
               node2.data = -1L;
               node2.size = 0U;
               file.seek(node2.addr);
               node2.store(file);
               change = true;
            }
            else if((node1.addr + sizeof(d_alloc_node)) == node2.addr) {
               if(node1.data == -1L && node2.data == -1L) {
                  node1.size = sizeof(d_alloc_node);
                  node1.data = node2.addr;
                  node1.is_free_node = true;
                  file.seek(prev);
                  node3.load(file);
                  node3.next = node2.next;
                  file.seek(prev);
                  node3.store(file);
                  file.seek(node1.addr);
                  node1.store(file);
                  change = true;
               }
            }

            address2 = node2.next;

            prev = node2.addr;
         }

         address1 = node1.next;
      }
   }
   while(change);
   sort();
}

}
