* [PATCH 0/5] JSON update preparation
@ 2019-07-13 22:11 Vladislav Shpilevoy
2019-07-13 22:11 ` [PATCH 1/5] tuple: remove alloc and alloc_ctx args from update() Vladislav Shpilevoy
` (7 more replies)
0 siblings, 8 replies; 10+ messages in thread
From: Vladislav Shpilevoy @ 2019-07-13 22:11 UTC (permalink / raw)
To: tarantool-patches; +Cc: vdavydov.dev
The patchset is mainly about rope and its usage. Rope is a data structure
allowing to modify an array with memory overhead not depending on the array
size. Only on the number of modifications. It is used when there is a long
array of something, and a one wants to insert new elements, delete existing
ones, change their values, but do not rebuild the whole array each time.
Rope is going to be one of the core data structures of the incoming JSON path
updates, and this patchset makes it faster and lighter.
Branch: http://github.com/tarantool/tarantool/tree/gerold103/gh-1261-update-json-prepare
Issue: https://github.com/tarantool/tarantool/issues/1261
Vladislav Shpilevoy (5):
tuple: remove alloc and alloc_ctx args from update()
rope: make rope library macro template
tuple: relax struct tuple_update dependency on rope
int96: add a missing header
tuple: implement update by field name
debian/copyright | 2 +-
src/box/errcode.h | 4 +-
src/box/lua/tuple.c | 10 +-
src/box/memtx_space.c | 27 +-
src/box/space.c | 26 +-
src/box/sql/insert.c | 3 +-
src/box/sql/resolve.c | 4 +-
src/box/sql/update.c | 2 +-
src/box/tuple.c | 18 +-
src/box/tuple_update.c | 292 +++++++++--------
src/box/tuple_update.h | 25 +-
src/box/vinyl.c | 19 +-
src/box/vy_upsert.c | 31 +-
src/lib/bit/int96.h | 1 +
src/lib/salad/rope.c | 479 +++++-----------------------
src/lib/salad/rope.h | 617 +++++++++++++++++++++++++++++++-----
test/box/misc.result | 3 +-
test/box/update.result | 2 +-
test/engine/update.result | 67 ++++
test/engine/update.test.lua | 28 ++
test/engine/upsert.result | 2 +-
test/unit/column_mask.c | 33 +-
test/unit/rope.c | 1 -
test/unit/rope_avl.c | 1 -
test/unit/rope_basic.c | 1 -
test/unit/rope_common.h | 41 ++-
test/unit/rope_stress.c | 5 +-
27 files changed, 993 insertions(+), 751 deletions(-)
--
2.20.1 (Apple Git-117)
^ permalink raw reply [flat|nested] 10+ messages in thread
* [PATCH 1/5] tuple: remove alloc and alloc_ctx args from update()
2019-07-13 22:11 [PATCH 0/5] JSON update preparation Vladislav Shpilevoy
@ 2019-07-13 22:11 ` Vladislav Shpilevoy
2019-07-13 22:11 ` [PATCH 2/5] rope: make rope library macro template Vladislav Shpilevoy
` (6 subsequent siblings)
7 siblings, 0 replies; 10+ messages in thread
From: Vladislav Shpilevoy @ 2019-07-13 22:11 UTC (permalink / raw)
To: tarantool-patches; +Cc: vdavydov.dev
They are always region_aligned_alloc and region pointer. Lets use
them always inside tuple_update.c, with no necessity to pass
explicitly.
The patch is motivated by forthcoming updates by JSON path, which
will strongly complicate and perhaps slow down the tuple_update.c
code. The present patch as well as some next ones should smooth
these problems.
---
src/box/lua/tuple.c | 9 +++--
src/box/memtx_space.c | 18 ++++------
src/box/space.c | 23 ++++++-------
src/box/tuple.c | 6 ++--
src/box/tuple_update.c | 74 +++++++++++++++++++++--------------------
src/box/tuple_update.h | 14 +++-----
src/box/vinyl.c | 10 ++----
src/box/vy_upsert.c | 29 ++++------------
test/unit/column_mask.c | 30 +++++++----------
9 files changed, 88 insertions(+), 125 deletions(-)
diff --git a/src/box/lua/tuple.c b/src/box/lua/tuple.c
index 183c3901d..2fbfb1473 100644
--- a/src/box/lua/tuple.c
+++ b/src/box/lua/tuple.c
@@ -447,11 +447,10 @@ lbox_tuple_transform(struct lua_State *L)
* to use the default one with no restrictions on field
* count or types.
*/
- const char *new_data = tuple_update_execute(region_aligned_alloc_cb,
- region, buf->buf,
- buf->buf + ibuf_used(buf),
- old_data, old_data + bsize,
- &new_size, 1, NULL);
+ const char *new_data =
+ tuple_update_execute(buf->buf, buf->buf + ibuf_used(buf),
+ old_data, old_data + bsize, &new_size, 1,
+ NULL);
if (new_data != NULL)
new_tuple = tuple_new(box_tuple_format_default(),
new_data, new_data + new_size);
diff --git a/src/box/memtx_space.c b/src/box/memtx_space.c
index f0e1cfd27..54b379c43 100644
--- a/src/box/memtx_space.c
+++ b/src/box/memtx_space.c
@@ -419,8 +419,7 @@ memtx_space_execute_update(struct space *space, struct txn *txn,
uint32_t new_size = 0, bsize;
const char *old_data = tuple_data_range(old_tuple, &bsize);
const char *new_data =
- tuple_update_execute(region_aligned_alloc_cb, &fiber()->gc,
- request->tuple, request->tuple_end,
+ tuple_update_execute(request->tuple, request->tuple_end,
old_data, old_data + bsize,
&new_size, request->index_base, NULL);
if (new_data == NULL)
@@ -489,9 +488,8 @@ memtx_space_execute_upsert(struct space *space, struct txn *txn,
* we get it here, it's also OK to throw it
* @sa https://github.com/tarantool/tarantool/issues/1156
*/
- if (tuple_update_check_ops(region_aligned_alloc_cb, &fiber()->gc,
- request->ops, request->ops_end,
- request->index_base)) {
+ if (tuple_update_check_ops(request->ops, request->ops_end,
+ request->index_base) != 0) {
return -1;
}
stmt->new_tuple = memtx_tuple_new(space->format,
@@ -511,12 +509,10 @@ memtx_space_execute_upsert(struct space *space, struct txn *txn,
*/
uint64_t column_mask = COLUMN_MASK_FULL;
const char *new_data =
- tuple_upsert_execute(region_aligned_alloc_cb,
- &fiber()->gc, request->ops,
- request->ops_end, old_data,
- old_data + bsize, &new_size,
- request->index_base, false,
- &column_mask);
+ tuple_upsert_execute(request->ops, request->ops_end,
+ old_data, old_data + bsize,
+ &new_size, request->index_base,
+ false, &column_mask);
if (new_data == NULL)
return -1;
diff --git a/src/box/space.c b/src/box/space.c
index e7babb2ae..e881aaf32 100644
--- a/src/box/space.c
+++ b/src/box/space.c
@@ -292,7 +292,6 @@ static int
space_before_replace(struct space *space, struct txn *txn,
struct request *request)
{
- struct region *gc = &fiber()->gc;
enum iproto_type type = request->type;
struct index *pk = space_index(space, 0);
@@ -358,10 +357,10 @@ space_before_replace(struct space *space, struct txn *txn,
}
old_data = tuple_data_range(old_tuple, &old_size);
old_data_end = old_data + old_size;
- new_data = tuple_update_execute(region_aligned_alloc_cb, gc,
- request->tuple, request->tuple_end,
- old_data, old_data_end, &new_size,
- request->index_base, NULL);
+ new_data = tuple_update_execute(request->tuple,
+ request->tuple_end, old_data,
+ old_data_end, &new_size,
+ request->index_base, NULL);
if (new_data == NULL)
return -1;
new_data_end = new_data + new_size;
@@ -381,18 +380,18 @@ space_before_replace(struct space *space, struct txn *txn,
*/
new_data = request->tuple;
new_data_end = request->tuple_end;
- if (tuple_update_check_ops(region_aligned_alloc_cb, gc,
- request->ops, request->ops_end,
- request->index_base) != 0)
+ if (tuple_update_check_ops(request->ops,
+ request->ops_end,
+ request->index_base) != 0)
return -1;
break;
}
old_data = tuple_data_range(old_tuple, &old_size);
old_data_end = old_data + old_size;
- new_data = tuple_upsert_execute(region_aligned_alloc_cb, gc,
- request->ops, request->ops_end,
- old_data, old_data_end, &new_size,
- request->index_base, false, NULL);
+ new_data = tuple_upsert_execute(request->ops, request->ops_end,
+ old_data, old_data_end,
+ &new_size, request->index_base,
+ false, NULL);
new_data_end = new_data + new_size;
break;
default:
diff --git a/src/box/tuple.c b/src/box/tuple.c
index a7ef332b2..1e5b2fb24 100644
--- a/src/box/tuple.c
+++ b/src/box/tuple.c
@@ -706,8 +706,7 @@ box_tuple_update(box_tuple_t *tuple, const char *expr, const char *expr_end)
struct region *region = &fiber()->gc;
size_t used = region_used(region);
const char *new_data =
- tuple_update_execute(region_aligned_alloc_cb, region, expr,
- expr_end, old_data, old_data + bsize,
+ tuple_update_execute(expr, expr_end, old_data, old_data + bsize,
&new_size, 1, NULL);
if (new_data == NULL) {
region_truncate(region, used);
@@ -729,8 +728,7 @@ box_tuple_upsert(box_tuple_t *tuple, const char *expr, const char *expr_end)
struct region *region = &fiber()->gc;
size_t used = region_used(region);
const char *new_data =
- tuple_upsert_execute(region_aligned_alloc_cb, region, expr,
- expr_end, old_data, old_data + bsize,
+ tuple_upsert_execute(expr, expr_end, old_data, old_data + bsize,
&new_size, 1, false, NULL);
if (new_data == NULL) {
region_truncate(region, used);
diff --git a/src/box/tuple_update.c b/src/box/tuple_update.c
index 7a203ced8..599952189 100644
--- a/src/box/tuple_update.c
+++ b/src/box/tuple_update.c
@@ -43,7 +43,7 @@
#include <bit/int96.h>
#include <salad/rope.h>
#include "column_mask.h"
-
+#include "fiber.h"
/** UPDATE request implementation.
* UPDATE request is represented by a sequence of operations, each
@@ -96,10 +96,27 @@
* deleted one.
*/
+static inline void *
+update_alloc(void *ctx, size_t size)
+{
+ void *ptr = region_aligned_alloc((struct region *) ctx, size,
+ alignof(uint64_t));
+ if (ptr == NULL)
+ diag_set(OutOfMemory, size, "region_aligned_alloc",
+ "update internals");
+ return ptr;
+}
+
+static void
+update_free(void *ctx, void *mem)
+{
+ (void) ctx;
+ (void) mem;
+}
+
/** Update internal state */
struct tuple_update
{
- tuple_update_alloc_func alloc;
void *alloc_ctx;
struct rope *rope;
struct update_op *ops;
@@ -508,7 +525,7 @@ do_op_insert(struct tuple_update *update, struct update_op *op)
if (op_adjust_field_no(update, op, rope_size(update->rope) + 1))
return -1;
struct update_field *field = (struct update_field *)
- update->alloc(update->alloc_ctx, sizeof(*field));
+ update_alloc(update->alloc_ctx, sizeof(*field));
if (field == NULL)
return -1;
update_field_init(field, op->arg.set.value, op->arg.set.length, 0);
@@ -778,7 +795,7 @@ update_field_split(void *split_ctx, void *data, size_t size, size_t offset)
struct update_field *prev = (struct update_field *) data;
struct update_field *next = (struct update_field *)
- update->alloc(update->alloc_ctx, sizeof(*next));
+ update_alloc(update->alloc_ctx, sizeof(*next));
if (next == NULL)
return NULL;
assert(offset > 0 && prev->tail_len > 0);
@@ -799,14 +816,6 @@ update_field_split(void *split_ctx, void *data, size_t size, size_t offset)
return next;
}
-/** Free rope node - do nothing, since we use a pool allocator. */
-static void
-region_alloc_free_stub(void *ctx, void *mem)
-{
- (void) ctx;
- (void) mem;
-}
-
/**
* We found a tuple to do the update on. Prepare a rope
* to perform operations on.
@@ -822,14 +831,14 @@ int
update_create_rope(struct tuple_update *update, const char *tuple_data,
const char *tuple_data_end, uint32_t field_count)
{
- update->rope = rope_new(update_field_split, update, update->alloc,
- region_alloc_free_stub, update->alloc_ctx);
+ update->rope = rope_new(update_field_split, update, update_alloc,
+ update_free, update->alloc_ctx);
if (update->rope == NULL)
return -1;
/* Initialize the rope with the old tuple. */
struct update_field *first = (struct update_field *)
- update->alloc(update->alloc_ctx, sizeof(*first));
+ update_alloc(update->alloc_ctx, sizeof(*first));
if (first == NULL)
return -1;
const char *field = tuple_data;
@@ -970,7 +979,7 @@ update_read_ops(struct tuple_update *update, const char *expr,
}
/* Read update operations. */
- update->ops = (struct update_op *) update->alloc(update->alloc_ctx,
+ update->ops = (struct update_op *) update_alloc(update->alloc_ctx,
update->op_count * sizeof(struct update_op));
if (update->ops == NULL)
return -1;
@@ -1160,13 +1169,10 @@ upsert_do_ops(struct tuple_update *update, const char *old_data,
}
static void
-update_init(struct tuple_update *update,
- tuple_update_alloc_func alloc, void *alloc_ctx,
- int index_base)
+update_init(struct tuple_update *update, int index_base)
{
memset(update, 0, sizeof(*update));
- update->alloc = alloc;
- update->alloc_ctx = alloc_ctx;
+ update->alloc_ctx = &fiber()->gc;
/*
* Base field offset, e.g. 0 for C and 1 for Lua. Used only for
* error messages. All fields numbers must be zero-based!
@@ -1178,7 +1184,7 @@ const char *
update_finish(struct tuple_update *update, uint32_t *p_tuple_len)
{
uint32_t tuple_len = update_calc_tuple_length(update);
- char *buffer = (char *) update->alloc(update->alloc_ctx, tuple_len);
+ char *buffer = (char *) update_alloc(update->alloc_ctx, tuple_len);
if (buffer == NULL)
return NULL;
*p_tuple_len = update_write_tuple(update, buffer, buffer + tuple_len);
@@ -1186,23 +1192,21 @@ update_finish(struct tuple_update *update, uint32_t *p_tuple_len)
}
int
-tuple_update_check_ops(tuple_update_alloc_func alloc, void *alloc_ctx,
- const char *expr, const char *expr_end, int index_base)
+tuple_update_check_ops(const char *expr, const char *expr_end, int index_base)
{
struct tuple_update update;
- update_init(&update, alloc, alloc_ctx, index_base);
+ update_init(&update, index_base);
return update_read_ops(&update, expr, expr_end, 0);
}
const char *
-tuple_update_execute(tuple_update_alloc_func alloc, void *alloc_ctx,
- const char *expr,const char *expr_end,
+tuple_update_execute(const char *expr,const char *expr_end,
const char *old_data, const char *old_data_end,
uint32_t *p_tuple_len, int index_base,
uint64_t *column_mask)
{
struct tuple_update update;
- update_init(&update, alloc, alloc_ctx, index_base);
+ update_init(&update, index_base);
uint32_t field_count = mp_decode_array(&old_data);
if (update_read_ops(&update, expr, expr_end, field_count) != 0)
@@ -1216,14 +1220,13 @@ tuple_update_execute(tuple_update_alloc_func alloc, void *alloc_ctx,
}
const char *
-tuple_upsert_execute(tuple_update_alloc_func alloc, void *alloc_ctx,
- const char *expr,const char *expr_end,
+tuple_upsert_execute(const char *expr,const char *expr_end,
const char *old_data, const char *old_data_end,
uint32_t *p_tuple_len, int index_base, bool suppress_error,
uint64_t *column_mask)
{
struct tuple_update update;
- update_init(&update, alloc, alloc_ctx, index_base);
+ update_init(&update, index_base);
uint32_t field_count = mp_decode_array(&old_data);
if (update_read_ops(&update, expr, expr_end, field_count) != 0)
@@ -1238,8 +1241,7 @@ tuple_upsert_execute(tuple_update_alloc_func alloc, void *alloc_ctx,
}
const char *
-tuple_upsert_squash(tuple_update_alloc_func alloc, void *alloc_ctx,
- const char *expr1, const char *expr1_end,
+tuple_upsert_squash(const char *expr1, const char *expr1_end,
const char *expr2, const char *expr2_end,
size_t *result_size, int index_base)
{
@@ -1247,7 +1249,7 @@ tuple_upsert_squash(tuple_update_alloc_func alloc, void *alloc_ctx,
const char *expr_end[2] = {expr1_end, expr2_end};
struct tuple_update update[2];
for (int j = 0; j < 2; j++) {
- update_init(&update[j], alloc, alloc_ctx, index_base);
+ update_init(&update[j], index_base);
if (update_read_ops(&update[j], expr[j], expr_end[j], 0))
return NULL;
mp_decode_array(&expr[j]);
@@ -1264,8 +1266,8 @@ tuple_upsert_squash(tuple_update_alloc_func alloc, void *alloc_ctx,
}
size_t possible_size = expr1_end - expr1 + expr2_end - expr2;
const uint32_t space_for_arr_tag = 5;
- char *buf = (char *)alloc(alloc_ctx,
- possible_size + space_for_arr_tag);
+ char *buf = (char *) update_alloc(&fiber()->gc,
+ possible_size + space_for_arr_tag);
if (buf == NULL)
return NULL;
/* reserve some space for mp array header */
diff --git a/src/box/tuple_update.h b/src/box/tuple_update.h
index 706edd55a..37faa1918 100644
--- a/src/box/tuple_update.h
+++ b/src/box/tuple_update.h
@@ -44,22 +44,17 @@ enum {
BOX_UPDATE_OP_CNT_MAX = 4000,
};
-typedef void *(*tuple_update_alloc_func)(void *, size_t);
-
int
-tuple_update_check_ops(tuple_update_alloc_func alloc, void *alloc_ctx,
- const char *expr, const char *expr_end, int index_base);
+tuple_update_check_ops(const char *expr, const char *expr_end, int index_base);
const char *
-tuple_update_execute(tuple_update_alloc_func alloc, void *alloc_ctx,
- const char *expr,const char *expr_end,
+tuple_update_execute(const char *expr,const char *expr_end,
const char *old_data, const char *old_data_end,
uint32_t *p_new_size, int index_base,
uint64_t *column_mask);
const char *
-tuple_upsert_execute(tuple_update_alloc_func alloc, void *alloc_ctx,
- const char *expr, const char *expr_end,
+tuple_upsert_execute(const char *expr, const char *expr_end,
const char *old_data, const char *old_data_end,
uint32_t *p_new_size, int index_base, bool suppress_error,
uint64_t *column_mask);
@@ -75,8 +70,7 @@ tuple_upsert_execute(tuple_update_alloc_func alloc, void *alloc_ctx,
* If it isn't possible to merge expressions NULL is returned.
*/
const char *
-tuple_upsert_squash(tuple_update_alloc_func alloc, void *alloc_ctx,
- const char *expr1, const char *expr1_end,
+tuple_upsert_squash(const char *expr1, const char *expr1_end,
const char *expr2, const char *expr2_end,
size_t *result_size, int index_base);
diff --git a/src/box/vinyl.c b/src/box/vinyl.c
index e0de65d05..d82cae766 100644
--- a/src/box/vinyl.c
+++ b/src/box/vinyl.c
@@ -1937,8 +1937,7 @@ vy_update(struct vy_env *env, struct vy_tx *tx, struct txn_stmt *stmt,
uint32_t new_size, old_size;
const char *old_tuple = tuple_data_range(stmt->old_tuple, &old_size);
const char *old_tuple_end = old_tuple + old_size;
- new_tuple = tuple_update_execute(region_aligned_alloc_cb, &fiber()->gc,
- request->tuple, request->tuple_end,
+ new_tuple = tuple_update_execute(request->tuple, request->tuple_end,
old_tuple, old_tuple_end, &new_size,
request->index_base, &column_mask);
if (new_tuple == NULL)
@@ -2117,8 +2116,7 @@ vy_upsert(struct vy_env *env, struct vy_tx *tx, struct txn_stmt *stmt,
if (vy_is_committed(env, pk))
return 0;
/* Check update operations. */
- if (tuple_update_check_ops(region_aligned_alloc_cb, &fiber()->gc,
- request->ops, request->ops_end,
+ if (tuple_update_check_ops(request->ops, request->ops_end,
request->index_base)) {
return -1;
}
@@ -2176,9 +2174,7 @@ vy_upsert(struct vy_env *env, struct vy_tx *tx, struct txn_stmt *stmt,
old_tuple_end = old_tuple + old_size;
/* Apply upsert operations to the old tuple. */
- new_tuple = tuple_upsert_execute(region_aligned_alloc_cb,
- &fiber()->gc, ops, ops_end,
- old_tuple, old_tuple_end,
+ new_tuple = tuple_upsert_execute(ops, ops_end, old_tuple, old_tuple_end,
&new_size, 0, false, &column_mask);
if (new_tuple == NULL)
return -1;
diff --git a/src/box/vy_upsert.c b/src/box/vy_upsert.c
index e5e53be79..1c55f86c2 100644
--- a/src/box/vy_upsert.c
+++ b/src/box/vy_upsert.c
@@ -38,17 +38,6 @@
#include "fiber.h"
#include "column_mask.h"
-static void *
-vy_update_alloc(void *arg, size_t size)
-{
- /* TODO: rewrite tuple_upsert_execute() without exceptions */
- struct region *region = (struct region *) arg;
- void *data = region_aligned_alloc(region, size, sizeof(uint64_t));
- if (data == NULL)
- diag_set(OutOfMemory, size, "region", "upsert");
- return data;
-}
-
/**
* Try to squash two upsert series (msgspacked index_base + ops)
* Try to create a tuple with squahed operations
@@ -58,7 +47,7 @@ vy_update_alloc(void *arg, size_t size)
* @retval -1 - memory error
*/
static int
-vy_upsert_try_to_squash(struct tuple_format *format, struct region *region,
+vy_upsert_try_to_squash(struct tuple_format *format,
const char *key_mp, const char *key_mp_end,
const char *old_serie, const char *old_serie_end,
const char *new_serie, const char *new_serie_end,
@@ -68,8 +57,7 @@ vy_upsert_try_to_squash(struct tuple_format *format, struct region *region,
size_t squashed_size;
const char *squashed =
- tuple_upsert_squash(vy_update_alloc, region,
- old_serie, old_serie_end,
+ tuple_upsert_squash(old_serie, old_serie_end,
new_serie, new_serie_end,
&squashed_size, 0);
if (squashed == NULL)
@@ -130,10 +118,9 @@ vy_apply_upsert(struct tuple *new_stmt, struct tuple *old_stmt,
size_t region_svp = region_used(region);
uint8_t old_type = vy_stmt_type(old_stmt);
uint64_t column_mask = COLUMN_MASK_FULL;
- result_mp = tuple_upsert_execute(vy_update_alloc, region, new_ops,
- new_ops_end, result_mp, result_mp_end,
- &mp_size, 0, suppress_error,
- &column_mask);
+ result_mp = tuple_upsert_execute(new_ops, new_ops_end, result_mp,
+ result_mp_end, &mp_size, 0,
+ suppress_error, &column_mask);
result_mp_end = result_mp + mp_size;
if (old_type != IPROTO_UPSERT) {
assert(old_type == IPROTO_INSERT ||
@@ -163,10 +150,8 @@ vy_apply_upsert(struct tuple *new_stmt, struct tuple *old_stmt,
* UPSERT + UPSERT case: combine operations
*/
assert(old_ops_end - old_ops > 0);
- if (vy_upsert_try_to_squash(format, region,
- result_mp, result_mp_end,
- old_ops, old_ops_end,
- new_ops, new_ops_end,
+ if (vy_upsert_try_to_squash(format, result_mp, result_mp_end,
+ old_ops, old_ops_end, new_ops, new_ops_end,
&result_stmt) != 0) {
region_truncate(region, region_svp);
return NULL;
diff --git a/test/unit/column_mask.c b/test/unit/column_mask.c
index 7859626f8..3ffd351ac 100644
--- a/test/unit/column_mask.c
+++ b/test/unit/column_mask.c
@@ -3,6 +3,9 @@
#include "unit.h"
#include "msgpuck.h"
#include "trivia/util.h"
+#include "fiber.h"
+#include "memory.h"
+#include "tuple.h"
#define MAX_OPS 20
#define MAX_FIELDS 100
@@ -102,20 +105,6 @@ tuple_new_update(const struct tuple_update_template *update, char **end)
return ret;
}
-static char buffer[2048];
-static size_t pos = 0;
-
-/** Allocator for the tuple_update function. */
-static void *
-tuple_update_alloc_f(void *unused, size_t size)
-{
- (void) unused;
- fail_if(pos + size > sizeof(buffer));
- char *ret = &buffer[pos];
- pos += size;
- return ret;
-}
-
/**
* Execute an update operation from the template and compare it
* with the expected tuple and expected column_mask.
@@ -138,20 +127,19 @@ check_update_result(const struct tuple_template *original,
uint32_t actual_len;
uint64_t column_mask;
+ struct region *region = &fiber()->gc;
const char *actual =
- tuple_update_execute(tuple_update_alloc_f, NULL, ops, ops_end,
- old, old_end, &actual_len, 1,
+ tuple_update_execute(ops, ops_end, old, old_end, &actual_len, 1,
&column_mask);
fail_if(actual == NULL);
is((int32_t)actual_len, new_end - new, "check result length");
is(memcmp(actual, new, actual_len), 0, "tuple update is correct");
is(column_mask, expected_mask, "column_mask is correct");
+ fiber_gc();
free(old);
free(new);
free(ops);
- /* reset the global buffer. */
- pos = 0;
}
static inline void
@@ -239,6 +227,9 @@ basic_test()
int
main()
{
+ memory_init();
+ fiber_init(fiber_c_invoke);
+ tuple_init(NULL);
header();
plan(27);
@@ -246,4 +237,7 @@ main()
footer();
check_plan();
+ tuple_free();
+ fiber_free();
+ memory_free();
}
--
2.20.1 (Apple Git-117)
^ permalink raw reply [flat|nested] 10+ messages in thread
* [PATCH 2/5] rope: make rope library macro template
2019-07-13 22:11 [PATCH 0/5] JSON update preparation Vladislav Shpilevoy
2019-07-13 22:11 ` [PATCH 1/5] tuple: remove alloc and alloc_ctx args from update() Vladislav Shpilevoy
@ 2019-07-13 22:11 ` Vladislav Shpilevoy
2019-07-13 22:11 ` [PATCH 3/5] tuple: relax struct tuple_update dependency on rope Vladislav Shpilevoy
` (5 subsequent siblings)
7 siblings, 0 replies; 10+ messages in thread
From: Vladislav Shpilevoy @ 2019-07-13 22:11 UTC (permalink / raw)
To: tarantool-patches; +Cc: vdavydov.dev
Rope library stores alloc, split and free functions by pointer,
that is a huge slog at performance, as any other virtual
function call. There is no reason, why the rope library may not
become a template, except historical ones.
The patch not only removes virtual functions, but also makes rope
deletion almost no-op in case if free() function is not defined.
A second motivation point of that patch is that original rope
structure was too big. Again, because it stored several pointers
to functions. In forthcoming patches on #1261 multiple ropes can
be created per each update, so it makes sense to reduce size of
this structure.
---
The patch is quite dubious, I agree, and ready to alternative options how to
remove these alloc/free/split pointers.
Talking of necessity of this patch at all - it makes rope struct 40 bytes
lighter. JSON updates will create a new rope (sometimes) for each updated array
inside the tuple. So I thought, that it is worth optimizing.
debian/copyright | 2 +-
src/box/tuple_update.c | 74 +++--
src/lib/salad/rope.c | 479 +++++--------------------------
src/lib/salad/rope.h | 617 ++++++++++++++++++++++++++++++++++------
test/unit/rope.c | 1 -
test/unit/rope_avl.c | 1 -
test/unit/rope_basic.c | 1 -
test/unit/rope_common.h | 41 ++-
test/unit/rope_stress.c | 5 +-
9 files changed, 674 insertions(+), 547 deletions(-)
diff --git a/debian/copyright b/debian/copyright
index a48171371..3d68dc390 100644
--- a/debian/copyright
+++ b/debian/copyright
@@ -218,7 +218,7 @@ Files: third_party/lua-cjson/*
Copyright: 2010-2012 Mark Pulford <mark@kyne.com.au>
License: Expat
-Files: src/lib/salad/rope.c
+Files: src/lib/salad/rope.*
Copyright: 1993-1994 by Xerox Corporation.
License: BSD-2-Clause
diff --git a/src/box/tuple_update.c b/src/box/tuple_update.c
index 599952189..7498d558a 100644
--- a/src/box/tuple_update.c
+++ b/src/box/tuple_update.c
@@ -30,8 +30,6 @@
*/
#include "tuple_update.h"
-
-#include <stdio.h>
#include <stdbool.h>
#include "say.h"
@@ -41,7 +39,6 @@
#include "third_party/queue.h"
#include <msgpuck/msgpuck.h>
#include <bit/int96.h>
-#include <salad/rope.h>
#include "column_mask.h"
#include "fiber.h"
@@ -97,27 +94,19 @@
*/
static inline void *
-update_alloc(void *ctx, size_t size)
+update_alloc(struct region *region, size_t size)
{
- void *ptr = region_aligned_alloc((struct region *) ctx, size,
- alignof(uint64_t));
+ void *ptr = region_aligned_alloc(region, size, alignof(uint64_t));
if (ptr == NULL)
diag_set(OutOfMemory, size, "region_aligned_alloc",
"update internals");
return ptr;
}
-static void
-update_free(void *ctx, void *mem)
-{
- (void) ctx;
- (void) mem;
-}
-
/** Update internal state */
struct tuple_update
{
- void *alloc_ctx;
+ struct region *region;
struct rope *rope;
struct update_op *ops;
uint32_t op_count;
@@ -206,6 +195,17 @@ union update_op_arg {
struct update_field;
struct update_op;
+static struct update_field *
+update_field_split(struct region *region, struct update_field *data,
+ size_t size, size_t offset);
+
+#define ROPE_SPLIT_F update_field_split
+#define ROPE_ALLOC_F update_alloc
+#define rope_data_t struct update_field *
+#define rope_ctx_t struct region *
+
+#include "salad/rope.h"
+
typedef int (*do_op_func)(struct tuple_update *update, struct update_op *op);
typedef int (*read_arg_func)(int index_base, struct update_op *op,
const char **expr);
@@ -525,7 +525,7 @@ do_op_insert(struct tuple_update *update, struct update_op *op)
if (op_adjust_field_no(update, op, rope_size(update->rope) + 1))
return -1;
struct update_field *field = (struct update_field *)
- update_alloc(update->alloc_ctx, sizeof(*field));
+ update_alloc(update->region, sizeof(*field));
if (field == NULL)
return -1;
update_field_init(field, op->arg.set.value, op->arg.set.length, 0);
@@ -540,8 +540,7 @@ do_op_set(struct tuple_update *update, struct update_op *op)
return do_op_insert(update, op);
if (op_adjust_field_no(update, op, rope_size(update->rope)))
return -1;
- struct update_field *field = (struct update_field *)
- rope_extract(update->rope, op->field_no);
+ struct update_field *field = rope_extract(update->rope, op->field_no);
if (field == NULL)
return -1;
/* Ignore the previous op, if any. */
@@ -578,8 +577,7 @@ do_op_arith(struct tuple_update *update, struct update_op *op)
if (op_adjust_field_no(update, op, rope_size(update->rope)))
return -1;
- struct update_field *field = (struct update_field *)
- rope_extract(update->rope, op->field_no);
+ struct update_field *field = rope_extract(update->rope, op->field_no);
if (field == NULL)
return -1;
if (field->op) {
@@ -608,8 +606,7 @@ do_op_bit(struct tuple_update *update, struct update_op *op)
{
if (op_adjust_field_no(update, op, rope_size(update->rope)))
return -1;
- struct update_field *field = (struct update_field *)
- rope_extract(update->rope, op->field_no);
+ struct update_field *field = rope_extract(update->rope, op->field_no);
if (field == NULL)
return -1;
struct op_bit_arg *arg = &op->arg.bit;
@@ -646,8 +643,7 @@ do_op_splice(struct tuple_update *update, struct update_op *op)
{
if (op_adjust_field_no(update, op, rope_size(update->rope)))
return -1;
- struct update_field *field = (struct update_field *)
- rope_extract(update->rope, op->field_no);
+ struct update_field *field = rope_extract(update->rope, op->field_no);
if (field == NULL)
return -1;
if (field->op) {
@@ -786,16 +782,13 @@ static const struct update_op_meta op_delete =
/** Split a range of fields in two, allocating update_field
* context for the new range.
*/
-static void *
-update_field_split(void *split_ctx, void *data, size_t size, size_t offset)
+static struct update_field *
+update_field_split(struct region *region, struct update_field *prev,
+ size_t size, size_t offset)
{
- (void)size;
- struct tuple_update *update = (struct tuple_update *) split_ctx;
-
- struct update_field *prev = (struct update_field *) data;
-
- struct update_field *next = (struct update_field *)
- update_alloc(update->alloc_ctx, sizeof(*next));
+ (void) size;
+ struct update_field *next =
+ (struct update_field *) update_alloc(region, sizeof(*next));
if (next == NULL)
return NULL;
assert(offset > 0 && prev->tail_len > 0);
@@ -831,14 +824,13 @@ int
update_create_rope(struct tuple_update *update, const char *tuple_data,
const char *tuple_data_end, uint32_t field_count)
{
- update->rope = rope_new(update_field_split, update, update_alloc,
- update_free, update->alloc_ctx);
+ update->rope = rope_new(update->region);
if (update->rope == NULL)
return -1;
/* Initialize the rope with the old tuple. */
struct update_field *first = (struct update_field *)
- update_alloc(update->alloc_ctx, sizeof(*first));
+ update_alloc(update->region, sizeof(*first));
if (first == NULL)
return -1;
const char *field = tuple_data;
@@ -864,8 +856,7 @@ update_calc_tuple_length(struct tuple_update *update)
rope_iter_create(&it, update->rope);
for (node = rope_iter_start(&it); node; node = rope_iter_next(&it)) {
- struct update_field *field =
- (struct update_field *) rope_leaf_data(node);
+ struct update_field *field = rope_leaf_data(node);
uint32_t field_len = (field->op ? field->op->new_field_len :
(uint32_t)(field->tail - field->old));
res += field_len + field->tail_len;
@@ -889,8 +880,7 @@ update_write_tuple(struct tuple_update *update, char *buffer, char *buffer_end)
rope_iter_create(&it, update->rope);
for (node = rope_iter_start(&it); node; node = rope_iter_next(&it)) {
- struct update_field *field = (struct update_field *)
- rope_leaf_data(node);
+ struct update_field *field = rope_leaf_data(node);
uint32_t field_count = rope_leaf_size(node);
const char *old_field = field->old;
struct update_op *op = field->op;
@@ -979,7 +969,7 @@ update_read_ops(struct tuple_update *update, const char *expr,
}
/* Read update operations. */
- update->ops = (struct update_op *) update_alloc(update->alloc_ctx,
+ update->ops = (struct update_op *) update_alloc(update->region,
update->op_count * sizeof(struct update_op));
if (update->ops == NULL)
return -1;
@@ -1172,7 +1162,7 @@ static void
update_init(struct tuple_update *update, int index_base)
{
memset(update, 0, sizeof(*update));
- update->alloc_ctx = &fiber()->gc;
+ update->region = &fiber()->gc;
/*
* Base field offset, e.g. 0 for C and 1 for Lua. Used only for
* error messages. All fields numbers must be zero-based!
@@ -1184,7 +1174,7 @@ const char *
update_finish(struct tuple_update *update, uint32_t *p_tuple_len)
{
uint32_t tuple_len = update_calc_tuple_length(update);
- char *buffer = (char *) update_alloc(update->alloc_ctx, tuple_len);
+ char *buffer = (char *) update_alloc(update->region, tuple_len);
if (buffer == NULL)
return NULL;
*p_tuple_len = update_write_tuple(update, buffer, buffer + tuple_len);
diff --git a/src/lib/salad/rope.c b/src/lib/salad/rope.c
index 06324ab65..5de951c78 100644
--- a/src/lib/salad/rope.c
+++ b/src/lib/salad/rope.c
@@ -1,5 +1,5 @@
/*
- * Copyright 2010-2016, Tarantool AUTHORS, please see AUTHORS file.
+ * Copyright 2010-2019, Tarantool AUTHORS, please see AUTHORS file.
*
* Redistribution and use in source and binary forms, with or
* without modification, are permitted provided that the following
@@ -42,127 +42,73 @@
*
* Author: Hans-J. Boehm (boehm@parc.xerox.com)
*/
-/*
- * This is a rope implementation which uses AVL tree
- * balancing algorithm for rope tree balance.
+#include <stdlib.h>
+
+/**
+ * This macro helps to implement some common rope functions, not
+ * depending on a specific rope, only once, in a single object
+ * file.
*/
+#define ROPE_SRC
+#define rope_data_t void *
+#define rope_ctx_t void *
#include "rope.h"
-#include <stdio.h>
-#include <string.h>
-#include <stdlib.h>
-#include <assert.h>
static inline int
-rope_node_height(struct rope_node *node)
+avl_node_height(struct avl_node *node)
{
return node ? node->height : 0;
}
-#if !defined(MAX)
-#define MAX(a, b) ((a) > (b) ? (a) : (b))
-#endif /* MAX */
-
static inline void
-rope_relink(struct rope_node *node)
+avl_node_relink(struct avl_node *node)
{
- node->tree_size = (rope_node_size(node->link[0]) +
- rope_node_size(node->link[1]) +
+ node->tree_size = (avl_node_size(node->link[0]) +
+ avl_node_size(node->link[1]) +
node->leaf_size);
- node->height = MAX(rope_node_height(node->link[0]),
- rope_node_height(node->link[1])) + 1;
-}
-
-static inline struct rope_node *
-rope_node_new(struct rope *rope, void *data, rope_size_t size)
-{
- struct rope_node *node =
- (struct rope_node *) rope->alloc(rope->alloc_ctx,
- sizeof(struct rope_node));
-
- if (node == NULL)
- return NULL;
-
- node->height = 1;
- node->tree_size = node->leaf_size = size;
- node->data = data;
- node->link[0] = node->link[1] = NULL;
-
- return node;
+ node->height = MAX(avl_node_height(node->link[0]),
+ avl_node_height(node->link[1])) + 1;
}
-void
-rope_clear(struct rope *rope)
+static inline struct avl_node *
+avl_rotate_single(struct avl_node *parent, int direction)
{
- struct rope_node *it = rope->root;
- struct rope_node *save;
-
- /* Destruction by rotation */
- while (it != NULL) {
- if (it->link[0] == NULL) {
- /* Remove node */
- save = it->link[1];
- rope->free(rope->alloc_ctx, it);
- } else {
- /* Rotate right */
- save = it->link[0];
- it->link[0] = save->link[1];
- save->link[1] = it;
- }
- it = save;
- }
- rope->root = NULL;
-}
-
-static struct rope_node *
-rope_node_split(struct rope *rope, struct rope_node *node, rope_size_t offset)
-{
- rope_size_t old_size = node->leaf_size;
- node->leaf_size = offset;
-
- void *data = rope->split(rope->split_ctx, node->data, old_size, offset);
- return rope_node_new(rope, data, old_size - offset);
-}
-
-static inline struct rope_node *
-avl_rotate_single(struct rope_node *parent, int direction)
-{
- struct rope_node *save = parent->link[!direction];
+ struct avl_node *save = parent->link[!direction];
parent->link[!direction] = save->link[direction];
save->link[direction] = parent;
/* First relink the parent, since it's now a child. */
- rope_relink(parent);
- rope_relink(save);
+ avl_node_relink(parent);
+ avl_node_relink(save);
return save;
}
-static inline struct rope_node *
-avl_rotate_double(struct rope_node *parent, int direction)
+static inline struct avl_node *
+avl_rotate_double(struct avl_node *parent, int direction)
{
parent->link[!direction] =
avl_rotate_single(parent->link[!direction], !direction);
return avl_rotate_single(parent, direction);
}
-/** Rebalance the tree. */
-static inline void
-avl_rebalance_after_insert(struct rope_node ***path,
- struct rope_node ***p_end, int insert_height)
+void
+avl_rebalance_after_insert(struct avl_node ***path, struct avl_node ***p_end,
+ int insert_height)
{
while (p_end > path) {
- struct rope_node *left = **p_end--;
- struct rope_node *parent = **p_end;
+ struct avl_node *left = **p_end--;
+ struct avl_node *parent = **p_end;
/*
* To use the same rotation functions, set mirror
* to 1 if left is right and right is left.
*/
int mirror = left != parent->link[0];
- struct rope_node *right = parent->link[!mirror];
+ struct avl_node *right = parent->link[!mirror];
- int left_height = rope_node_height(left);
- int right_height = rope_node_height(right);
+ int left_height = avl_node_height(left);
+ int right_height = avl_node_height(right);
parent->height = MAX(left_height, right_height) + 1;
/*
* Rotations flattened the tree, so there is no
@@ -179,10 +125,10 @@ avl_rebalance_after_insert(struct rope_node ***path,
* in the range -1..1 + height(new_node).
*/
if (left_height - right_height >= 2) {
- struct rope_node *l_left = left->link[mirror];
- struct rope_node *l_right = left->link[!mirror];
- int l_left_height = rope_node_height(l_left);
- int l_right_height = rope_node_height(l_right);
+ struct avl_node *l_left = left->link[mirror];
+ struct avl_node *l_right = left->link[!mirror];
+ int l_left_height = avl_node_height(l_left);
+ int l_right_height = avl_node_height(l_right);
/*
* Rotate in the direction, opposite to
* the skew. E.g. if we have two left-left
@@ -212,24 +158,20 @@ avl_rebalance_after_insert(struct rope_node ***path,
}
}
-/* This is a copy-cat of the previous loop,
- * with the exception that the heuristic to break
- * the loop is different.
- */
-static inline void
-avl_rebalance_after_delete(struct rope_node ***path,
- struct rope_node ***p_end)
+void
+avl_rebalance_after_delete(struct avl_node ***path,
+ struct avl_node ***p_end)
{
while (p_end > path) {
- struct rope_node *left = **p_end--;
- struct rope_node *parent = **p_end;
+ struct avl_node *left = **p_end--;
+ struct avl_node *parent = **p_end;
int mirror = left != parent->link[0];
- struct rope_node *right = parent->link[!mirror];
+ struct avl_node *right = parent->link[!mirror];
- int left_height = rope_node_height(left);
- int right_height = rope_node_height(right);
+ int left_height = avl_node_height(left);
+ int right_height = avl_node_height(right);
parent->height = MAX(left_height, right_height) + 1;
/*
@@ -241,10 +183,10 @@ avl_rebalance_after_delete(struct rope_node ***path,
break;
if (left_height - right_height <= -2) {
- struct rope_node *r_left = right->link[mirror];
- struct rope_node *r_right = right->link[!mirror];
- int r_left_height = rope_node_height(r_left);
- int r_right_height = rope_node_height(r_right);
+ struct avl_node *r_left = right->link[mirror];
+ struct avl_node *r_right = right->link[!mirror];
+ int r_left_height = avl_node_height(r_left);
+ int r_right_height = avl_node_height(r_right);
if (r_left_height <= r_right_height)
**p_end = avl_rotate_single(parent, mirror);
@@ -254,24 +196,17 @@ avl_rebalance_after_delete(struct rope_node ***path,
}
}
-/**
- * Find a rope node which contains the substring at offset,
- * adjusting tree size with adjust_size and saving the path
- * in path.
- *
- * @return the end of the route.
- */
-static inline struct rope_node ***
-avl_route_to_offset(struct rope_node ***path, rope_size_t *p_offset,
+struct avl_node ***
+avl_route_to_offset(struct avl_node ***path, uint32_t *p_offset,
ssize_t adjust_size)
{
- rope_size_t offset = *p_offset;
+ uint32_t offset = *p_offset;
while (**path) {
- struct rope_node *node = **path;
+ struct avl_node *node = **path;
node->tree_size += adjust_size;
- rope_size_t left_size = rope_node_size(node->link[0]);
+ uint32_t left_size = avl_node_size(node->link[0]);
if (offset < left_size) {
/* The offset lays in the left subtree. */
@@ -297,15 +232,10 @@ avl_route_to_offset(struct rope_node ***path, rope_size_t *p_offset,
return path;
}
-/**
- * Route to successor or predecessor node of the node
- * in **path. It's either the rightmost leaf of the left child
- * (previous node) or leftmost leaf of the right child.
- */
-static inline struct rope_node ***
-avl_route_to_next(struct rope_node ***path, int dir, rope_ssize_t adjust_size)
+struct avl_node ***
+avl_route_to_next(struct avl_node ***path, int dir, int32_t adjust_size)
{
- struct rope_node *node = **path;
+ struct avl_node *node = **path;
*++path = &node->link[dir];
while (**path) {
node = **path;
@@ -315,198 +245,6 @@ avl_route_to_next(struct rope_node ***path, int dir, rope_ssize_t adjust_size)
return path;
}
-/**
- * A new node is always inserted at a leaf position.
- * If insertion unbalances the tree, the rebalancing
- * procedure may put the node into an intermediate position.
- *
- * While traversing the tree, we simultaneously update
- * tree sizes of all intermediate nodes, taking into account
- * the size of the new node.
- *
- * When insertion offset falls at the middle of an existing node,
- * we truncate this node and attach its tail to the left leaf
- * of the new node. This trim operation doesn't decrease the old
- * subtree height, and, while it does change subtree size
- * temporarily, as long as we attach the new node to the right
- * subtree of the truncated node, truncation has no effect on the
- * tree size either.
- *
- * Rebalancing, when it occurs, will correctly update subtree
- * heights and sizes of all modified nodes.
- */
-int
-rope_insert(struct rope *rope, rope_size_t offset, void *data, rope_size_t size)
-{
- if (offset > rope_size(rope))
- offset = rope_size(rope);
-
- assert(size);
-
- struct rope_node *new_node = rope_node_new(rope, data, size);
-
- if (new_node == NULL)
- return -1;
-
- struct rope_node **path[ROPE_HEIGHT_MAX];
- path[0] = &rope->root;
-
- struct rope_node ***p_end = avl_route_to_offset(path, &offset, size);
- if (**p_end != NULL) {
- /*
- * The offset is inside an existing
- * substring in the rope. If offset is 0,
- * then insert the new node at the rightmost leaf
- * of the left child. Otherwise, cut the tail of
- * the substring, make it a prefix of the inserted
- * string, and insert the result at the leftmost
- * leaf of the right child.
- */
- if (offset != 0) {
- struct rope_node *split_node;
- split_node = rope_node_split(rope, **p_end, offset);
- if (split_node == NULL)
- return -1;
- split_node->link[0] = new_node;
- split_node->height++;
- split_node->tree_size += new_node->tree_size;
- new_node = split_node;
- }
- p_end = avl_route_to_next(p_end, offset != 0,
- new_node->tree_size);
- }
- **p_end = new_node;
- avl_rebalance_after_insert(path, p_end, new_node->height);
- return 0;
-}
-
-/** Make sure there is a rope node at the given offset. */
-struct rope_node *
-rope_extract_node(struct rope *rope, rope_size_t offset)
-{
- assert(offset < rope_size(rope));
-
- struct rope_node **path[ROPE_HEIGHT_MAX];
- path[0] = &rope->root;
-
- struct rope_node ***p_end = avl_route_to_offset(path, &offset, 0);
- if (offset == 0)
- return **p_end;
- struct rope_node *new_node = rope_node_split(rope, **p_end, offset);
- if (new_node == NULL)
- return NULL;
- p_end = avl_route_to_next(p_end, 1, new_node->tree_size);
- **p_end = new_node;
- avl_rebalance_after_insert(path, p_end, new_node->height);
- return new_node;
-}
-
-/**
- * Erase a single element from the rope.
- * This is a straightforward implementation for a single-element
- * deletion from a rope. A generic cut from a rope involves
- * 2 tree splits and one merge.
- *
- * When deleting a single element, 3 cases are possible:
- * - offset falls at a node with a single element. In this
- * case we perform a normal AVL tree delete.
- * - offset falls at the end or the beginning of an existing node
- * with leaf_size > 1. In that case we trim the existing node
- * and return.
- * - offset falls inside an existing node. In that case
- * we split the existing node at offset, and insert the tail.
- *
- * The implementation is a copycat of rope_insert(). If you're
- * trying to understand the code, it's recommended to start
- * from rope_insert().
- */
-int
-rope_erase(struct rope *rope, rope_size_t offset)
-{
- assert(offset < rope_size(rope));
-
- struct rope_node **path[ROPE_HEIGHT_MAX];
- path[0] = &rope->root;
-
- struct rope_node ***p_end = avl_route_to_offset(path, &offset, -1);
-
- struct rope_node *node = **p_end;
-
- if (node->leaf_size > 1) {
- /* Check if we can simply trim the node. */
- if (offset == 0) {
- /* Cut the head. */
- node->data = rope->split(rope->split_ctx, node->data,
- node->leaf_size, 1);
- node->leaf_size -= 1;
- return 0;
- }
- rope_size_t size = node->leaf_size;
- /* Cut the tail */
- void *next = rope->split(rope->split_ctx, node->data,
- node->leaf_size, offset);
- node->leaf_size = offset;
- if (offset == size - 1)
- return 0; /* Trimmed the tail, nothing else to do */
- /*
- * Offset falls inside a substring. Erase the
- * first field and insert the tail.
- */
- next = rope->split(rope->split_ctx, next, size - offset, 1);
- struct rope_node *new_node =
- rope_node_new(rope, next, size - offset - 1);
- if (new_node == NULL)
- return -1;
- /* Trim the old node. */
- p_end = avl_route_to_next(p_end, 1, new_node->tree_size);
- **p_end = new_node;
- avl_rebalance_after_insert(path, p_end, new_node->height);
- return 0;
- }
- /* We need to delete the node. */
- assert(offset == 0);
- int direction;
- if (node->link[0] != NULL && node->link[1] != NULL) {
- /*
- * The node has two non-NULL leaves. We can't
- * simply delete the node since in that case we
- * won't know what to do with one of the leaves.
- * Instead of deleting the node, store in it data
- * from the rightmost node in the left subtree, or
- * the leftmost node in the right subtree,
- * (depending on which subtree is taller), and
- * delete this leftmost/rightmost node instead.
- */
- struct rope_node *save = node;
- direction = node->link[1]->height > node->link[0]->height;
- p_end = avl_route_to_next(p_end, direction, 0) - 1;
- node = **p_end;
- /* Move the data pointers. */
- save->data = node->data;
- save->leaf_size = node->leaf_size;
- /*
- * Now follow the path again and update tree_size
- * in the parents of the moved child.
- */
- save = save->link[direction];
- while (save != node) {
- save->tree_size -= node->leaf_size;
- save = save->link[!direction];
- }
- } else {
- /*
- * Left or right subtree are NULL, so we
- * can simply put the non-NULL leaf in place
- * of the parent.
- */
- direction = node->link[0] == NULL;
- }
- **p_end = node->link[direction];
- rope->free(rope, node);
- avl_rebalance_after_delete(path, p_end);
- return 0;
-}
-
/**
* Traverse left until the left subtree is NULL,
* save the path in iter->path.
@@ -515,7 +253,7 @@ rope_erase(struct rope *rope, rope_size_t offset)
* not-NULL node.
*/
static inline void
-rope_iter_down_to_leaf(struct rope_iter *it)
+avl_iter_down_to_leaf(struct avl_iter *it)
{
while (it->top[0]->link[0] != NULL) {
it->top[1] = it->top[0]->link[0];
@@ -523,24 +261,24 @@ rope_iter_down_to_leaf(struct rope_iter *it)
}
}
-struct rope_node *
-rope_iter_start(struct rope_iter *it)
+struct avl_node *
+avl_iter_start(struct avl_iter *it)
{
it->top = it->path;
it->top[0] = it->rope->root;
if (it->top[0] != NULL)
- rope_iter_down_to_leaf(it);
+ avl_iter_down_to_leaf(it);
return it->top[0];
}
-struct rope_node *
-rope_iter_next(struct rope_iter *it)
+struct avl_node *
+avl_iter_next(struct avl_iter *it)
{
if (it->top[0]->link[1] != NULL) {
it->top[1] = it->top[0]->link[1];
it->top++;
- rope_iter_down_to_leaf(it);
+ avl_iter_down_to_leaf(it);
} else {
/*
* Right subtree is NULL. Left subtree is fully
@@ -569,96 +307,25 @@ rope_iter_next(struct rope_iter *it)
return *it->top;
}
-/** Apply visit_leaf function to every rope leaf. */
void
-rope_traverse(struct rope *rope, void (*visit_leaf)(void *, size_t))
+avl_iter_check(struct avl_iter *iter)
{
- struct rope_iter iter;
- rope_iter_create(&iter, rope);
-
- struct rope_node *leaf;
-
- for (leaf = rope_iter_start(&iter);
- leaf != NULL;
- leaf = rope_iter_next(&iter)) {
-
- visit_leaf(leaf->data, leaf->leaf_size);
- }
-}
-
-void
-rope_check(struct rope *rope)
-{
- struct rope_iter iter;
- rope_iter_create(&iter, rope);
-
- struct rope_node *node;
-
- for (node = rope_iter_start(&iter);
- node != NULL;
- node = rope_iter_next(&iter)) {
+ for (struct avl_node *node = avl_iter_start(iter); node != NULL;
+ node = avl_iter_next(iter)) {
assert(node->leaf_size != 0);
- assert(node->tree_size == rope_node_size(node->link[0])
- + rope_node_size(node->link[1]) + node->leaf_size);
+ assert(node->tree_size == avl_node_size(node->link[0])
+ + avl_node_size(node->link[1]) + node->leaf_size);
- assert(node->height == (MAX(rope_node_height(node->link[0]),
- rope_node_height(node->link[1])) + 1));
+ assert(node->height == (MAX(avl_node_height(node->link[0]),
+ avl_node_height(node->link[1])) + 1));
if (node->leaf_size == 0 ||
- node->tree_size != (rope_node_size(node->link[0]) +
- rope_node_size(node->link[1]) +
+ node->tree_size != (avl_node_size(node->link[0]) +
+ avl_node_size(node->link[1]) +
node->leaf_size) ||
- node->height != MAX(rope_node_height(node->link[0]),
- rope_node_height(node->link[1])) + 1)
+ node->height != MAX(avl_node_height(node->link[0]),
+ avl_node_height(node->link[1])) + 1)
abort();
}
}
-
-static void
-rope_node_print(struct rope_node *node,
- void (*print)(void *, size_t),
- const char *prefix, int dir)
-{
- const char *conn[] = { "┌──", "└──" };
-
- const char *padding[] = { "│ ", " " };
-
- rope_size_t child_prefix_len = strlen(prefix) + strlen(padding[0]) + 1;
- char *child_prefix = malloc(child_prefix_len);
-
- if (node && (node->link[0] || node->link[1])) {
- snprintf(child_prefix, child_prefix_len - 1,
- "%s%s", prefix, padding[!dir]);
- rope_node_print(node->link[0], print, child_prefix, 0);
- }
-
- snprintf(child_prefix, child_prefix_len - 1, "%s%s",
- prefix, padding[dir]);
- printf("%s%s", prefix, conn[dir]);
-
- if (node == NULL) {
- printf("nil\n");
- } else {
-
- printf("{ len = %zu, height = %d, data = '",
- (size_t) node->leaf_size, node->height);
- print(node->data, node->leaf_size);
- printf("'}\n");
-
- if (node->link[0] || node->link[1])
- rope_node_print(node->link[1], print, child_prefix, 1);
- }
-
- free(child_prefix);
-}
-
-void
-rope_pretty_print(struct rope *rope, void (*print_leaf)(void *, size_t))
-{
- printf("size = %zu\nstring = '", (size_t) rope_size(rope));
- rope_traverse(rope, print_leaf);
- printf("'\n");
- rope_node_print(rope->root, print_leaf, "", true);
- printf("\n");
-}
diff --git a/src/lib/salad/rope.h b/src/lib/salad/rope.h
index c19f0e319..f38ac0e79 100644
--- a/src/lib/salad/rope.h
+++ b/src/lib/salad/rope.h
@@ -1,7 +1,5 @@
-#ifndef TARANTOOL_LIB_SALAD_ROPE_H_INCLUDED
-#define TARANTOOL_LIB_SALAD_ROPE_H_INCLUDED
/*
- * Copyright 2010-2016, Tarantool AUTHORS, please see AUTHORS file.
+ * Copyright 2010-2019, Tarantool AUTHORS, please see AUTHORS file.
*
* Redistribution and use in source and binary forms, with or
* without modification, are permitted provided that the following
@@ -30,49 +28,161 @@
* THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*/
+/*
+ * Copyright (c) 1993-1994 by Xerox Corporation. All rights reserved.
+ *
+ * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
+ * OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
+ *
+ * Permission is hereby granted to use or copy this program
+ * for any purpose, provided the above notices are retained on all copies.
+ * Permission to modify the code and to distribute modified code is granted,
+ * provided the above notices are retained, and a notice that the code was
+ * modified is included with the above copyright notice.
+ *
+ * Author: Hans-J. Boehm (boehm@parc.xerox.com)
+ */
+/*
+ * This is a rope implementation which uses AVL tree
+ * balancing algorithm for rope tree balance.
+ */
#include <stdint.h>
-#include <stddef.h>
#include <stdbool.h>
+#include <stdio.h>
+#include <assert.h>
#if defined(__cplusplus)
extern "C" {
#endif /* defined(__cplusplus) */
+#ifndef MAX
+#define NEED_UNDEF_MAX
+#define MAX(a, b) ((a) > (b) ? (a) : (b))
+#endif /* MAX */
+
+/** {{{ AVL private API */
+
+struct avl_node;
+struct avl_iter;
+
+void
+avl_rebalance_after_insert(struct avl_node ***path,
+ struct avl_node ***p_end, int insert_height);
+
+void
+avl_rebalance_after_delete(struct avl_node ***path,
+ struct avl_node ***p_end);
+
+/**
+ * Find a rope node which contains the substring at @a p_offset,
+ * adjusting tree size with @a adjust_size and saving the path in
+ * @a path.
+ * @return The end of the route.
+ */
+struct avl_node ***
+avl_route_to_offset(struct avl_node ***path, uint32_t *p_offset,
+ ssize_t adjust_size);
+
+/**
+ * Route to successor or predecessor node of the node in @a path.
+ * It's either the rightmost leaf of the left child (previous
+ * node) or leftmost leaf of the right child.
+ */
+struct avl_node ***
+avl_route_to_next(struct avl_node ***path, int dir,
+ int32_t adjust_size);
+
+struct avl_node *
+avl_iter_start(struct avl_iter *it);
+
+struct avl_node *
+avl_iter_next(struct avl_iter *it);
+
+void
+avl_iter_check(struct avl_iter *iter);
+
+/** }}} AVL private API */
+
+/**
+ * Needed definitions:
+ *
+ * rope_name, optional
+ * rope_data_t
+ * rope_ctx_t
+ * ROPE_SPLIT_F
+ * ROPE_ALLOC_F
+ * ROPE_FREE_F, optional
+ */
+
+#if defined(ROPE_SRC)
+ #define rope_api(x) avl_##x
+#elif defined(rope_name)
+ #define rope_api(x) rope_##rope_name##_##x
+ #define rope rope_##rope_name
+#else
+ #define rope_api(x) rope_##x
+#endif
+
+#ifndef ROPE_FREE_F
+ #define ROPE_FREE(a, b) do { (void) a; (void) b; } while(0)
+#else
+ #define ROPE_FREE(a, b) ROPE_FREE_F(a, b)
+#endif
+
+#define rope_node rope_api(node)
+#define rope_node_size rope_api(node_size)
+#define rope_leaf_size rope_api(leaf_size)
+#define rope_leaf_data rope_api(leaf_data)
+#define rope_iter rope_api(iter)
+#define rope_create rope_api(create)
+#define rope_new rope_api(new)
+#define rope_size rope_api(size)
+#define rope_clear rope_api(clear)
+#define rope_delete rope_api(delete)
+#define rope_node_new rope_api(node_new)
+#define rope_node_split rope_api(node_split)
+#define rope_insert rope_api(insert)
+#define rope_append rope_api(append)
+#define rope_extract_node rope_api(extract_node)
+#define rope_extract rope_api(extract)
+#define rope_erase rope_api(erase)
+#define rope_iter_create rope_api(iter_create)
+#define rope_iter_new rope_api(iter_new)
+#define rope_iter_start rope_api(iter_start)
+#define rope_iter_next rope_api(iter_next)
+#define rope_iter_delete rope_api(iter_delete)
+#define rope_traverse rope_api(traverse)
+#define rope_check rope_api(check)
+#define rope_node_print rope_api(node_print)
+#define rope_pretty_print rope_api(pretty_print)
+
typedef uint32_t rope_size_t;
typedef int32_t rope_ssize_t;
-typedef void *(*rope_split_func)(void *, void *, size_t, size_t);
-typedef void *(*rope_alloc_func)(void *, size_t);
-typedef void (*rope_free_func)(void *, void *);
/** Tallest allowable tree, 1.44*log(2^32) */
-enum { ROPE_HEIGHT_MAX = 46 };
+#define ROPE_HEIGHT_MAX 46
struct rope_node {
- /** Node height, see rope_node_height(), used for AVL balance. */
+ /**
+ * Node height, see avl_node_height(), used for AVL
+ * balance.
+ */
int height;
/** Subtree size. */
rope_size_t tree_size;
/* Substring size. */
rope_size_t leaf_size;
- /* Substring. */
- void *data;
/* Left (0) and right (1) links */
struct rope_node *link[2];
+ /* Substring. */
+ rope_data_t data;
};
struct rope {
/** Top of the tree */
struct rope_node *root;
- /** Memory management context. */
- void *alloc_ctx;
- /** Get a sequence tail, given offset. */
- rope_split_func split;
- /** Split function context. */
- void *split_ctx;
- /** Allocate memory (context, size). */
- void *(*alloc)(void *, size_t);
- /** Free memory (context, pointer) */
- void (*free)(void *, void *);
+ /** Rope context. */
+ rope_ctx_t ctx;
};
struct rope_iter {
@@ -96,7 +206,7 @@ rope_leaf_size(struct rope_node *node)
return node->leaf_size;
}
-static inline void *
+static inline rope_data_t
rope_leaf_data(struct rope_node *node)
{
return node->data;
@@ -108,78 +218,178 @@ rope_size(struct rope *rope)
return rope_node_size(rope->root);
}
+/**
+ * Everything below is not needed in the rope's own source file,
+ * so it is macrosed out.
+ */
+#ifndef ROPE_SRC
+
/** Initialize an empty rope. */
static inline void
-rope_create(struct rope *rope, rope_split_func split_func, void *split_ctx,
- rope_alloc_func alloc_func, rope_free_func free_func,
- void *alloc_ctx)
+rope_create(struct rope *rope, rope_ctx_t ctx)
{
rope->root = NULL;
- rope->split = split_func;
- rope->split_ctx = split_ctx;
- rope->alloc = alloc_func;
- rope->free = free_func;
- rope->alloc_ctx = alloc_ctx;
+ rope->ctx = ctx;
}
/** Create a new empty rope.
- * @param split_func a function which returns
- * a pointer to substring
- * given an offset. Used
- * to split substrings when
- * inserting into a rope.
- * @param alloc_func used to allocate memory
- * @param free_func used to free memory
* @param alloc_ctx allocator context
*
* @return an empty rope, or NULL if failed
* to allocate memory
*/
static inline struct rope *
-rope_new(rope_split_func split_func, void *split_ctx,
- rope_alloc_func alloc_func, rope_free_func free_func, void *alloc_ctx)
+rope_new(rope_ctx_t ctx)
{
- struct rope *rope= (struct rope *) alloc_func(alloc_ctx,
- sizeof(struct rope));
- if (rope == NULL)
- return NULL;
- rope_create(rope, split_func, split_ctx, alloc_func, free_func, alloc_ctx);
+ struct rope *rope = (struct rope *) ROPE_ALLOC_F(ctx, sizeof(*rope));
+ if (rope != NULL)
+ rope_create(rope, ctx);
return rope;
}
-
/** Delete rope contents. Can also be used
* to free a rope which is allocated on stack.
* Doesn't delete rope substrings, only
* rope nodes.
*/
-void
-rope_clear(struct rope *rope);
+static void
+rope_clear(struct rope *rope)
+{
+#ifdef ROPE_FREE_F
+ struct rope_node *it = rope->root;
+ struct rope_node *save;
+
+ /* Destruction by rotation */
+ while (it != NULL) {
+ if (it->link[0] == NULL) {
+ /* Remove node */
+ save = it->link[1];
+ ROPE_FREE(rope->ctx, it);
+ } else {
+ /* Rotate right */
+ save = it->link[0];
+ it->link[0] = save->link[1];
+ save->link[1] = it;
+ }
+ it = save;
+ }
+#endif /* ROPE_FREE_F */
+ rope->root = NULL;
+}
/** Delete a rope allocated with rope_new() */
static inline void
rope_delete(struct rope *rope)
{
rope_clear(rope);
- rope->free(rope->alloc_ctx, rope);
+ ROPE_FREE(rope->ctx, rope);
+}
+
+static inline struct rope_node *
+rope_node_new(struct rope *rope, rope_data_t data, rope_size_t size)
+{
+ struct rope_node *node =
+ (struct rope_node *) ROPE_ALLOC_F(rope->ctx, sizeof(*node));
+ if (node == NULL)
+ return NULL;
+ node->height = 1;
+ node->tree_size = node->leaf_size = size;
+ node->data = data;
+ node->link[0] = node->link[1] = NULL;
+
+ return node;
+}
+
+static inline struct rope_node *
+rope_node_split(struct rope *rope, struct rope_node *node, rope_size_t offset)
+{
+ rope_size_t old_size = node->leaf_size;
+ node->leaf_size = offset;
+
+ rope_data_t data = ROPE_SPLIT_F(rope->ctx, node->data, old_size,
+ offset);
+
+ return rope_node_new(rope, data, old_size - offset);
}
-/** Insert a substring into a rope at the given
- * offset.
- * If offset is greater than rope size, insertion
- * happens at the end.
+/**
+ * Insert a substring into a rope at the given offset. If offset
+ * is greater than rope size, insertion happens at the end. A new
+ * node is always inserted at a leaf position. If insertion
+ * unbalances the tree, the rebalancing procedure may put the node
+ * into an intermediate position.
+ *
+ * While traversing the tree, we simultaneously update tree sizes
+ * of all intermediate nodes, taking into account the size of the
+ * new node.
+ *
+ * When insertion offset falls at the middle of an existing node,
+ * we truncate this node and attach its tail to the left leaf of
+ * the new node. This trim operation doesn't decrease the old
+ * subtree height, and, while it does change subtree size
+ * temporarily, as long as we attach the new node to the right
+ * subtree of the truncated node, truncation has no effect on the
+ * tree size either.
*
- * @retval 0 success
- * @retval -1 failed to allocate memory for a new
- * tree node
+ * Rebalancing, when it occurs, will correctly update subtree
+ * heights and sizes of all modified nodes.
+ *
+ * @retval 0 Success.
+ * @retval -1 Memory error.
*/
-int
-rope_insert(struct rope *rope, rope_size_t offset, void *data,
- rope_size_t size);
+static int
+rope_insert(struct rope *rope, rope_size_t offset, rope_data_t data,
+ rope_size_t size)
+{
+ if (offset > rope_size(rope))
+ offset = rope_size(rope);
+
+ assert(size);
+
+ struct rope_node *new_node = rope_node_new(rope, data, size);
+
+ if (new_node == NULL)
+ return -1;
+
+ struct rope_node **path[ROPE_HEIGHT_MAX];
+ path[0] = &rope->root;
+
+ struct rope_node ***p_end = (struct rope_node ***)
+ avl_route_to_offset((struct avl_node ***) path, &offset, size);
+ if (**p_end != NULL) {
+ /*
+ * The offset is inside an existing
+ * substring in the rope. If offset is 0,
+ * then insert the new node at the rightmost leaf
+ * of the left child. Otherwise, cut the tail of
+ * the substring, make it a prefix of the inserted
+ * string, and insert the result at the leftmost
+ * leaf of the right child.
+ */
+ if (offset != 0) {
+ struct rope_node *split_node;
+ split_node = rope_node_split(rope, **p_end, offset);
+ if (split_node == NULL)
+ return -1;
+ split_node->link[0] = new_node;
+ split_node->height++;
+ split_node->tree_size += new_node->tree_size;
+ new_node = split_node;
+ }
+ p_end = (struct rope_node ***)
+ avl_route_to_next((struct avl_node ***) p_end,
+ offset != 0, new_node->tree_size);
+ }
+ **p_end = new_node;
+ avl_rebalance_after_insert((struct avl_node ***) path,
+ (struct avl_node ***) p_end,
+ new_node->height);
+ return 0;
+}
/** Append a substring at rope tail. */
static inline int
-rope_append(struct rope *rope, void *data, size_t size)
+rope_append(struct rope *rope, rope_data_t data, size_t size)
{
return rope_insert(rope, rope_size(rope), data, size);
}
@@ -191,23 +401,149 @@ rope_append(struct rope *rope, void *data, size_t size)
* @retval NULL failed to allocate memory for a new
* tree node
*/
-struct rope_node *
-rope_extract_node(struct rope *rope, rope_size_t offset);
+static struct rope_node *
+rope_extract_node(struct rope *rope, rope_size_t offset)
+{
+ assert(offset < rope_size(rope));
+
+ struct rope_node **path[ROPE_HEIGHT_MAX];
+ path[0] = &rope->root;
-static inline void *
+ struct rope_node ***p_end = (struct rope_node ***)
+ avl_route_to_offset((struct avl_node ***) path, &offset, 0);
+ if (offset == 0)
+ return **p_end;
+ struct rope_node *new_node = rope_node_split(rope, **p_end, offset);
+ if (new_node == NULL)
+ return NULL;
+ p_end = (struct rope_node ***)
+ avl_route_to_next((struct avl_node ***) p_end, 1,
+ new_node->tree_size);
+ **p_end = new_node;
+ avl_rebalance_after_insert((struct avl_node ***) path,
+ (struct avl_node ***) p_end,
+ new_node->height);
+ return new_node;
+}
+
+static inline rope_data_t
rope_extract(struct rope *rope, rope_size_t offset)
{
return rope_leaf_data(rope_extract_node(rope, offset));
}
/**
- * Erase a single element from a rope at the given
- * offset.
+ * Erase a single element from the rope. This is a straightforward
+ * implementation for a single-element deletion from a rope. A
+ * generic cut from a rope involves 2 tree splits and one merge.
+ *
+ * When deleting a single element, 3 cases are possible:
+ * - offset falls at a node with a single element. In this case we
+ * perform a normal AVL tree delete.
+ * - offset falls at the end or the beginning of an existing node
+ * with leaf_size > 1. In that case we trim the existing node
+ * and return.
+ * - offset falls inside an existing node. In that case we split
+ * the existing node at offset, and insert the tail.
*
- * @pre offset < rope_size(rope)
+ * The implementation is a copycat of rope_insert(). If you're
+ * trying to understand the code, it's recommended to start from
+ * rope_insert().
*/
-int
-rope_erase(struct rope *rope, rope_size_t offset);
+static inline int
+rope_erase(struct rope *rope, rope_size_t offset)
+{
+ assert(offset < rope_size(rope));
+
+ struct rope_node **path[ROPE_HEIGHT_MAX];
+ path[0] = &rope->root;
+
+ struct rope_node ***p_end = (struct rope_node ***)
+ avl_route_to_offset((struct avl_node ***) path, &offset, -1);
+
+ struct rope_node *node = **p_end;
+
+ if (node->leaf_size > 1) {
+ /* Check if we can simply trim the node. */
+ if (offset == 0) {
+ /* Cut the head. */
+ node->data = ROPE_SPLIT_F(rope->ctx, node->data,
+ node->leaf_size, 1);
+ node->leaf_size -= 1;
+ return 0;
+ }
+ rope_size_t size = node->leaf_size;
+ /* Cut the tail */
+ rope_data_t next = ROPE_SPLIT_F(rope->ctx, node->data,
+ node->leaf_size, offset);
+ node->leaf_size = offset;
+ if (offset == size - 1)
+ return 0; /* Trimmed the tail, nothing else to do */
+ /*
+ * Offset falls inside a substring. Erase the
+ * first field and insert the tail.
+ */
+ next = ROPE_SPLIT_F(rope->ctx, next, size - offset, 1);
+ struct rope_node *new_node =
+ rope_node_new(rope, next, size - offset - 1);
+ if (new_node == NULL)
+ return -1;
+ /* Trim the old node. */
+ p_end = (struct rope_node ***)
+ avl_route_to_next((struct avl_node ***) p_end, 1,
+ new_node->tree_size);
+ **p_end = new_node;
+ avl_rebalance_after_insert((struct avl_node ***) path,
+ (struct avl_node ***) p_end,
+ new_node->height);
+ return 0;
+ }
+ /* We need to delete the node. */
+ assert(offset == 0);
+ int direction;
+ if (node->link[0] != NULL && node->link[1] != NULL) {
+ /*
+ * The node has two non-NULL leaves. We can't
+ * simply delete the node since in that case we
+ * won't know what to do with one of the leaves.
+ * Instead of deleting the node, store in it data
+ * from the rightmost node in the left subtree, or
+ * the leftmost node in the right subtree,
+ * (depending on which subtree is taller), and
+ * delete this leftmost/rightmost node instead.
+ */
+ struct rope_node *save = node;
+ direction = node->link[1]->height > node->link[0]->height;
+ p_end = (struct rope_node ***)
+ avl_route_to_next((struct avl_node ***) p_end,
+ direction, 0) - 1;
+ node = **p_end;
+ /* Move the data pointers. */
+ save->data = node->data;
+ save->leaf_size = node->leaf_size;
+ /*
+ * Now follow the path again and update tree_size
+ * in the parents of the moved child.
+ */
+ save = save->link[direction];
+ while (save != node) {
+ save->tree_size -= node->leaf_size;
+ save = save->link[!direction];
+ }
+ } else {
+ /*
+ * Left or right subtree are NULL, so we
+ * can simply put the non-NULL leaf in place
+ * of the parent.
+ */
+ direction = node->link[0] == NULL;
+ }
+ **p_end = node->link[direction];
+ ROPE_FREE(rope->ctx, node);
+ avl_rebalance_after_delete((struct avl_node ***) path,
+ (struct avl_node ***) p_end);
+ return 0;
+}
/** Initialize an iterator. */
static inline void
@@ -220,12 +556,10 @@ rope_iter_create(struct rope_iter *it, struct rope *rope)
static inline struct rope_iter *
rope_iter_new(struct rope *rope)
{
- struct rope_iter *it = (struct rope_iter *)
- rope->alloc(rope->alloc_ctx, sizeof(struct rope_iter));
-
- if (it == NULL)
- return NULL;
- rope_iter_create(it, rope);
+ struct rope_iter *it =
+ (struct rope_iter *) ROPE_ALLOC_F(rope->ctx, sizeof(*it));
+ if (it != NULL)
+ rope_iter_create(it, rope);
return it;
}
@@ -233,8 +567,11 @@ rope_iter_new(struct rope *rope)
* Begin iteration.
* @retval NULL the rope is empty
*/
-struct rope_node *
-rope_iter_start(struct rope_iter *it);
+static inline struct rope_node *
+rope_iter_start(struct rope_iter *it)
+{
+ return (struct rope_node *) avl_iter_start((struct avl_iter *) it);
+}
/**
* Advance to the next rope node.
@@ -243,30 +580,138 @@ rope_iter_start(struct rope_iter *it);
* has advanced beyond the last
* node.
*/
-struct rope_node *
-rope_iter_next(struct rope_iter *it);
+static struct rope_node *
+rope_iter_next(struct rope_iter *it)
+{
+ return (struct rope_node *) avl_iter_next((struct avl_iter *) it);
+}
/** Free iterator. */
static inline void
rope_iter_delete(struct rope_iter *it)
{
- it->rope->free(it->rope->alloc_ctx, it);
+ ROPE_FREE(it->rope->ctx, it);
}
/** Apply visit_leaf function to every rope leaf. */
-void
-rope_traverse(struct rope *rope, void (*visit_leaf)(void *, size_t));
+static void
+rope_traverse(struct rope *rope, void (*visit_leaf)(rope_data_t, size_t))
+{
+ struct rope_iter iter;
+ rope_iter_create(&iter, rope);
+
+ struct rope_node *leaf;
+
+ for (leaf = rope_iter_start(&iter);
+ leaf != NULL;
+ leaf = rope_iter_next(&iter)) {
+
+ visit_leaf(leaf->data, leaf->leaf_size);
+ }
+}
/** Check AVL tree consistency. */
-void
-rope_check(struct rope *rope);
+static inline void
+rope_check(struct rope *rope)
+{
+ struct rope_iter iter;
+ rope_iter_create(&iter, rope);
+ avl_iter_check((struct avl_iter *) &iter);
+}
+
+static void
+rope_node_print(struct rope_node *node, void (*print)(rope_data_t, size_t),
+ const char *prefix, int dir)
+{
+ const char *conn[] = { "┌──", "└──" };
+
+ const char *padding[] = { "│ ", " " };
+
+ rope_size_t child_prefix_len = strlen(prefix) + strlen(padding[0]) + 1;
+ char *child_prefix = malloc(child_prefix_len);
+
+ if (node && (node->link[0] || node->link[1])) {
+ snprintf(child_prefix, child_prefix_len - 1,
+ "%s%s", prefix, padding[!dir]);
+ rope_node_print(node->link[0], print, child_prefix, 0);
+ }
+
+ snprintf(child_prefix, child_prefix_len - 1, "%s%s",
+ prefix, padding[dir]);
+ printf("%s%s", prefix, conn[dir]);
+
+ if (node == NULL) {
+ printf("nil\n");
+ } else {
+
+ printf("{ len = %zu, height = %d, data = '",
+ (size_t) node->leaf_size, node->height);
+ print(node->data, node->leaf_size);
+ printf("'}\n");
+
+ if (node->link[0] || node->link[1])
+ rope_node_print(node->link[1], print, child_prefix, 1);
+ }
+
+ free(child_prefix);
+}
/** Pretty print a rope. */
-void
-rope_pretty_print(struct rope *rope, void (*print_leaf)(void *, size_t));
+static inline void
+rope_pretty_print(struct rope *rope, void (*print_leaf)(rope_data_t, size_t))
+{
+ printf("size = %zu\nstring = '", (size_t) rope_size(rope));
+ rope_traverse(rope, print_leaf);
+ printf("'\n");
+ rope_node_print(rope->root, print_leaf, "", true);
+ printf("\n");
+}
+
+#ifdef NEED_UNDEF_MAX
+#undef NEED_UNDEF_MAX
+#undef MAX
+#endif
+
+#endif /* ROPE_SRC */
+
+#undef rope_node
+#undef rope_node_size
+#undef rope_leaf_size
+#undef rope_leaf_data
+#undef rope_iter
+#undef rope_create
+#undef rope_new
+#undef rope_size
+#undef rope_clear
+#undef rope_delete
+#undef rope_node_new
+#undef rope_node_split
+#undef rope_insert
+#undef rope_append
+#undef rope_extract_node
+#undef rope_extract
+#undef rope_erase
+#undef rope_iter_create
+#undef rope_iter_new
+#undef rope_iter_start
+#undef rope_iter_next
+#undef rope_iter_delete
+#undef rope_traverse
+#undef rope_check
+#undef rope_node_print
+#undef rope_pretty_print
+
+#undef rope
+#undef rope_api
+#undef rope_name
+#undef ROPE_HEIGHT_MAX
+#undef rope_ctx_t
+#undef rope_data_t
+#undef ROPE_SPLIT_F
+#undef ROPE_ALLOC_F
+#undef ROPE_FREE_F
+#undef ROPE_FREE
#if defined(__cplusplus)
}
#endif /* defined(__cplusplus) */
-
-#endif /* TARANTOOL_LIB_SALAD_ROPE_H_INCLUDED */
diff --git a/test/unit/rope.c b/test/unit/rope.c
index e19dcaa10..5ab4c51f7 100644
--- a/test/unit/rope.c
+++ b/test/unit/rope.c
@@ -1,4 +1,3 @@
-#include "salad/rope.h"
#include "unit.h"
#include "rope_common.h"
diff --git a/test/unit/rope_avl.c b/test/unit/rope_avl.c
index 9e978f46c..b095fb1a6 100644
--- a/test/unit/rope_avl.c
+++ b/test/unit/rope_avl.c
@@ -1,4 +1,3 @@
-#include "salad/rope.h"
#include "unit.h"
#include "rope_common.h"
diff --git a/test/unit/rope_basic.c b/test/unit/rope_basic.c
index b4a0e7876..d9e116292 100644
--- a/test/unit/rope_basic.c
+++ b/test/unit/rope_basic.c
@@ -1,4 +1,3 @@
-#include "salad/rope.h"
#include "unit.h"
#include "rope_common.h"
diff --git a/test/unit/rope_common.h b/test/unit/rope_common.h
index 6c52153b2..3392e87e3 100644
--- a/test/unit/rope_common.h
+++ b/test/unit/rope_common.h
@@ -3,17 +3,17 @@
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
-static inline void *
-str_getn(void *ctx, void *data, size_t size, size_t offset)
+static inline char *
+str_getn(void *ctx, char *data, size_t size, size_t offset)
{
(void) ctx;
- return (char *) data + offset;
+ return data + offset;
}
static inline void
-str_print(void *data, size_t n)
+str_print(char *data, size_t n)
{
- printf("%.*s", (int) n, (char *) data);
+ printf("%.*s", (int) n, data);
}
static inline void *
@@ -30,10 +30,39 @@ mem_free(void *data, void *ptr)
free(ptr);
}
+#define ROPE_ALLOC_F mem_alloc
+#define ROPE_FREE_F mem_free
+#define ROPE_SPLIT_F str_getn
+#define rope_data_t char *
+#define rope_ctx_t void *
+
+#include "salad/rope.h"
+
+/**
+ * Define a second rope just to check if compilation of two
+ * ropes in one object file works.
+ */
+
+static inline int *
+str_getn2(int *ctx, int *data, size_t size, size_t offset)
+{
+ (void) ctx;
+ return data + offset;
+}
+
+#define rope_name second
+#define ROPE_ALLOC_F mem_alloc
+#define ROPE_FREE_F mem_free
+#define ROPE_SPLIT_F str_getn2
+#define rope_data_t int *
+#define rope_ctx_t int *
+
+#include "salad/rope.h"
+
static inline struct rope *
test_rope_new()
{
- return rope_new(str_getn, NULL, mem_alloc, mem_free, NULL);
+ return rope_new(NULL);
}
static inline void
diff --git a/test/unit/rope_stress.c b/test/unit/rope_stress.c
index dc3f2817e..bc312d7c0 100644
--- a/test/unit/rope_stress.c
+++ b/test/unit/rope_stress.c
@@ -1,4 +1,3 @@
-#include "salad/rope.h"
#include <time.h>
#include "unit.h"
#include "rope_common.h"
@@ -10,7 +9,7 @@ test_rope_stress_small()
{
header();
- struct rope *rope = rope_new(str_getn, NULL, mem_alloc, mem_free, NULL);
+ struct rope *rope = test_rope_new();
const int iterations = 500;
int i = 0;
for (i = 0; i < iterations; ++i) {
@@ -39,7 +38,7 @@ test_rope_stress_large()
{
header();
- struct rope *rope = rope_new(str_getn, NULL, mem_alloc, mem_free, NULL);
+ struct rope *rope = test_rope_new();
const int iterations = 50000;
int i = 0;
for (i = 0; i < iterations; ++i) {
--
2.20.1 (Apple Git-117)
^ permalink raw reply [flat|nested] 10+ messages in thread
* [PATCH 3/5] tuple: relax struct tuple_update dependency on rope
2019-07-13 22:11 [PATCH 0/5] JSON update preparation Vladislav Shpilevoy
2019-07-13 22:11 ` [PATCH 1/5] tuple: remove alloc and alloc_ctx args from update() Vladislav Shpilevoy
2019-07-13 22:11 ` [PATCH 2/5] rope: make rope library macro template Vladislav Shpilevoy
@ 2019-07-13 22:11 ` Vladislav Shpilevoy
2019-07-13 22:11 ` [PATCH 4/5] int96: add a missing header Vladislav Shpilevoy
` (4 subsequent siblings)
7 siblings, 0 replies; 10+ messages in thread
From: Vladislav Shpilevoy @ 2019-07-13 22:11 UTC (permalink / raw)
To: tarantool-patches; +Cc: vdavydov.dev
Rope will not be used by tuple_update directly in
next patches.
---
src/box/tuple_update.c | 34 ++++++++++++++++++----------------
1 file changed, 18 insertions(+), 16 deletions(-)
diff --git a/src/box/tuple_update.c b/src/box/tuple_update.c
index 7498d558a..21ea876c9 100644
--- a/src/box/tuple_update.c
+++ b/src/box/tuple_update.c
@@ -820,31 +820,29 @@ update_field_split(struct region *region, struct update_field *prev,
* @retval 0 Success.
* @retval -1 Error.
*/
-int
-update_create_rope(struct tuple_update *update, const char *tuple_data,
- const char *tuple_data_end, uint32_t field_count)
+struct rope *
+tuple_rope_new(struct region *region, const char *tuple_data,
+ const char *tuple_data_end, uint32_t field_count)
{
- update->rope = rope_new(update->region);
- if (update->rope == NULL)
- return -1;
+ struct rope *rope = rope_new(region);
+ if (rope == NULL)
+ return NULL;
/* Initialize the rope with the old tuple. */
-
- struct update_field *first = (struct update_field *)
- update_alloc(update->region, sizeof(*first));
+ struct update_field *first =
+ (struct update_field *) update_alloc(region, sizeof(*first));
if (first == NULL)
- return -1;
+ return NULL;
const char *field = tuple_data;
const char *end = tuple_data_end;
if (field == end)
- return 0;
+ return rope;
/* Add first field to rope */
mp_next(&tuple_data);
uint32_t field_len = tuple_data - field;
- update_field_init(first, field, field_len,
- end - field - field_len);
+ update_field_init(first, field, field_len, end - field - field_len);
- return rope_append(update->rope, first, field_count);
+ return rope_append(rope, first, field_count) != 0 ? NULL : rope;
}
static uint32_t
@@ -1119,7 +1117,9 @@ static int
update_do_ops(struct tuple_update *update, const char *old_data,
const char *old_data_end, uint32_t part_count)
{
- if (update_create_rope(update, old_data, old_data_end, part_count) != 0)
+ update->rope = tuple_rope_new(update->region, old_data, old_data_end,
+ part_count);
+ if (update->rope == NULL)
return -1;
struct update_op *op = update->ops;
struct update_op *ops_end = op + update->op_count;
@@ -1140,7 +1140,9 @@ upsert_do_ops(struct tuple_update *update, const char *old_data,
const char *old_data_end, uint32_t part_count,
bool suppress_error)
{
- if (update_create_rope(update, old_data, old_data_end, part_count) != 0)
+ update->rope = tuple_rope_new(update->region, old_data, old_data_end,
+ part_count);
+ if (update->rope == NULL)
return -1;
struct update_op *op = update->ops;
struct update_op *ops_end = op + update->op_count;
--
2.20.1 (Apple Git-117)
^ permalink raw reply [flat|nested] 10+ messages in thread
* [PATCH 4/5] int96: add a missing header
2019-07-13 22:11 [PATCH 0/5] JSON update preparation Vladislav Shpilevoy
` (2 preceding siblings ...)
2019-07-13 22:11 ` [PATCH 3/5] tuple: relax struct tuple_update dependency on rope Vladislav Shpilevoy
@ 2019-07-13 22:11 ` Vladislav Shpilevoy
2019-07-13 22:11 ` [PATCH 5/5] tuple: implement update by field name Vladislav Shpilevoy
` (3 subsequent siblings)
7 siblings, 0 replies; 10+ messages in thread
From: Vladislav Shpilevoy @ 2019-07-13 22:11 UTC (permalink / raw)
To: tarantool-patches; +Cc: vdavydov.dev
---
src/lib/bit/int96.h | 1 +
1 file changed, 1 insertion(+)
diff --git a/src/lib/bit/int96.h b/src/lib/bit/int96.h
index f615e2fe9..cdde0e995 100644
--- a/src/lib/bit/int96.h
+++ b/src/lib/bit/int96.h
@@ -33,6 +33,7 @@
#include <inttypes.h>
#include <assert.h>
+#include <stdbool.h>
/**
* 96-bit signed integer.
--
2.20.1 (Apple Git-117)
^ permalink raw reply [flat|nested] 10+ messages in thread
* [PATCH 5/5] tuple: implement update by field name
2019-07-13 22:11 [PATCH 0/5] JSON update preparation Vladislav Shpilevoy
` (3 preceding siblings ...)
2019-07-13 22:11 ` [PATCH 4/5] int96: add a missing header Vladislav Shpilevoy
@ 2019-07-13 22:11 ` Vladislav Shpilevoy
2019-07-31 12:15 ` [PATCH 0/5] JSON update preparation Vladimir Davydov
` (2 subsequent siblings)
7 siblings, 0 replies; 10+ messages in thread
From: Vladislav Shpilevoy @ 2019-07-13 22:11 UTC (permalink / raw)
To: tarantool-patches; +Cc: vdavydov.dev
Tuple fields can be named, accessed by name, indexed by name, but
till this commit field names couldn't be used in update
operations. Now it is possible.
This patch is a teaser of updates by JSON path.
Part of #1261
---
src/box/errcode.h | 4 +-
src/box/lua/tuple.c | 5 +-
src/box/memtx_space.c | 17 ++--
src/box/space.c | 9 ++-
src/box/sql/insert.c | 3 +-
src/box/sql/resolve.c | 4 +-
src/box/sql/update.c | 2 +-
src/box/tuple.c | 12 +--
src/box/tuple_update.c | 152 ++++++++++++++++++++++--------------
src/box/tuple_update.h | 15 ++--
src/box/vinyl.c | 9 ++-
src/box/vy_upsert.c | 6 +-
test/box/misc.result | 3 +-
test/box/update.result | 2 +-
test/engine/update.result | 67 ++++++++++++++++
test/engine/update.test.lua | 28 +++++++
test/engine/upsert.result | 2 +-
test/unit/column_mask.c | 5 +-
18 files changed, 247 insertions(+), 98 deletions(-)
diff --git a/src/box/errcode.h b/src/box/errcode.h
index be8dab27d..ccbc43b02 100644
--- a/src/box/errcode.h
+++ b/src/box/errcode.h
@@ -205,14 +205,14 @@ struct errcode_record {
/*150 */_(ER_CANT_CREATE_COLLATION, "Failed to initialize collation: %s.") \
/*151 */_(ER_WRONG_COLLATION_OPTIONS, "Wrong collation options (field %u): %s") \
/*152 */_(ER_NULLABLE_PRIMARY, "Primary index of the space '%s' can not contain nullable parts") \
- /*153 */_(ER_NO_SUCH_FIELD_NAME, "Field '%s' was not found in the space '%s' format") \
+ /*153 */_(ER_NO_SUCH_FIELD_NAME_IN_SPACE, "Field '%s' was not found in the space '%s' format") \
/*154 */_(ER_TRANSACTION_YIELD, "Transaction has been aborted by a fiber yield") \
/*155 */_(ER_NO_SUCH_GROUP, "Replication group '%s' does not exist") \
/*156 */_(ER_SQL_BIND_VALUE, "Bind value for parameter %s is out of range for type %s") \
/*157 */_(ER_SQL_BIND_TYPE, "Bind value type %s for parameter %s is not supported") \
/*158 */_(ER_SQL_BIND_PARAMETER_MAX, "SQL bind parameter limit reached: %d") \
/*159 */_(ER_SQL_EXECUTE, "Failed to execute SQL statement: %s") \
- /*160 */_(ER_UNUSED, "") \
+ /*160 */_(ER_NO_SUCH_FIELD_NAME, "Field '%s' was not found in the tuple") \
/*161 */_(ER_SQL_BIND_NOT_FOUND, "Parameter %s was not found in the statement") \
/*162 */_(ER_ACTION_MISMATCH, "Field %s contains %s on conflict action, but %s in index parts") \
/*163 */_(ER_VIEW_MISSING_SQL, "Space declared as a view must have SQL statement") \
diff --git a/src/box/lua/tuple.c b/src/box/lua/tuple.c
index 2fbfb1473..3902288bf 100644
--- a/src/box/lua/tuple.c
+++ b/src/box/lua/tuple.c
@@ -439,6 +439,7 @@ lbox_tuple_transform(struct lua_State *L)
const char *old_data = tuple_data_range(tuple, &bsize);
struct region *region = &fiber()->gc;
size_t used = region_used(region);
+ struct tuple_format *format = tuple_format(tuple);
struct tuple *new_tuple = NULL;
/*
* Can't use box_tuple_update() since transform must reset
@@ -449,8 +450,8 @@ lbox_tuple_transform(struct lua_State *L)
*/
const char *new_data =
tuple_update_execute(buf->buf, buf->buf + ibuf_used(buf),
- old_data, old_data + bsize, &new_size, 1,
- NULL);
+ old_data, old_data + bsize, format->dict,
+ &new_size, 1, NULL);
if (new_data != NULL)
new_tuple = tuple_new(box_tuple_format_default(),
new_data, new_data + new_size);
diff --git a/src/box/memtx_space.c b/src/box/memtx_space.c
index 54b379c43..d6286924e 100644
--- a/src/box/memtx_space.c
+++ b/src/box/memtx_space.c
@@ -417,15 +417,16 @@ memtx_space_execute_update(struct space *space, struct txn *txn,
/* Update the tuple; legacy, request ops are in request->tuple */
uint32_t new_size = 0, bsize;
+ struct tuple_format *format = space->format;
const char *old_data = tuple_data_range(old_tuple, &bsize);
const char *new_data =
tuple_update_execute(request->tuple, request->tuple_end,
- old_data, old_data + bsize,
+ old_data, old_data + bsize, format->dict,
&new_size, request->index_base, NULL);
if (new_data == NULL)
return -1;
- stmt->new_tuple = memtx_tuple_new(space->format, new_data,
+ stmt->new_tuple = memtx_tuple_new(format, new_data,
new_data + new_size);
if (stmt->new_tuple == NULL)
return -1;
@@ -471,6 +472,7 @@ memtx_space_execute_upsert(struct space *space, struct txn *txn,
if (index_get(index, key, part_count, &old_tuple) != 0)
return -1;
+ struct tuple_format *format = space->format;
if (old_tuple == NULL) {
/**
* Old tuple was not found. A write optimized
@@ -489,11 +491,11 @@ memtx_space_execute_upsert(struct space *space, struct txn *txn,
* @sa https://github.com/tarantool/tarantool/issues/1156
*/
if (tuple_update_check_ops(request->ops, request->ops_end,
+ format->dict,
request->index_base) != 0) {
return -1;
}
- stmt->new_tuple = memtx_tuple_new(space->format,
- request->tuple,
+ stmt->new_tuple = memtx_tuple_new(format, request->tuple,
request->tuple_end);
if (stmt->new_tuple == NULL)
return -1;
@@ -511,12 +513,13 @@ memtx_space_execute_upsert(struct space *space, struct txn *txn,
const char *new_data =
tuple_upsert_execute(request->ops, request->ops_end,
old_data, old_data + bsize,
- &new_size, request->index_base,
- false, &column_mask);
+ format->dict, &new_size,
+ request->index_base, false,
+ &column_mask);
if (new_data == NULL)
return -1;
- stmt->new_tuple = memtx_tuple_new(space->format, new_data,
+ stmt->new_tuple = memtx_tuple_new(format, new_data,
new_data + new_size);
if (stmt->new_tuple == NULL)
return -1;
diff --git a/src/box/space.c b/src/box/space.c
index e881aaf32..d4ac90ad9 100644
--- a/src/box/space.c
+++ b/src/box/space.c
@@ -359,7 +359,8 @@ space_before_replace(struct space *space, struct txn *txn,
old_data_end = old_data + old_size;
new_data = tuple_update_execute(request->tuple,
request->tuple_end, old_data,
- old_data_end, &new_size,
+ old_data_end,
+ space->format->dict, &new_size,
request->index_base, NULL);
if (new_data == NULL)
return -1;
@@ -382,6 +383,7 @@ space_before_replace(struct space *space, struct txn *txn,
new_data_end = request->tuple_end;
if (tuple_update_check_ops(request->ops,
request->ops_end,
+ space->format->dict,
request->index_base) != 0)
return -1;
break;
@@ -390,8 +392,9 @@ space_before_replace(struct space *space, struct txn *txn,
old_data_end = old_data + old_size;
new_data = tuple_upsert_execute(request->ops, request->ops_end,
old_data, old_data_end,
- &new_size, request->index_base,
- false, NULL);
+ space->format->dict, &new_size,
+ request->index_base, false,
+ NULL);
new_data_end = new_data + new_size;
break;
default:
diff --git a/src/box/sql/insert.c b/src/box/sql/insert.c
index b35314855..c8ad2f7f7 100644
--- a/src/box/sql/insert.c
+++ b/src/box/sql/insert.c
@@ -373,7 +373,8 @@ sqlInsert(Parse * pParse, /* Parser context */
}
}
if (j >= (int) space_def->field_count) {
- diag_set(ClientError, ER_NO_SUCH_FIELD_NAME,
+ diag_set(ClientError,
+ ER_NO_SUCH_FIELD_NAME_IN_SPACE,
pColumn->a[i].zName,
pTabList->a[0].zName);
pParse->is_aborted = true;
diff --git a/src/box/sql/resolve.c b/src/box/sql/resolve.c
index 0b90edd06..bb2e94e9e 100644
--- a/src/box/sql/resolve.c
+++ b/src/box/sql/resolve.c
@@ -431,8 +431,8 @@ lookupName(Parse * pParse, /* The parsing context */
if (zTab == NULL) {
diag_set(ClientError, ER_SQL_CANT_RESOLVE_FIELD, zCol);
} else {
- diag_set(ClientError, ER_NO_SUCH_FIELD_NAME, zCol,
- zTab);
+ diag_set(ClientError, ER_NO_SUCH_FIELD_NAME_IN_SPACE,
+ zCol, zTab);
}
pParse->is_aborted = true;
pTopNC->nErr++;
diff --git a/src/box/sql/update.c b/src/box/sql/update.c
index d77bee051..e9262de2e 100644
--- a/src/box/sql/update.c
+++ b/src/box/sql/update.c
@@ -192,7 +192,7 @@ sqlUpdate(Parse * pParse, /* The parser context */
}
}
if (j >= (int)def->field_count) {
- diag_set(ClientError, ER_NO_SUCH_FIELD_NAME,
+ diag_set(ClientError, ER_NO_SUCH_FIELD_NAME_IN_SPACE,
pChanges->a[i].zName, def->name);
pParse->is_aborted = true;
goto update_cleanup;
diff --git a/src/box/tuple.c b/src/box/tuple.c
index 1e5b2fb24..f1225d3d5 100644
--- a/src/box/tuple.c
+++ b/src/box/tuple.c
@@ -705,15 +705,15 @@ box_tuple_update(box_tuple_t *tuple, const char *expr, const char *expr_end)
const char *old_data = tuple_data_range(tuple, &bsize);
struct region *region = &fiber()->gc;
size_t used = region_used(region);
+ struct tuple_format *format = tuple_format(tuple);
const char *new_data =
tuple_update_execute(expr, expr_end, old_data, old_data + bsize,
- &new_size, 1, NULL);
+ format->dict, &new_size, 1, NULL);
if (new_data == NULL) {
region_truncate(region, used);
return NULL;
}
- struct tuple *ret = tuple_new(tuple_format(tuple), new_data,
- new_data + new_size);
+ struct tuple *ret = tuple_new(format, new_data, new_data + new_size);
region_truncate(region, used);
if (ret != NULL)
return tuple_bless(ret);
@@ -727,16 +727,16 @@ box_tuple_upsert(box_tuple_t *tuple, const char *expr, const char *expr_end)
const char *old_data = tuple_data_range(tuple, &bsize);
struct region *region = &fiber()->gc;
size_t used = region_used(region);
+ struct tuple_format *format = tuple_format(tuple);
const char *new_data =
tuple_upsert_execute(expr, expr_end, old_data, old_data + bsize,
- &new_size, 1, false, NULL);
+ format->dict, &new_size, 1, false, NULL);
if (new_data == NULL) {
region_truncate(region, used);
return NULL;
}
- struct tuple *ret = tuple_new(tuple_format(tuple),
- new_data, new_data + new_size);
+ struct tuple *ret = tuple_new(format, new_data, new_data + new_size);
region_truncate(region, used);
if (ret != NULL)
return tuple_bless(ret);
diff --git a/src/box/tuple_update.c b/src/box/tuple_update.c
index 21ea876c9..34e0e767f 100644
--- a/src/box/tuple_update.c
+++ b/src/box/tuple_update.c
@@ -41,6 +41,8 @@
#include <bit/int96.h>
#include "column_mask.h"
#include "fiber.h"
+#include "tuple_dictionary.h"
+#include "tt_static.h"
/** UPDATE request implementation.
* UPDATE request is represented by a sequence of operations, each
@@ -929,12 +931,87 @@ update_op_by(char opcode)
}
}
+/**
+ * Decode an update operation from MessagePack.
+ * @param[out] op Update operation.
+ * @param index_base Field numbers base: 0 or 1.
+ * @param dict Dictionary to lookup field number by a name.
+ * @param expr MessagePack.
+ *
+ * @retval 0 Success.
+ * @retval -1 Client error.
+ */
+static inline int
+update_op_decode(struct update_op *op, int index_base,
+ struct tuple_dictionary *dict, const char **expr)
+{
+ if (mp_typeof(**expr) != MP_ARRAY) {
+ diag_set(ClientError, ER_ILLEGAL_PARAMS, "update operation "
+ "must be an array {op,..}");
+ return -1;
+ }
+ uint32_t len, args = mp_decode_array(expr);
+ if (args < 1) {
+ diag_set(ClientError, ER_ILLEGAL_PARAMS, "update operation "\
+ "must be an array {op,..}, got empty array");
+ return -1;
+ }
+ if (mp_typeof(**expr) != MP_STR) {
+ diag_set(ClientError, ER_ILLEGAL_PARAMS,
+ "update operation name must be a string");
+ return -1;
+ }
+ op->opcode = *mp_decode_str(expr, &len);
+ op->meta = update_op_by(op->opcode);
+ if (op->meta == NULL)
+ return -1;
+ if (args != op->meta->args) {
+ diag_set(ClientError, ER_UNKNOWN_UPDATE_OP);
+ return -1;
+ }
+ int32_t field_no;
+ switch(mp_typeof(**expr)) {
+ case MP_INT:
+ case MP_UINT: {
+ if (mp_read_i32(index_base, op, expr, &field_no) != 0)
+ return -1;
+ if (field_no - index_base >= 0) {
+ op->field_no = field_no - index_base;
+ } else if (field_no < 0) {
+ op->field_no = field_no;
+ } else {
+ diag_set(ClientError, ER_NO_SUCH_FIELD_NO, field_no);
+ return -1;
+ }
+ break;
+ }
+ case MP_STR: {
+ const char *path = mp_decode_str(expr, &len);
+ uint32_t field_no, hash = field_name_hash(path, len);
+ if (tuple_fieldno_by_name(dict, path, len, hash,
+ &field_no) != 0) {
+ diag_set(ClientError, ER_NO_SUCH_FIELD_NAME,
+ tt_cstr(path, len));
+ return -1;
+ }
+ op->field_no = (int32_t) field_no;
+ break;
+ }
+ default:
+ diag_set(ClientError, ER_ILLEGAL_PARAMS,
+ "field id must be a number or a string");
+ return -1;
+ }
+ return op->meta->read_arg(index_base, op, expr);
+}
+
/**
* Read and check update operations and fill column mask.
*
* @param[out] update Update meta.
* @param expr MessagePack array of operations.
* @param expr_end End of the @expr.
+ * @param dict Dictionary to lookup field number by a name.
* @param field_count_hint Field count in the updated tuple. If
* there is no tuple at hand (for example, when we are
* reading UPSERT operations), then 0 for field count will
@@ -948,7 +1025,8 @@ update_op_by(char opcode)
*/
static int
update_read_ops(struct tuple_update *update, const char *expr,
- const char *expr_end, int32_t field_count_hint)
+ const char *expr_end, struct tuple_dictionary *dict,
+ int32_t field_count_hint)
{
if (mp_typeof(*expr) != MP_ARRAY) {
diag_set(ClientError, ER_ILLEGAL_PARAMS,
@@ -974,59 +1052,14 @@ update_read_ops(struct tuple_update *update, const char *expr,
struct update_op *op = update->ops;
struct update_op *ops_end = op + update->op_count;
for (; op < ops_end; op++) {
- if (mp_typeof(*expr) != MP_ARRAY) {
- diag_set(ClientError, ER_ILLEGAL_PARAMS,
- "update operation"
- " must be an array {op,..}");
- return -1;
- }
- /* Read operation */
- uint32_t args, len;
- args = mp_decode_array(&expr);
- if (args < 1) {
- diag_set(ClientError, ER_ILLEGAL_PARAMS,
- "update operation must be an "
- "array {op,..}, got empty array");
- return -1;
- }
- if (mp_typeof(*expr) != MP_STR) {
- diag_set(ClientError, ER_ILLEGAL_PARAMS,
- "update operation name must be a string");
- return -1;
- }
-
- op->opcode = *mp_decode_str(&expr, &len);
- op->meta = update_op_by(op->opcode);
- if (op->meta == NULL)
- return -1;
- if (args != op->meta->args) {
- diag_set(ClientError, ER_UNKNOWN_UPDATE_OP);
- return -1;
- }
- if (mp_typeof(*expr) != MP_INT && mp_typeof(*expr) != MP_UINT) {
- diag_set(ClientError, ER_ILLEGAL_PARAMS,
- "field id must be a number");
- return -1;
- }
- int32_t field_no = 0;
- if (mp_read_i32(update->index_base, op, &expr, &field_no))
- return -1;
- if (field_no - update->index_base >= 0) {
- op->field_no = field_no - update->index_base;
- } else if (field_no < 0) {
- op->field_no = field_no;
- } else {
- diag_set(ClientError, ER_NO_SUCH_FIELD_NO, field_no);
+ if (update_op_decode(op, update->index_base, dict, &expr) != 0)
return -1;
- }
- if (op->meta->read_arg(update->index_base, op, &expr))
- return -1;
-
/*
* Continue collecting the changed columns
* only if there are unset bits in the mask.
*/
if (column_mask != COLUMN_MASK_FULL) {
+ int32_t field_no;
if (op->field_no >= 0)
field_no = op->field_no;
else if (op->opcode != '!')
@@ -1184,24 +1217,25 @@ update_finish(struct tuple_update *update, uint32_t *p_tuple_len)
}
int
-tuple_update_check_ops(const char *expr, const char *expr_end, int index_base)
+tuple_update_check_ops(const char *expr, const char *expr_end,
+ struct tuple_dictionary *dict, int index_base)
{
struct tuple_update update;
update_init(&update, index_base);
- return update_read_ops(&update, expr, expr_end, 0);
+ return update_read_ops(&update, expr, expr_end, dict, 0);
}
const char *
tuple_update_execute(const char *expr,const char *expr_end,
const char *old_data, const char *old_data_end,
- uint32_t *p_tuple_len, int index_base,
- uint64_t *column_mask)
+ struct tuple_dictionary *dict, uint32_t *p_tuple_len,
+ int index_base, uint64_t *column_mask)
{
struct tuple_update update;
update_init(&update, index_base);
uint32_t field_count = mp_decode_array(&old_data);
- if (update_read_ops(&update, expr, expr_end, field_count) != 0)
+ if (update_read_ops(&update, expr, expr_end, dict, field_count) != 0)
return NULL;
if (update_do_ops(&update, old_data, old_data_end, field_count))
return NULL;
@@ -1214,14 +1248,14 @@ tuple_update_execute(const char *expr,const char *expr_end,
const char *
tuple_upsert_execute(const char *expr,const char *expr_end,
const char *old_data, const char *old_data_end,
- uint32_t *p_tuple_len, int index_base, bool suppress_error,
- uint64_t *column_mask)
+ struct tuple_dictionary *dict, uint32_t *p_tuple_len,
+ int index_base, bool suppress_error, uint64_t *column_mask)
{
struct tuple_update update;
update_init(&update, index_base);
uint32_t field_count = mp_decode_array(&old_data);
- if (update_read_ops(&update, expr, expr_end, field_count) != 0)
+ if (update_read_ops(&update, expr, expr_end, dict, field_count) != 0)
return NULL;
if (upsert_do_ops(&update, old_data, old_data_end, field_count,
suppress_error))
@@ -1235,14 +1269,16 @@ tuple_upsert_execute(const char *expr,const char *expr_end,
const char *
tuple_upsert_squash(const char *expr1, const char *expr1_end,
const char *expr2, const char *expr2_end,
- size_t *result_size, int index_base)
+ struct tuple_dictionary *dict, size_t *result_size,
+ int index_base)
{
const char *expr[2] = {expr1, expr2};
const char *expr_end[2] = {expr1_end, expr2_end};
struct tuple_update update[2];
for (int j = 0; j < 2; j++) {
update_init(&update[j], index_base);
- if (update_read_ops(&update[j], expr[j], expr_end[j], 0))
+ if (update_read_ops(&update[j], expr[j], expr_end[j],
+ dict, 0) != 0)
return NULL;
mp_decode_array(&expr[j]);
int32_t prev_field_no = index_base - 1;
diff --git a/src/box/tuple_update.h b/src/box/tuple_update.h
index 37faa1918..b6210dd38 100644
--- a/src/box/tuple_update.h
+++ b/src/box/tuple_update.h
@@ -44,19 +44,23 @@ enum {
BOX_UPDATE_OP_CNT_MAX = 4000,
};
+struct tuple_dictionary;
+
int
-tuple_update_check_ops(const char *expr, const char *expr_end, int index_base);
+tuple_update_check_ops(const char *expr, const char *expr_end,
+ struct tuple_dictionary *dict, int index_base);
const char *
tuple_update_execute(const char *expr,const char *expr_end,
const char *old_data, const char *old_data_end,
- uint32_t *p_new_size, int index_base,
- uint64_t *column_mask);
+ struct tuple_dictionary *dict, uint32_t *p_new_size,
+ int index_base, uint64_t *column_mask);
const char *
tuple_upsert_execute(const char *expr, const char *expr_end,
const char *old_data, const char *old_data_end,
- uint32_t *p_new_size, int index_base, bool suppress_error,
+ struct tuple_dictionary *dict, uint32_t *p_new_size,
+ int index_base, bool suppress_error,
uint64_t *column_mask);
/**
@@ -72,7 +76,8 @@ tuple_upsert_execute(const char *expr, const char *expr_end,
const char *
tuple_upsert_squash(const char *expr1, const char *expr1_end,
const char *expr2, const char *expr2_end,
- size_t *result_size, int index_base);
+ struct tuple_dictionary *dict, size_t *result_size,
+ int index_base);
#if defined(__cplusplus)
} /* extern "C" */
diff --git a/src/box/vinyl.c b/src/box/vinyl.c
index d82cae766..3be999caf 100644
--- a/src/box/vinyl.c
+++ b/src/box/vinyl.c
@@ -1938,7 +1938,8 @@ vy_update(struct vy_env *env, struct vy_tx *tx, struct txn_stmt *stmt,
const char *old_tuple = tuple_data_range(stmt->old_tuple, &old_size);
const char *old_tuple_end = old_tuple + old_size;
new_tuple = tuple_update_execute(request->tuple, request->tuple_end,
- old_tuple, old_tuple_end, &new_size,
+ old_tuple, old_tuple_end,
+ pk->mem_format->dict, &new_size,
request->index_base, &column_mask);
if (new_tuple == NULL)
return -1;
@@ -2117,7 +2118,8 @@ vy_upsert(struct vy_env *env, struct vy_tx *tx, struct txn_stmt *stmt,
return 0;
/* Check update operations. */
if (tuple_update_check_ops(request->ops, request->ops_end,
- request->index_base)) {
+ pk->mem_format->dict,
+ request->index_base) != 0) {
return -1;
}
if (request->index_base != 0) {
@@ -2175,7 +2177,8 @@ vy_upsert(struct vy_env *env, struct vy_tx *tx, struct txn_stmt *stmt,
/* Apply upsert operations to the old tuple. */
new_tuple = tuple_upsert_execute(ops, ops_end, old_tuple, old_tuple_end,
- &new_size, 0, false, &column_mask);
+ pk->mem_format->dict, &new_size, 0,
+ false, &column_mask);
if (new_tuple == NULL)
return -1;
/*
diff --git a/src/box/vy_upsert.c b/src/box/vy_upsert.c
index 1c55f86c2..817d29cfd 100644
--- a/src/box/vy_upsert.c
+++ b/src/box/vy_upsert.c
@@ -58,7 +58,7 @@ vy_upsert_try_to_squash(struct tuple_format *format,
size_t squashed_size;
const char *squashed =
tuple_upsert_squash(old_serie, old_serie_end,
- new_serie, new_serie_end,
+ new_serie, new_serie_end, format->dict,
&squashed_size, 0);
if (squashed == NULL)
return 0;
@@ -119,8 +119,8 @@ vy_apply_upsert(struct tuple *new_stmt, struct tuple *old_stmt,
uint8_t old_type = vy_stmt_type(old_stmt);
uint64_t column_mask = COLUMN_MASK_FULL;
result_mp = tuple_upsert_execute(new_ops, new_ops_end, result_mp,
- result_mp_end, &mp_size, 0,
- suppress_error, &column_mask);
+ result_mp_end, format->dict, &mp_size,
+ 0, suppress_error, &column_mask);
result_mp_end = result_mp + mp_size;
if (old_type != IPROTO_UPSERT) {
assert(old_type == IPROTO_INSERT ||
diff --git a/test/box/misc.result b/test/box/misc.result
index dab8549bd..02482ef6d 100644
--- a/test/box/misc.result
+++ b/test/box/misc.result
@@ -482,13 +482,14 @@ t;
150: box.error.CANT_CREATE_COLLATION
151: box.error.WRONG_COLLATION_OPTIONS
152: box.error.NULLABLE_PRIMARY
- 153: box.error.NO_SUCH_FIELD_NAME
+ 153: box.error.NO_SUCH_FIELD_NAME_IN_SPACE
154: box.error.TRANSACTION_YIELD
155: box.error.NO_SUCH_GROUP
156: box.error.SQL_BIND_VALUE
157: box.error.SQL_BIND_TYPE
158: box.error.SQL_BIND_PARAMETER_MAX
159: box.error.SQL_EXECUTE
+ 160: box.error.NO_SUCH_FIELD_NAME
161: box.error.SQL_BIND_NOT_FOUND
162: box.error.ACTION_MISMATCH
163: box.error.VIEW_MISSING_SQL
diff --git a/test/box/update.result b/test/box/update.result
index a3f731b55..f5de3bc09 100644
--- a/test/box/update.result
+++ b/test/box/update.result
@@ -794,7 +794,7 @@ s:update({0}, {{'+', 0}})
...
s:update({0}, {{'+', '+', '+'}})
---
-- error: Illegal parameters, field id must be a number
+- error: Field '+' was not found in the tuple
...
s:update({0}, {{0, 0, 0}})
---
diff --git a/test/engine/update.result b/test/engine/update.result
index 69293e468..f181924f3 100644
--- a/test/engine/update.result
+++ b/test/engine/update.result
@@ -788,3 +788,70 @@ sk:select()
s:drop()
---
...
+--
+-- gh-1261: tuple update by JSON.
+-- At first, test tuple update by field names.
+--
+format = {}
+---
+...
+format[1] = {'field1', 'unsigned'}
+---
+...
+format[2] = {'field2', 'array'}
+---
+...
+format[3] = {'field3', 'map'}
+---
+...
+format[4] = {'field4', 'string'}
+---
+...
+format[5] = {'field5', 'any'}
+---
+...
+format[6] = {'field6', 'integer'}
+---
+...
+format[7] = {'[1]', 'unsigned'}
+---
+...
+s = box.schema.create_space('test', {format = format})
+---
+...
+pk = s:create_index('pk')
+---
+...
+t = s:replace{1, {10, 11, 12}, {a = 20, b = 21, c = 22}, 'abcdefgh', true, -100, 200}
+---
+...
+t:update({{'+', 'field1', 1}})
+---
+- [2, [10, 11, 12], {'b': 21, 'a': 20, 'c': 22}, 'abcdefgh', true, -100, 200]
+...
+t:update({{'=', 'field2', {13, 14, 15}}})
+---
+- [1, [13, 14, 15], {'b': 21, 'a': 20, 'c': 22}, 'abcdefgh', true, -100, 200]
+...
+t:update({{':', 'field4', 3, 3, 'bbccdd'}, {'+', 'field6', 50}, {'!', 7, 300}})
+---
+- [1, [10, 11, 12], {'b': 21, 'a': 20, 'c': 22}, 'abbbccddfgh', true, -50, 300, 200]
+...
+-- Any path is interpreted as a field name first. And only then
+-- as JSON.
+t:update({{'+', '[1]', 50}})
+---
+- [1, [10, 11, 12], {'b': 21, 'a': 20, 'c': 22}, 'abcdefgh', true, -100, 250]
+...
+-- JSON paths are not allowed yet.
+t:update({{'=', 'field2[1]', 13}})
+---
+- error: Field 'field2[1]' was not found in the tuple
+...
+s:update({1}, {{'=', 'field3', {d = 30, e = 31, f = 32}}})
+---
+- [1, [10, 11, 12], {'d': 30, 'f': 32, 'e': 31}, 'abcdefgh', true, -100, 200]
+...
+s:drop()
+---
+...
diff --git a/test/engine/update.test.lua b/test/engine/update.test.lua
index 51263f577..4ca2589e4 100644
--- a/test/engine/update.test.lua
+++ b/test/engine/update.test.lua
@@ -134,3 +134,31 @@ box.begin() s:update(1, {{'=', 2, 2}}) s:update(1, {{'=', 3, 2}}) box.commit()
pk:select()
sk:select()
s:drop()
+
+--
+-- gh-1261: tuple update by JSON.
+-- At first, test tuple update by field names.
+--
+format = {}
+format[1] = {'field1', 'unsigned'}
+format[2] = {'field2', 'array'}
+format[3] = {'field3', 'map'}
+format[4] = {'field4', 'string'}
+format[5] = {'field5', 'any'}
+format[6] = {'field6', 'integer'}
+format[7] = {'[1]', 'unsigned'}
+s = box.schema.create_space('test', {format = format})
+pk = s:create_index('pk')
+t = s:replace{1, {10, 11, 12}, {a = 20, b = 21, c = 22}, 'abcdefgh', true, -100, 200}
+t:update({{'+', 'field1', 1}})
+t:update({{'=', 'field2', {13, 14, 15}}})
+t:update({{':', 'field4', 3, 3, 'bbccdd'}, {'+', 'field6', 50}, {'!', 7, 300}})
+-- Any path is interpreted as a field name first. And only then
+-- as JSON.
+t:update({{'+', '[1]', 50}})
+-- JSON paths are not allowed yet.
+t:update({{'=', 'field2[1]', 13}})
+
+s:update({1}, {{'=', 'field3', {d = 30, e = 31, f = 32}}})
+
+s:drop()
diff --git a/test/engine/upsert.result b/test/engine/upsert.result
index b35545588..47da307fa 100644
--- a/test/engine/upsert.result
+++ b/test/engine/upsert.result
@@ -2108,7 +2108,7 @@ test(t, {{'&', 3, 1}, {'&', 2, 1}, {'&', 4, 1}}, {{1, '1', 1, '1'}})
...
test(t, {{'&', 'a', 3}, {'+', 3, 3}}, {{1, '1', 1, '1'}})
---
-- error: Illegal parameters, field id must be a number
+- error: Field 'a' was not found in the tuple
...
test(t, {{'+', 3, 3}, {'&', 3, 'a'}}, {{1, '1', 1, '1'}})
---
diff --git a/test/unit/column_mask.c b/test/unit/column_mask.c
index 3ffd351ac..5ee8b7332 100644
--- a/test/unit/column_mask.c
+++ b/test/unit/column_mask.c
@@ -129,8 +129,9 @@ check_update_result(const struct tuple_template *original,
uint64_t column_mask;
struct region *region = &fiber()->gc;
const char *actual =
- tuple_update_execute(ops, ops_end, old, old_end, &actual_len, 1,
- &column_mask);
+ tuple_update_execute(ops, ops_end, old, old_end,
+ box_tuple_format_default()->dict,
+ &actual_len, 1, &column_mask);
fail_if(actual == NULL);
is((int32_t)actual_len, new_end - new, "check result length");
is(memcmp(actual, new, actual_len), 0, "tuple update is correct");
--
2.20.1 (Apple Git-117)
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH 0/5] JSON update preparation
2019-07-13 22:11 [PATCH 0/5] JSON update preparation Vladislav Shpilevoy
` (4 preceding siblings ...)
2019-07-13 22:11 ` [PATCH 5/5] tuple: implement update by field name Vladislav Shpilevoy
@ 2019-07-31 12:15 ` Vladimir Davydov
2019-07-31 20:36 ` [tarantool-patches] " Vladislav Shpilevoy
2019-08-22 21:18 ` Vladislav Shpilevoy
2019-08-27 22:08 ` [tarantool-patches] " Kirill Yukhin
7 siblings, 1 reply; 10+ messages in thread
From: Vladimir Davydov @ 2019-07-31 12:15 UTC (permalink / raw)
To: Vladislav Shpilevoy; +Cc: tarantool-patches
On Sun, Jul 14, 2019 at 12:11:03AM +0200, Vladislav Shpilevoy wrote:
> The patchset is mainly about rope and its usage. Rope is a data structure
> allowing to modify an array with memory overhead not depending on the array
> size. Only on the number of modifications. It is used when there is a long
> array of something, and a one wants to insert new elements, delete existing
> ones, change their values, but do not rebuild the whole array each time.
>
> Rope is going to be one of the core data structures of the incoming JSON path
> updates, and this patchset makes it faster and lighter.
>
> Branch: http://github.com/tarantool/tarantool/tree/gerold103/gh-1261-update-json-prepare
> Issue: https://github.com/tarantool/tarantool/issues/1261
>
> Vladislav Shpilevoy (5):
> tuple: remove alloc and alloc_ctx args from update()
> rope: make rope library macro template
> tuple: relax struct tuple_update dependency on rope
> int96: add a missing header
> tuple: implement update by field name
LGTM
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [tarantool-patches] Re: [PATCH 0/5] JSON update preparation
2019-07-31 12:15 ` [PATCH 0/5] JSON update preparation Vladimir Davydov
@ 2019-07-31 20:36 ` Vladislav Shpilevoy
0 siblings, 0 replies; 10+ messages in thread
From: Vladislav Shpilevoy @ 2019-07-31 20:36 UTC (permalink / raw)
To: Vladimir Davydov; +Cc: tarantool-patches, Kirill Yukhin
I can't believe that you've watched this huge patchset, and
don't have a single comment. But ok, understandable.
Kirill, I've rebased it, made a couple of minor changes, and
force pushed to the branch. You can merge, or propose who else
could review this.
On 31/07/2019 14:15, Vladimir Davydov wrote:
> On Sun, Jul 14, 2019 at 12:11:03AM +0200, Vladislav Shpilevoy wrote:
>> The patchset is mainly about rope and its usage. Rope is a data structure
>> allowing to modify an array with memory overhead not depending on the array
>> size. Only on the number of modifications. It is used when there is a long
>> array of something, and a one wants to insert new elements, delete existing
>> ones, change their values, but do not rebuild the whole array each time.
>>
>> Rope is going to be one of the core data structures of the incoming JSON path
>> updates, and this patchset makes it faster and lighter.
>>
>> Branch: http://github.com/tarantool/tarantool/tree/gerold103/gh-1261-update-json-prepare
>> Issue: https://github.com/tarantool/tarantool/issues/1261
>>
>> Vladislav Shpilevoy (5):
>> tuple: remove alloc and alloc_ctx args from update()
>> rope: make rope library macro template
>> tuple: relax struct tuple_update dependency on rope
>> int96: add a missing header
>> tuple: implement update by field name
>
> LGTM
>
^ permalink raw reply [flat|nested] 10+ messages in thread
* [tarantool-patches] Re: [PATCH 0/5] JSON update preparation
2019-07-13 22:11 [PATCH 0/5] JSON update preparation Vladislav Shpilevoy
` (5 preceding siblings ...)
2019-07-31 12:15 ` [PATCH 0/5] JSON update preparation Vladimir Davydov
@ 2019-08-22 21:18 ` Vladislav Shpilevoy
2019-08-27 22:08 ` [tarantool-patches] " Kirill Yukhin
7 siblings, 0 replies; 10+ messages in thread
From: Vladislav Shpilevoy @ 2019-08-22 21:18 UTC (permalink / raw)
To: tarantool-patches, Kirill Yukhin
Hi! As you asked, I rebased it. But not on the
latest master, because the latest one crashes.
Nonetheless, conflicting part about decimals update
is fixed, so once the master is stable, it should be
pushable without new conflicts.
On 14/07/2019 00:11, Vladislav Shpilevoy wrote:
> The patchset is mainly about rope and its usage. Rope is a data structure
> allowing to modify an array with memory overhead not depending on the array
> size. Only on the number of modifications. It is used when there is a long
> array of something, and a one wants to insert new elements, delete existing
> ones, change their values, but do not rebuild the whole array each time.
>
> Rope is going to be one of the core data structures of the incoming JSON path
> updates, and this patchset makes it faster and lighter.
>
> Branch: http://github.com/tarantool/tarantool/tree/gerold103/gh-1261-update-json-prepare
> Issue: https://github.com/tarantool/tarantool/issues/1261
>
> Vladislav Shpilevoy (5):
> tuple: remove alloc and alloc_ctx args from update()
> rope: make rope library macro template
> tuple: relax struct tuple_update dependency on rope
> int96: add a missing header
> tuple: implement update by field name
>
> debian/copyright | 2 +-
> src/box/errcode.h | 4 +-
> src/box/lua/tuple.c | 10 +-
> src/box/memtx_space.c | 27 +-
> src/box/space.c | 26 +-
> src/box/sql/insert.c | 3 +-
> src/box/sql/resolve.c | 4 +-
> src/box/sql/update.c | 2 +-
> src/box/tuple.c | 18 +-
> src/box/tuple_update.c | 292 +++++++++--------
> src/box/tuple_update.h | 25 +-
> src/box/vinyl.c | 19 +-
> src/box/vy_upsert.c | 31 +-
> src/lib/bit/int96.h | 1 +
> src/lib/salad/rope.c | 479 +++++-----------------------
> src/lib/salad/rope.h | 617 +++++++++++++++++++++++++++++++-----
> test/box/misc.result | 3 +-
> test/box/update.result | 2 +-
> test/engine/update.result | 67 ++++
> test/engine/update.test.lua | 28 ++
> test/engine/upsert.result | 2 +-
> test/unit/column_mask.c | 33 +-
> test/unit/rope.c | 1 -
> test/unit/rope_avl.c | 1 -
> test/unit/rope_basic.c | 1 -
> test/unit/rope_common.h | 41 ++-
> test/unit/rope_stress.c | 5 +-
> 27 files changed, 993 insertions(+), 751 deletions(-)
>
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [tarantool-patches] [PATCH 0/5] JSON update preparation
2019-07-13 22:11 [PATCH 0/5] JSON update preparation Vladislav Shpilevoy
` (6 preceding siblings ...)
2019-08-22 21:18 ` Vladislav Shpilevoy
@ 2019-08-27 22:08 ` Kirill Yukhin
7 siblings, 0 replies; 10+ messages in thread
From: Kirill Yukhin @ 2019-08-27 22:08 UTC (permalink / raw)
To: tarantool-patches; +Cc: vdavydov.dev
Hello,
On 14 июл 00:11, Vladislav Shpilevoy wrote:
> The patchset is mainly about rope and its usage. Rope is a data structure
> allowing to modify an array with memory overhead not depending on the array
> size. Only on the number of modifications. It is used when there is a long
> array of something, and a one wants to insert new elements, delete existing
> ones, change their values, but do not rebuild the whole array each time.
>
> Rope is going to be one of the core data structures of the incoming JSON path
> updates, and this patchset makes it faster and lighter.
>
> Branch: http://github.com/tarantool/tarantool/tree/gerold103/gh-1261-update-json-prepare
> Issue: https://github.com/tarantool/tarantool/issues/1261
I've checked your patchset into master.
--
Regards, Kirill Yukhin
^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2019-08-27 22:08 UTC | newest]
Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-07-13 22:11 [PATCH 0/5] JSON update preparation Vladislav Shpilevoy
2019-07-13 22:11 ` [PATCH 1/5] tuple: remove alloc and alloc_ctx args from update() Vladislav Shpilevoy
2019-07-13 22:11 ` [PATCH 2/5] rope: make rope library macro template Vladislav Shpilevoy
2019-07-13 22:11 ` [PATCH 3/5] tuple: relax struct tuple_update dependency on rope Vladislav Shpilevoy
2019-07-13 22:11 ` [PATCH 4/5] int96: add a missing header Vladislav Shpilevoy
2019-07-13 22:11 ` [PATCH 5/5] tuple: implement update by field name Vladislav Shpilevoy
2019-07-31 12:15 ` [PATCH 0/5] JSON update preparation Vladimir Davydov
2019-07-31 20:36 ` [tarantool-patches] " Vladislav Shpilevoy
2019-08-22 21:18 ` Vladislav Shpilevoy
2019-08-27 22:08 ` [tarantool-patches] " Kirill Yukhin
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox