This is an automated email from the git hooks/post-receive script.
firstyear pushed a commit to branch master
in repository libsds.
commit b6573b2bcdabf7d258c04849d7f73eb28c3c6f44
Author: William Brown <firstyear(a)redhat.com>
Date: Fri Feb 17 13:49:43 2017 +1000
Add update method to make more efficient cow updates.
---
src/sds/bpt/bpt.h | 1 +
src/sds/bpt/common.c | 2 +-
src/sds/bpt_cow/bpt_cow.c | 40 ++++++++++++++++++++++++++++++++++++++++
src/sds/bpt_cow/bpt_cow.h | 1 +
src/sds/bpt_cow/node.c | 10 ++++++++++
src/sds/sds.h | 15 +++++++++++++++
test/test_sds_cow.c | 33 +++++++++++++++++++++++++++++++++
7 files changed, 101 insertions(+), 1 deletion(-)
diff --git a/src/sds/bpt/bpt.h b/src/sds/bpt/bpt.h
index 4b42d3b..6430f6e 100644
--- a/src/sds/bpt/bpt.h
+++ b/src/sds/bpt/bpt.h
@@ -29,6 +29,7 @@ sds_result sds_bptree_node_list_to_tree(sds_bptree_instance *binst,
sds_bptree_n
sds_bptree_node * sds_bptree_node_create(void);
sds_result sds_bptree_node_destroy(sds_bptree_instance *binst, sds_bptree_node *node);
sds_result sds_bptree_node_contains_key(sds_bptree_instance *binst, sds_bptree_node
*node, void *key);
+size_t sds_bptree_node_key_eq_index(sds_bptree_instance *binst, sds_bptree_node *node,
void *key);
size_t sds_bptree_node_key_lt_index(sds_bptree_instance *binst, sds_bptree_node *node,
void *key);
void sds_bptree_node_siblings(sds_bptree_node *target, sds_bptree_node **left,
sds_bptree_node **right);
sds_result sds_bptree_node_retrieve_key(sds_bptree_instance *binst, sds_bptree_node
*node, void *key, void **target);
diff --git a/src/sds/bpt/common.c b/src/sds/bpt/common.c
index 5c53eba..05b748e 100644
--- a/src/sds/bpt/common.c
+++ b/src/sds/bpt/common.c
@@ -65,7 +65,7 @@ sds_bptree_node_key_lt_index(sds_bptree_instance *binst, sds_bptree_node
*node,
return index;
}
-inline static size_t __attribute__((always_inline))
+size_t
sds_bptree_node_key_eq_index(sds_bptree_instance *binst, sds_bptree_node *node, void
*key) {
size_t index = 0;
int64_t result = 0;
diff --git a/src/sds/bpt_cow/bpt_cow.c b/src/sds/bpt_cow/bpt_cow.c
index 8c9b157..97d9d2a 100644
--- a/src/sds/bpt_cow/bpt_cow.c
+++ b/src/sds/bpt_cow/bpt_cow.c
@@ -413,6 +413,46 @@ sds_result sds_bptree_cow_insert(sds_bptree_transaction *btxn, void
*key, void *
return SDS_SUCCESS;
}
+sds_result sds_bptree_cow_update(sds_bptree_transaction *btxn, void *key, void *value) {
+ sds_result result = SDS_SUCCESS;
+ sds_bptree_node *cow_node = NULL;
+ sds_bptree_node *target_node = NULL;
+
+#ifdef DEBUG
+ sds_log("sds_bptree_cow_update", "==> Beginning update of %d",
key);
+#endif
+ // Need to fail if txn is RO
+ if (btxn == NULL || btxn->state != SDS_TXN_WRITE) {
+ return SDS_INVALID_TXN;
+ }
+
+ // First check the key doesn't already exist.
+ if (key == NULL) {
+ return SDS_INVALID_KEY;
+ }
+
+ // This grabs the node, but updates the path parent pointers as we descend down.
+ result = sds_bptree_search_node_path(btxn, key, &target_node);
+ if (result != SDS_SUCCESS) {
+ return result;
+ }
+
+ if (sds_bptree_node_contains_key(btxn->bi, target_node, key) ==
SDS_KEY_NOT_PRESENT) {
+ // Call insert instead!
+ sds_bptree_cow_insert(btxn, key, value);
+ }
+
+ cow_node = sds_bptree_cow_node_prepare(btxn, target_node);
+
+ sds_bptree_cow_node_update(btxn, cow_node, key, value);
+
+ // Else, insert to leaf and let things happen.
+#ifdef DEBUG
+ sds_log("sds_bptree_cow_update", "<== Finishing update of %d",
key);
+#endif
+ return SDS_SUCCESS;
+}
+
// Does this need to work on a transaction perhaps to verify the tree is
"sane"?
sds_result
sds_bptree_cow_verify(sds_bptree_cow_instance *binst) {
diff --git a/src/sds/bpt_cow/bpt_cow.h b/src/sds/bpt_cow/bpt_cow.h
index 8b69f99..4c0adc0 100644
--- a/src/sds/bpt_cow/bpt_cow.h
+++ b/src/sds/bpt_cow/bpt_cow.h
@@ -29,6 +29,7 @@ sds_result sds_bptree_cow_verify_node(sds_bptree_instance *binst,
sds_bptree_nod
sds_bptree_node * sds_bptree_cow_node_prepare(sds_bptree_transaction *btxn,
sds_bptree_node *node);
sds_bptree_node * sds_bptree_cow_node_create(sds_bptree_transaction *btxn);
+void sds_bptree_cow_node_update(sds_bptree_transaction *btxn, sds_bptree_node *node, void
*key, void *value);
void sds_bptree_cow_node_siblings(sds_bptree_node *target, 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);
diff --git a/src/sds/bpt_cow/node.c b/src/sds/bpt_cow/node.c
index a602658..2eb9272 100644
--- a/src/sds/bpt_cow/node.c
+++ b/src/sds/bpt_cow/node.c
@@ -232,4 +232,14 @@ sds_bptree_cow_node_create(sds_bptree_transaction *btxn) {
return node;
}
+void
+sds_bptree_cow_node_update(sds_bptree_transaction *btxn, sds_bptree_node *node, void
*key, void *value) {
+ // find the key index.
+ size_t index = sds_bptree_node_key_eq_index(btxn->bi, node, key);
+ // value free
+ btxn->bi->value_free_fn(node->values[index]);
+ // insert.
+ node->values[index] = value;
+}
+
diff --git a/src/sds/sds.h b/src/sds/sds.h
index b2aa91a..941661c 100644
--- a/src/sds/sds.h
+++ b/src/sds/sds.h
@@ -1267,6 +1267,21 @@ sds_result sds_bptree_cow_delete(sds_bptree_transaction *btxn, void
*key);
sds_result sds_bptree_cow_insert(sds_bptree_transaction *btxn, void *key, void *value);
/**
+ * Update a key to have a new associated value within a valid write transaction.
+ * This is more efficient than delete -> insert, so for updates it's preferred.
+ * This is needed in the case that you have previous read transactions, and want
+ * to alter a value, without affecting the read. You would use this by calling
+ * retrieve, copying the value, then calling update on the b+tree.
+ *
+ * \param btxn The write transaction to operate on.
+ * \param key The key to update. If the key does not exist, fall back to insert.
+ * \param value The value to update. May be NULL.
+ * \retval Result of the operation as sds_result.
+ */
+
+sds_result sds_bptree_cow_update(sds_bptree_transaction *btxn, void *key, void *value);
+
+/**
* Search atomic functions as search, but implies a single short lived read transaction.
*
* If you have multiple searches to make, it is better to use a read transaction due to
diff --git a/test/test_sds_cow.c b/test/test_sds_cow.c
index f45b7f9..2868b39 100644
--- a/test/test_sds_cow.c
+++ b/test/test_sds_cow.c
@@ -486,6 +486,36 @@ test_txn_delete_branch_right(void **state) {
}
}
+static void
+test_cow_update(void **state) {
+ sds_bptree_cow_instance *binst = *state;
+ sds_bptree_transaction *wr_btxn = NULL;
+ sds_bptree_transaction *ro_btxn = NULL;
+
+ uint64_t result = 0;
+
+ assert_int_equal(sds_bptree_cow_wrtxn_begin(binst, &wr_btxn), SDS_SUCCESS);
+ assert_int_equal(sds_bptree_cow_insert(wr_btxn, (void *)1, (void *)1), SDS_SUCCESS);
+ assert_int_equal(sds_bptree_cow_wrtxn_commit(&wr_btxn), SDS_SUCCESS);
+
+ assert_int_equal(sds_bptree_cow_rotxn_begin(binst, &ro_btxn), SDS_SUCCESS);
+ assert_int_equal(sds_bptree_cow_retrieve(ro_btxn, (void *)1, (void *)&result),
SDS_KEY_PRESENT);
+ assert_int_equal(result, 1);
+ assert_int_equal(sds_bptree_cow_rotxn_close(&ro_btxn), SDS_SUCCESS);
+
+ assert_int_equal(sds_bptree_cow_wrtxn_begin(binst, &wr_btxn), SDS_SUCCESS);
+ assert_int_equal(sds_bptree_cow_update(wr_btxn, (void *)1, (void *)2), SDS_SUCCESS);
+ assert_int_equal(sds_bptree_cow_update(wr_btxn, (void *)2, (void *)3), SDS_SUCCESS);
+ assert_int_equal(sds_bptree_cow_wrtxn_commit(&wr_btxn), SDS_SUCCESS);
+
+ assert_int_equal(sds_bptree_cow_rotxn_begin(binst, &ro_btxn), SDS_SUCCESS);
+ assert_int_equal(sds_bptree_cow_retrieve(ro_btxn, (void *)1, (void *)&result),
SDS_KEY_PRESENT);
+ assert_int_equal(result, 2);
+ assert_int_equal(sds_bptree_cow_retrieve(ro_btxn, (void *)2, (void *)&result),
SDS_KEY_PRESENT);
+ assert_int_equal(result, 3);
+ assert_int_equal(sds_bptree_cow_rotxn_close(&ro_btxn), SDS_SUCCESS);
+}
+
int
run_cow_tests (void) {
const struct CMUnitTest tests[] = {
@@ -547,6 +577,9 @@ run_cow_tests (void) {
cmocka_unit_test_setup_teardown(test_txn_delete_branch_right,
bptree_test_cow_setup,
bptree_test_cow_teardown),
+ cmocka_unit_test_setup_teardown(test_cow_update,
+ bptree_test_cow_setup,
+ bptree_test_cow_teardown),
};
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.