// Simple-minded code to determine the performance of various node-management
// strategies.
//
// CS 503 - Advanced Programming I
// Spring '06

#include <cstdlib>	// for srandom() and random()
#include <sys/types.h>  // for getpid()
#include <unistd.h>	// for getpid()
#include <iostream>	// for printf()
#include <numeric>	// for accumulate()
#include "stopwatch.h"


// The node that's being managed.

    template <typename t>
    struct node {
      t data;
      node * next, * prev;
      };


// One of the node element types; the other is an int.

   struct point {
     double x, y, z;
     };


// A simple node manager that calls new on every allocation and delete on every
// deallocation.  This is the least sophisticated and presumably lowest
// performing of the node managers.

   template <typename t>
   class simple_node_mgr {
     public:

       typedef node<t> node_type;

       node_type * alloc() {
	 return new node_type;
	 }

       void free(node_type * n) {
	 delete n;
	 }
     };


// A free-list node manager.  Deallocated nodes are hung up on the free list
// rather than being passed on to delete.  Allocations first check the free
// list and, if the free list is empty, then call new.

   template <typename t>
   class flist_node_mgr {
     public:

       typedef node<t> node_type;

       node_type * alloc() {
	 if (not free_list) {
	   free_list = new node_type;
	   free_list->next = 0;
	   }
	 node_type * n = free_list;
	 free_list = n->next;
	 return n;
	 }

       void free(node_type * n) {
	 n->next = free_list;
	 free_list = n;
	 }

       flist_node_mgr() : free_list(0) { }

      ~flist_node_mgr() { 
         while (free_list) {
	   node_type * n = free_list;
	   free_list = n->next;
	   delete n;
	   }
	}

     private:

       node_type * free_list;

       flist_node_mgr(flist_node_mgr &) { }
       flist_node_mgr & operator = (const flist_node_mgr &) { return *this; }
     };


// A block node manager.  Similar to the free-list node manager except it
// allocates a bunch of nodes when the free list is empty rather than just one
// as the free-list manager does.  The size of the block in elements is passed
// in as the integral template parameter bs.

  template <typename t, unsigned bs>
  class block_node_mgr {
    public:

       typedef node<t> node_type;

      node_type * alloc() {
	if (not free_list) {
	  if (free_list_next == free_list_end) {
	    free_list_next = new node_type [bs];
	    free_list_end = free_list_next + bs;
	    free_list_next->next = block_list;
	    block_list = free_list_next++;
	    }
	  free_list = free_list_next++;
	  free_list->next = 0;
	  }

	node_type * n = free_list;
	free_list = n->next;
	return n;
	}

      void free(node_type * n) {
	n->next = free_list;
	free_list = n;
	}

      block_node_mgr() 
	: free_list(0), free_list_next(0), free_list_end(0), block_list(0)
        { }

     ~block_node_mgr() { 
        while (block_list) {
	  node_type * n = block_list;
	  block_list = n->next;
	  delete [] n;
	  }
        }

    private:

      // Points to the next free node to allocate.  If free_list == 0, there
      // are no free nodes available.

         node_type * free_list;		

      // Points to the first unallocated node in the most recently allocated
      // block.  The node pointed to by free_list_next is the one that will be
      // moved to the free list when the free list is empty.

         node_type * free_list_next;

      // Points to one past the last unallocated node in the most recently
      // allocated block.  It's time to allocate a new block when
      // free_list_next == free_list_end.

         node_type * free_list_end;

      // Head of the list of blocks allocated.  The first node of the block is
      // used as the list link and is not available for allocation.

         node_type * block_list;

    block_node_mgr(block_node_mgr &) { }
    block_node_mgr & operator = (const block_node_mgr &) { return *this; }
    };


// Deja vu c++ style.

   template <typename t> 
     static void run_test(unsigned *, unsigned, t &, const char * const);


template<typename t>
static void
do_test(unsigned a[], unsigned n) {

  // Test the node managers on nodes containing elements of type t.  The
  // n-element array a contains allocation-deallocation pattern to use for the
  // test.

  simple_node_mgr<t> snm;
  flist_node_mgr<t> fnm;
  block_node_mgr<t, 1000u> bnm;

  run_test(a, n, snm, "simple");
  run_test(a, n, snm, "simple");
  run_test(a, n, fnm, "free-list");
  run_test(a, n, bnm, "block");
  }


int 
main() {

  // Write to std-out some performance data for various node managers executing
  // a synthetic allocation-deallocation pattern.

  const unsigned size = 1000;
  unsigned cnts[size];

  srandom(getpid());

  for (unsigned i = 0; i < size; i++)
    cnts[i] = random() % 100000;

  printf("%9u aloc-frees\n", std::accumulate(cnts, cnts + size, 0u));

  do_test<int>(cnts, size);
  }


template <typename t>
static void
run_test(unsigned a[], unsigned n, t & nm, const char * const name) {

  // Run performance tests on the node manager nm with the identifier name.
  // The n-element array a contains the synthetic allocate-deallocate load:
  // allocate a[i] nodes then deallocate them.

  stopwatch sw;

  sw.start();

  for (unsigned i = 0; i < n; i++) {
    typename t::node_type
      * nd = nm.alloc(),
      * n2 = nd;
    unsigned j;

    for (j = 0; j < a[i]; j++)
      n2 = n2->next = nm.alloc();

    n2 = nd;
    for (j = 0; j < a[i]; j++) {
      typename t::node_type * n3 = n2;
      n2 = n3->next;
      nm.free(n3);
      }
    }

  sw.stop();

  const double ops = 2*std::accumulate(a, a + n, 0u);
  printf("%9s %9u usec., %g usec/pair\n", 
	 name, sw.elapsed(), sw.elapsed()/ops);
  }


// $Log: list-node-mgr.cc,v $
// Revision 1.2  2006-02-22 23:35:51  rclayton
// Document, document; added the block list for the block mgr.
//
// Revision 1.1  2006-02-20 05:26:04  rclayton
// Created.
//