}  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==TRUEstatic 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;