gdsl_rbtree.c

一个通用的C语言实现的数据结构

					    rbtree_left_rot (sister);
					    sister = LEFT (parent);
					}
				    sister->color = COLOR (parent);
				    sister->left->color = BLACK;
				    parent->color = BLACK;
				    rbtree_right_rot (parent);
				    break;
				}
			}
		}

	    child->color = BLACK;
	    t->sent.right->color = BLACK;
	}

    e = CONTENT (n);
    rbtree_node_free (n);

    return e;
}

extern gdsl_rbtree_t
gdsl_rbtree_delete (gdsl_rbtree_t t, void* v)
{
    gdsl_element_t e;

    assert (t != NULL);

    e = gdsl_rbtree_remove (t, v);

    if (e == NULL)
	{
	    return NULL;
	}

    t->free_f (e);

    return t;
}

/******************************************************************************/
/* Search functions of red-black trees                                        */
/******************************************************************************/

extern gdsl_element_t
gdsl_rbtree_search (const gdsl_rbtree_t t, gdsl_compare_func_t comp_f, void* v)
{
    gdsl_rbtree_node_t n;

    assert (t != NULL);

    n = rbtree_search (ROOT (t), SENT (t), comp_f ? comp_f : t->comp_f, v);

    return (n == NULL) ? NULL : CONTENT (n);
}

/******************************************************************************/
/* Parse functions of red-black trees                                         */
/******************************************************************************/

extern gdsl_element_t
gdsl_rbtree_map_prefix (const gdsl_rbtree_t t, gdsl_map_func_t map_f, void* d)
{
    assert (t != NULL);
    assert (map_f != NULL);

    return rbtree_prefix_parse (ROOT (t), SENT (t), map_f, d);
}

extern gdsl_element_t
gdsl_rbtree_map_infix (const gdsl_rbtree_t t, gdsl_map_func_t map_f, void* d)
{
    assert (t != NULL);
    assert (map_f != NULL);

    return rbtree_infix_parse (ROOT (t), SENT (t), map_f, d);
}

extern gdsl_element_t
gdsl_rbtree_map_postfix (const gdsl_rbtree_t t, gdsl_map_func_t map_f, void* d)
{
    assert (t != NULL);
    assert (map_f != NULL);

    return rbtree_postfix_parse (ROOT (t), SENT (t), map_f, d);
}

/******************************************************************************/
/* Input/output functions of red-black trees                                  */
/******************************************************************************/

extern void
gdsl_rbtree_write (const gdsl_rbtree_t t, gdsl_write_func_t write_f, 
		   FILE* file, void* d)
{
    assert (t != NULL);
    assert (write_f != NULL);
    assert (file != NULL);

    rbtree_write (ROOT (t), SENT (t), write_f, file, d);
}

extern void
gdsl_rbtree_write_xml (const gdsl_rbtree_t t, gdsl_write_func_t write_f, 
		       FILE* file, void* d)
{
    assert (t != NULL);
    assert (file != NULL);

    fprintf (file, "<GDSL_RBTREE NAME=\"%s\" CARD=\"%ld\">\n", 
	     t->name, t->card);

    rbtree_write_xml (ROOT (t), SENT (t), write_f, file, d);

    fprintf (file, "</GDSL_RBTREE>\n");
}

extern void
gdsl_rbtree_dump (const gdsl_rbtree_t t, gdsl_write_func_t write_f, 
		  FILE* file, void* d)
{
    assert (t != NULL);
    assert (file != NULL);

    fprintf (file, "<GDSL_RBTREE REF=\"%p\" NAME=\"%s\" CARD=\"%ld\">\n", 
	     (void *) t, t->name, t->card);
    fprintf (file, "<GDSL_RBTREE_SENT REF=\"%p\" LEFT=\"%p\" RIGHT=\"%p\" PARENT=\"%p\"", 
	     (void *) SENT (t), (void *) t->sent.left, (void *) t->sent.right, 
	     (void *) PARENT (SENT (t)));
    fprintf (file, " COLOR=\"%s\"/>\n", COLOR (SENT (t)) == RED ? "RED" : "BLACK");

    rbtree_dump (ROOT (t), SENT (t), write_f, file, d);

    fprintf (file, "</GDSL_RBTREE>\n");
}

/******************************************************************************/
/* Private functions                                                          */
/******************************************************************************/

static gdsl_element_t 
default_alloc (void* v)
{
    return v;
}

static void 
default_free (gdsl_element_t e)
{
    ;
}

static long int 
default_compare (gdsl_element_t e, void* v)
{
    return 0;
}

static gdsl_rbtree_node_t
rbtree_node_alloc (gdsl_rbtree_t t, gdsl_element_t e)
{
    gdsl_rbtree_node_t n;

    n = (gdsl_rbtree_node_t) malloc (sizeof (struct gdsl_rbtree_node));

    if (n == NULL)
	{
	    return NULL;
	}
  
    n->left    = SENT (t);
    n->right   = SENT (t);
    n->parent  = SENT (t);
    n->content = e;
    n->color   = RED;

    return n;
}

