gtree.c

嵌入式下基于MiniGUI的Web Browser

  if (tree->root)
    return g_tree_node_search (tree->root, search_func, user_data);
  else
    return NULL;
}

/**
 * g_tree_height:
 * @tree: a #GTree.
 * 
 * Gets the height of a #GTree.
 *
 * If the #GTree contains no nodes, the height is 0.
 * If the #GTree contains only one root node the height is 1.
 * If the root node has children the height is 2, etc.
 * 
 * Return value: the height of the #GTree.
 **/
gint
g_tree_height (GTree *tree)
{
  g_return_val_if_fail (tree != NULL, 0);

  if (tree->root)
    return g_tree_node_height (tree->root);
  else
    return 0;
}

/**
 * g_tree_nnodes:
 * @tree: a #GTree.
 * 
 * Gets the number of nodes in a #GTree.
 * 
 * Return value: the number of nodes in the #GTree.
 **/
gint
g_tree_nnodes (GTree *tree)
{
  g_return_val_if_fail (tree != NULL, 0);

  if (tree->root)
    return g_tree_node_count (tree->root);
  else
    return 0;
}

static GTreeNode*
g_tree_node_insert (GTree     *tree,
                    GTreeNode *node,
		    gpointer   key,
		    gpointer   value,
                    gboolean   replace,
		    gboolean  *inserted)
{
  gint  old_balance;
  gint  cmp;

  if (!node)
    {
      *inserted = TRUE;
      return g_tree_node_new (key, value);
    }

  cmp = tree->key_compare (key, node->key, tree->key_compare_data);
  if (cmp == 0)
    {
      *inserted = FALSE;

      if (tree->value_destroy_func)
	tree->value_destroy_func (node->value);

      node->value = value;
      
      if (replace)
	{
	  if (tree->key_destroy_func)
	    tree->key_destroy_func (node->key);

	  node->key = key;
	}
      else
	{
	  /* free the passed key */
	  if (tree->key_destroy_func)
	    tree->key_destroy_func (key);
	}

      return node;
    }

  if (cmp < 0)
    {
      if (node->left)
	{
	  old_balance = node->left->balance;
	  node->left = g_tree_node_insert (tree,
                                           node->left,
					   key, value,
					   replace, inserted);

	  if ((old_balance != node->left->balance) && node->left->balance)
	    node->balance -= 1;
	}
      else
	{
	  *inserted = TRUE;
	  node->left = g_tree_node_new (key, value);
	  node->balance -= 1;
	}
    }
  else if (cmp > 0)
    {
      if (node->right)
	{
	  old_balance = node->right->balance;
	  node->right = g_tree_node_insert (tree,
                                            node->right,
					    key, value, 
					    replace, inserted);

	  if ((old_balance != node->right->balance) && node->right->balance)
	    node->balance += 1;
	}
      else
	{
	  *inserted = TRUE;
	  node->right = g_tree_node_new (key, value);
	  node->balance += 1;
	}
    }

  if (*inserted)
    {
      if ((node->balance < -1) || (node->balance > 1))
	node = g_tree_node_balance (node);
    }

  return node;
}

static GTreeNode*
g_tree_node_remove (GTree         *tree,
                    GTreeNode     *node,
		    gconstpointer  key,
                    gboolean       notify)
{
  GTreeNode *new_root;
  gint old_balance;
  gint cmp;

  if (!node)
    return NULL;

  cmp = tree->key_compare (key, node->key, tree->key_compare_data);
  if (cmp == 0)
    {
      GTreeNode *garbage;

      garbage = node;

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

      if (notify)
        {
          if (tree->key_destroy_func)
            tree->key_destroy_func (garbage->key);
          if (tree->value_destroy_func)
            tree->value_destroy_func (garbage->value);
        }

#ifdef ENABLE_GC_FRIENDLY
      garbage->left = NULL;
      garbage->key = NULL;
      garbage->value = NULL;
#endif /* ENABLE_GC_FRIENDLY */

      G_LOCK (g_tree_global);
      garbage->right = node_free_list;
      node_free_list = garbage;
      G_UNLOCK (g_tree_global);
   }
  else if (cmp < 0)
    {
      if (node->left)
	{
	  old_balance = node->left->balance;
	  node->left = g_tree_node_remove (tree, node->left, key, notify);
	  node = g_tree_node_restore_left_balance (node, old_balance);
	}
    }
  else if (cmp > 0)
    {
      if (node->right)
	{
	  old_balance = node->right->balance;
	  node->right = g_tree_node_remove (tree, node->right, key, notify);
	  node = g_tree_node_restore_right_balance (node, old_balance);
	}
    }

  return node;
}

static GTreeNode*
g_tree_node_balance (GTreeNode *node)
{
  if (node->balance < -1)
    {
      if (node->left->balance > 0)
	node->left = g_tree_node_rotate_left (node->left);
      node = g_tree_node_rotate_right (node);
    }
  else if (node->balance > 1)
    {
      if (node->right->balance < 0)
	node->right = g_tree_node_rotate_right (node->right);
      node = g_tree_node_rotate_left (node);
    }

  return node;
}

static GTreeNode*
g_tree_node_remove_leftmost (GTreeNode  *node,
			     GTreeNode **leftmost)
{
  gint old_balance;

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

  old_balance = node->left->balance;
  node->left = g_tree_node_remove_leftmost (node->left, leftmost);
  return g_tree_node_restore_left_balance (node, old_balance);
}

static GTreeNode*
g_tree_node_restore_left_balance (GTreeNode *node,
				  gint       old_balance)
{
  if (!node->left)
    node->balance += 1;
  else if ((node->left->balance != old_balance) &&
	   (node->left->balance == 0))
    node->balance += 1;

  if (node->balance > 1)
    return g_tree_node_balance (node);
  return node;
}

static GTreeNode*
g_tree_node_restore_right_balance (GTreeNode *node,
				   gint       old_balance)
{
  if (!node->right)
    node->balance -= 1;
  else if ((node->right->balance != old_balance) &&
	   (node->right->balance == 0))
    node->balance -= 1;

  if (node->balance < -1)
    return g_tree_node_balance (node);
  return node;
}

static GTreeNode *
g_tree_node_lookup (GTreeNode        *node,
		    GCompareDataFunc  compare,
		    gpointer          compare_data,
		    gconstpointer     key)
{
  gint cmp;

  if (!node)
    return NULL;

  cmp = (* compare) (key, node->key, compare_data);
  if (cmp == 0)
    return node;

  if (cmp < 0)
    {
      if (node->left)
	return g_tree_node_lookup (node->left, compare, compare_data, key);
    }
  else if (cmp > 0)
    {
      if (node->right)
	return g_tree_node_lookup (node->right, compare, compare_data, key);
    }

  return NULL;
}

static gint
g_tree_node_count (GTreeNode *node)
{
  gint count;

  count = 1;
  if (node->left)
    count += g_tree_node_count (node->left);
  if (node->right)
    count += g_tree_node_count (node->right);

  return count;
}

static gint
g_tree_node_pre_order (GTreeNode     *node,
		       GTraverseFunc  traverse_func,
		       gpointer       data)
{
  if ((*traverse_func) (node->key, node->value, data))
    return TRUE;
  if (node->left)
    {
      if (g_tree_node_pre_order (node->left, traverse_func, data))
	return TRUE;
    }
  if (node->right)
    {
      if (g_tree_node_pre_order (node->right, traverse_func, data))
	return TRUE;
    }

  return FALSE;
}

static gint
g_tree_node_in_order (GTreeNode     *node,
		      GTraverseFunc  traverse_func,
		      gpointer       data)
{
  if (node->left)
    {
      if (g_tree_node_in_order (node->left, traverse_func, data))
	return TRUE;
    }
  if ((*traverse_func) (node->key, node->value, data))
    return TRUE;
  if (node->right)
    {
      if (g_tree_node_in_order (node->right, traverse_func, data))
	return TRUE;
    }

  return FALSE;
}

static gint
g_tree_node_post_order (GTreeNode     *node,
			GTraverseFunc  traverse_func,
			gpointer       data)
{
  if (node->left)
    {
      if (g_tree_node_post_order (node->left, traverse_func, data))
	return TRUE;
    }
  if (node->right)
    {
      if (g_tree_node_post_order (node->right, traverse_func, data))
	return TRUE;
    }
  if ((*traverse_func) (node->key, node->value, data))
    return TRUE;

  return FALSE;
}

static gpointer
g_tree_node_search (GTreeNode     *node,
		    GCompareFunc   search_func,
		    gconstpointer  data)
{
  gint dir;

  if (!node)
    return NULL;

  do {
    dir = (* search_func) (node->key, data);
    if (dir == 0)
      return node->value;

    if (dir < 0)
      node = node->left;
    else if (dir > 0)
      node = node->right;
  } while (node);

  return NULL;
}

static gint
g_tree_node_height (GTreeNode *node)
{
  gint left_height;
  gint right_height;

  if (node)
    {
      left_height = 0;
      right_height = 0;

      if (node->left)
	left_height = g_tree_node_height (node->left);

      if (node->right)
	right_height = g_tree_node_height (node->right);

      return MAX (left_height, right_height) + 1;
    }

  return 0;
}

static GTreeNode*
g_tree_node_rotate_left (GTreeNode *node)
{
  GTreeNode *right;
  gint a_bal;
  gint 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 GTreeNode*
g_tree_node_rotate_right (GTreeNode *node)
{
  GTreeNode *left;
  gint a_bal;
  gint 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 void
g_tree_node_check (GTreeNode *node)
{
  gint left_height;
  gint right_height;
  gint balance;
  
  if (node)
    {
      left_height = 0;
      right_height = 0;
      
      if (node->left)
	left_height = g_tree_node_height (node->left);
      if (node->right)
	right_height = g_tree_node_height (node->right);
      
      balance = right_height - left_height;
      if (balance != node->balance)
	g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO,
	       "g_tree_node_check: failed: %d ( %d )\n",
	       balance, node->balance);
      
      if (node->left)
	g_tree_node_check (node->left);
      if (node->right)
	g_tree_node_check (node->right);
    }
}