memory_chunks.c

关于遗传算法的一些见地。特别是关于简单遗传程序设计的实现。

/**********************************************************************
  memory_chunks.c
 **********************************************************************

  memory_chunks - Efficient bulk memory allocation.
  Copyright ©2001-2005, Stewart Adcock <[e-mail]>
  All rights reserved.

  The latest version of this program should be available at:
  http://gaul.sourceforge.net/

  This program 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 2 of the License, or
  (at your option) any later version.  Alternatively, if your project
  is incompatible with the GPL, I will probably agree to requests
  for permission to use the terms of any other license.

  This program is distributed in the hope that it will be useful, but
  WITHOUT ANY WARRANTY WHATSOEVER.

  A full copy of the GNU General Public License should be in the file
  "COPYING" provided with this distribution; if not, see:
  http://www.gnu.org/

 **********************************************************************

  Synopsis:	Efficient bulk memory allocation.
 
		This code is part of memory_util.c - its own
		integrated implementation of memory chunks.
		It may be used independantly if you feel very brave.

		Define MEMORY_CHUNKS_MIMIC to allow your favourite
		memory debugger to function properly.  However, note
		that by defining MEMORY_CHUNKS_MIMIC a number of memory
		leaks will occur if you rely on mem_chunk_clean(),
	       	mem_chunk_reset() or mem_chunk_free() to implicitly
	       	deallocate all memory atoms (which would normally be
		a valid thing to do).
 
		This is thread safe.

		For OpenMP code, USE_OPENMP must be defined and 
		mem_chunk_init_openmp() must be called prior to any
		other function.

  To do:	Padding for array under/overflow checking.
 		Observe contents of atoms in the FreeAtom list.
 
  Known bugs:	High padding may be offset from the real end of the data - so some
 		overflows will be missed.
		Much of the tree handling code may now be optimised.
 
 **********************************************************************/

#include "gaul/memory_chunks.h"

/* MEMORY_ALIGN_SIZE should be set in gaul_config.h */

#define MEMORY_AREA_SIZE 4L

typedef void *Key_t;

typedef struct node_s
  {
  struct node_s *left;		/* Left subtree. */
  struct node_s *right;		/* Right subtree. */
  int		balance;	/* Height (left) - height (right). */
  Key_t		key;		/* The key for this node. */
  vpointer	data;		/* Data stored at this node. */
  } node_t;

typedef struct
  {
  node_t	*root;
  } tree_t;

typedef struct FreeAtom_t
  {
  struct FreeAtom_t *next;
  } FreeAtom;

typedef struct MemArea_t
  {
  struct MemArea_t *next;	/* The next memory area */
  struct MemArea_t *prev;	/* The previous memory area */
  size_t	index;		/* The current index into the "mem" array */
  size_t	free;		/* The number of free bytes in this memory area */
  unsigned int	used;		/* The number of atoms allocated from this area */
  unsigned char	*mem;		/* The mem array from which atoms get allocated. */
  } MemArea;

struct MemChunk_t
  {
  unsigned int	num_mem_areas;		/* The total number of memory areas */
  unsigned int	num_unused_areas;	/* The number of areas that may be deallocated */
  size_t	atom_size;		/* The size of an atom (used in mimic routines) */
  size_t	area_size;		/* The size of a memory area */
  MemArea	*mem_area;		/* The current memory area */
  MemArea	*mem_areas;		/* A list of all the memory areas owned by this chunk */
  MemArea	*free_mem_area;		/* Free area... which is about to be destroyed */
  FreeAtom	*free_atoms;		/* Free atoms list */
  tree_t	*mem_tree;		/* Tree of memory areas sorted by memory address */
  long		num_atoms_alloc;	/* The number of allocated atoms (only used in mimic routines) */
  };


/*
 * Private function prototypes.
 */
static node_t	*node_new(Key_t key, void *data);
static void	node_free(node_t *node);
static void	node_delete(node_t *node);
static node_t	*node_insert(node_t *node, Key_t key,
					     void *data, boolean *inserted);
