[tarantool-patches] [PATCH 3/3] rope: make rope library be C template using macros

[Vladislav Shpilevoy <v.shpilevoy@tarantool.org>]

Rope library stores alloc, split and free functions by pointer,
that is a huge slog at performance. There is no reason, why the
rope library can not become a template.

Inline a concrete functions on compilation instead of pointers on
runtime.
---
 debian/copyright             |   2 +-
 src/box/tuple_update.c       |  84 ++---
 src/lib/salad/CMakeLists.txt |   2 +-
 src/lib/salad/rope.c         | 664 ------------------------------------
 src/lib/salad/rope.h         | 790 ++++++++++++++++++++++++++++++++++++++-----
 test/unit/rope.c             |   1 -
 test/unit/rope_avl.c         |   1 -
 test/unit/rope_basic.c       |   1 -
 test/unit/rope_common.h      |  21 +-
 test/unit/rope_stress.c      |   5 +-
 10 files changed, 766 insertions(+), 805 deletions(-)
 delete mode 100644 src/lib/salad/rope.c

diff --git a/debian/copyright b/debian/copyright
index a48171371..c56b8a246 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.h
 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 03a293785..b1e341d55 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,28 +94,22 @@
  */
 
 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;
 }
 
-/** Free rope node - do nothing, since we use a pool allocator. */
-static void
-update_free(void *ctx, void *mem)
-{
-	(void) ctx;
-	(void) mem;
-}
+struct update_field;
+struct update_op;
 
 /** Update internal state */
 struct tuple_update
 {
-	void *alloc_ctx;
+	struct region *region;
 	struct rope *rope;
 	struct update_op *ops;
 	uint32_t op_count;
@@ -127,6 +118,18 @@ struct tuple_update
 	uint64_t column_mask;
 };
 
