24 Jan, 2014
2 commits
-
Signed-off-by: Cody P Schafer
Cc: Michel Lespinasse
Cc: Jan Kara
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds -
Avoid making the rb_node the first entry to catch some bugs around NULL
checking the rb_node.Signed-off-by: Cody P Schafer
Cc: Michel Lespinasse
Cc: Jan Kara
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
12 Sep, 2013
1 commit
-
Just check that we examine all nodes in the tree for the postorder
iteration.Signed-off-by: Cody P Schafer
Reviewed-by: Seth Jennings
Cc: David Woodhouse
Cc: Rik van Riel
Cc: Michel Lespinasse
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
01 May, 2013
2 commits
-
Signed-off-by: Davidlohr Bueso
Reviewed-by: Michel Lespinasse
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds -
Account for the rbtree having 2**bh(v)-1 internal nodes.
While this can be seen as a consequence of other checks, Michel states
that it nicely sums up what the other properties are for.Signed-off-by: Davidlohr Bueso
Reviewed-by: Michel Lespinasse
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
18 Dec, 2012
2 commits
-
This renames all random32 functions to have 'prandom_' prefix as follows:
void prandom_seed(u32 seed); /* rename from srandom32() */
u32 prandom_u32(void); /* rename from random32() */
void prandom_seed_state(struct rnd_state *state, u64 seed);
/* rename from prandom32_seed() */
u32 prandom_u32_state(struct rnd_state *state);
/* rename from prandom32() */The purpose of this renaming is to prevent some kernel developers from
assuming that prandom32() and random32() might imply that only
prandom32() was the one using a pseudo-random number generator by
prandom32's "p", and the result may be a very embarassing security
exposure. This concern was expressed by Theodore Ts'o.And furthermore, I'm going to introduce new functions for getting the
requested number of pseudo-random bytes. If I continue to use both
prandom32 and random32 prefixes for these functions, the confusion
is getting worse.As a result of this renaming, "prandom_" is the common prefix for
pseudo-random number library.Currently, srandom32() and random32() are preserved because it is
difficult to rename too many users at once.Signed-off-by: Akinobu Mita
Cc: "Theodore Ts'o"
Cc: Robert Love
Cc: Michel Lespinasse
Cc: Valdis Kletnieks
Cc: David Laight
Cc: Adrian Hunter
Cc: Artem Bityutskiy
Cc: David Woodhouse
Cc: Eilon Greenstein
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds -
Fix this warning:
lib/rbtree_test.c: In function `check':
lib/rbtree_test.c:121: warning: `blacks' may be used uninitialized in this functionSigned-off-by: Cong Ding
Cc: Michel Lespinasse
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
09 Oct, 2012
6 commits
-
Provide rb_insert_augmented() and rb_erase_augmented() through a new
rbtree_augmented.h include file. rb_erase_augmented() is defined there as
an __always_inline function, in order to allow inlining of augmented
rbtree callbacks into it. Since this generates a relatively large
function, each augmented rbtree user should make sure to have a single
call site.Signed-off-by: Michel Lespinasse
Cc: Rik van Riel
Cc: Hillf Danton
Cc: Peter Zijlstra
Cc: Catalin Marinas
Cc: Andrea Arcangeli
Cc: David Woodhouse
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds -
As proposed by Peter Zijlstra, this makes it easier to define the augmented
rbtree callbacks.Signed-off-by: Michel Lespinasse
Cc: Rik van Riel
Cc: Peter Zijlstra
Cc: Andrea Arcangeli
Cc: David Woodhouse
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds -
Introduce new augmented rbtree APIs that allow minimal recalculation of
augmented node information.A new callback is added to the rbtree insertion and erase rebalancing
functions, to be called on each tree rotations. Such rotations preserve
the subtree's root augmented value, but require recalculation of the one
child that was previously located at the subtree root.In the insertion case, the handcoded search phase must be updated to
maintain the augmented information on insertion, and then the rbtree
coloring/rebalancing algorithms keep it up to date.In the erase case, things are more complicated since it is library
code that manipulates the rbtree in order to remove internal nodes.
This requires a couple additional callbacks to copy a subtree's
augmented value when a new root is stitched in, and to recompute
augmented values down the ancestry path when a node is removed from
the tree.In order to preserve maximum speed for the non-augmented case,
we provide two versions of each tree manipulation function.
rb_insert_augmented() is the augmented equivalent of rb_insert_color(),
and rb_erase_augmented() is the augmented equivalent of rb_erase().Signed-off-by: Michel Lespinasse
Acked-by: Rik van Riel
Cc: Peter Zijlstra
Cc: Andrea Arcangeli
Cc: David Woodhouse
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds -
Small test to measure the performance of augmented rbtrees.
Signed-off-by: Michel Lespinasse
Acked-by: Rik van Riel
Cc: Peter Zijlstra
Cc: Andrea Arcangeli
Cc: David Woodhouse
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds -
Just a small fix to make sparse happy.
Signed-off-by: Michel Lespinasse
Reported-by: Fengguang Wu
Acked-by: Rik van Riel
Cc: Peter Zijlstra
Cc: Andrea Arcangeli
Cc: David Woodhouse
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds -
This small module helps measure the performance of rbtree insert and
erase.Additionally, we run a few correctness tests to check that the rbtrees
have all desired properties:- contains the right number of nodes in the order desired,
- never two consecutive red nodes on any path,
- all paths to leaf nodes have the same number of black nodes,
- root node is black[akpm@linux-foundation.org: fix printk warning: sparc64 cycles_t is unsigned long]
Signed-off-by: Michel Lespinasse
Cc: Andrea Arcangeli
Acked-by: David Woodhouse
Cc: Rik van Riel
Cc: Peter Zijlstra
Cc: Daniel Santos
Cc: Jens Axboe
Cc: "Eric W. Biederman"
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds