]> git.itanic.dy.fi Git - scan-pagemap/commit
Replace bintree with rbtree implementation
authorTimo Kokkonen <kaapeli@itanic.dy.fi>
Sat, 15 Oct 2011 18:02:26 +0000 (21:02 +0300)
committerTimo Kokkonen <kaapeli@itanic.dy.fi>
Sat, 15 Oct 2011 18:19:04 +0000 (21:19 +0300)
commit9778934872cd83a6f5c06bc981381212b3e120b3
tree9ccba53d3f3b2edfa7f3b53686c2394684731860
parent57d8370a98d2bb36fff331a7a4a0bc14310f22b9
Replace bintree with rbtree implementation

The biggest flaw with the bintree is that they can easily become
unbalanced. For example, if X server maps the video card memory into
its address space as 1:1 mapping, running scan-pagemap can be really
slow. This is because reading the 1:1 mapping will generate horribly
skewed binary tree that resembles more closely a single direction
linked list. Replacing the simple binary tree implementation with the
red black tree can make full scan over five times faster.

Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Makefile
analyze.c
analyze.h
main.c
pagemap.h
parse.c
parse.h
treeops.c [new file with mode: 0644]