/*
 *  Copyright (C) 1996-2017 Edward F. Valeev and Justin T. Fermann
 *
 *  This file is part of Libint.
 *
 *  Libint 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 3 of the License, or
 *  (at your option) any later version.
 *
 *  Libint 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 Libint.  If not, see <http://www.gnu.org/licenses/>.
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <libderiv/mem_man.h>
#define MAXALLOC 10000

int free_block[MAXALLOC];   /* Marks of free-occupied blocks */
int block_length[MAXALLOC]; /* Keeps sizes of all blocks */
int last_free;              /* Number of the last free block */
int max_mem;                /* Amount of memory used by classes up to this point */
int mem_top;                /* Total memory allocated up to this point */

/* initialize memory stack */
void init_mem(int memory)
{
  last_free = 1;
  memset(free_block,0,MAXALLOC*sizeof(int));    /* All blocks are free */
  memset(block_length,0,MAXALLOC*sizeof(int));  /* All of them are zero in length ... */
  block_length[0] = memory;                     /* except for the first one */
  max_mem = 0;
  mem_top = memory;
}

/* add memory */
void add_mem(int memory)
{
  int i;
  int addto = 0;
  int himem = 0;

  mem_top += memory;
  /* Find the last free block and add all this memory to it */
  for(i=0; i<last_free; i++){
    if(free_block[i] > himem){
      himem = free_block[i];
      addto = i;
      }
    }
#if 0
  printf("adding %d to memory\n\tnew top = %d\n", memory,
    free_block[addto]+block_length[addto]+memory);
#endif
  block_length[addto] = block_length[addto]+memory;
}

/* Find a block of the requested size */
int get_mem(int size)
{
  int i, j;

/* try to find one that fits exactly */
  for(i=last_free-1; i>=0; i--){
    if(block_length[i] == size){
      j = free_block[i];
      if(free_block[i]+block_length[i]==mem_top) add_mem(500);
      use(i, size);
      return j;
      }
    }

/* ok, try to find a bigger one that will work */
  for(i=last_free-1; i>=0; i--){
    if(block_length[i] > size){
      j = free_block[i];
      use(i, size);
      return j;
      }
    }

  
/* last resort, expand memory */
  add_mem(1000);
  return get_mem(size);

}


void use(int n, int s)
{
  int i;
#if 0
  printf("issuing %d doubles starting at %d out of free block %d\n",
        s, free_block[n], n);
  printf("last_free = %d\n", last_free);
#endif
  if(s==block_length[n]){
    for(i=n; i<last_free; i++){
      free_block[i] = free_block[i+1];
      block_length[i] = block_length[i+1];
      }
    last_free--;
    }
  else if(s<block_length[n]){
    free_block[n] = free_block[n]+s;
    block_length[n] = block_length[n]-s;
/* keep track of how much memory we use overall */
    if(free_block[n]>max_mem) max_mem = free_block[n];
    }
  else exit(1);

}

void free_mem(int n, int size)
{
  int i, j;

  free_block[last_free] = n;
  block_length[last_free] = size;
  last_free++;

  consolidate();

}

void consolidate()
{
  int i, j;
  int right_bound_i;
  int done = 1;

  do {
    done = 1;
    for(i=0; i<last_free; i++){
      right_bound_i = free_block[i]+block_length[i];
      for(j=0; j<last_free; j++){
        if(free_block[j]==right_bound_i){
          block_length[i]+=block_length[j];
          use(j, block_length[j]);
          done = 0;
          }
        }
      }
    } while (!done);
#if 0
  printf("after consolidation, free_blocks looks like:\n");
  for(i=1; i<=last_free; i++){
    printf("%d[%d]\t", free_block[i-1], block_length[i-1]);
    if(!(i%5)) printf("\n");
    }
  printf("\n");
#endif

}

int get_total_memory()
{
  return max_mem;
}