/*     A simple memory management implemenation for parallel treaps
 *	   Margaret Reid-Miller <mrmiller@cs.cmu.edu>
 *   	               June 1998
 *
 * The code here provides a simple memory management for allocating
 * treap nodes so that each processor gets its nodes from its own
 * block of shared memory to avoid false sharing. (False sharing is
 * when two processors write to different locations of the same cache
 * line.)  The approach is intented for the parallel persistent
 * version of the treap set operations (see
 * <http://www.cs.cmu.edu/~scandal/treap.html>) and a garbage
 * collector. It uses MIT's Cilk runtime system for shared memory
 * multiprocessors (see <http://theory.lcs.mit.edu/~cilk/>).
 */

#include <math.h>
#include <stdio.h>

#ifdef CILK
# include <cilk.h>
# include <cilk-lib.h> 
# include <cilk-compat.h>
#endif

typedef int key_type;

typedef struct tnode *Tree_ptr;

typedef struct tnode {
  Tree_ptr left;        /* left subtree (keys less than key) */
  key_type key;         /* key (kept in in-order) */
  Tree_ptr right;       /* right subtree (keys greater than key) */
  int priority;         /* priority (kept in heap-order) */
}Tree_node;


#define ERROR_STATUS 1
#define OK_STATUS 0

/*----------------------Parallel Allocation code ---------------------*/
#define TALLOC() talloc()
#define LINE_LEN  30
#define MAX_BLOCK_LEN 1024
#define MAX_THREADS 16


#ifndef CILK
# define  Cilk_active_size 1
# define  Self 0
 typedef int Cilk_mutex;
 void Cilk_mutex_init(Cilk_mutex *l){};
 void Cilk_mutex_wait(Cilk_mutex *l){};
 void Cilk_mutex_signal(Cilk_mutex *l){};
#endif

typedef Tree_node Space_unit;

typedef struct memblock{
  Space_unit *next;       /* pointer to next free space_unit */
  Space_unit *end;        /* last free space_unit assigned */
  int align[LINE_LEN];    /* each memblock is one cache line long */
} Mem_block;
 
static int Align[LINE_LEN]; /* Ensures first mem block on own cache line */
static Mem_block Proc_mem[MAX_THREADS]; /* one block per processor */
static Mem_block *Proc_mem_end;         /* end of Proc_mem array */
static int Block_len = MAX_BLOCK_LEN;   /* block length per procs */
static Space_unit *Mem_end;   /* last allocated space (need lock) */
static Cilk_mutex Mem_lock;   /* lock for Mem_end, a shared resource */
static Space_unit *Arena;     /* pointer to allocated Space_units */
static Space_unit *Arena_end; /* outside the arena allocated */

/*----------------------Allocation code----------------------------*/

/* "init_memory" initializes the memory management of tree
 * nodes. "alloc_memory divides memory for tree nodes into blocks of
 * nodes of length Block_len.  "clear_memory" assigns each thread one
 * block of memory from the begining of the allocated space.
 * "free_memory" frees allocated memory.  Can realloc memory by first
 * calling "free_memory" and then "alloc_memory".  Can reuse memory by
 * calling "clear_memory".  "t_alloc" returns one allocated tree node.
 * There is no "t_free" to deallocate a tree node: it assumes there is
 * a garbage collector. */


/* Initialize memory.  Call only once and use only when in single
   thread mode. */

void init_memory(void){
  Proc_mem_end = Proc_mem + Cilk_active_size;
  Cilk_mutex_init(&Mem_lock);
}


/* Allocate enough shared memory for "n" nodes. To be use by all
 * threads. Use only when in single thread mode.
 */

void alloc_memory(int n)
{
  int size;
  int n_blocks;

  /* Number of blocks of size Block_len needed to hold n nodes */
  n_blocks = ceil((float) n / (float) Block_len);
  if (n_blocks < Cilk_active_size) {
    n_blocks = Cilk_active_size;
    Block_len = ceil((float) n / (float) n_blocks);
  }
  
  /* allow for one almost empty block per thread */
  size = (n_blocks + Cilk_active_size) * Block_len;

  /* Actually allocate the space for the n nodes */
  if ((Arena = (Space_unit *) malloc(sizeof(Space_unit) * size))
      == NULL) {
    fprintf(stderr,"Can't alloc space for tree");
    exit(ERROR_STATUS);
  }
  Arena_end = Arena + size;

}

void free_memory(void){
  free(Arena);
}


/* Reset the set of thread memory pointers to their own blocks of
 * memory at the begining of allocated area.  Use only when in single
 * thread mode.  */

void clear_memory(void){
  Mem_block *p_mem;

  Mem_end = Arena;
  for (p_mem = Proc_mem;  p_mem < Proc_mem_end; p_mem++) {
    p_mem->next = Mem_end;
    Mem_end += Block_len;
    p_mem->end = Mem_end;
  }
}

/* Return next unassigned block from shared pool of blocks */

Space_unit *get_next_block() {
  Space_unit *next;

  Cilk_mutex_wait(&Mem_lock);      /* wait for Mem_lock to be available */
  next = Mem_end;                  /* read Mem_end */
  Mem_end += Block_len;            /* bump Mem_end to next block */
  Cilk_mutex_signal(&Mem_lock);    /* release the lock */
  if (Mem_end > Arena_end) {
    fprintf(stderr, "Ran out of allocated space for the tree data\n!!!");
    exit(ERROR_STATUS);
  }
  return next;
}

/* Return one Tree_node of allocated memory from processor's
   own block of memroy. */

inline Tree_ptr talloc(void)
{
  Mem_block *s = Proc_mem + Self;
  
  if (s->next == s->end) {
    s->next = get_next_block();
    s->end = s->next + Block_len;
  }
  return (Tree_ptr) s->next++;
}