[PATCH 2/5] rope: make rope library macro template

Vladislav Shpilevoy v.shpilevoy at tarantool.org
Sun Jul 14 01:11:05 MSK 2019


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 at 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 at 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 at 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)




More information about the Tarantool-patches mailing list