memory_chunks.c

http://gaul.sourceforge.net/ 这里大部分人讨论的是在Matlab里实现GA的toolbox.以上为一个GA的C语言的软件包.如果你想利用GA做优化算法,非常有用.而且有

    }

  if (node->balance > 1) return node_balance(node);

  return node;
  }


static node_t *node_restore_right_balance(node_t	*node,
				   int		old_balance)
  {
  if ( (!node->right) || ((node->right->balance != old_balance) &&
	   (node->right->balance == 0)) )
    {
    node->balance--;
    }

  if (node->balance < -1) return node_balance(node);

  return node;
  }


static int node_height(node_t *node)
  {
  int left_height;
  int right_height;

  if (!node) return 0;

  if (node->left)
    left_height = node_height(node->left);
  else
    left_height = 0;

  if (node->right)
    right_height = node_height(node->right);
  else
    right_height = 0;

  return MAX(left_height, right_height) + 1;
  }


static node_t *node_rotate_left(node_t *node)
  {
  node_t *right;
  int a_bal;
  int b_bal;

  right = node->right;

  node->right = right->left;
  right->left = node;

  a_bal = node->balance;
  b_bal = right->balance;

  if (b_bal <= 0)
    {
    if (a_bal >= 1) right->balance = b_bal - 1;
    else right->balance = a_bal + b_bal - 2;

    node->balance = a_bal - 1;
    }
  else
    {
    if (a_bal <= b_bal) right->balance = a_bal - 2;
    else right->balance = b_bal - 1;

    node->balance = a_bal - b_bal - 1;
    }

  return right;
  }


static node_t *node_rotate_right(node_t *node)
  {
  node_t *left;
  int a_bal;
  int b_bal;

  left = node->left;

  node->left = left->right;
  left->right = node;

  a_bal = node->balance;
  b_bal = left->balance;

  if (b_bal <= 0)
    {
    if (b_bal > a_bal) left->balance = b_bal + 1;
    else left->balance = a_bal + 2;

    node->balance = a_bal - b_bal + 1;
    }
  else
    {
    if (a_bal <= -1) left->balance = b_bal + 1;
    else left->balance = a_bal + b_bal + 2;

    node->balance = a_bal + 1;
    }

  return left;
  }


static tree_t *tree_new(void)
  {
  tree_t *tree;

  num_trees++;

  if (!(tree = malloc(sizeof(tree_t))) )
    die("Unable to allocate memory.");

  tree->root = NULL;

  return tree;
  }


static void delete(tree_t *tree)
  {
  if (!tree) return;

  node_delete(tree->root);

  s_free(tree);

  num_trees--;

  THREAD_LOCK(node_buffer_lock);
  if (num_trees == 0)
    _destroy_buffers();
  THREAD_UNLOCK(node_buffer_lock);

  return;
  }


static boolean insert(tree_t *tree, void *data)
  {
  boolean	inserted=FALSE;

  if (!data) die("Internal error: Trying to insert NULL data.");
  if (!tree) die("Internal error: Trying to insert into NULL tree.");

  tree->root = node_insert(tree->root, (Key_t) ((MemArea *)data)->mem, data, &inserted);

  return inserted;
  }


static void *remove_data(tree_t *tree, void *data)
  {
  void *removed=NULL;

  if (!tree || !tree->root) return NULL;

  tree->root = node_remove(tree->root, (Key_t) ((MemArea *)data)->mem, &removed);

  return removed;
  }


static void *remove_key(tree_t *tree, Key_t key)
  {
  void *removed=NULL;

  if (!tree || !tree->root) return NULL;

  tree->root = node_remove(tree->root, key, &removed);

  return removed;
  }


static void *ordered_search(tree_t *tree, void *userdata)
  {
  if (!tree || !tree->root) return NULL;

  return node_ordered_search(tree->root, userdata);
  }


/*
 * Padding functions:
 */
#if MEMORY_PADDING==TRUE
static unsigned char *pad_values="abcdefghijklmnopqr";

#define BUMP_DOWN(X)	( (void *) (((unsigned char *)(X))-MEMORY_ALIGN_SIZE) )
#define BUMP_UP(X)	( (void *) (((unsigned char *)(X))+MEMORY_ALIGN_SIZE) )

static void set_pad_low(MemChunk *mem_chunk, void *mem)
  {
  memcpy(((unsigned char *)mem),pad_values,MEMORY_ALIGN_SIZE);

  return;
  }


