From: Damien Miller (djmmindrot.org)
Date: Tue May 02 2006 - 01:15:43 CDT

• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

On Mon, 1 May 2006, Brian wrote:

> I am reading through the tree(3), and I need some clarification. If I
> want to correctly remove an element from a red black tree that I have
> found and free it's memory allocation, this code should work, right?
>
> find.i = 400;
> n = RB_FIND(inttree, &head, &find);
> if (n != NULL) {
> n = RB_REMOVE(inttree, &head, n);
> free(n);
> } else if (n == NULL)
> (void)printf("satisfied NULL check\n");

It depends entirely on how you are allocating the tree entries. You
didn't say... Either way, you don't need to worry about the return
value of RB_REMOVE, just use the value returned by RB_FIND() directly.

> I ask because the man page is clear for splay trees, but I am not
> certain for Red Black trees. I looked at /usr/include/sys/tree.h, and
> I did not find any explicit free's.

That is because it is a data structure and not an allocator. The caller
must do all its own memory management.

> I assume that since RB_REMOVE will provide me with a pointer to the
> removed element, that all I need to do is free it.

RB_FIND() gives you a pointer to the element. RB_REMOVE() just gives
you back whatever element pointer you put in, so there is no point in
looking at the return value.

> Also, is the above the most efficient way to find and remove an
> element from a red black tree?

That depends. It may be to search using RB_FIND(), but your application
may have other ways that are quicker. Who knows?

-d

• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]