Module Name: src Committed By: rmind Date: Fri Sep 24 22:51:52 UTC 2010
Modified Files: src/common/lib/libc/gen: rb.c src/common/lib/libprop: prop_dictionary.c prop_number.c src/sys/fs/udf: udf.h udf_subr.c src/sys/kern: subr_lockdebug.c src/sys/net/npf: npf_session.c npf_tableset.c src/sys/nfs: nfs_node.c src/sys/rump/librump/rumpkern: vm.c src/sys/sys: rb.h src/sys/uvm: uvm_map.c uvm_object.h uvm_page.c Log Message: Fixes/improvements to RB-tree implementation: 1. Fix inverted node order, so that negative value from comparison operator would represent lower (left) node, and positive - higher (right) node. 2. Add an argument (i.e. "context"), passed to comparison operators. 3. Change rb_tree_insert_node() to return a node - either inserted one or already existing one. 4. Amend the interface to manipulate the actual object, instead of the rb_node (in a similar way as Patricia-tree interface does). 5. Update all RB-tree users accordingly. XXX: Perhaps rename rb.h to rbtree.h, since cleaning-up.. 1-3 address the PR/43488 by Jeremy Huddleston. Passes RB-tree regression tests. Reviewed by: matt@, christos@ To generate a diff of this commit: cvs rdiff -u -r1.6 -r1.7 src/common/lib/libc/gen/rb.c cvs rdiff -u -r1.35 -r1.36 src/common/lib/libprop/prop_dictionary.c cvs rdiff -u -r1.22 -r1.23 src/common/lib/libprop/prop_number.c cvs rdiff -u -r1.41 -r1.42 src/sys/fs/udf/udf.h cvs rdiff -u -r1.107 -r1.108 src/sys/fs/udf/udf_subr.c cvs rdiff -u -r1.41 -r1.42 src/sys/kern/subr_lockdebug.c cvs rdiff -u -r1.2 -r1.3 src/sys/net/npf/npf_session.c cvs rdiff -u -r1.1 -r1.2 src/sys/net/npf/npf_tableset.c cvs rdiff -u -r1.113 -r1.114 src/sys/nfs/nfs_node.c cvs rdiff -u -r1.95 -r1.96 src/sys/rump/librump/rumpkern/vm.c cvs rdiff -u -r1.13 -r1.14 src/sys/sys/rb.h cvs rdiff -u -r1.292 -r1.293 src/sys/uvm/uvm_map.c cvs rdiff -u -r1.26 -r1.27 src/sys/uvm/uvm_object.h cvs rdiff -u -r1.155 -r1.156 src/sys/uvm/uvm_page.c Please note that diffs are not public domain; they are subject to the copyright notices on the relevant files.