+static struct update_field *
+update_field_split(struct tuple_update *split_ctx, 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_alloc_ctx_t struct region *
+#define rope_split_ctx_t struct tuple_update *
+
+#include "salad/rope.h"
+
 /** Argument of SET (and INSERT) operation. */
 struct op_set_arg {
 	uint32_t length;
@@ -204,9 +207,6 @@ union update_op_arg {
 	struct op_splice_arg splice;
 };
 
-struct update_field;
-struct update_op;
-
 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);
@@ -526,7 +526,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);
@@ -541,8 +541,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. */
@@ -579,8 +578,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) {
@@ -609,8 +607,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;
@@ -647,8 +644,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) {
@@ -787,16 +783,14 @@ 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 tuple_update *update, 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(update->region,
+						     sizeof(*next));
 	if (next == NULL)
 		return NULL;
 	assert(offset > 0 && prev->tail_len > 0);
@@ -804,9 +798,8 @@ update_field_split(void *split_ctx, void *data, size_t size, size_t offset)
 	const char *field = prev->tail;
 	const char *end = field + prev->tail_len;
 
-	for (uint32_t i = 1; i < offset; i++) {
+	for (uint32_t i = 1; i < offset; i++)
 		mp_next(&field);
-	}
 
 	prev->tail_len = field - prev->tail;
 	const char *f = field;
@@ -832,14 +825,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, 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;
@@ -863,8 +855,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;
@@ -888,8 +879,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;
@@ -978,7 +968,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;
@@ -1171,7 +1161,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!
@@ -1183,7 +1173,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/CMakeLists.txt b/src/lib/salad/CMakeLists.txt
index 5263c16e4..41cb08898 100644
--- a/src/lib/salad/CMakeLists.txt
+++ b/src/lib/salad/CMakeLists.txt
@@ -1,3 +1,3 @@
-set(lib_sources rope.c rtree.c guava.c bloom.c)
+set(lib_sources rtree.c guava.c bloom.c)
 set_source_files_compile_flags(${lib_sources})
 add_library(salad STATIC ${lib_sources})
diff --git a/src/lib/salad/rope.c b/src/lib/salad/rope.c
deleted file mode 100644
index 06324ab65..000000000
--- a/src/lib/salad/rope.c
+++ /dev/null
@@ -1,664 +0,0 @@
-/*
- * Copyright 2010-2016, Tarantool AUTHORS, please see AUTHORS file.
- *
- * Redistribution and use in source and binary forms, with or
- * without modification, are permitted provided that the following
- * conditions are met:
- *
- * 1. Redistributions of source code must retain the above
- *    copyright notice, this list of conditions and the
- *    following disclaimer.
- *
- * 2. Redistributions in binary form must reproduce the above
- *    copyright notice, this list of conditions and the following
- *    disclaimer in the documentation and/or other materials
- *    provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
- * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
- * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
- * <COPYRIGHT HOLDER> OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
- * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
- * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
- * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
- * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
- * 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 "rope.h"
-#include <stdio.h>
-#include <string.h>
-#include <stdlib.h>
-#include <assert.h>
-
-static inline int
-rope_node_height(struct rope_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)
-{
-	node->tree_size = (rope_node_size(node->link[0]) +
-			   rope_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;
-}
-
-void
-rope_clear(struct rope *rope)
-{
-	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];
-
-	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);
-
-	return save;
-}
-
-static inline struct rope_node *
-avl_rotate_double(struct rope_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)
-{
-	while (p_end > path) {
-		struct rope_node *left = **p_end--;
-		struct rope_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];
-
-		int left_height = rope_node_height(left);
-		int right_height = rope_node_height(right);
-		parent->height = MAX(left_height, right_height) + 1;
-		/*
-		 * Rotations flattened the tree, so there is no
-		 * further changes in height up the insertion
-		 * path.
-		 */
-		if (left_height == right_height)
-			break;
-		/*
-		 * We've been adding a new child (children) to the
-		 * 'left' subtree, so it couldn't get shorter.
-		 * The old difference between subtrees was in the
-		 * range -1..1. So the new difference can only be
-		 * 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);
-			/*
-			 * Rotate in the direction, opposite to
-			 * the skew. E.g. if we have two left-left
-			 * nodes hanging off the tree, rotate the
-			 * parent clockwise. If we have a left
-			 * node with a right child, rotate the
-			 * child counterclockwise, and then the whole
-			 * thing clockwise.
-			 */
-			if (l_left_height >= l_right_height)
-				**p_end = avl_rotate_single(parent,
-							    !mirror);
-			else
-				**p_end = avl_rotate_double(parent,
-							    !mirror);
-			/*
-			 * If we inserted only one node, no more
-			 * than 1 rotation is required (see
-			 * D. Knuth, Introduction to Algorithms,
-			 * vol. 3.). For 2 nodes, its max
-			 * 2 rotations.
-			 */
-			if (l_left_height != l_right_height &&
-			    --insert_height == 0)
-				break;
-		}
-	}
-}
-
-/* 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)
-{
-	while (p_end > path) {
-		struct rope_node *left = **p_end--;
-		struct rope_node *parent = **p_end;
-
-		int mirror = left != parent->link[0];
-
-		struct rope_node *right = parent->link[!mirror];
-
-		int left_height = rope_node_height(left);
-		int right_height = rope_node_height(right);
-
-		parent->height = MAX(left_height, right_height) + 1;
-		/*
-		 * Right was taller, and we deleted from the left.
-		 * We can break the loop since there can be no
-		 * changes in height up in the route.
-		 */
-		if (left_height - right_height == -1)
-			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);
-
-			if (r_left_height <= r_right_height)
-				**p_end = avl_rotate_single(parent, mirror);
-			else
-				**p_end = avl_rotate_double(parent, mirror);
-		}
-	}
-}
-
-/**
- * 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,
-		    ssize_t adjust_size)
-{
-	rope_size_t offset = *p_offset;
-	while (**path) {
-		struct rope_node *node = **path;
-
-		node->tree_size += adjust_size;
-
-		rope_size_t left_size = rope_node_size(node->link[0]);
-
-		if (offset < left_size) {
-			/* The offset lays in  the left subtree. */
-			*++path = &node->link[0];
-		} else {
-			/* Make the new offset relative to the parent. */
-			offset -= left_size;
-
-			if (offset < node->leaf_size) {
-				/* Found. */
-				break;
-			} else {
-				/*
-				 * Make the offset relative to the
-				 * leftmost node in the right subtree.
-				 */
-				offset -= node->leaf_size;
-			}
-			*++path = &node->link[1];
-		}
-	}
-	*p_offset = 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 rope_node *node = **path;
-	*++path = &node->link[dir];
-	while (**path) {
-		node = **path;
-		node->tree_size += adjust_size;
-		*++path = &node->link[!dir];
-	}
-	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.
- * @pre iter->path[iter->top] is not NULL
- * @post iter->path[iter->top] is not NULL and points to the last
- * not-NULL node.
- */
-static inline void
-rope_iter_down_to_leaf(struct rope_iter *it)
-{
-	while (it->top[0]->link[0] != NULL) {
-		it->top[1] = it->top[0]->link[0];
-		it->top++;
-	}
-}
-
-struct rope_node *
-rope_iter_start(struct rope_iter *it)
-{
-	it->top = it->path;
-	it->top[0] = it->rope->root;
-
-	if (it->top[0] != NULL)
-		rope_iter_down_to_leaf(it);
-	return it->top[0];
-}
-
-struct rope_node *
-rope_iter_next(struct rope_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);
-	} else {
-		/*
-		 * Right subtree is NULL. Left subtree is fully
-		 * traversed (guaranteed by the order in which we
-		 * iterate). Pop up the path until the current
-		 * node points to a link we haven't visited
-		 * yet: this is the case when we return to the
-		 * parent from its left child.
-		 */
-		do {
-			/*
-			 * Returned to the root from the right
-			 * subtree: the tree is fully traversed.
-			 */
-			if (it->top == it->path) {
-				/*
-				 * Crash, rather than infinite loop
-				 * if next() is called beyond last.
-				 */
-				it->top[0] = NULL;
-				return NULL;
-			}
-			it->top--;
-		} while (it->top[1] == it->top[0]->link[1]);
-	}
-	return *it->top;
-}
-
-/** Apply visit_leaf function to every rope leaf. */
-void
-rope_traverse(struct rope *rope, void (*visit_leaf)(void *, 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);
-	}
-}
-
-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)) {
-
-		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->height == (MAX(rope_node_height(node->link[0]),
-					    rope_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->leaf_size) ||
-		    node->height != MAX(rope_node_height(node->link[0]),
-					rope_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 719fd9c99..3e4585809 100644
--- a/src/lib/salad/rope.h
+++ b/src/lib/salad/rope.h
@@ -1,5 +1,3 @@
-#ifndef INCLUDES_TARANTOOL_ROPE_H
-#define INCLUDES_TARANTOOL_ROPE_H
 /*
  * Copyright 2010-2016, Tarantool AUTHORS, please see AUTHORS file.
  *
@@ -30,19 +28,52 @@
  * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
  */
-#include <stdint.h>
-#include <stddef.h>
+/*
+ * 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 <stdbool.h>
-
-#if defined(__cplusplus)
-extern "C" {
-#endif /* defined(__cplusplus) */
+#include <stdio.h>
+#include <assert.h>
 
 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 *);
+
+/**
+ * Needed definitions:
+ *
+ * rope_data_t
+ * rope_split_ctx_t
+ * rope_alloc_ctx_t
+ * ROPE_SPLIT_F
+ * ROPE_ALLOC_F
+ * ROPE_FREE_F [optional]
+ */
+
+#ifndef ROPE_FREE_F
+#define ROPE_FREE_F_IMPL(a, b) do { (void) a; (void) b; } while(0)
+#else
+#define ROPE_FREE_F_IMPL(a, b) ROPE_FREE_F(a, b)
+#endif /* ROPE_FREE_F */
+
+#ifndef MAX
+#define NEED_UNDEF_MAX
+#define MAX(a, b) ((a) > (b) ? (a) : (b))
+#endif /* MAX */
 
 /** Tallest allowable tree, 1.44*log(2^32) */
 enum { ROPE_HEIGHT_MAX = 46 };
@@ -55,7 +86,7 @@ struct rope_node {
 	/* Substring size. */
 	rope_size_t leaf_size;
 	/* Substring. */
-	void *data;
+	rope_data_t data;
 	/* Left (0) and right (1) links */
 	struct rope_node *link[2];
 };
@@ -64,15 +95,10 @@ struct rope {
 	/** Top of the tree */
 	struct rope_node *root;
 	/** Memory management context. */
-	void *alloc_ctx;
+	rope_alloc_ctx_t 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_split_ctx_t split_ctx;
 };
 
 struct rope_iter {
@@ -84,6 +110,34 @@ struct rope_iter {
 	struct rope_node *path[ROPE_HEIGHT_MAX];
 };
 
+/** Public API {{{ */
+
+/** Initialize an empty rope. */
+static inline void
+rope_create(struct rope *rope, rope_split_ctx_t split_ctx,
+	    rope_alloc_ctx_t alloc_ctx)
+{
+	rope->root = NULL;
+	rope->split_ctx = split_ctx;
+	rope->alloc_ctx = alloc_ctx;
+}
+
+/** Create a new empty rope.
+ * @param alloc_ctx  allocator context
+ *
+ * @return  an empty rope, or NULL if failed
+ *          to allocate memory
+ */
+static inline struct rope *
+rope_new(rope_split_ctx_t split_ctx, rope_alloc_ctx_t alloc_ctx)
+{
+	struct rope *rope=
+		(struct rope *) ROPE_ALLOC_F(alloc_ctx, sizeof(*rope));
+	if (rope != NULL)
+		rope_create(rope, split_ctx, alloc_ctx);
+	return rope;
+}
+
 static inline rope_size_t
 rope_node_size(struct rope_node *node)
 {
@@ -96,7 +150,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,63 +162,47 @@ rope_size(struct rope *rope)
 	return rope_node_size(rope->root);
 }
 
-/** 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->root = NULL;
-	rope->split = split_func;
-	rope->split_ctx = split_ctx;
-	rope->alloc = alloc_func;
-	rope->free = free_func;
-	rope->alloc_ctx = alloc_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)
-{
-	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);
-	return rope;
-}
-
-
-/** Delete rope contents. Can also be used
+/**
+ * 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);
+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_F(rope->alloc_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_F_IMPL(rope->alloc_ctx, rope);
 }
 
-/** Insert a substring into a rope at the given
+/**
+ * Insert a substring into a rope at the given
  * offset.
  * If offset is greater than rope size, insertion
  * happens at the end.
@@ -174,17 +212,18 @@ rope_delete(struct rope *rope)
  *             tree node
  */
 int
-rope_insert(struct rope *rope, rope_size_t offset, void *data,
+rope_insert(struct rope *rope, rope_size_t offset, rope_data_t data,
 	    rope_size_t size);
 
 /** 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);
 }
 
-/** Make sure there is a rope node which has a substring
+/**
+ * Make sure there is a rope node which has a substring
  * which starts at the given offset. Useful when
  * rope substrings carry additional information.
  *
@@ -194,7 +233,7 @@ rope_append(struct rope *rope, void *data, size_t size)
 struct rope_node *
 rope_extract_node(struct rope *rope, rope_size_t offset);
 
-static inline void *
+static inline rope_data_t
 rope_extract(struct rope *rope, rope_size_t offset)
 {
 	return rope_leaf_data(rope_extract_node(rope, offset));
@@ -220,12 +259,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->alloc_ctx, sizeof(*it));
+	if (it != NULL)
+		rope_iter_create(it, rope);
 	return it;
 }
 
@@ -250,12 +287,12 @@ rope_iter_next(struct rope_iter *it);
 static inline void
 rope_iter_delete(struct rope_iter *it)
 {
-	it->rope->free(it->rope->alloc_ctx, it);
+	ROPE_FREE_F_IMPL(it->rope->alloc_ctx, it);
 }
 
 /** Apply visit_leaf function to every rope leaf. */
 void
-rope_traverse(struct rope *rope, void (*visit_leaf)(void *, size_t));
+rope_traverse(struct rope *rope, void (*visit_leaf)(rope_data_t, size_t));
 
 /** Check AVL tree consistency. */
 void
@@ -263,10 +300,603 @@ rope_check(struct rope *rope);
 
 /** Pretty print a rope. */
 void
-rope_pretty_print(struct rope *rope, void (*print_leaf)(void *, size_t));
+rope_pretty_print(struct rope *rope, void (*print_leaf)(rope_data_t, size_t));
+
+/** }}} */
+
+static inline int
+rope_node_height(struct rope_node *node)
+{
+	return node ? node->height : 0;
+}
+
+static inline void
+rope_relink(struct rope_node *node)
+{
+	node->tree_size = (rope_node_size(node->link[0]) +
+			   rope_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, rope_data_t data, rope_size_t size)
+{
+	struct rope_node *node =
+		(struct rope_node *) ROPE_ALLOC_F(rope->alloc_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 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->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];
+
+	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);
+
+	return save;
+}
+
+static inline struct rope_node *
+avl_rotate_double(struct rope_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)
+{
+	while (p_end > path) {
+		struct rope_node *left = **p_end--;
+		struct rope_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];
+
+		int left_height = rope_node_height(left);
+		int right_height = rope_node_height(right);
+		parent->height = MAX(left_height, right_height) + 1;
+		/*
+		 * Rotations flattened the tree, so there is no
+		 * further changes in height up the insertion
+		 * path.
+		 */
+		if (left_height == right_height)
+			break;
+		/*
+		 * We've been adding a new child (children) to the
+		 * 'left' subtree, so it couldn't get shorter.
+		 * The old difference between subtrees was in the
+		 * range -1..1. So the new difference can only be
+		 * 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);
+			/*
+			 * Rotate in the direction, opposite to
+			 * the skew. E.g. if we have two left-left
+			 * nodes hanging off the tree, rotate the
+			 * parent clockwise. If we have a left
+			 * node with a right child, rotate the
+			 * child counterclockwise, and then the whole
+			 * thing clockwise.
+			 */
+			if (l_left_height >= l_right_height)
+				**p_end = avl_rotate_single(parent,
+							    !mirror);
+			else
+				**p_end = avl_rotate_double(parent,
+							    !mirror);
+			/*
+			 * If we inserted only one node, no more
+			 * than 1 rotation is required (see
+			 * D. Knuth, Introduction to Algorithms,
+			 * vol. 3.). For 2 nodes, its max
+			 * 2 rotations.
+			 */
+			if (l_left_height != l_right_height &&
+			    --insert_height == 0)
+				break;
+		}
+	}
+}
+
+/* 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)
+{
+	while (p_end > path) {
+		struct rope_node *left = **p_end--;
+		struct rope_node *parent = **p_end;
+
+		int mirror = left != parent->link[0];
+
+		struct rope_node *right = parent->link[!mirror];
+
+		int left_height = rope_node_height(left);
+		int right_height = rope_node_height(right);
+
+		parent->height = MAX(left_height, right_height) + 1;
+		/*
+		 * Right was taller, and we deleted from the left.
+		 * We can break the loop since there can be no
+		 * changes in height up in the route.
+		 */
+		if (left_height - right_height == -1)
+			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);
+
+			if (r_left_height <= r_right_height)
+				**p_end = avl_rotate_single(parent, mirror);
+			else
+				**p_end = avl_rotate_double(parent, mirror);
+		}
+	}
+}
+
+/**
+ * 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,
+		    ssize_t adjust_size)
+{
+	rope_size_t offset = *p_offset;
+	while (**path) {
+		struct rope_node *node = **path;
+
+		node->tree_size += adjust_size;
+
+		rope_size_t left_size = rope_node_size(node->link[0]);
+
+		if (offset < left_size) {
+			/* The offset lays in  the left subtree. */
+			*++path = &node->link[0];
+		} else {
+			/* Make the new offset relative to the parent. */
+			offset -= left_size;
+
+			if (offset < node->leaf_size) {
+				/* Found. */
+				break;
+			} else {
+				/*
+				 * Make the offset relative to the
+				 * leftmost node in the right subtree.
+				 */
+				offset -= node->leaf_size;
+			}
+			*++path = &node->link[1];
+		}
+	}
+	*p_offset = 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 rope_node *node = **path;
+	*++path = &node->link[dir];
+	while (**path) {
+		node = **path;
+		node->tree_size += adjust_size;
+		*++path = &node->link[!dir];
+	}
+	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, 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 = 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_F(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 */
+		rope_data_t next = ROPE_SPLIT_F(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_F(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_F_IMPL(rope->alloc_ctx, node);
+	avl_rebalance_after_delete(path, p_end);
+	return 0;
+}
+
+/**
+ * Traverse left until the left subtree is NULL,
+ * save the path in iter->path.
+ * @pre iter->path[iter->top] is not NULL
+ * @post iter->path[iter->top] is not NULL and points to the last
+ * not-NULL node.
+ */
+static inline void
+rope_iter_down_to_leaf(struct rope_iter *it)
+{
+	while (it->top[0]->link[0] != NULL) {
+		it->top[1] = it->top[0]->link[0];
+		it->top++;
+	}
+}
+
+struct rope_node *
+rope_iter_start(struct rope_iter *it)
+{
+	it->top = it->path;
+	it->top[0] = it->rope->root;
+
+	if (it->top[0] != NULL)
+		rope_iter_down_to_leaf(it);
+	return it->top[0];
+}
+
+struct rope_node *
+rope_iter_next(struct rope_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);
+	} else {
+		/*
+		 * Right subtree is NULL. Left subtree is fully
+		 * traversed (guaranteed by the order in which we
+		 * iterate). Pop up the path until the current
+		 * node points to a link we haven't visited
+		 * yet: this is the case when we return to the
+		 * parent from its left child.
+		 */
+		do {
+			/*
+			 * Returned to the root from the right
+			 * subtree: the tree is fully traversed.
+			 */
+			if (it->top == it->path) {
+				/*
+				 * Crash, rather than infinite loop
+				 * if next() is called beyond last.
+				 */
+				it->top[0] = NULL;
+				return NULL;
+			}
+			it->top--;
+		} while (it->top[1] == it->top[0]->link[1]);
+	}
+	return *it->top;
+}
+
+/** Apply visit_leaf function to every rope leaf. */
+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);
+	}
+}
+
+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)) {
 
-#if defined(__cplusplus)
+		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->height == (MAX(rope_node_height(node->link[0]),
+					    rope_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->leaf_size) ||
+		    node->height != MAX(rope_node_height(node->link[0]),
+					rope_node_height(node->link[1])) + 1)
+			abort();
+	}
 }
-#endif /* defined(__cplusplus) */
 
-#endif /* INCLUDES_TARANTOOL_ROPE_H */
+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);
+}
+
+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");
+}
+
+#undef rope_alloc_ctx_t
+#undef rope_split_ctx_t
+#undef rope_data_t
+#undef ROPE_SPLIT_F
+#undef ROPE_ALLOC_F
+#undef ROPE_FREE_F
+#undef ROPE_FREE_F_IMPL
+
+#ifdef NEED_UNDEF_MAX
+#undef NEED_UNDEF_MAX
+#undef MAX
+#endif
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..3b3823ced 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,19 @@ 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_alloc_ctx_t void *
+#define rope_split_ctx_t void *
+
+#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, 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.15.1 (Apple Git-101)