splay tree and red-black tree for vm_map entry lookups.

Matthew Dillon dillon at apollo.backplane.com
Wed Jan 19 14:18:29 PST 2005


:Works a lot better now (I can log in and everything).
:
:http://leaf.dragonflybsd.org/~eirikn/vm_map-rb-tree-netbsd-eirikn-hint.patch
:
:-- 
:Eirik Nygaard

    Looking good.  I think there are some minor code cleanups
    that can be done.  For example:

        while (tmp) {
		if (address >= tmp->start) {
			...
                } else {
                        tmp = RB_LEFT(tmp, rb_entry);
                }
                *entry = last;		<<<<<<<<<<<<< IS THIS NEEDED?
        }
                                   
        /*
         * If there are no entries yet last will end up being NULL and we need
         * to set it to &map->header.
         */
        if (last == NULL)
                last = &map->header;

        *entry = last;
        return (FALSE);

    Double check, but I think that '*entry = last' in the loop
    is not necessary.

    Also, I think you can pre-initialize the 'last' variable
    to &map->header at the top and then get rid of this code:

	/*
	 * If there are no entries yet last will end up being NULL and we need
	 * to set it to &map->header.
	 */
	if (last == NULL)
		last = &map->header;

					-Matt
					Matthew Dillon 
					<dillon at xxxxxxxxxxxxx>





More information about the Kernel mailing list