We should not omit searching the node that radix_tree_previous() was
first called in when there is only one slot filled in. That's because
when we miss the lookup on some level, there is a possibility that
previous key is right in the same node.
Signed-off-by: Tomek Grabiec <tgrab...@gmail.com>
---
vm/radix-tree.c | 30 ++++++++++++++++++------------
1 files changed, 18 insertions(+), 12 deletions(-)
diff --git a/vm/radix-tree.c b/vm/radix-tree.c
index 61aaf3c..0fca5ef 100644
--- a/vm/radix-tree.c
+++ b/vm/radix-tree.c
@@ -188,22 +188,28 @@ radix_tree_previous(struct radix_tree *tree, struct
radix_tree_node *node,
{
int index;
- /* We don't have to search this level if there are no
- other slots */
- while (node != NULL && node->count == 1) {
- node = node->parent;
- level--;
- }
-
- if (node == NULL)
- return NULL;
+ while (node) {
+ index = get_index(tree, key, level) - 1;
+ for (; index >= 0; index--) {
+ if (node->slots[index] == NULL)
+ continue;
- for (index = get_index(tree, key, level) - 1; index >= 0; index--)
- if (node->slots[index] != NULL)
return radix_tree_last(tree, node->slots[index],
level + 1);
+ }
+
+ /*
+ * Go back one level until we find level with more
+ * than one slot filed in. We don't have to search
+ * level if there are no other slots.
+ */
+ do {
+ node = node->parent;
+ level--;
+ } while (node != NULL && node->count == 1);
+ }
- return radix_tree_previous(tree, node->parent, key, level - 1);
+ return NULL;
}
/**
--
1.6.0.6
------------------------------------------------------------------------------
Are you an open source citizen? Join us for the Open Source Bridge conference!
Portland, OR, June 17-19. Two days of sessions, one day of unconference: $250.
Need another reason to go? 24-hour hacker lounge. Register today!
http://ad.doubleclick.net/clk;215844324;13503038;v?http://opensourcebridge.org
_______________________________________________
Jatovm-devel mailing list
Jatovm-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/jatovm-devel
