[brlcad-commits] SF.net SVN: brlcad:[49996] brlcad/trunk/include/bu.h
Open Source Solid Modeling CAD
Brought to you by:
brlcad
From: <tbr...@us...> - 2012-04-13 11:58:32
|
Revision: 49996 http://brlcad.svn.sourceforge.net/brlcad/?rev=49996&view=rev Author: tbrowder2 Date: 2012-04-13 11:58:25 +0000 (Fri, 13 Apr 2012) Log Message: ----------- expand note further highlighting possible errors in impementation Modified Paths: -------------- brlcad/trunk/include/bu.h Modified: brlcad/trunk/include/bu.h =================================================================== --- brlcad/trunk/include/bu.h 2012-04-13 11:42:03 UTC (rev 49995) +++ brlcad/trunk/include/bu.h 2012-04-13 11:58:25 UTC (rev 49996) @@ -2304,9 +2304,21 @@ * Many of these routines are based on the algorithms in chapter 13 of * Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, * "Introduction to Algorithms", MIT Press, Cambridge, MA, 1990. - * (Note that the third edition was published in 2009 and the book - * has had significant updates since the first edition.) * + * FIXME: check implementation given the following note: + * + * Note that the third edition was published in 2009 and the book + * has had significant updates since the first edition. Quoting the + * authors in the preface: "The way we delete a node from binary search + * trees (which includes red-black trees) now guarantees that the node + * requested for deletion is the node that is actually deleted. In the + * first two editions, in certain cases, some other node would be + * deleted, with its contents movings into the node passed to the + * deletion procedure. With our new way to delete nodes, if other + * components of a program maintain pointers to nodes in the tree, they + * will not mistakenly end up with stale pointers to nodes that have + * been deleted." + * * The implementation of balanced binary red-black tree operations * provides all the basic dynamic set operations (e.g., insertion, * deletion, search, minimum, maximum, predecessor, and successor) and This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |