/* Ordered set data type implemented by a binary tree.
- Copyright (C) 2006-2007 Free Software Foundation, Inc.
+ Copyright (C) 2006-2007, 2009-2011 Free Software Foundation, Inc.
Written by Bruno Haible <bruno@clisp.org>, 2006.
This program is free software: you can redistribute it and/or modify
#include <stdlib.h>
-#include "xalloc.h"
-
/* An AVL tree is a binary tree where
1. The height of each node is calculated as
heightof(node) = 1 + max (heightof(node.left), heightof(node.right)).
}
static gl_oset_node_t
-gl_tree_add_first (gl_oset_t set, const void *elt)
+gl_tree_nx_add_first (gl_oset_t set, const void *elt)
{
/* Create new node. */
- gl_oset_node_t new_node = XMALLOC (struct gl_oset_node_impl);
+ gl_oset_node_t new_node =
+ (struct gl_oset_node_impl *) malloc (sizeof (struct gl_oset_node_impl));
+
+ if (new_node == NULL)
+ return NULL;
new_node->left = NULL;
new_node->right = NULL;
}
static gl_oset_node_t
-gl_tree_add_before (gl_oset_t set, gl_oset_node_t node, const void *elt)
+gl_tree_nx_add_before (gl_oset_t set, gl_oset_node_t node, const void *elt)
{
/* Create new node. */
- gl_oset_node_t new_node = XMALLOC (struct gl_oset_node_impl);
+ gl_oset_node_t new_node =
+ (struct gl_oset_node_impl *) malloc (sizeof (struct gl_oset_node_impl));
bool height_inc;
+ if (new_node == NULL)
+ return NULL;
+
new_node->left = NULL;
new_node->right = NULL;
new_node->balance = 0;
}
static gl_oset_node_t
-gl_tree_add_after (gl_oset_t set, gl_oset_node_t node, const void *elt)
+gl_tree_nx_add_after (gl_oset_t set, gl_oset_node_t node, const void *elt)
{
/* Create new node. */
- gl_oset_node_t new_node = XMALLOC (struct gl_oset_node_impl);
+ gl_oset_node_t new_node =
+ (struct gl_oset_node_impl *) malloc (sizeof (struct gl_oset_node_impl));
bool height_inc;
+ if (new_node == NULL)
+ return NULL;
+
new_node->left = NULL;
new_node->right = NULL;
new_node->balance = 0;
const struct gl_oset_implementation gl_avltree_oset_implementation =
{
- gl_tree_create_empty,
+ gl_tree_nx_create_empty,
gl_tree_size,
gl_tree_search,
gl_tree_search_atleast,
- gl_tree_add,
+ gl_tree_nx_add,
gl_tree_remove,
gl_tree_oset_free,
gl_tree_iterator,