linux-stable.git/lib/radix-tree.c, branch linux-2.6.17.y

[PATCH] radix-tree documentation cleanups

2006-03-25T16:22:59+00:00

Documentation changes to help radix tree users avoid overrunning the tags
array.  RADIX_TREE_TAGS moves to linux/radix-tree.h and is now known as
RADIX_TREE_MAX_TAGS (Nick Piggin's idea).  Tag parameters are changed to
unsigned, and some comments are updated.

Signed-off-by: Jonathan Corbet 
Cc: Nick Piggin 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

[PATCH] Fix over-zealous tag clearing in radix_tree_delete

2006-02-16T16:45:50+00:00

If a tag is set for a node being deleted from a radix_tree, then that
tag gets cleared from the parent of the node, even if it is set for some
siblings of the node begin deleted.

This patch changes the logic to include a test for any_tag_set similar
to the logic a little futher down.  Care is taken to ensure that
'nr_cleared_tags' remains equals to the number of entries in the 'tags'
array which are set to '0' (which means that this tag is not set in the
tree below pathp->node, and should be cleared at pathp->node and
possibly above.

[ Nick says: "Linus FYI, I was able to modify the radix tree test
  harness to catch the bug and can no longer trigger it after the fix.
  Resulting code passes all other harness tests as well of course." ]

Signed-off-by: Neil Brown 
Acked-by: Nick Piggin 
Signed-off-by: Linus Torvalds

[PATCH] radix-tree: reduce tree height upon partial truncation

2006-01-09T04:13:41+00:00

Shrink the height of a radix tree when it is partially truncated - we only do
shrinkage of full truncation at present.

Signed-off-by: Nick Piggin 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

[PATCH] radix tree: early termination of tag clearing

2006-01-09T04:13:41+00:00

Correctly determine the tags to be cleared in radix_tree_delete() so we
don't keep moving up the tree clearing tags that we don't need to.  For
example, if a tag is simply not set in the deleted item, nor anywhere up
the tree, radix_tree_delete() would attempt to clear it up the entire
height of the tree.

Also, tag_set() was made conditional so as not to dirty too many cachelines
high up in the radix tree.  Instead, put this logic into
radix_tree_tag_set().

Signed-off-by: Nick Piggin 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

[PATCH] radix tree: code consolidation

2006-01-09T04:13:41+00:00

Introduce helper any_tag_set() rather than repeat the same code sequence 4
times.

Signed-off-by: Nick Piggin 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

[PATCH] reiser4: add radix_tree_lookup_slot()

2005-11-07T15:53:37+00:00

Reiser4 uses radix trees to solve a trouble reiser4_readdir has serving nfs
requests.

Unfortunately, radix tree api lacks an operation suitable for modifying
existing entry.  This patch adds radix_tree_lookup_slot which returns pointer
to found item within the tree.  That location can be then updated.

Both Nick and Christoph Lameter have patches which need this as well.

Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

[PATCH] gfp flags annotations - part 1

2005-10-08T22:00:57+00:00

 - added typedef unsigned int __nocast gfp_t;

 - replaced __nocast uses for gfp flags with gfp_t - it gives exactly
   the same warnings as far as sparse is concerned, doesn't change
   generated code (from gcc point of view we replaced unsigned int with
   typedef) and documents what's going on far better.

Signed-off-by: Al Viro 
Signed-off-by: Linus Torvalds

[PATCH] lib/radix-tree: Fix "nocast type" warnings

2005-09-10T17:06:28+00:00

Fix the sparse warning "implicit cast to nocast type"

Signed-off-by: Victor Fusco 
Signed-off-by: Domen Puncer 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

[PATCH] radix_tag_get(): differentiate between no present node and tag unset cases

2005-09-07T23:57:21+00:00

Simple patch to radix_tree_tag_get() to return different values for non
present node and tag unset.

The function is not used by any in-kernel callers (yet), but this
information is definitely useful.

Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

[PATCH] radix-tree: Remove unnecessary indirections and clean up code

2005-09-07T23:57:21+00:00

- There is frequent use of indirections in the radix code. This patch
  removes those indirections, makes the code more readable and allows
  the compilers to generate better code.

- Removing indirections allows the removal of several casts.

- Removing indirections allows the reduction of the radix_tree_path
  size from 3 to 2 words.

- Use pathp-> consistently.

- Remove unnecessary tmp variable in radix_tree_insert

- Separate the upper layer processing from the lowest layer in __lookup()
  in order to make it easier to understand what is going on and allow
  compilers to generate better code for the loop.

Signed-off-by: Christoph Lameter 
Cc: Nick Piggin 
Cc: James Bottomley 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds