CVS commit: src

[Mindaugas Rasiukevicius <rmind%netbsd.org@localhost>]

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.