This is an automated email from the git hooks/post-receive script.
firstyear pushed a commit to branch master
in repository libsds.
commit a610033cc3a95268af8f5807f9ca2dd7cbc9db1a
Author: William Brown <firstyear(a)redhat.com>
Date: Thu Feb 16 12:39:50 2017 +1000
Working delete
---
src/sds/bpt/bpt.h | 2 +
src/sds/bpt/common.c | 6 +--
src/sds/bpt_cow/bpt_cow.c | 94 ++++++++++++++++++++++++++++++++++++++++++++---
src/sds/bpt_cow/bpt_cow.h | 5 ++-
src/sds/bpt_cow/delete.c | 61 +++++++++++++++---------------
src/sds/bpt_cow/node.c | 8 ++--
test/benchmark_parwrap.c | 3 ++
test/test_sds.c | 4 --
test/test_sds_bpt.c | 2 +-
test/test_sds_cow.c | 53 ++++++++++++++++++++++----
10 files changed, 183 insertions(+), 55 deletions(-)
diff --git a/src/sds/bpt/bpt.h b/src/sds/bpt/bpt.h
index c4ae865..4b42d3b 100644
--- a/src/sds/bpt/bpt.h
+++ b/src/sds/bpt/bpt.h
@@ -42,6 +42,8 @@ sds_result sds_bptree_search_node(sds_bptree_instance *binst,
sds_bptree_node *r
sds_result sds_bptree_search_internal(sds_bptree_instance *binst, sds_bptree_node *root,
void *key);
sds_result sds_bptree_retrieve_internal(sds_bptree_instance *binst, sds_bptree_node
*root, void *key, void **target);
+void * sds_bptree_node_leftmost_child_key(sds_bptree_node *parent);
+
/* Leaf insert and delete */
void sds_bptree_leaf_insert(sds_bptree_instance *binst, sds_bptree_node *node, void *key,
void *new_value);
diff --git a/src/sds/bpt/common.c b/src/sds/bpt/common.c
index 7ffdd53..5c53eba 100644
--- a/src/sds/bpt/common.c
+++ b/src/sds/bpt/common.c
@@ -104,7 +104,7 @@ sds_bptree_node_node_replace(sds_bptree_node *target_node,
sds_bptree_node *orig
replace_node->parent = target_node;
}
-inline static void * __attribute__((always_inline))
+void *
sds_bptree_node_leftmost_child_key(sds_bptree_node *parent) {
sds_bptree_node *right_prime = parent;
while (right_prime->level > 0) {
@@ -608,15 +608,15 @@ sds_bptree_root_promote(sds_bptree_instance *binst, sds_bptree_node
*root) {
void
sds_bptree_branch_delete(sds_bptree_instance *binst, sds_bptree_node *node,
sds_bptree_node *delete_node) {
+
/* This deletes by NODE not by KEY!!!! */
size_t index = sds_bptree_node_node_index(node, delete_node);
- /* FREE HERE */
+ /* Most of the times, keys / values right associate. IE index key -> value + 1 */
binst->key_free_fn(node->keys[index - 1]);
/* Have to move everything down. */
/* Remember, we belong to key index - 1 */
- /* Has a 6x cost. */
for (; index < node->item_count; index++) {
node->keys[index - 1] = node->keys[index];
node->values[index] = node->values[index + 1];
diff --git a/src/sds/bpt_cow/bpt_cow.c b/src/sds/bpt_cow/bpt_cow.c
index 85747db..d25cc29 100644
--- a/src/sds/bpt_cow/bpt_cow.c
+++ b/src/sds/bpt_cow/bpt_cow.c
@@ -214,7 +214,7 @@ sds_result sds_bptree_cow_delete(sds_bptree_transaction *btxn, void
*key) {
sds_log("sds_bptree_cow_delete", "Right leaf contract");
#endif
/* WARNING: DO NOT COW THE RIGHT NODE */
- sds_bptree_cow_right_leaf_compact(btxn, next_node, right);
+ sds_bptree_cow_leaf_compact(btxn, next_node, right);
/* Setup the branch delete properly */
deleted_node = right;
/* Next node is correct, and ready for FIXUP */
@@ -223,9 +223,9 @@ sds_result sds_bptree_cow_delete(sds_bptree_transaction *btxn, void
*key) {
#ifdef DEBUG
sds_log("sds_bptree_cow_delete", "Left leaf contract");
#endif
- /* WARNING: DO NOT COW THE LEFT NODE */
- sds_bptree_cow_left_leaf_compact(btxn, left, next_node);
- deleted_node = left;
+ cow_node = sds_bptree_cow_node_prepare(btxn, left);
+ sds_bptree_cow_leaf_compact(btxn, cow_node, next_node);
+ deleted_node = next_node;
/* Next node is correct, and ready for FIXUP */
} else {
/* Mate, if you get here you are fucked. */
@@ -262,7 +262,91 @@ sds_result sds_bptree_cow_delete(sds_bptree_transaction *btxn, void
*key) {
target_node = target_node->parent;
/* Is the node less than half? */
if (target_node != NULL && next_node->item_count <
SDS_BPTREE_HALF_CAPACITY) {
- abort();
+ /* Now we do borrow and merge for branches. */
+
+ /* Get siblings */
+ sds_bptree_node *left = NULL;
+ sds_bptree_node *right = NULL;
+ /* This updates the left and right parent paths, but does NOT cow!!! */
+ sds_bptree_cow_node_siblings(next_node, &left, &right);
+ /* Note the conditions for HALF_CAPACITY change here due to
+ * space requirements. we only merge if < half. IE for 7 keys
+ * we have 8 links. If we have a node at 3 keys, and one at 4 keys
+ * they have 4 and 5 links each. Too many! So we have to delay
+ * the merge by a fraction, to allow space for 3 keys and 3 keys.
+ *
+ */
+#ifdef DEBUG
+ sds_log("sds_bptree_cow_delete", " %p -> %p ->
%p", left, next_node, right);
+ sds_log("sds_bptree_cow_delete", "
next_node->item_count = %d", next_node->item_count);
+ if (right != NULL) {
+ sds_log("sds_bptree_cow_delete", "
right->item_count = %d", right->item_count);
+ if (btxn->bi->offline_checksumming) {
+ sds_bptree_crc32c_update_node(right);
+ }
+ }
+ if (left != NULL) {
+ sds_log("sds_bptree_cow_delete", " left->item_count
= %d", left->item_count);
+ if (btxn->bi->offline_checksumming) {
+ sds_bptree_crc32c_update_node(left);
+ }
+ }
+#endif
+ if (right != NULL && right->item_count >=
SDS_BPTREE_HALF_CAPACITY) {
+ /* Does right have excess keys? */
+#ifdef DEBUG
+ sds_log("sds_bptree_cow_delete", "Right branch
borrow");
+#endif
+ /* Since we are about to borrow, we need to cow RIGHT */
+ cow_node = sds_bptree_cow_node_prepare(btxn, right);
+
+ sds_bptree_branch_right_borrow(btxn->bi, next_node, cow_node);
+ /* We setup next_node to be right now, so that key fixing on the path
works */
+ next_node = cow_node;
+ } else if (left != NULL && left->item_count >=
SDS_BPTREE_HALF_CAPACITY) {
+ /* Does left have excess keys? */
+#ifdef DEBUG
+ sds_log("sds_bptree_cow_delete", "Left branch
borrow");
+#endif
+ /* Since we are about to borrow, we need to cow LEFT */
+ cow_node = sds_bptree_cow_node_prepare(btxn, left);
+
+ sds_bptree_branch_left_borrow(btxn->bi, cow_node, next_node);
+ /* Next node is still on right, key fix will work next loop. */
+ } else if (right != NULL && right->item_count <
SDS_BPTREE_HALF_CAPACITY) {
+ /* Does right want to merge? */
+#ifdef DEBUG
+ sds_log("sds_bptree_cow_delete", "Right branch
contract");
+#endif
+ /* WARNING: DO NOT COW THE RIGHT NODE */
+ sds_bptree_cow_branch_compact(btxn, next_node, right);
+ /* Setup the branch delete properly */
+ // next_node = right;
+ deleted_node = right;
+ } else if (left != NULL && left->item_count <
SDS_BPTREE_HALF_CAPACITY) {
+ /* Does left want to merge? */
+#ifdef DEBUG
+ sds_log("sds_bptree_cow_delete", "Left branch
contract");
+#endif
+ /* Since we are about to merge, we need to cow left */
+ /* This is much, much easier than the inverse proposition ... */
+ cow_node = sds_bptree_cow_node_prepare(btxn, left);
+ sds_bptree_cow_branch_compact(btxn, cow_node, next_node);
+ deleted_node = next_node;
+ } else {
+ /* Mate, if you get here you are fucked. */
+ return SDS_INVALID_NODE;
+ }
+
+ } else if ( target_node == NULL && next_node->item_count == 0) {
+ sds_log("sds_bptree_cow_delete", "Begine deleting the
root");
+ if (btxn->root != next_node) {
+ sds_log("sds_bptree_cow_delete", "Transaction is
corrupted");
+ result = SDS_UNKNOWN_ERROR;
+ goto fail;
+ }
+ // Promote the root now.
+ sds_bptree_cow_root_promote(btxn, next_node);
}
} // End of branch "which target_node" loop
diff --git a/src/sds/bpt_cow/bpt_cow.h b/src/sds/bpt_cow/bpt_cow.h
index 60195af..8b69f99 100644
--- a/src/sds/bpt_cow/bpt_cow.h
+++ b/src/sds/bpt_cow/bpt_cow.h
@@ -31,8 +31,9 @@ sds_bptree_node * sds_bptree_cow_node_prepare(sds_bptree_transaction
*btxn, sds_
sds_bptree_node * sds_bptree_cow_node_create(sds_bptree_transaction *btxn);
void sds_bptree_cow_node_siblings(sds_bptree_node *target, sds_bptree_node **left,
sds_bptree_node **right);
-void sds_bptree_cow_left_leaf_compact(sds_bptree_transaction *btxn, sds_bptree_node
*left, sds_bptree_node *right);
-void sds_bptree_cow_right_leaf_compact(sds_bptree_transaction *btxn, sds_bptree_node
*left, sds_bptree_node *right);
+void sds_bptree_cow_leaf_compact(sds_bptree_transaction *btxn, sds_bptree_node *left,
sds_bptree_node *right);
+void sds_bptree_cow_root_promote(sds_bptree_transaction *btxn, sds_bptree_node *root);
+void sds_bptree_cow_branch_compact(sds_bptree_transaction *btxn, sds_bptree_node *left,
sds_bptree_node *right);
/* Insert algo parts */
diff --git a/src/sds/bpt_cow/delete.c b/src/sds/bpt_cow/delete.c
index 49f2222..910eb76 100644
--- a/src/sds/bpt_cow/delete.c
+++ b/src/sds/bpt_cow/delete.c
@@ -9,7 +9,7 @@
#include "bpt_cow.h"
void
-sds_bptree_cow_right_leaf_compact(sds_bptree_transaction *btxn, sds_bptree_node *left,
sds_bptree_node *right) {
+sds_bptree_cow_leaf_compact(sds_bptree_transaction *btxn, sds_bptree_node *left,
sds_bptree_node *right) {
/* Append content of right to left, mark right for free. */
/*
@@ -46,44 +46,47 @@ sds_bptree_cow_right_leaf_compact(sds_bptree_transaction *btxn,
sds_bptree_node
}
void
-sds_bptree_cow_left_leaf_compact(sds_bptree_transaction *btxn, sds_bptree_node *left,
sds_bptree_node *right) {
- /* Prepend content of left to right, mark left for free */
- /* SEE ALSO: sds_bptree_cow_left_leaf_compact */
+sds_bptree_cow_branch_compact(sds_bptree_transaction *btxn, sds_bptree_node *left,
sds_bptree_node *right) {
+ /* REMEMBER: Left is COWed, right is NOT */
+ /* Append content of right to left, mark right for deletion */
- /* First, make space on the right */
- for (size_t i = right->item_count; i > 0; i--) {
- size_t offset = (i - 1) + left->item_count;
- right->keys[offset] = right->keys[i - 1];
- right->values[offset] = right->values[i - 1];
- }
+ /* We have to recreate the missing intermediate key. */
+ left->keys[left->item_count] =
btxn->bi->key_dup_fn(sds_bptree_node_leftmost_child_key(right));
+ /* Node reference, so can just copy */
+ left->values[left->item_count + 1] = right->values[0];
+ left->item_count++;
- /* Now copy the values in. */
- for (size_t i = 0; i < left->item_count; i++) {
- right->keys[i] = btxn->bi->key_dup_fn(left->keys[i]);
- if (left->values[i] != NULL && btxn->bi->value_dup_fn != NULL)
{
- right->values[i] = btxn->bi->value_dup_fn(left->values[i]);
- }
- }
- right->item_count += left->item_count;
- /* CRITICAL: YOU MUST UPDATE THE PARENT KEY LINK TO YOU. */
- /* At this point because you have taken in keys that were LESS than your previous
- * key[0] value. You can *safely* update parent here, because when the branch_delete
- * occurs, it shuffles the key down.
- *
- * WARNING: Check if parent exists?
- */
- if (right->parent != NULL) {
- sds_bptree_branch_key_fixup(btxn->bi, right->parent, right);
+ /* Has about a 3 times impact */
+ for (size_t i = 0; i < right->item_count; i++) {
+ left->keys[left->item_count] =
btxn->bi->key_dup_fn(right->keys[i]);
+ /* These are all node pointers, so we can just copy them as is. */
+ left->values[left->item_count + 1] = right->values[i + 1];
+ left->item_count++;
}
- sds_bptree_node_list_push(&(btxn->owned), left);
+ sds_bptree_node_list_push(&(btxn->owned), right);
#ifdef DEBUG
if (btxn->bi->offline_checksumming) {
- sds_bptree_crc32c_update_node(right);
+ sds_bptree_crc32c_update_node(left);
// Update this becuase we are updating the owned node lists.
sds_bptree_crc32c_update_btxn(btxn);
}
#endif
}
+
+
+void
+sds_bptree_cow_root_promote(sds_bptree_transaction *btxn, sds_bptree_node *root) {
+ /* Current root is empty! We have one child, so we promote them. */
+ btxn->root = (sds_bptree_node *)root->values[0];
+ sds_bptree_node_list_push(&(btxn->owned), root);
+ btxn->root->parent = NULL;
+#ifdef DEBUG
+ if (btxn->bi->offline_checksumming) {
+ sds_bptree_crc32c_update_node(btxn->root);
+ sds_bptree_crc32c_update_btxn(btxn);
+ }
+#endif
+}
diff --git a/src/sds/bpt_cow/node.c b/src/sds/bpt_cow/node.c
index 2a90b5b..b7d3cc3 100644
--- a/src/sds/bpt_cow/node.c
+++ b/src/sds/bpt_cow/node.c
@@ -8,11 +8,11 @@
#include "bpt_cow.h"
-sds_result
-sds_bptree_cow_node_path_verify(sds_bptree_transaction *btxn, sds_bptree_node *node) {
+static sds_result
+sds_bptree_cow_node_path_verify(sds_bptree_transaction *btxn, sds_bptree_node *old_node,
sds_bptree_node *node) {
// Verify that the node has a valid parent path back to the root!
sds_bptree_node *boom = NULL;
- uint64_t level = 0;
+ uint64_t level = old_node->level;
sds_bptree_node *target_node = node;
while (target_node->parent != NULL) {
if (target_node->level != level) {
@@ -197,7 +197,7 @@ sds_bptree_cow_node_prepare(sds_bptree_transaction *btxn,
sds_bptree_node *node)
result_node = clone_node;
}
#ifdef DEBUG
- if (sds_bptree_cow_node_path_verify(btxn, result_node)!= SDS_SUCCESS) {
+ if (sds_bptree_cow_node_path_verify(btxn, node, result_node)!= SDS_SUCCESS) {
sds_log("sds_bptree_cow_node_prepare", "!!! Invalid path from
cow_node to root!");
return NULL;
}
diff --git a/test/benchmark_parwrap.c b/test/benchmark_parwrap.c
index 2fa9bec..36fe9db 100644
--- a/test/benchmark_parwrap.c
+++ b/test/benchmark_parwrap.c
@@ -134,6 +134,9 @@ int64_t bptree_cow_read_complete(void **inst __attribute__((unused)),
void *read
int64_t bptree_cow_write_begin(void **inst, void **write_txn) {
sds_bptree_cow_instance **binst = (sds_bptree_cow_instance **)inst;
sds_bptree_transaction **txn = (sds_bptree_transaction **)write_txn;
+#ifdef DEBUG
+ assert_int_equal(sds_bptree_cow_verify(*binst), SDS_SUCCESS);
+#endif
sds_bptree_cow_wrtxn_begin(*binst, txn);
return 0;
}
diff --git a/test/test_sds.c b/test/test_sds.c
index e29ca6d..276d3d5 100644
--- a/test/test_sds.c
+++ b/test/test_sds.c
@@ -11,16 +11,12 @@
int
main ( int argc __attribute__((unused)), char **argv __attribute__((unused))) {
int result = 0;
- /*
result += run_bpt_tests();
result += run_set_tests();
- */
result += run_cow_tests();
- /*
result += run_queue_tests();
result += run_tqueue_tests();
result += run_lqueue_tests();
- */
return result;
}
diff --git a/test/test_sds_bpt.c b/test/test_sds_bpt.c
index 17fe228..18760a9 100644
--- a/test/test_sds_bpt.c
+++ b/test/test_sds_bpt.c
@@ -954,6 +954,6 @@ run_bpt_tests (void) {
cmocka_unit_test(test_30_insert_and_delete_strings),
};
- return cmocka_run_group_tests(tests, NULL, NULL);
+ return cmocka_run_group_tests_name("bpt", tests, NULL, NULL);
}
diff --git a/test/test_sds_cow.c b/test/test_sds_cow.c
index e25a337..f45b7f9 100644
--- a/test/test_sds_cow.c
+++ b/test/test_sds_cow.c
@@ -443,15 +443,52 @@ test_txn_delete_leaf_right(void **state) {
}
static void
-test_txn_delete_all(void **state) {
- /* Add extra nodes to grow the tree to 2 levels */
- /* Now delete everything */
+test_txn_delete_branch_left(void **state) {
+ /* Add enough to create some extra nodes */
+ sds_bptree_cow_instance *binst = *state;
+ sds_bptree_transaction *wr_btxn = NULL;
+
+ assert_int_equal(sds_bptree_cow_wrtxn_begin(binst, &wr_btxn), SDS_SUCCESS);
+ for (uint64_t i = 1; i <= (SDS_BPTREE_DEFAULT_CAPACITY << 3); i++) {
+ assert_int_equal(sds_bptree_cow_insert(wr_btxn, (void *)i, NULL), SDS_SUCCESS);
+ assert_int_equal(sds_bptree_cow_display(wr_btxn), SDS_SUCCESS);
+ }
+ assert_int_equal(sds_bptree_cow_wrtxn_commit(&wr_btxn), SDS_SUCCESS);
+ /* Now delete down to create borrow and merge left in branches */
+ for (uint64_t i = (SDS_BPTREE_DEFAULT_CAPACITY << 3); i > 0; i--) {
+ assert_int_equal(sds_bptree_cow_wrtxn_begin(binst, &wr_btxn), SDS_SUCCESS);
+ assert_int_equal(sds_bptree_cow_delete(wr_btxn, (void *)i), SDS_KEY_PRESENT);
+ assert_int_equal(sds_bptree_cow_display(wr_btxn), SDS_SUCCESS);
+ assert_int_equal(sds_bptree_cow_wrtxn_commit(&wr_btxn), SDS_SUCCESS);
+ assert_int_equal(sds_bptree_cow_verify(binst), SDS_SUCCESS);
+ }
+}
+
+static void
+test_txn_delete_branch_right(void **state) {
+ /* Add enough to create some extra nodes */
+ sds_bptree_cow_instance *binst = *state;
+ sds_bptree_transaction *wr_btxn = NULL;
+
+ assert_int_equal(sds_bptree_cow_wrtxn_begin(binst, &wr_btxn), SDS_SUCCESS);
+ for (uint64_t i = 1; i <= (SDS_BPTREE_DEFAULT_CAPACITY << 3); i++) {
+ assert_int_equal(sds_bptree_cow_insert(wr_btxn, (void *)i, NULL), SDS_SUCCESS);
+ assert_int_equal(sds_bptree_cow_display(wr_btxn), SDS_SUCCESS);
+ }
+ assert_int_equal(sds_bptree_cow_wrtxn_commit(&wr_btxn), SDS_SUCCESS);
+ /* Now delete down to create borrow and merge left in branches */
+ for (uint64_t i = 1; i <= (SDS_BPTREE_DEFAULT_CAPACITY << 3); i++) {
+ assert_int_equal(sds_bptree_cow_wrtxn_begin(binst, &wr_btxn), SDS_SUCCESS);
+ assert_int_equal(sds_bptree_cow_delete(wr_btxn, (void *)i), SDS_KEY_PRESENT);
+ assert_int_equal(sds_bptree_cow_display(wr_btxn), SDS_SUCCESS);
+ assert_int_equal(sds_bptree_cow_wrtxn_commit(&wr_btxn), SDS_SUCCESS);
+ assert_int_equal(sds_bptree_cow_verify(binst), SDS_SUCCESS);
+ }
}
int
run_cow_tests (void) {
const struct CMUnitTest tests[] = {
- /*
cmocka_unit_test(test_1_cow_init),
cmocka_unit_test_setup_teardown(test_2_begin_rotxn,
bptree_test_cow_setup,
@@ -504,11 +541,13 @@ run_cow_tests (void) {
cmocka_unit_test_setup_teardown(test_txn_delete_leaf_right,
bptree_test_cow_setup,
bptree_test_cow_teardown),
- */
- cmocka_unit_test_setup_teardown(test_txn_delete_all,
+ cmocka_unit_test_setup_teardown(test_txn_delete_branch_left,
+ bptree_test_cow_setup,
+ bptree_test_cow_teardown),
+ cmocka_unit_test_setup_teardown(test_txn_delete_branch_right,
bptree_test_cow_setup,
bptree_test_cow_teardown),
};
- return cmocka_run_group_tests(tests, NULL, NULL);
+ return cmocka_run_group_tests_name("bpt_cow", tests, NULL, NULL);
}
--
To stop receiving notification emails like this one, please contact
the administrator of this repository.