Re: splay tree and red-black tree for vm_map entry lookups.
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@backplane.com>
>
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
討論串 (同標題文章)
完整討論串 (本文為第 9 之 11 篇)：