static void
rbtree_node_free (gdsl_rbtree_node_t n)
{
    free (n);
}

static void 
rbtree_destroy (gdsl_rbtree_node_t n, gdsl_rbtree_node_t sent, gdsl_free_func_t free_f)
{
    if (n != sent)
	{
	    rbtree_destroy (LEFT (n), sent, free_f);
	    rbtree_destroy (RIGHT (n), sent, free_f);
	    free_f (CONTENT (n));
	    free (n);
	}
}

static ulong
rbtree_size (gdsl_rbtree_node_t n, gdsl_rbtree_node_t sent)
{
    if (n == sent)
	{
	    return 0UL;
	}

    return (ulong) (1UL 
		    + rbtree_size (LEFT (n), sent)
		    + rbtree_size (RIGHT (n), sent));
}

static ulong
rbtree_height (gdsl_rbtree_node_t n, gdsl_rbtree_node_t sent)
{
    if (n == sent)
	{
	    return 0UL;
	}

    if (LEFT (n) == sent && RIGHT (n) == sent)
	{
	    return 0UL;
	}

    return (ulong) (1UL + 
		    GDSL_MAX (rbtree_height (LEFT (n), sent),
			      rbtree_height (RIGHT (n), sent)));
}

static gdsl_rbtree_node_t
rbtree_left_rot (gdsl_rbtree_node_t n)
{
    gdsl_rbtree_node_t rn;

    rn = RIGHT (n);
    n->right = LEFT (rn);

    /* LEFT( rn ) is always != NULL */
    rn->left->parent = n;

    rn->parent = PARENT (n);
  
    if (n == LEFT (PARENT (n)))
	{
	    n->parent->left = rn;
	}
    else
	{
	    n->parent->right = rn;
	}

    rn->left = n;
    n->parent = rn;

    return rn;
}

static gdsl_rbtree_node_t
rbtree_right_rot (gdsl_rbtree_node_t n)
{
    gdsl_rbtree_node_t ln;

    ln = LEFT (n);
    n->left = RIGHT (ln);

    /* RIGHT( ln ) is always != NULL */
    ln->right->parent = n;

    ln->parent = PARENT (n);

    if (n == RIGHT (PARENT (n)))
	{
	    n->parent->right = ln;
	}
    else
	{
	    n->parent->left = ln;
	}

    ln->right = n;
    n->parent = ln;

    return ln;
}

static gdsl_rbtree_node_t
rbtree_search (gdsl_rbtree_node_t root, gdsl_rbtree_node_t sent, 
	       gdsl_compare_func_t f, void* v)
{
    int comp;

    while (root != sent)
	{
	    comp = f (CONTENT (root), v);

	    if (comp == 0)
		{
		    return root;
		}

	    root = (comp > 0) ? LEFT (root) : RIGHT (root);
	}

    return NULL;
}

static gdsl_rbtree_node_t
rbtree_next (gdsl_rbtree_t t, gdsl_rbtree_node_t n)
{
    n = RIGHT (n);
  
    while (LEFT (n) != SENT (t))
	{
	    n = LEFT (n);
	}

    return n;
}

static gdsl_element_t
rbtree_prefix_parse (gdsl_rbtree_node_t root, gdsl_rbtree_node_t sent, 
		     gdsl_map_func_t map_f, void* d)
{
    if (root != sent)
	{
	    gdsl_element_t e = CONTENT (root);

	    if (map_f (e, get_location (root, sent), d) == GDSL_MAP_STOP)
		{
		    return e;
		}

	    rbtree_prefix_parse (LEFT (root), sent, map_f, d);
	    rbtree_prefix_parse (RIGHT (root), sent, map_f, d);
	}

    return NULL;
}

static gdsl_element_t
rbtree_infix_parse (gdsl_rbtree_node_t root, gdsl_rbtree_node_t sent, 
		    gdsl_map_func_t map_f, void* d)
{
    if (root != sent)
	{
	    gdsl_element_t e;

	    rbtree_infix_parse (LEFT (root), sent, map_f, d);

	    e = CONTENT (root);

	    if (map_f (e, get_location (root, sent), d) == GDSL_MAP_STOP)
		{
		    return e;
		}

	    rbtree_infix_parse (RIGHT (root), sent, map_f, d);
	}

    return NULL;
}

static gdsl_element_t
rbtree_postfix_parse (gdsl_rbtree_node_t root, gdsl_rbtree_node_t sent, 
		      gdsl_map_func_t map_f, void* d)
{
    if (root != sent)
	{
	    gdsl_element_t e;

	    rbtree_postfix_parse (LEFT (root), sent, map_f, d);
	    rbtree_postfix_parse (RIGHT (root), sent, map_f, d);

	    e = CONTENT (root);

	    if (map_f (e, get_location (root, sent), d) == GDSL_MAP_STOP)
		{
		    return e;
		}
	}

    return NULL;
}

static void
rbtree_write (gdsl_rbtree_node_t n, gdsl_rbtree_node_t sent, 
	      gdsl_write_func_t write_f, FILE* file, void* d)
{
    if (n != sent)
	{
	    rbtree_write (LEFT (n), sent, write_f, file, d);
	    write_f (CONTENT (n), file, get_location (n, sent), d);
	    rbtree_write (RIGHT (n), sent, write_f, file, d);
	}
}

static void
rbtree_write_xml (gdsl_rbtree_node_t n, gdsl_rbtree_node_t sent, 
		  gdsl_write_func_t write_f, FILE* file, void* d)
{
    if (n != sent)
	{
	    rbtree_write_xml (LEFT (n), sent, write_f, file, d);

	    if (LEFT (n) == sent && RIGHT (n) == sent)
		{
		    fprintf (file, "<GDSL_RBTREE_LEAF REF=\"%p\"", (void *) n);
		}
	    else
		{
		    fprintf (file, "<GDSL_RBTREE_NODE REF=\"%p\"", (void *) n);
		}

	    if (LEFT (n) != sent || RIGHT (n) != sent)
		{
		    if (LEFT (n) != sent)
			{
			    fprintf (file, " LEFT=\"%p\"", (void *) LEFT (n));
			}
		    else
			{
			    fprintf (file, " LEFT=\"\"");
			}
	  
		    if (RIGHT (n) != sent)
			{
			    fprintf (file, " RIGHT=\"%p\"", (void *) RIGHT (n));
			}
		    else
			{
			    fprintf (file, " RIGHT=\"\"");
			}
		}

	    if (PARENT (n) != sent)
		{
		    fprintf (file, " PARENT=\"%p\"", (void *) PARENT (n));
		}
	    else
		{
		    fprintf (file, " PARENT=\"\"");
		}

	    fprintf (file, " COLOR=\"%s\">", COLOR (n) == RED ? "RED" : "BLACK");

	    if (write_f != NULL && CONTENT (n) != NULL)
		{
		    write_f (CONTENT (n), file, get_location (n, sent), d);
		}

	    if (LEFT (n) == sent && RIGHT (n) == sent)
		{
		    fprintf (file, "</GDSL_RBTREE_LEAF>\n");
		}
	    else
		{
		    fprintf (file, "</GDSL_RBTREE_NODE>\n");
		}

	    rbtree_write_xml (RIGHT (n), sent, write_f, file, d);
	}
}

static void
rbtree_dump (gdsl_rbtree_node_t n, gdsl_rbtree_node_t sent, gdsl_write_func_t write_f, 
	     FILE* file, void* d)
{
    if (n != sent)
	{
	    rbtree_dump (LEFT (n), sent, write_f, file, d);

	    if (LEFT (n) == sent && RIGHT (n) == sent)
		{
		    fprintf (file, "<GDSL_RBTREE_LEAF REF=\"%p\"", (void *) n);
		}
	    else
		{
		    fprintf (file, "<GDSL_RBTREE_NODE REF=\"%p\"", (void *) n);
		}

	    if (CONTENT (n))
		{
		    fprintf (file, " CONTENT=\"%p\"", (void *) CONTENT (n));
		}
	    else
		{
		    fprintf (file, " CONTENT=\"\"");
		}

	    fprintf (file, " LEFT=\"%p\" RIGHT=\"%p\"", (void *) LEFT (n), 
		     (void *) RIGHT (n));

	    if (PARENT (n))
		{
		    fprintf (file, " PARENT=\"%p\"", (void *) PARENT (n));
		}
	    else
		{
		    fprintf (file, " PARENT=\"\"");
		}

	    fprintf (file, " COLOR=\"%s\">", COLOR (n) == RED ? "RED" : "BLACK");

	    if (write_f != NULL && CONTENT (n) != NULL)
		{
		    write_f (CONTENT (n), file, get_location (n, sent), d);
		}

	    if (LEFT (n) == sent && RIGHT (n) == sent)
		{
		    fprintf (file, "</GDSL_RBTREE_LEAF>\n");
		}
	    else
		{
		    fprintf (file, "</GDSL_RBTREE_NODE>\n");
		}

	    rbtree_dump (RIGHT (n), sent, write_f, file, d);
	}
}

static gdsl_location_t
get_location (gdsl_rbtree_node_t n, gdsl_rbtree_node_t s)
{
    gdsl_location_t location = GDSL_LOCATION_UNDEF;

    if (LEFT (n) == s && RIGHT (n) == s)
	{
	    location |= GDSL_LOCATION_LEAF;
	}

    if (PARENT (n) == s)
	{
	    location |= GDSL_LOCATION_ROOT;
	}

    return location;
}


/** EMACS **
 * Local variables:
 * mode: c
 * c-basic-offset: 4
 * End:
 */