static void set_pad_high(MemChunk *mem_chunk, void *mem)
  {
  memcpy(((unsigned char *)mem)+mem_chunk->atom_size-MEMORY_ALIGN_SIZE,
            pad_values,MEMORY_ALIGN_SIZE);

  return;
  }


static int check_pad_low(MemChunk *mem_chunk, void *mem)
  {
  return memcmp(((unsigned char *)mem),pad_values,MEMORY_ALIGN_SIZE);
  }


static int check_pad_high(MemChunk *mem_chunk, void *mem)
  {
  return memcmp(((unsigned char *)mem)+mem_chunk->atom_size-MEMORY_ALIGN_SIZE,
                   pad_values,MEMORY_ALIGN_SIZE);
  }

#endif	/* MEMORY_PADDING==TRUE */


boolean mem_chunk_has_freeable_atoms_real(MemChunk *mem_chunk)
  {

  return mem_chunk->mem_tree?TRUE:FALSE;
  }


static MemChunk *_mem_chunk_new(size_t atom_size, unsigned int num_atoms)
  {
  MemChunk	*mem_chunk;

/*
 * Ensure that we don't misalign allocated memory for the user.
 * This also ensures that the minimum atom_size is okay for the
 * FreeAtom list.
 */
  if (atom_size % MEMORY_ALIGN_SIZE > 0)
    {
    atom_size += MEMORY_ALIGN_SIZE - (atom_size % MEMORY_ALIGN_SIZE);
    printf("DEBUG: modified MemChunk atom size.\n");
    }
#if MEMORY_PADDING==TRUE
  atom_size += 2*MEMORY_ALIGN_SIZE;
#endif

  if ( !(mem_chunk = (MemChunk *) malloc(sizeof(MemChunk))) )
    die("Unable to allocate memory.");

  mem_chunk->num_mem_areas = 0;
  mem_chunk->num_unused_areas = 0;
  mem_chunk->mem_area = NULL;
  mem_chunk->free_mem_area = NULL;
  mem_chunk->free_atoms = NULL;
  mem_chunk->mem_areas = NULL;
  mem_chunk->atom_size = atom_size;
  mem_chunk->area_size = atom_size*num_atoms;
  mem_chunk->mem_tree = NULL;
  
  return mem_chunk;
  }


/*
 * Return TRUE is the memory chunk is empty.
 */
boolean mem_chunk_isempty_real(MemChunk *mem_chunk)
  {

  if (!mem_chunk) die("Null pointer to mem_chunk passed.");

  return mem_chunk->num_mem_areas==mem_chunk->num_unused_areas;
  }


/*
 * Constricted memory chunks: Atoms may not be individually released.
 */
MemChunk *mem_chunk_new_unfreeable_real(size_t atom_size, unsigned int num_atoms)
  {
  MemChunk	*mem_chunk;

  if (atom_size<1) die("Passed atom size is < 1 byte.");
  if (num_atoms<1) die("Passed number of atoms is < 1.");

  mem_chunk = _mem_chunk_new(atom_size, num_atoms);

  return mem_chunk;
  }


MemChunk *mem_chunk_new_real(size_t atom_size, unsigned int num_atoms)
  {
  MemChunk	*mem_chunk;

  if (atom_size<1) die("Passed atom size is < 1 byte.");
  if (num_atoms<1) die("Passed number of atoms is < 1.");

  mem_chunk = _mem_chunk_new(atom_size, num_atoms);
  mem_chunk->mem_tree = tree_new();
  
  return mem_chunk;
  }


void mem_chunk_destroy_real(MemChunk *mem_chunk)
  {
  MemArea *mem_areas;
  MemArea *temp_area;

  if (!mem_chunk) die("Null pointer to mem_chunk passed.");

  mem_areas = mem_chunk->mem_areas;
  while (mem_areas)
    {
    temp_area = mem_areas;
    mem_areas = mem_areas->next;
    free(temp_area);
    }
  
  delete(mem_chunk->mem_tree);
  
  free(mem_chunk);

  return;
  }


void *mem_chunk_alloc_real(MemChunk *mem_chunk)
  {
  MemArea *temp_area;
  void *mem;

  if (!mem_chunk) die("Null pointer to mem_chunk passed.");

  while (mem_chunk->free_atoms)
    {
      /* Get the first piece of memory on the "free_atoms" list.
       * We can go ahead and destroy the list node we used to keep
       *  track of it with and to update the "free_atoms" list to
       *  point to its next element.
       */
      mem = mem_chunk->free_atoms;
      mem_chunk->free_atoms = mem_chunk->free_atoms->next;

      /* Determine which area this piece of memory is allocated from */
      temp_area = ordered_search(mem_chunk->mem_tree, mem);

      /* If the area is unused, then it may be destroyed.
       * We check to see if all of the segments on the free list that
       *  reference this area have been removed. This occurs when
       *  the ammount of free memory is less than the allocatable size.
       * If the chunk should be freed, then we place it in the "free_mem_area".
       * This is so we make sure not to free the memory area here and then
       *  allocate it again a few lines down.
       * If we don't allocate a chunk a few lines down then the "free_mem_area"
       *  will be freed.
       * If there is already a "free_mem_area" then we'll just free this memory area.
       */
      if (temp_area->used==0)
        {
          /* Update the "free" memory available in that area */
          temp_area->free += mem_chunk->atom_size;

          if (temp_area->free == mem_chunk->area_size)
            {
              if (temp_area == mem_chunk->mem_area)
                mem_chunk->mem_area = NULL;

              if (mem_chunk->free_mem_area)
                {
                mem_chunk->num_mem_areas--;

                  if (temp_area->next)
                    temp_area->next->prev = temp_area->prev;
                  if (temp_area->prev)
                    temp_area->prev->next = temp_area->next;
                  if (temp_area == mem_chunk->mem_areas)
                    mem_chunk->mem_areas = mem_chunk->mem_areas->next;

                  if (mem_chunk->mem_tree)
                    {
                    if (!remove_data(mem_chunk->mem_tree, temp_area)) die("Unable to find temp_area.");
                    }

                  free (temp_area);
                }
              else
                mem_chunk->free_mem_area = temp_area;

              mem_chunk->num_unused_areas--;
            }
        }
      else
        {
          /* Update the number of allocated atoms count.
           */
          temp_area->used++;

          /* The area is still in use...return the memory
           */
#if MEMORY_PADDING==TRUE
  set_pad_low(mem_chunk, mem);
  set_pad_high(mem_chunk, mem);
/*
  if (check_pad_low(mem_chunk, mem)!=0) die("LOW MEMORY_PADDING ALREADY CORRUPT!");
  if (check_pad_high(mem_chunk, mem)!=0) die("HIGH MEMORY_PADDING ALREADY CORRUPT!");
*/
  mem = BUMP_UP(mem);
#endif

        return mem;
        }
    }

  /* If there isn't a current memory area or the current memory area is out of
   * space then allocate a new memory area. We'll first check and see if we can
   * use the "free_mem_area".  Otherwise we'll just malloc the memory area.
   */
  if ((!mem_chunk->mem_area) ||
      ((mem_chunk->mem_area->index + mem_chunk->atom_size) > mem_chunk->area_size))
    {
      if (mem_chunk->free_mem_area)
        {
          mem_chunk->mem_area = mem_chunk->free_mem_area;
          mem_chunk->free_mem_area = NULL;
        }
      else
        {
          mem_chunk->mem_area = (MemArea*) malloc(sizeof(MemArea)+
                                                  MEMORY_ALIGN_SIZE-(sizeof(MemArea)%MEMORY_ALIGN_SIZE)+
                                                  mem_chunk->area_size);
          mem_chunk->mem_area->mem = ((unsigned char*) (mem_chunk->mem_area)+
                                     sizeof(MemArea)+
                                     MEMORY_ALIGN_SIZE-
                                     (sizeof(MemArea)%MEMORY_ALIGN_SIZE));

          if (!mem_chunk->mem_area) die("Unable to allocate memory.");

          mem_chunk->num_mem_areas++;
          mem_chunk->mem_area->next = mem_chunk->mem_areas;
          mem_chunk->mem_area->prev = NULL;

          if (mem_chunk->mem_areas)
            mem_chunk->mem_areas->prev = mem_chunk->mem_area;
          mem_chunk->mem_areas = mem_chunk->mem_area;

          if (mem_chunk->mem_tree)
            insert(mem_chunk->mem_tree, mem_chunk->mem_area);
        }

      mem_chunk->mem_area->index = 0;