[tarantool-patches] [PATCH 3/3] rope: make rope library be C template using macros
Vladislav Shpilevoy
v.shpilevoy at tarantool.org
Sat Apr 28 01:36:40 MSK 2018
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 at 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 at 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 at 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)
More information about the Tarantool-patches
mailing list