// Simple-minded code to determine the performance of various node-management
// strategies.
//
// CS 306 - Computer Algorithms II
// Fall '07

#include <iostream>	// for printf()
#include <numeric>	// for accumulate()
#include <cassert>      // for assert()
#include "stopwatch.h"


// The node that's being managed.

    template <typename t>
    struct node
      t data
      node * left, * right


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

   struct point
     double x, y, z


// A static node manager.

   template <typename t, unsigned node_count = 1000>
   class static_node_mgr
     public:

       typedef node<t> node_type

       node_type * alloc()
	 if free_list
	   node_type * const n = free_list
	   free_list = n→left
	   return n
	 assert(!"no more nodes")
	 return 0

       void free(node_type * n)
	 n→left = free_list
	 free_list = n

     static_node_mgr()
       for unsigned i = 1; i < node_count; i++
	 nodes[i - 1].left = nodes + i
       free_list = nodes
       nodes[node_count - 1].left = 0

     private:

       node_type nodes[node_count]
       node_type * free_list



// 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 dynamic 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→left = 0
	 node_type * n = free_list
	 free_list = n→left
	 return n

       void free(node_type * n)
	 n→left = free_list
	 free_list = n


      ~flist_node_mgr()
         while free_list
	   node_type * n = free_list
	   free_list = n→left
	   delete n

     private:

       node_type * free_list



// 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→left = block_list
	    block_list = free_list_next++
	  free_list = free_list_next++
	  free_list→left = 0

	node_type * n = free_list
	free_list = n→left
	return n

      void free(node_type * n)
	n→left = 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→left
	  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



// 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
  static_node_mgr<t, 200000u> stnm

  run_test(a, n, snm, "simple")
  run_test(a, n, stnm, "static")
  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→left = nm.alloc()

    n2 = nd
    for j = 0; j < a[i]; j++
      typename t::node_type * n3 = n2
      n2 = n3→left
      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: node-mgr.cc,v $
// Revision 1.2  2007-09-23 15:19:28  rclayton
// Remove some unneeded includes.
//
// Revision 1.1  2007-09-16 22:20:06  rclayton
// Created.
//