static node_t	*node_remove(node_t *node,
                                             Key_t key, void **removed_data);
static node_t	*node_balance(node_t *node);
static node_t	*node_remove_leftmost(node_t *node,
						     node_t **leftmost);
static node_t	*node_restore_left_balance(node_t *node,
						     int old_balance);
static node_t	*node_restore_right_balance(node_t *node,
						     int old_balance);
static int	node_height(node_t *node);
static node_t	*node_rotate_left(node_t *node);
static node_t	*node_rotate_right(node_t *node);

/*
 * Compilation constants.
 */
#define _NODE_BUFFER_NUM_INCR	16
#define _NODE_BUFFER_SIZE		1024

/*
 * Global variables.
 */
static node_t		*node_free_list = NULL;
static int		num_trees = 0;	/* Count number of trees in use. */
static int		buffer_num = -1;
static int		num_buffers = 0;
static int		num_used = _NODE_BUFFER_SIZE;
static node_t		**node_buffers = NULL;

/*
 * Note that a single coarse thread lock is used when a number of
 * less coarse locks might be better.
 */
THREAD_LOCK_DEFINE_STATIC(node_buffer_lock);
#if USE_OPENMP == 1
static boolean mem_chunk_openmp_initialised = FALSE;
#endif

/*
 * This function must be called before any other functions is OpenMP
 * code is to be used.  Can be safely called when OpenMP code is not
 * being used, and can be safely called more than once.
 */
void mem_chunk_init_openmp(void)
  {

#if USE_OPENMP == 1
  if (mem_chunk_openmp_initialised == FALSE)
    {
    omp_init_lock(&node_buffer_lock);
    mem_chunk_openmp_initialised = TRUE;
    }
#endif

  return;
  }



/*
 * Private functions.
 */

/*
 * Deallocate all memory associated with buffers.  Should
 * never be called outside of a "node_buffer_lock"
 * block.
 */
static void _destroy_buffers(void)
  {

  while (buffer_num >= 0)
    {
    s_free(node_buffers[buffer_num]);
    buffer_num--;
    }

  s_free(node_buffers);
  node_buffers = NULL;
  num_buffers = 0;
  num_used = _NODE_BUFFER_SIZE;

  node_free_list = NULL;

  return;
  }


static node_t *node_new(Key_t key, void *data)
  {
  node_t *node;

  THREAD_LOCK(node_buffer_lock);
/*
 * Find an unused node.  Look for unused node in current buffer, then
 * in the free node list, then allocate new buffer.
 */
  if (num_used < _NODE_BUFFER_SIZE)
    {
    node = &(node_buffers[buffer_num][num_used]);
    num_used++;
    }
  else
    {
    if (node_free_list)
      {
      node = node_free_list;
      node_free_list = node->right;
      }
    else
      {
      buffer_num++;

      if (buffer_num == num_buffers)
        {
        num_buffers += _NODE_BUFFER_NUM_INCR;
        node_buffers = s_realloc(node_buffers, sizeof(node_t *)*num_buffers);
        }

      node_buffers[buffer_num] = malloc(sizeof(node_t)*_NODE_BUFFER_SIZE);

      if (!node_buffers[buffer_num]) die("Unable to allocate memory.");

      node = node_buffers[buffer_num];
      num_used = 1;
      }
    }
  THREAD_UNLOCK(node_buffer_lock);

  node->balance = 0;
  node->left = NULL;
  node->right = NULL;
  node->key = key;
  node->data = data;

  return node;
  }


static void node_free(node_t *node)
  {
  THREAD_LOCK(node_buffer_lock);
  node->right = node_free_list;
  node_free_list = node;
  THREAD_UNLOCK(node_buffer_lock);

  return;
  }


static void node_delete(node_t *node)
  {
  if (node)
    {
    node_delete(node->right);
    node_delete(node->left);
    node_free(node);
    }

  return;
  }


/*
 * Systematically search tree with a search function which has the
 * same ordering as the tree.
 * This iterative version is much faster than the equivalent recursive version.
 */
static void *node_ordered_search(node_t *node, void *userdata)
  {

  while (node)
    {
    if (userdata < (void *) ((MemArea *)node->data)->mem)
      node=node->left;
    else if (userdata > (void *) &(((MemArea *)node->data)->mem[((MemArea *)node->data)->index]))
      node=node->right;
    else
      return node->data;
    }

  return NULL;
  }


static node_t *node_insert(node_t *node,
		    Key_t key, void *data, boolean *inserted)
  {
  int old_balance;

  if (!node)
    {
    *inserted = TRUE;
    return node_new(key, data);
    }

  if (key < node->key)
    {
    if (node->left)
      {
      old_balance = node->left->balance;
      node->left = node_insert(node->left, key, data, inserted);

      if ((old_balance != node->left->balance) && node->left->balance)
        node->balance--;
      }
    else
      {
      *inserted = TRUE;
      node->left = node_new(key, data);
      node->balance--;
      }
    }
  else if (key > node->key)
    {
    if (node->right)
      {
      old_balance = node->right->balance;
      node->right = node_insert(node->right, key, data, inserted);

      if ((old_balance != node->right->balance) && node->right->balance)
        node->balance++;
      }
    else
      {
      *inserted = TRUE;
      node->right = node_new(key, data);
      node->balance++;
      }
    }
  else
    {	/* key == node->key */
/*
    *inserted = FALSE;
 */
    printf("WARNING: -- Replaced node -- (Key clash?)\n");

    node->data = data;
    return node;
    }

  if (*inserted && (node->balance < -1 || node->balance > 1))
    node = node_balance(node);

  return node;
  }


static node_t *node_remove(node_t *node,
                            Key_t key, void **removed_data)
  {
  node_t	*new_root;
  int		old_balance;

  if (!node) return NULL;

  if (key < node->key)
    {
    if (node->left)
      {
      old_balance = node->left->balance;
      node->left = node_remove(node->left, key, removed_data);
      node = node_restore_left_balance(node, old_balance);
      }
    }
  else if (key > node->key)
    {
    if (node->right)
      {
      old_balance = node->right->balance;
      node->right = node_remove(node->right, key, removed_data);
      node = node_restore_right_balance(node, old_balance);
      }
    }
  else if (key == node->key)
    {
    node_t *removed_node;

    removed_node = node;

    if (!node->right)
      {
      node = node->left;
      }
    else
      {
      old_balance = node->right->balance;
      node->right = node_remove_leftmost (node->right, &new_root);
      new_root->left = node->left;
      new_root->right = node->right;
      new_root->balance = node->balance;
      node = node_restore_right_balance (new_root, old_balance);
      }

    *removed_data = removed_node->data;
    node_free(removed_node);
    }

  return node;
  }


static node_t *node_balance(node_t *node)
  {
  if (node->balance < -1)
    {
    if (node->left->balance > 0)
      node->left = node_rotate_left(node->left);
    node = node_rotate_right (node);
    }
  else if (node->balance > 1)
    {
    if (node->right->balance < 0)
      node->right = node_rotate_right(node->right);
    node = node_rotate_left (node);
    }

  return node;
  }


static node_t *node_remove_leftmost(node_t  *node,
			     node_t **leftmost)
  {
  int old_balance;

  if (!node->left)
    {
    *leftmost = node;
    return node->right;
    }

  old_balance = node->left->balance;
  node->left = node_remove_leftmost(node->left, leftmost);
  return node_restore_left_balance(node, old_balance);
  }


static node_t *node_restore_left_balance(node_t	*node,
				  int		old_balance)
  {
  if ( (!node->left) || ((node->left->balance != old_balance) &&
           (node->left->balance == 0)) )
    {
    node->balance++;