I would definitely recommend a skip list or splay tree. Both are very
fast. Both are very short code. (_Much_ shorter and simpler than the
AVL code was).
The skip list has the advantage that it's fairly simple to code and
nothing is written (cache advantage).
The splay tree has the advantage that it automatically caches the
recently used entries. So much so that there's no need for a one entry
cache in front of it.
Both have the advantage that you don't need to maintain any invariants,
so the cutting and glueing operations for new vmas etc. are simple in
both cases. Actually I'd say the splay tree is easier for this.
-- Jamie
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.altern.org/andrebalsa/doc/lkml-faq.html