// Simple-minded code to determine the performance of various node-management
// strategies.
//
// CS 305-503 - Data Structures and Algorithms I
// Fall '08

#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.
//