cvs commit: src/sys/vm vm_map.c vm_map.h

[Matthew Dillon]

dillon      2005/01/20 10:00:38 PST

DragonFly src repository

  Modified files:
    sys/vm               vm_map.c vm_map.h 
  Log:
  Replace the cache-point linear search algorithm for VM map entries with
  a red-black tree.  This makes VM map lookups O(log N) in all cases.
  
  Note that FreeBSD seems to have gone the splay-tree route, but I really
  dislike the fact that splay trees are constantly writing to memory even
  for simple lookups.  This would also limit our ability to implement a
  separate hinting/caching mechanism.  A red-black tree is basically a
  binary tree with internal nodes containing real data in addition to the leafs,
  simlar to a B+Tree.  A red-black tree is very similar to a splay tree but it
  does not attempt to modify the data structure for pure lookups.
  
  Caveat: we tried to revive the map->hint mechanism but there is currently
  a serious crash/lockup bug related to it so it is disabled in this commit.
  
  Submitted-by: Eirik Nygaard <eirikn at xxxxxxxxxxxx>
  Using-Red-Black-Macros-From: NetBSD (sys/tree.h)
  
  Revision  Changes    Path
  1.37      +82 -69    src/sys/vm/vm_map.c
  1.15      +6 -0      src/sys/vm/vm_map.h


http://www.dragonflybsd.org/cvsweb/src/sys/vm/vm_map.c.diff?r1=1.36&r2=1.37&f=u
http://www.dragonflybsd.org/cvsweb/src/sys/vm/vm_map.h.diff?r1=1.14&r2=1.15&f=u