radix-tree: use indirect bit
authorNick Piggin <npiggin@suse.de>
Tue, 16 Oct 2007 08:24:42 +0000 (01:24 -0700)
committerLinus Torvalds <torvalds@woody.linux-foundation.org>
Tue, 16 Oct 2007 16:42:53 +0000 (09:42 -0700)
commitc0bc9875b701c588e448302d41181995c21e8040
treec320855d4c04bd51ded6b4888bc5895ab539165f
parentb55ed816235cf41c29159d22a4cdeec7deb5821c
radix-tree: use indirect bit

Rather than sign direct radix-tree pointers with a special bit, sign the
indirect one that hangs off the root.  This means that, given a lookup_slot
operation, the invalid result will be differentiated from the valid
(previously, valid results could have the bit either set or clear).

This does not affect slot lookups which occur under lock -- they can never
return an invalid result.  Is needed in future for lockless pagecache.

Signed-off-by: Nick Piggin <npiggin@suse.de>
Acked-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Hugh Dickins <hugh@veritas.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
include/linux/radix-tree.h
lib/radix-tree.c