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

[Eirik Nygaard <eirikn@xxxxxxxxxxxx>]

On Wed, Jan 19, 2005 at 02:16:57PM -0800, Matthew Dillon wrote:
> 
> :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?
						No, it is not 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:
Good idea.
> 
> 	/*
> 	 * 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@xxxxxxxxxxxxx>
> 

I will do some more testing here and see if I hit the hint problem. Is there a
possibility it hits another invalid entry, perhaps it has something to do with
the map->hint = entry->prev; change?

-- 
Eirik Nygaard