[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

Bug#63575: twalk()+tdelete() example incompatible with balanced tree deletion

Well a peek at tsearch.c enlightened me a bit:
The example in tsearch(3) has the following bit:
       The example program depends on the fact that  twalk  makes
       no  further  reference  to  a  node after calling the user
       function with argument "endorder" or "leaf".   This  works
       with  the  GNU  library  implementation, but is not in the
       SysV documentation.
Now that isn't exactly true with the current red-black tree implemenatation
as tdelete() mangles the tree in a way that makes it incompatible with twalk().

So it looks like the example was written back when tsearch used unbalanced
trees (like the other *IXes) instead of red-black trees. Maybe the manual page
should be updated to mention tdestroy() too? (as non-standard function)
... and yes I know the info pages are much more up to date ;)

There are two ways to fix this bug:
1. the evil way: abort() if tdelete() is called from twalk()
2. the compatible way: make tdelete() called from twalk() act like tdestroy()

Implementing the compatible way should be rather trivial once somebody gets
the evil way done ;)

Attachment: pgpfFMI4Ld6Sn.pgp
Description: PGP signature

Reply to: