[tarantool-patches] [PATCH 02/13] rope: make rope library macro template
Vladislav Shpilevoy
v.shpilevoy at tarantool.org
Tue Aug 13 02:05:12 MSK 2019
Rope library stores alloc, split and free functions by pointer,
that is a huge slog at performance, as any other virtual
function call. There is no reason, why the rope library may not
become a template, except historical ones.
The patch not only removes virtual functions, but also makes rope
deletion almost no-op in case if free() function is not defined.
A second motivation point of that patch is that original rope
structure was too big. Again, because it stored several pointers
to functions. In forthcoming patches on #1261 multiple ropes can
be created per each update, so it makes sense to reduce size of
this structure.
---
debian/copyright | 2 +-
src/box/tuple_update.c | 74 +++--
src/lib/salad/rope.c | 479 +++++--------------------------
src/lib/salad/rope.h | 617 ++++++++++++++++++++++++++++++++++------
test/unit/rope.c | 1 -
test/unit/rope_avl.c | 1 -
test/unit/rope_basic.c | 1 -
test/unit/rope_common.h | 41 ++-
test/unit/rope_stress.c | 5 +-
9 files changed, 674 insertions(+), 547 deletions(-)
diff --git a/debian/copyright b/debian/copyright
index a48171371..3d68dc390 100644
--- a/debian/copyright
+++ b/debian/copyright
@@ -218,7 +218,7 @@ Files: third_party/lua-cjson/*
Copyright: 2010-2012 Mark Pulford <mark at kyne.com.au>
License: Expat
-Files: src/lib/salad/rope.c
+Files: src/lib/salad/rope.*
Copyright: 1993-1994 by Xerox Corporation.
License: BSD-2-Clause
diff --git a/src/box/tuple_update.c b/src/box/tuple_update.c
index 599952189..7498d558a 100644
--- a/src/box/tuple_update.c
+++ b/src/box/tuple_update.c
@@ -30,8 +30,6 @@
*/
#include "tuple_update.h"
-
-#include <stdio.h>
#include <stdbool.h>
#include "say.h"
@@ -41,7 +39,6 @@
#include "third_party/queue.h"
#include <msgpuck/msgpuck.h>
#include <bit/int96.h>
-#include <salad/rope.h>
#include "column_mask.h"
#include "fiber.h"
@@ -97,27 +94,19 @@
*/
static inline void *
-update_alloc(void *ctx, size_t size)
+update_alloc(struct region *region, size_t size)
{
- void *ptr = region_aligned_alloc((struct region *) ctx, size,
- alignof(uint64_t));
+ void *ptr = region_aligned_alloc(region, size, alignof(uint64_t));
if (ptr == NULL)
diag_set(OutOfMemory, size, "region_aligned_alloc",
"update internals");
return ptr;
}
-static void
-update_free(void *ctx, void *mem)
-{
- (void) ctx;
- (void) mem;
-}
-
/** Update internal state */
struct tuple_update
{
- void *alloc_ctx;
+ struct region *region;
struct rope *rope;
struct update_op *ops;
uint32_t op_count;
@@ -206,6 +195,17 @@ union update_op_arg {
struct update_field;
struct update_op;
+static struct update_field *
+update_field_split(struct region *region, struct update_field *data,
+ size_t size, size_t offset);
+
+#define ROPE_SPLIT_F update_field_split
+#define ROPE_ALLOC_F update_alloc
+#define rope_data_t struct update_field *
+#define rope_ctx_t struct region *
+
+#include "salad/rope.h"
+
typedef int (*do_op_func)(struct tuple_update *update, struct update_op *op);
typedef int (*read_arg_func)(int index_base, struct update_op *op,
const char **expr);
@@ -525,7 +525,7 @@ do_op_insert(struct tuple_update *update, struct update_op *op)
if (op_adjust_field_no(update, op, rope_size(update->rope) + 1))
return -1;
struct update_field *field = (struct update_field *)
- update_alloc(update->alloc_ctx, sizeof(*field));
+ update_alloc(update->region, sizeof(*field));
if (field == NULL)
return -1;
update_field_init(field, op->arg.set.value, op->arg.set.length, 0);
@@ -540,8 +540,7 @@ do_op_set(struct tuple_update *update, struct update_op *op)
return do_op_insert(update, op);
if (op_adjust_field_no(update, op, rope_size(update->rope)))
return -1;
- struct update_field *field = (struct update_field *)
- rope_extract(update->rope, op->field_no);
+ struct update_field *field = rope_extract(update->rope, op->field_no);
if (field == NULL)
return -1;
/* Ignore the previous op, if any. */
@@ -578,8 +577,7 @@ do_op_arith(struct tuple_update *update, struct update_op *op)
if (op_adjust_field_no(update, op, rope_size(update->rope)))
return -1;
- struct update_field *field = (struct update_field *)
- rope_extract(update->rope, op->field_no);
+ struct update_field *field = rope_extract(update->rope, op->field_no);
if (field == NULL)
return -1;
if (field->op) {
@@ -608,8 +606,7 @@ do_op_bit(struct tuple_update *update, struct update_op *op)
{
if (op_adjust_field_no(update, op, rope_size(update->rope)))
return -1;
- struct update_field *field = (struct update_field *)
- rope_extract(update->rope, op->field_no);
+ struct update_field *field = rope_extract(update->rope, op->field_no);
if (field == NULL)
return -1;
struct op_bit_arg *arg = &op->arg.bit;
@@ -646,8 +643,7 @@ do_op_splice(struct tuple_update *update, struct update_op *op)
{
if (op_adjust_field_no(update, op, rope_size(update->rope)))
return -1;
- struct update_field *field = (struct update_field *)
- rope_extract(update->rope, op->field_no);
+ struct update_field *field = rope_extract(update->rope, op->field_no);
if (field == NULL)
return -1;
if (field->op) {
@@ -786,16 +782,13 @@ static const struct update_op_meta op_delete =
/** Split a range of fields in two, allocating update_field
* context for the new range.
*/
-static void *
-update_field_split(void *split_ctx, void *data, size_t size, size_t offset)
+static struct update_field *
+update_field_split(struct region *region, struct update_field *prev,
+ size_t size, size_t offset)
{
- (void)size;
- struct tuple_update *update = (struct tuple_update *) split_ctx;
-
- struct update_field *prev = (struct update_field *) data;
-
- struct update_field *next = (struct update_field *)
- update_alloc(update->alloc_ctx, sizeof(*next));
+ (void) size;
+ struct update_field *next =
+ (struct update_field *) update_alloc(region, sizeof(*next));
if (next == NULL)
return NULL;
assert(offset > 0 && prev->tail_len > 0);
@@ -831,14 +824,13 @@ int
update_create_rope(struct tuple_update *update, const char *tuple_data,
const char *tuple_data_end, uint32_t field_count)
{
- update->rope = rope_new(update_field_split, update, update_alloc,
- update_free, update->alloc_ctx);
+ update->rope = rope_new(update->region);
if (update->rope == NULL)
return -1;
/* Initialize the rope with the old tuple. */
struct update_field *first = (struct update_field *)
- update_alloc(update->alloc_ctx, sizeof(*first));
+ update_alloc(update->region, sizeof(*first));
if (first == NULL)
return -1;
const char *field = tuple_data;
@@ -864,8 +856,7 @@ update_calc_tuple_length(struct tuple_update *update)
rope_iter_create(&it, update->rope);
for (node = rope_iter_start(&it); node; node = rope_iter_next(&it)) {
- struct update_field *field =
- (struct update_field *) rope_leaf_data(node);
+ struct update_field *field = rope_leaf_data(node);
uint32_t field_len = (field->op ? field->op->new_field_len :
(uint32_t)(field->tail - field->old));
res += field_len + field->tail_len;
@@ -889,8 +880,7 @@ update_write_tuple(struct tuple_update *update, char *buffer, char *buffer_end)
rope_iter_create(&it, update->rope);
for (node = rope_iter_start(&it); node; node = rope_iter_next(&it)) {
- struct update_field *field = (struct update_field *)
- rope_leaf_data(node);
+ struct update_field *field = rope_leaf_data(node);
uint32_t field_count = rope_leaf_size(node);
const char *old_field = field->old;
struct update_op *op = field->op;
@@ -979,7 +969,7 @@ update_read_ops(struct tuple_update *update, const char *expr,
}
/* Read update operations. */
- update->ops = (struct update_op *) update_alloc(update->alloc_ctx,
+ update->ops = (struct update_op *) update_alloc(update->region,
update->op_count * sizeof(struct update_op));
if (update->ops == NULL)
return -1;
@@ -1172,7 +1162,7 @@ static void
update_init(struct tuple_update *update, int index_base)
{
memset(update, 0, sizeof(*update));
- update->alloc_ctx = &fiber()->gc;
+ update->region = &fiber()->gc;
/*
* Base field offset, e.g. 0 for C and 1 for Lua. Used only for
* error messages. All fields numbers must be zero-based!
@@ -1184,7 +1174,7 @@ const char *
update_finish(struct tuple_update *update, uint32_t *p_tuple_len)
{
uint32_t tuple_len = update_calc_tuple_length(update);
- char *buffer = (char *) update_alloc(update->alloc_ctx, tuple_len);
+ char *buffer = (char *) update_alloc(update->region, tuple_len);
if (buffer == NULL)
return NULL;
*p_tuple_len = update_write_tuple(update, buffer, buffer + tuple_len);
diff --git a/src/lib/salad/rope.c b/src/lib/salad/rope.c
index 06324ab65..5de951c78 100644
--- a/src/lib/salad/rope.c
+++ b/src/lib/salad/rope.c
@@ -1,5 +1,5 @@
/*
- * Copyright 2010-2016, Tarantool AUTHORS, please see AUTHORS file.
+ * Copyright 2010-2019, Tarantool AUTHORS, please see AUTHORS file.
*
* Redistribution and use in source and binary forms, with or
* without modification, are permitted provided that the following
@@ -42,127 +42,73 @@
*
* Author: Hans-J. Boehm (boehm at parc.xerox.com)
*/
-/*
- * This is a rope implementation which uses AVL tree
- * balancing algorithm for rope tree balance.
+#include <stdlib.h>
+
+/**
+ * This macro helps to implement some common rope functions, not
+ * depending on a specific rope, only once, in a single object
+ * file.
*/
+#define ROPE_SRC
+#define rope_data_t void *
+#define rope_ctx_t void *
#include "rope.h"
-#include <stdio.h>
-#include <string.h>
-#include <stdlib.h>
-#include <assert.h>
static inline int
-rope_node_height(struct rope_node *node)
+avl_node_height(struct avl_node *node)
{
return node ? node->height : 0;
}
-#if !defined(MAX)
-#define MAX(a, b) ((a) > (b) ? (a) : (b))
-#endif /* MAX */
-
static inline void
-rope_relink(struct rope_node *node)
+avl_node_relink(struct avl_node *node)
{
- node->tree_size = (rope_node_size(node->link[0]) +
- rope_node_size(node->link[1]) +
+ node->tree_size = (avl_node_size(node->link[0]) +
+ avl_node_size(node->link[1]) +
node->leaf_size);
- node->height = MAX(rope_node_height(node->link[0]),
- rope_node_height(node->link[1])) + 1;
-}
-
-static inline struct rope_node *
-rope_node_new(struct rope *rope, void *data, rope_size_t size)
-{
- struct rope_node *node =
- (struct rope_node *) rope->alloc(rope->alloc_ctx,
- sizeof(struct rope_node));
-
- if (node == NULL)
- return NULL;
-
- node->height = 1;
- node->tree_size = node->leaf_size = size;
- node->data = data;
- node->link[0] = node->link[1] = NULL;
-
- return node;
+ node->height = MAX(avl_node_height(node->link[0]),
+ avl_node_height(node->link[1])) + 1;
}
-void
-rope_clear(struct rope *rope)
+static inline struct avl_node *
+avl_rotate_single(struct avl_node *parent, int direction)
{
- struct rope_node *it = rope->root;
- struct rope_node *save;
-
- /* Destruction by rotation */
- while (it != NULL) {
- if (it->link[0] == NULL) {
- /* Remove node */
- save = it->link[1];
- rope->free(rope->alloc_ctx, it);
- } else {
- /* Rotate right */
- save = it->link[0];
- it->link[0] = save->link[1];
- save->link[1] = it;
- }
- it = save;
- }
- rope->root = NULL;
-}
-
-static struct rope_node *
-rope_node_split(struct rope *rope, struct rope_node *node, rope_size_t offset)
-{
- rope_size_t old_size = node->leaf_size;
- node->leaf_size = offset;
-
- void *data = rope->split(rope->split_ctx, node->data, old_size, offset);
- return rope_node_new(rope, data, old_size - offset);
-}
-
-static inline struct rope_node *
-avl_rotate_single(struct rope_node *parent, int direction)
-{
- struct rope_node *save = parent->link[!direction];
+ struct avl_node *save = parent->link[!direction];
parent->link[!direction] = save->link[direction];
save->link[direction] = parent;
/* First relink the parent, since it's now a child. */
- rope_relink(parent);
- rope_relink(save);
+ avl_node_relink(parent);
+ avl_node_relink(save);
return save;
}
-static inline struct rope_node *
-avl_rotate_double(struct rope_node *parent, int direction)
+static inline struct avl_node *
+avl_rotate_double(struct avl_node *parent, int direction)
{
parent->link[!direction] =
avl_rotate_single(parent->link[!direction], !direction);
return avl_rotate_single(parent, direction);
}
-/** Rebalance the tree. */
-static inline void
-avl_rebalance_after_insert(struct rope_node ***path,
- struct rope_node ***p_end, int insert_height)
+void
+avl_rebalance_after_insert(struct avl_node ***path, struct avl_node ***p_end,
+ int insert_height)
{
while (p_end > path) {
- struct rope_node *left = **p_end--;
- struct rope_node *parent = **p_end;
+ struct avl_node *left = **p_end--;
+ struct avl_node *parent = **p_end;
/*
* To use the same rotation functions, set mirror
* to 1 if left is right and right is left.
*/
int mirror = left != parent->link[0];
- struct rope_node *right = parent->link[!mirror];
+ struct avl_node *right = parent->link[!mirror];
- int left_height = rope_node_height(left);
- int right_height = rope_node_height(right);
+ int left_height = avl_node_height(left);
+ int right_height = avl_node_height(right);
parent->height = MAX(left_height, right_height) + 1;
/*
* Rotations flattened the tree, so there is no
@@ -179,10 +125,10 @@ avl_rebalance_after_insert(struct rope_node ***path,
* in the range -1..1 + height(new_node).
*/
if (left_height - right_height >= 2) {
- struct rope_node *l_left = left->link[mirror];
- struct rope_node *l_right = left->link[!mirror];
- int l_left_height = rope_node_height(l_left);
- int l_right_height = rope_node_height(l_right);
+ struct avl_node *l_left = left->link[mirror];
+ struct avl_node *l_right = left->link[!mirror];
+ int l_left_height = avl_node_height(l_left);
+ int l_right_height = avl_node_height(l_right);
/*
* Rotate in the direction, opposite to
* the skew. E.g. if we have two left-left
@@ -212,24 +158,20 @@ avl_rebalance_after_insert(struct rope_node ***path,
}
}
-/* This is a copy-cat of the previous loop,
- * with the exception that the heuristic to break
- * the loop is different.
- */
-static inline void
-avl_rebalance_after_delete(struct rope_node ***path,
- struct rope_node ***p_end)
+void
+avl_rebalance_after_delete(struct avl_node ***path,
+ struct avl_node ***p_end)
{
while (p_end > path) {
- struct rope_node *left = **p_end--;
- struct rope_node *parent = **p_end;
+ struct avl_node *left = **p_end--;
+ struct avl_node *parent = **p_end;
int mirror = left != parent->link[0];
- struct rope_node *right = parent->link[!mirror];
+ struct avl_node *right = parent->link[!mirror];
- int left_height = rope_node_height(left);
- int right_height = rope_node_height(right);
+ int left_height = avl_node_height(left);
+ int right_height = avl_node_height(right);
parent->height = MAX(left_height, right_height) + 1;
/*
@@ -241,10 +183,10 @@ avl_rebalance_after_delete(struct rope_node ***path,
break;
if (left_height - right_height <= -2) {
- struct rope_node *r_left = right->link[mirror];
- struct rope_node *r_right = right->link[!mirror];
- int r_left_height = rope_node_height(r_left);
- int r_right_height = rope_node_height(r_right);
+ struct avl_node *r_left = right->link[mirror];
+ struct avl_node *r_right = right->link[!mirror];
+ int r_left_height = avl_node_height(r_left);
+ int r_right_height = avl_node_height(r_right);
if (r_left_height <= r_right_height)
**p_end = avl_rotate_single(parent, mirror);
@@ -254,24 +196,17 @@ avl_rebalance_after_delete(struct rope_node ***path,
}
}
-/**
- * Find a rope node which contains the substring at offset,
- * adjusting tree size with adjust_size and saving the path
- * in path.
- *
- * @return the end of the route.
- */
-static inline struct rope_node ***
-avl_route_to_offset(struct rope_node ***path, rope_size_t *p_offset,
+struct avl_node ***
+avl_route_to_offset(struct avl_node ***path, uint32_t *p_offset,
ssize_t adjust_size)
{
- rope_size_t offset = *p_offset;
+ uint32_t offset = *p_offset;
while (**path) {
- struct rope_node *node = **path;
+ struct avl_node *node = **path;
node->tree_size += adjust_size;
- rope_size_t left_size = rope_node_size(node->link[0]);
+ uint32_t left_size = avl_node_size(node->link[0]);
if (offset < left_size) {
/* The offset lays in the left subtree. */
@@ -297,15 +232,10 @@ avl_route_to_offset(struct rope_node ***path, rope_size_t *p_offset,
return path;
}
-/**
- * Route to successor or predecessor node of the node
- * in **path. It's either the rightmost leaf of the left child
- * (previous node) or leftmost leaf of the right child.
- */
-static inline struct rope_node ***
-avl_route_to_next(struct rope_node ***path, int dir, rope_ssize_t adjust_size)
+struct avl_node ***
+avl_route_to_next(struct avl_node ***path, int dir, int32_t adjust_size)
{
- struct rope_node *node = **path;
+ struct avl_node *node = **path;
*++path = &node->link[dir];
while (**path) {
node = **path;
@@ -315,198 +245,6 @@ avl_route_to_next(struct rope_node ***path, int dir, rope_ssize_t adjust_size)
return path;
}
-/**
- * A new node is always inserted at a leaf position.
- * If insertion unbalances the tree, the rebalancing
- * procedure may put the node into an intermediate position.
- *
- * While traversing the tree, we simultaneously update
- * tree sizes of all intermediate nodes, taking into account
- * the size of the new node.
- *
- * When insertion offset falls at the middle of an existing node,
- * we truncate this node and attach its tail to the left leaf
- * of the new node. This trim operation doesn't decrease the old
- * subtree height, and, while it does change subtree size
- * temporarily, as long as we attach the new node to the right
- * subtree of the truncated node, truncation has no effect on the
- * tree size either.
- *
- * Rebalancing, when it occurs, will correctly update subtree
- * heights and sizes of all modified nodes.
- */
-int
-rope_insert(struct rope *rope, rope_size_t offset, void *data, rope_size_t size)
-{
- if (offset > rope_size(rope))
- offset = rope_size(rope);
-
- assert(size);
-
- struct rope_node *new_node = rope_node_new(rope, data, size);
-
- if (new_node == NULL)
- return -1;
-
- struct rope_node **path[ROPE_HEIGHT_MAX];
- path[0] = &rope->root;
-
- struct rope_node ***p_end = avl_route_to_offset(path, &offset, size);
- if (**p_end != NULL) {
- /*
- * The offset is inside an existing
- * substring in the rope. If offset is 0,
- * then insert the new node at the rightmost leaf
- * of the left child. Otherwise, cut the tail of
- * the substring, make it a prefix of the inserted
- * string, and insert the result at the leftmost
- * leaf of the right child.
- */
- if (offset != 0) {
- struct rope_node *split_node;
- split_node = rope_node_split(rope, **p_end, offset);
- if (split_node == NULL)
- return -1;
- split_node->link[0] = new_node;
- split_node->height++;
- split_node->tree_size += new_node->tree_size;
- new_node = split_node;
- }
- p_end = avl_route_to_next(p_end, offset != 0,
- new_node->tree_size);
- }
- **p_end = new_node;
- avl_rebalance_after_insert(path, p_end, new_node->height);
- return 0;
-}
-
-/** Make sure there is a rope node at the given offset. */
-struct rope_node *
-rope_extract_node(struct rope *rope, rope_size_t offset)
-{
- assert(offset < rope_size(rope));
-
- struct rope_node **path[ROPE_HEIGHT_MAX];
- path[0] = &rope->root;
-
- struct rope_node ***p_end = avl_route_to_offset(path, &offset, 0);
- if (offset == 0)
- return **p_end;
- struct rope_node *new_node = rope_node_split(rope, **p_end, offset);
- if (new_node == NULL)
- return NULL;
- p_end = avl_route_to_next(p_end, 1, new_node->tree_size);
- **p_end = new_node;
- avl_rebalance_after_insert(path, p_end, new_node->height);
- return new_node;
-}
-
-/**
- * Erase a single element from the rope.
- * This is a straightforward implementation for a single-element
- * deletion from a rope. A generic cut from a rope involves
- * 2 tree splits and one merge.
- *
- * When deleting a single element, 3 cases are possible:
- * - offset falls at a node with a single element. In this
- * case we perform a normal AVL tree delete.
- * - offset falls at the end or the beginning of an existing node
- * with leaf_size > 1. In that case we trim the existing node
- * and return.
- * - offset falls inside an existing node. In that case
- * we split the existing node at offset, and insert the tail.
- *
- * The implementation is a copycat of rope_insert(). If you're
- * trying to understand the code, it's recommended to start
- * from rope_insert().
- */
-int
-rope_erase(struct rope *rope, rope_size_t offset)
-{
- assert(offset < rope_size(rope));
-
- struct rope_node **path[ROPE_HEIGHT_MAX];
- path[0] = &rope->root;
-
- struct rope_node ***p_end = avl_route_to_offset(path, &offset, -1);
-
- struct rope_node *node = **p_end;
-
- if (node->leaf_size > 1) {
- /* Check if we can simply trim the node. */
- if (offset == 0) {
- /* Cut the head. */
- node->data = rope->split(rope->split_ctx, node->data,
- node->leaf_size, 1);
- node->leaf_size -= 1;
- return 0;
- }
- rope_size_t size = node->leaf_size;
- /* Cut the tail */
- void *next = rope->split(rope->split_ctx, node->data,
- node->leaf_size, offset);
- node->leaf_size = offset;
- if (offset == size - 1)
- return 0; /* Trimmed the tail, nothing else to do */
- /*
- * Offset falls inside a substring. Erase the
- * first field and insert the tail.
- */
- next = rope->split(rope->split_ctx, next, size - offset, 1);
- struct rope_node *new_node =
- rope_node_new(rope, next, size - offset - 1);
- if (new_node == NULL)
- return -1;
- /* Trim the old node. */
- p_end = avl_route_to_next(p_end, 1, new_node->tree_size);
- **p_end = new_node;
- avl_rebalance_after_insert(path, p_end, new_node->height);
- return 0;
- }
- /* We need to delete the node. */
- assert(offset == 0);
- int direction;
- if (node->link[0] != NULL && node->link[1] != NULL) {
- /*
- * The node has two non-NULL leaves. We can't
- * simply delete the node since in that case we
- * won't know what to do with one of the leaves.
- * Instead of deleting the node, store in it data
- * from the rightmost node in the left subtree, or
- * the leftmost node in the right subtree,
- * (depending on which subtree is taller), and
- * delete this leftmost/rightmost node instead.
- */
- struct rope_node *save = node;
- direction = node->link[1]->height > node->link[0]->height;
- p_end = avl_route_to_next(p_end, direction, 0) - 1;
- node = **p_end;
- /* Move the data pointers. */
- save->data = node->data;
- save->leaf_size = node->leaf_size;
- /*
- * Now follow the path again and update tree_size
- * in the parents of the moved child.
- */
- save = save->link[direction];
- while (save != node) {
- save->tree_size -= node->leaf_size;
- save = save->link[!direction];
- }
- } else {
- /*
- * Left or right subtree are NULL, so we
- * can simply put the non-NULL leaf in place
- * of the parent.
- */
- direction = node->link[0] == NULL;
- }
- **p_end = node->link[direction];
- rope->free(rope, node);
- avl_rebalance_after_delete(path, p_end);
- return 0;
-}
-
/**
* Traverse left until the left subtree is NULL,
* save the path in iter->path.
@@ -515,7 +253,7 @@ rope_erase(struct rope *rope, rope_size_t offset)
* not-NULL node.
*/
static inline void
-rope_iter_down_to_leaf(struct rope_iter *it)
+avl_iter_down_to_leaf(struct avl_iter *it)
{
while (it->top[0]->link[0] != NULL) {
it->top[1] = it->top[0]->link[0];
@@ -523,24 +261,24 @@ rope_iter_down_to_leaf(struct rope_iter *it)
}
}
-struct rope_node *
-rope_iter_start(struct rope_iter *it)
+struct avl_node *
+avl_iter_start(struct avl_iter *it)
{
it->top = it->path;
it->top[0] = it->rope->root;
if (it->top[0] != NULL)
- rope_iter_down_to_leaf(it);
+ avl_iter_down_to_leaf(it);
return it->top[0];
}
-struct rope_node *
-rope_iter_next(struct rope_iter *it)
+struct avl_node *
+avl_iter_next(struct avl_iter *it)
{
if (it->top[0]->link[1] != NULL) {
it->top[1] = it->top[0]->link[1];
it->top++;
- rope_iter_down_to_leaf(it);
+ avl_iter_down_to_leaf(it);
} else {
/*
* Right subtree is NULL. Left subtree is fully
@@ -569,96 +307,25 @@ rope_iter_next(struct rope_iter *it)
return *it->top;
}
-/** Apply visit_leaf function to every rope leaf. */
void
-rope_traverse(struct rope *rope, void (*visit_leaf)(void *, size_t))
+avl_iter_check(struct avl_iter *iter)
{
- struct rope_iter iter;
- rope_iter_create(&iter, rope);
-
- struct rope_node *leaf;
-
- for (leaf = rope_iter_start(&iter);
- leaf != NULL;
- leaf = rope_iter_next(&iter)) {
-
- visit_leaf(leaf->data, leaf->leaf_size);
- }
-}
-
-void
-rope_check(struct rope *rope)
-{
- struct rope_iter iter;
- rope_iter_create(&iter, rope);
-
- struct rope_node *node;
-
- for (node = rope_iter_start(&iter);
- node != NULL;
- node = rope_iter_next(&iter)) {
+ for (struct avl_node *node = avl_iter_start(iter); node != NULL;
+ node = avl_iter_next(iter)) {
assert(node->leaf_size != 0);
- assert(node->tree_size == rope_node_size(node->link[0])
- + rope_node_size(node->link[1]) + node->leaf_size);
+ assert(node->tree_size == avl_node_size(node->link[0])
+ + avl_node_size(node->link[1]) + node->leaf_size);
- assert(node->height == (MAX(rope_node_height(node->link[0]),
- rope_node_height(node->link[1])) + 1));
+ assert(node->height == (MAX(avl_node_height(node->link[0]),
+ avl_node_height(node->link[1])) + 1));
if (node->leaf_size == 0 ||
- node->tree_size != (rope_node_size(node->link[0]) +
- rope_node_size(node->link[1]) +
+ node->tree_size != (avl_node_size(node->link[0]) +
+ avl_node_size(node->link[1]) +
node->leaf_size) ||
- node->height != MAX(rope_node_height(node->link[0]),
- rope_node_height(node->link[1])) + 1)
+ node->height != MAX(avl_node_height(node->link[0]),
+ avl_node_height(node->link[1])) + 1)
abort();
}
}
-
-static void
-rope_node_print(struct rope_node *node,
- void (*print)(void *, size_t),
- const char *prefix, int dir)
-{
- const char *conn[] = { "┌──", "└──" };
-
- const char *padding[] = { "│ ", " " };
-
- rope_size_t child_prefix_len = strlen(prefix) + strlen(padding[0]) + 1;
- char *child_prefix = malloc(child_prefix_len);
-
- if (node && (node->link[0] || node->link[1])) {
- snprintf(child_prefix, child_prefix_len - 1,
- "%s%s", prefix, padding[!dir]);
- rope_node_print(node->link[0], print, child_prefix, 0);
- }
-
- snprintf(child_prefix, child_prefix_len - 1, "%s%s",
- prefix, padding[dir]);
- printf("%s%s", prefix, conn[dir]);
-
- if (node == NULL) {
- printf("nil\n");
- } else {
-
- printf("{ len = %zu, height = %d, data = '",
- (size_t) node->leaf_size, node->height);
- print(node->data, node->leaf_size);
- printf("'}\n");
-
- if (node->link[0] || node->link[1])
- rope_node_print(node->link[1], print, child_prefix, 1);
- }
-
- free(child_prefix);
-}
-
-void
-rope_pretty_print(struct rope *rope, void (*print_leaf)(void *, size_t))
-{
- printf("size = %zu\nstring = '", (size_t) rope_size(rope));
- rope_traverse(rope, print_leaf);
- printf("'\n");
- rope_node_print(rope->root, print_leaf, "", true);
- printf("\n");
-}
diff --git a/src/lib/salad/rope.h b/src/lib/salad/rope.h
index c19f0e319..f38ac0e79 100644
--- a/src/lib/salad/rope.h
+++ b/src/lib/salad/rope.h
@@ -1,7 +1,5 @@
-#ifndef TARANTOOL_LIB_SALAD_ROPE_H_INCLUDED
-#define TARANTOOL_LIB_SALAD_ROPE_H_INCLUDED
/*
- * Copyright 2010-2016, Tarantool AUTHORS, please see AUTHORS file.
+ * Copyright 2010-2019, Tarantool AUTHORS, please see AUTHORS file.
*
* Redistribution and use in source and binary forms, with or
* without modification, are permitted provided that the following
@@ -30,49 +28,161 @@
* THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*/
+/*
+ * Copyright (c) 1993-1994 by Xerox Corporation. All rights reserved.
+ *
+ * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
+ * OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
+ *
+ * Permission is hereby granted to use or copy this program
+ * for any purpose, provided the above notices are retained on all copies.
+ * Permission to modify the code and to distribute modified code is granted,
+ * provided the above notices are retained, and a notice that the code was
+ * modified is included with the above copyright notice.
+ *
+ * Author: Hans-J. Boehm (boehm at parc.xerox.com)
+ */
+/*
+ * This is a rope implementation which uses AVL tree
+ * balancing algorithm for rope tree balance.
+ */
#include <stdint.h>
-#include <stddef.h>
#include <stdbool.h>
+#include <stdio.h>
+#include <assert.h>
#if defined(__cplusplus)
extern "C" {
#endif /* defined(__cplusplus) */
+#ifndef MAX
+#define NEED_UNDEF_MAX
+#define MAX(a, b) ((a) > (b) ? (a) : (b))
+#endif /* MAX */
+
+/** {{{ AVL private API */
+
+struct avl_node;
+struct avl_iter;
+
+void
+avl_rebalance_after_insert(struct avl_node ***path,
+ struct avl_node ***p_end, int insert_height);
+
+void
+avl_rebalance_after_delete(struct avl_node ***path,
+ struct avl_node ***p_end);
+
+/**
+ * Find a rope node which contains the substring at @a p_offset,
+ * adjusting tree size with @a adjust_size and saving the path in
+ * @a path.
+ * @return The end of the route.
+ */
+struct avl_node ***
+avl_route_to_offset(struct avl_node ***path, uint32_t *p_offset,
+ ssize_t adjust_size);
+
+/**
+ * Route to successor or predecessor node of the node in @a path.
+ * It's either the rightmost leaf of the left child (previous
+ * node) or leftmost leaf of the right child.
+ */
+struct avl_node ***
+avl_route_to_next(struct avl_node ***path, int dir,
+ int32_t adjust_size);
+
+struct avl_node *
+avl_iter_start(struct avl_iter *it);
+
+struct avl_node *
+avl_iter_next(struct avl_iter *it);
+
+void
+avl_iter_check(struct avl_iter *iter);
+
+/** }}} AVL private API */
+
+/**
+ * Needed definitions:
+ *
+ * rope_name, optional
+ * rope_data_t
+ * rope_ctx_t
+ * ROPE_SPLIT_F
+ * ROPE_ALLOC_F
+ * ROPE_FREE_F, optional
+ */
+
+#if defined(ROPE_SRC)
+ #define rope_api(x) avl_##x
+#elif defined(rope_name)
+ #define rope_api(x) rope_##rope_name##_##x
+ #define rope rope_##rope_name
+#else
+ #define rope_api(x) rope_##x
+#endif
+
+#ifndef ROPE_FREE_F
+ #define ROPE_FREE(a, b) do { (void) a; (void) b; } while(0)
+#else
+ #define ROPE_FREE(a, b) ROPE_FREE_F(a, b)
+#endif
+
+#define rope_node rope_api(node)
+#define rope_node_size rope_api(node_size)
+#define rope_leaf_size rope_api(leaf_size)
+#define rope_leaf_data rope_api(leaf_data)
+#define rope_iter rope_api(iter)
+#define rope_create rope_api(create)
+#define rope_new rope_api(new)
+#define rope_size rope_api(size)
+#define rope_clear rope_api(clear)
+#define rope_delete rope_api(delete)
+#define rope_node_new rope_api(node_new)
+#define rope_node_split rope_api(node_split)
+#define rope_insert rope_api(insert)
+#define rope_append rope_api(append)
+#define rope_extract_node rope_api(extract_node)
+#define rope_extract rope_api(extract)
+#define rope_erase rope_api(erase)
+#define rope_iter_create rope_api(iter_create)
+#define rope_iter_new rope_api(iter_new)
+#define rope_iter_start rope_api(iter_start)
+#define rope_iter_next rope_api(iter_next)
+#define rope_iter_delete rope_api(iter_delete)
+#define rope_traverse rope_api(traverse)
+#define rope_check rope_api(check)
+#define rope_node_print rope_api(node_print)
+#define rope_pretty_print rope_api(pretty_print)
+
typedef uint32_t rope_size_t;
typedef int32_t rope_ssize_t;
-typedef void *(*rope_split_func)(void *, void *, size_t, size_t);
-typedef void *(*rope_alloc_func)(void *, size_t);
-typedef void (*rope_free_func)(void *, void *);
/** Tallest allowable tree, 1.44*log(2^32) */
-enum { ROPE_HEIGHT_MAX = 46 };
+#define ROPE_HEIGHT_MAX 46
struct rope_node {
- /** Node height, see rope_node_height(), used for AVL balance. */
+ /**
+ * Node height, see avl_node_height(), used for AVL
+ * balance.
+ */
int height;
/** Subtree size. */
rope_size_t tree_size;
/* Substring size. */
rope_size_t leaf_size;
- /* Substring. */
- void *data;
/* Left (0) and right (1) links */
struct rope_node *link[2];
+ /* Substring. */
+ rope_data_t data;
};
struct rope {
/** Top of the tree */
struct rope_node *root;
- /** Memory management context. */
- void *alloc_ctx;
- /** Get a sequence tail, given offset. */
- rope_split_func split;
- /** Split function context. */
- void *split_ctx;
- /** Allocate memory (context, size). */
- void *(*alloc)(void *, size_t);
- /** Free memory (context, pointer) */
- void (*free)(void *, void *);
+ /** Rope context. */
+ rope_ctx_t ctx;
};
struct rope_iter {
@@ -96,7 +206,7 @@ rope_leaf_size(struct rope_node *node)
return node->leaf_size;
}
-static inline void *
+static inline rope_data_t
rope_leaf_data(struct rope_node *node)
{
return node->data;
@@ -108,78 +218,178 @@ rope_size(struct rope *rope)
return rope_node_size(rope->root);
}
+/**
+ * Everything below is not needed in the rope's own source file,
+ * so it is macrosed out.
+ */
+#ifndef ROPE_SRC
+
/** Initialize an empty rope. */
static inline void
-rope_create(struct rope *rope, rope_split_func split_func, void *split_ctx,
- rope_alloc_func alloc_func, rope_free_func free_func,
- void *alloc_ctx)
+rope_create(struct rope *rope, rope_ctx_t ctx)
{
rope->root = NULL;
- rope->split = split_func;
- rope->split_ctx = split_ctx;
- rope->alloc = alloc_func;
- rope->free = free_func;
- rope->alloc_ctx = alloc_ctx;
+ rope->ctx = ctx;
}
/** Create a new empty rope.
- * @param split_func a function which returns
- * a pointer to substring
- * given an offset. Used
- * to split substrings when
- * inserting into a rope.
- * @param alloc_func used to allocate memory
- * @param free_func used to free memory
* @param alloc_ctx allocator context
*
* @return an empty rope, or NULL if failed
* to allocate memory
*/
static inline struct rope *
-rope_new(rope_split_func split_func, void *split_ctx,
- rope_alloc_func alloc_func, rope_free_func free_func, void *alloc_ctx)
+rope_new(rope_ctx_t ctx)
{
- struct rope *rope= (struct rope *) alloc_func(alloc_ctx,
- sizeof(struct rope));
- if (rope == NULL)
- return NULL;
- rope_create(rope, split_func, split_ctx, alloc_func, free_func, alloc_ctx);
+ struct rope *rope = (struct rope *) ROPE_ALLOC_F(ctx, sizeof(*rope));
+ if (rope != NULL)
+ rope_create(rope, ctx);
return rope;
}
-
/** Delete rope contents. Can also be used
* to free a rope which is allocated on stack.
* Doesn't delete rope substrings, only
* rope nodes.
*/
-void
-rope_clear(struct rope *rope);
+static void
+rope_clear(struct rope *rope)
+{
+#ifdef ROPE_FREE_F
+ struct rope_node *it = rope->root;
+ struct rope_node *save;
+
+ /* Destruction by rotation */
+ while (it != NULL) {
+ if (it->link[0] == NULL) {
+ /* Remove node */
+ save = it->link[1];
+ ROPE_FREE(rope->ctx, it);
+ } else {
+ /* Rotate right */
+ save = it->link[0];
+ it->link[0] = save->link[1];
+ save->link[1] = it;
+ }
+ it = save;
+ }
+#endif /* ROPE_FREE_F */
+ rope->root = NULL;
+}
/** Delete a rope allocated with rope_new() */
static inline void
rope_delete(struct rope *rope)
{
rope_clear(rope);
- rope->free(rope->alloc_ctx, rope);
+ ROPE_FREE(rope->ctx, rope);
+}
+
+static inline struct rope_node *
+rope_node_new(struct rope *rope, rope_data_t data, rope_size_t size)
+{
+ struct rope_node *node =
+ (struct rope_node *) ROPE_ALLOC_F(rope->ctx, sizeof(*node));
+ if (node == NULL)
+ return NULL;
+ node->height = 1;
+ node->tree_size = node->leaf_size = size;
+ node->data = data;
+ node->link[0] = node->link[1] = NULL;
+
+ return node;
+}
+
+static inline struct rope_node *
+rope_node_split(struct rope *rope, struct rope_node *node, rope_size_t offset)
+{
+ rope_size_t old_size = node->leaf_size;
+ node->leaf_size = offset;
+
+ rope_data_t data = ROPE_SPLIT_F(rope->ctx, node->data, old_size,
+ offset);
+
+ return rope_node_new(rope, data, old_size - offset);
}
-/** Insert a substring into a rope at the given
- * offset.
- * If offset is greater than rope size, insertion
- * happens at the end.
+/**
+ * Insert a substring into a rope at the given offset. If offset
+ * is greater than rope size, insertion happens at the end. A new
+ * node is always inserted at a leaf position. If insertion
+ * unbalances the tree, the rebalancing procedure may put the node
+ * into an intermediate position.
+ *
+ * While traversing the tree, we simultaneously update tree sizes
+ * of all intermediate nodes, taking into account the size of the
+ * new node.
+ *
+ * When insertion offset falls at the middle of an existing node,
+ * we truncate this node and attach its tail to the left leaf of
+ * the new node. This trim operation doesn't decrease the old
+ * subtree height, and, while it does change subtree size
+ * temporarily, as long as we attach the new node to the right
+ * subtree of the truncated node, truncation has no effect on the
+ * tree size either.
*
- * @retval 0 success
- * @retval -1 failed to allocate memory for a new
- * tree node
+ * Rebalancing, when it occurs, will correctly update subtree
+ * heights and sizes of all modified nodes.
+ *
+ * @retval 0 Success.
+ * @retval -1 Memory error.
*/
-int
-rope_insert(struct rope *rope, rope_size_t offset, void *data,
- rope_size_t size);
+static int
+rope_insert(struct rope *rope, rope_size_t offset, rope_data_t data,
+ rope_size_t size)
+{
+ if (offset > rope_size(rope))
+ offset = rope_size(rope);
+
+ assert(size);
+
+ struct rope_node *new_node = rope_node_new(rope, data, size);
+
+ if (new_node == NULL)
+ return -1;
+
+ struct rope_node **path[ROPE_HEIGHT_MAX];
+ path[0] = &rope->root;
+
+ struct rope_node ***p_end = (struct rope_node ***)
+ avl_route_to_offset((struct avl_node ***) path, &offset, size);
+ if (**p_end != NULL) {
+ /*
+ * The offset is inside an existing
+ * substring in the rope. If offset is 0,
+ * then insert the new node at the rightmost leaf
+ * of the left child. Otherwise, cut the tail of
+ * the substring, make it a prefix of the inserted
+ * string, and insert the result at the leftmost
+ * leaf of the right child.
+ */
+ if (offset != 0) {
+ struct rope_node *split_node;
+ split_node = rope_node_split(rope, **p_end, offset);
+ if (split_node == NULL)
+ return -1;
+ split_node->link[0] = new_node;
+ split_node->height++;
+ split_node->tree_size += new_node->tree_size;
+ new_node = split_node;
+ }
+ p_end = (struct rope_node ***)
+ avl_route_to_next((struct avl_node ***) p_end,
+ offset != 0, new_node->tree_size);
+ }
+ **p_end = new_node;
+ avl_rebalance_after_insert((struct avl_node ***) path,
+ (struct avl_node ***) p_end,
+ new_node->height);
+ return 0;
+}
/** Append a substring at rope tail. */
static inline int
-rope_append(struct rope *rope, void *data, size_t size)
+rope_append(struct rope *rope, rope_data_t data, size_t size)
{
return rope_insert(rope, rope_size(rope), data, size);
}
@@ -191,23 +401,149 @@ rope_append(struct rope *rope, void *data, size_t size)
* @retval NULL failed to allocate memory for a new
* tree node
*/
-struct rope_node *
-rope_extract_node(struct rope *rope, rope_size_t offset);
+static struct rope_node *
+rope_extract_node(struct rope *rope, rope_size_t offset)
+{
+ assert(offset < rope_size(rope));
+
+ struct rope_node **path[ROPE_HEIGHT_MAX];
+ path[0] = &rope->root;
-static inline void *
+ struct rope_node ***p_end = (struct rope_node ***)
+ avl_route_to_offset((struct avl_node ***) path, &offset, 0);
+ if (offset == 0)
+ return **p_end;
+ struct rope_node *new_node = rope_node_split(rope, **p_end, offset);
+ if (new_node == NULL)
+ return NULL;
+ p_end = (struct rope_node ***)
+ avl_route_to_next((struct avl_node ***) p_end, 1,
+ new_node->tree_size);
+ **p_end = new_node;
+ avl_rebalance_after_insert((struct avl_node ***) path,
+ (struct avl_node ***) p_end,
+ new_node->height);
+ return new_node;
+}
+
+static inline rope_data_t
rope_extract(struct rope *rope, rope_size_t offset)
{
return rope_leaf_data(rope_extract_node(rope, offset));
}
/**
- * Erase a single element from a rope at the given
- * offset.
+ * Erase a single element from the rope. This is a straightforward
+ * implementation for a single-element deletion from a rope. A
+ * generic cut from a rope involves 2 tree splits and one merge.
+ *
+ * When deleting a single element, 3 cases are possible:
+ * - offset falls at a node with a single element. In this case we
+ * perform a normal AVL tree delete.
+ * - offset falls at the end or the beginning of an existing node
+ * with leaf_size > 1. In that case we trim the existing node
+ * and return.
+ * - offset falls inside an existing node. In that case we split
+ * the existing node at offset, and insert the tail.
*
- * @pre offset < rope_size(rope)
+ * The implementation is a copycat of rope_insert(). If you're
+ * trying to understand the code, it's recommended to start from
+ * rope_insert().
*/
-int
-rope_erase(struct rope *rope, rope_size_t offset);
+static inline int
+rope_erase(struct rope *rope, rope_size_t offset)
+{
+ assert(offset < rope_size(rope));
+
+ struct rope_node **path[ROPE_HEIGHT_MAX];
+ path[0] = &rope->root;
+
+ struct rope_node ***p_end = (struct rope_node ***)
+ avl_route_to_offset((struct avl_node ***) path, &offset, -1);
+
+ struct rope_node *node = **p_end;
+
+ if (node->leaf_size > 1) {
+ /* Check if we can simply trim the node. */
+ if (offset == 0) {
+ /* Cut the head. */
+ node->data = ROPE_SPLIT_F(rope->ctx, node->data,
+ node->leaf_size, 1);
+ node->leaf_size -= 1;
+ return 0;
+ }
+ rope_size_t size = node->leaf_size;
+ /* Cut the tail */
+ rope_data_t next = ROPE_SPLIT_F(rope->ctx, node->data,
+ node->leaf_size, offset);
+ node->leaf_size = offset;
+ if (offset == size - 1)
+ return 0; /* Trimmed the tail, nothing else to do */
+ /*
+ * Offset falls inside a substring. Erase the
+ * first field and insert the tail.
+ */
+ next = ROPE_SPLIT_F(rope->ctx, next, size - offset, 1);
+ struct rope_node *new_node =
+ rope_node_new(rope, next, size - offset - 1);
+ if (new_node == NULL)
+ return -1;
+ /* Trim the old node. */
+ p_end = (struct rope_node ***)
+ avl_route_to_next((struct avl_node ***) p_end, 1,
+ new_node->tree_size);
+ **p_end = new_node;
+ avl_rebalance_after_insert((struct avl_node ***) path,
+ (struct avl_node ***) p_end,
+ new_node->height);
+ return 0;
+ }
+ /* We need to delete the node. */
+ assert(offset == 0);
+ int direction;
+ if (node->link[0] != NULL && node->link[1] != NULL) {
+ /*
+ * The node has two non-NULL leaves. We can't
+ * simply delete the node since in that case we
+ * won't know what to do with one of the leaves.
+ * Instead of deleting the node, store in it data
+ * from the rightmost node in the left subtree, or
+ * the leftmost node in the right subtree,
+ * (depending on which subtree is taller), and
+ * delete this leftmost/rightmost node instead.
+ */
+ struct rope_node *save = node;
+ direction = node->link[1]->height > node->link[0]->height;
+ p_end = (struct rope_node ***)
+ avl_route_to_next((struct avl_node ***) p_end,
+ direction, 0) - 1;
+ node = **p_end;
+ /* Move the data pointers. */
+ save->data = node->data;
+ save->leaf_size = node->leaf_size;
+ /*
+ * Now follow the path again and update tree_size
+ * in the parents of the moved child.
+ */
+ save = save->link[direction];
+ while (save != node) {
+ save->tree_size -= node->leaf_size;
+ save = save->link[!direction];
+ }
+ } else {
+ /*
+ * Left or right subtree are NULL, so we
+ * can simply put the non-NULL leaf in place
+ * of the parent.
+ */
+ direction = node->link[0] == NULL;
+ }
+ **p_end = node->link[direction];
+ ROPE_FREE(rope->ctx, node);
+ avl_rebalance_after_delete((struct avl_node ***) path,
+ (struct avl_node ***) p_end);
+ return 0;
+}
/** Initialize an iterator. */
static inline void
@@ -220,12 +556,10 @@ rope_iter_create(struct rope_iter *it, struct rope *rope)
static inline struct rope_iter *
rope_iter_new(struct rope *rope)
{
- struct rope_iter *it = (struct rope_iter *)
- rope->alloc(rope->alloc_ctx, sizeof(struct rope_iter));
-
- if (it == NULL)
- return NULL;
- rope_iter_create(it, rope);
+ struct rope_iter *it =
+ (struct rope_iter *) ROPE_ALLOC_F(rope->ctx, sizeof(*it));
+ if (it != NULL)
+ rope_iter_create(it, rope);
return it;
}
@@ -233,8 +567,11 @@ rope_iter_new(struct rope *rope)
* Begin iteration.
* @retval NULL the rope is empty
*/
-struct rope_node *
-rope_iter_start(struct rope_iter *it);
+static inline struct rope_node *
+rope_iter_start(struct rope_iter *it)
+{
+ return (struct rope_node *) avl_iter_start((struct avl_iter *) it);
+}
/**
* Advance to the next rope node.
@@ -243,30 +580,138 @@ rope_iter_start(struct rope_iter *it);
* has advanced beyond the last
* node.
*/
-struct rope_node *
-rope_iter_next(struct rope_iter *it);
+static struct rope_node *
+rope_iter_next(struct rope_iter *it)
+{
+ return (struct rope_node *) avl_iter_next((struct avl_iter *) it);
+}
/** Free iterator. */
static inline void
rope_iter_delete(struct rope_iter *it)
{
- it->rope->free(it->rope->alloc_ctx, it);
+ ROPE_FREE(it->rope->ctx, it);
}
/** Apply visit_leaf function to every rope leaf. */
-void
-rope_traverse(struct rope *rope, void (*visit_leaf)(void *, size_t));
+static void
+rope_traverse(struct rope *rope, void (*visit_leaf)(rope_data_t, size_t))
+{
+ struct rope_iter iter;
+ rope_iter_create(&iter, rope);
+
+ struct rope_node *leaf;
+
+ for (leaf = rope_iter_start(&iter);
+ leaf != NULL;
+ leaf = rope_iter_next(&iter)) {
+
+ visit_leaf(leaf->data, leaf->leaf_size);
+ }
+}
/** Check AVL tree consistency. */
-void
-rope_check(struct rope *rope);
+static inline void
+rope_check(struct rope *rope)
+{
+ struct rope_iter iter;
+ rope_iter_create(&iter, rope);
+ avl_iter_check((struct avl_iter *) &iter);
+}
+
+static void
+rope_node_print(struct rope_node *node, void (*print)(rope_data_t, size_t),
+ const char *prefix, int dir)
+{
+ const char *conn[] = { "┌──", "└──" };
+
+ const char *padding[] = { "│ ", " " };
+
+ rope_size_t child_prefix_len = strlen(prefix) + strlen(padding[0]) + 1;
+ char *child_prefix = malloc(child_prefix_len);
+
+ if (node && (node->link[0] || node->link[1])) {
+ snprintf(child_prefix, child_prefix_len - 1,
+ "%s%s", prefix, padding[!dir]);
+ rope_node_print(node->link[0], print, child_prefix, 0);
+ }
+
+ snprintf(child_prefix, child_prefix_len - 1, "%s%s",
+ prefix, padding[dir]);
+ printf("%s%s", prefix, conn[dir]);
+
+ if (node == NULL) {
+ printf("nil\n");
+ } else {
+
+ printf("{ len = %zu, height = %d, data = '",
+ (size_t) node->leaf_size, node->height);
+ print(node->data, node->leaf_size);
+ printf("'}\n");
+
+ if (node->link[0] || node->link[1])
+ rope_node_print(node->link[1], print, child_prefix, 1);
+ }
+
+ free(child_prefix);
+}
/** Pretty print a rope. */
-void
-rope_pretty_print(struct rope *rope, void (*print_leaf)(void *, size_t));
+static inline void
+rope_pretty_print(struct rope *rope, void (*print_leaf)(rope_data_t, size_t))
+{
+ printf("size = %zu\nstring = '", (size_t) rope_size(rope));
+ rope_traverse(rope, print_leaf);
+ printf("'\n");
+ rope_node_print(rope->root, print_leaf, "", true);
+ printf("\n");
+}
+
+#ifdef NEED_UNDEF_MAX
+#undef NEED_UNDEF_MAX
+#undef MAX
+#endif
+
+#endif /* ROPE_SRC */
+
+#undef rope_node
+#undef rope_node_size
+#undef rope_leaf_size
+#undef rope_leaf_data
+#undef rope_iter
+#undef rope_create
+#undef rope_new
+#undef rope_size
+#undef rope_clear
+#undef rope_delete
+#undef rope_node_new
+#undef rope_node_split
+#undef rope_insert
+#undef rope_append
+#undef rope_extract_node
+#undef rope_extract
+#undef rope_erase
+#undef rope_iter_create
+#undef rope_iter_new
+#undef rope_iter_start
+#undef rope_iter_next
+#undef rope_iter_delete
+#undef rope_traverse
+#undef rope_check
+#undef rope_node_print
+#undef rope_pretty_print
+
+#undef rope
+#undef rope_api
+#undef rope_name
+#undef ROPE_HEIGHT_MAX
+#undef rope_ctx_t
+#undef rope_data_t
+#undef ROPE_SPLIT_F
+#undef ROPE_ALLOC_F
+#undef ROPE_FREE_F
+#undef ROPE_FREE
#if defined(__cplusplus)
}
#endif /* defined(__cplusplus) */
-
-#endif /* TARANTOOL_LIB_SALAD_ROPE_H_INCLUDED */
diff --git a/test/unit/rope.c b/test/unit/rope.c
index e19dcaa10..5ab4c51f7 100644
--- a/test/unit/rope.c
+++ b/test/unit/rope.c
@@ -1,4 +1,3 @@
-#include "salad/rope.h"
#include "unit.h"
#include "rope_common.h"
diff --git a/test/unit/rope_avl.c b/test/unit/rope_avl.c
index 9e978f46c..b095fb1a6 100644
--- a/test/unit/rope_avl.c
+++ b/test/unit/rope_avl.c
@@ -1,4 +1,3 @@
-#include "salad/rope.h"
#include "unit.h"
#include "rope_common.h"
diff --git a/test/unit/rope_basic.c b/test/unit/rope_basic.c
index b4a0e7876..d9e116292 100644
--- a/test/unit/rope_basic.c
+++ b/test/unit/rope_basic.c
@@ -1,4 +1,3 @@
-#include "salad/rope.h"
#include "unit.h"
#include "rope_common.h"
diff --git a/test/unit/rope_common.h b/test/unit/rope_common.h
index 6c52153b2..3392e87e3 100644
--- a/test/unit/rope_common.h
+++ b/test/unit/rope_common.h
@@ -3,17 +3,17 @@
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
-static inline void *
-str_getn(void *ctx, void *data, size_t size, size_t offset)
+static inline char *
+str_getn(void *ctx, char *data, size_t size, size_t offset)
{
(void) ctx;
- return (char *) data + offset;
+ return data + offset;
}
static inline void
-str_print(void *data, size_t n)
+str_print(char *data, size_t n)
{
- printf("%.*s", (int) n, (char *) data);
+ printf("%.*s", (int) n, data);
}
static inline void *
@@ -30,10 +30,39 @@ mem_free(void *data, void *ptr)
free(ptr);
}
+#define ROPE_ALLOC_F mem_alloc
+#define ROPE_FREE_F mem_free
+#define ROPE_SPLIT_F str_getn
+#define rope_data_t char *
+#define rope_ctx_t void *
+
+#include "salad/rope.h"
+
+/**
+ * Define a second rope just to check if compilation of two
+ * ropes in one object file works.
+ */
+
+static inline int *
+str_getn2(int *ctx, int *data, size_t size, size_t offset)
+{
+ (void) ctx;
+ return data + offset;
+}
+
+#define rope_name second
+#define ROPE_ALLOC_F mem_alloc
+#define ROPE_FREE_F mem_free
+#define ROPE_SPLIT_F str_getn2
+#define rope_data_t int *
+#define rope_ctx_t int *
+
+#include "salad/rope.h"
+
static inline struct rope *
test_rope_new()
{
- return rope_new(str_getn, NULL, mem_alloc, mem_free, NULL);
+ return rope_new(NULL);
}
static inline void
diff --git a/test/unit/rope_stress.c b/test/unit/rope_stress.c
index dc3f2817e..bc312d7c0 100644
--- a/test/unit/rope_stress.c
+++ b/test/unit/rope_stress.c
@@ -1,4 +1,3 @@
-#include "salad/rope.h"
#include <time.h>
#include "unit.h"
#include "rope_common.h"
@@ -10,7 +9,7 @@ test_rope_stress_small()
{
header();
- struct rope *rope = rope_new(str_getn, NULL, mem_alloc, mem_free, NULL);
+ struct rope *rope = test_rope_new();
const int iterations = 500;
int i = 0;
for (i = 0; i < iterations; ++i) {
@@ -39,7 +38,7 @@ test_rope_stress_large()
{
header();
- struct rope *rope = rope_new(str_getn, NULL, mem_alloc, mem_free, NULL);
+ struct rope *rope = test_rope_new();
const int iterations = 50000;
int i = 0;
for (i = 0; i < iterations; ++i) {
--
2.20.1 (Apple Git-117)
More information about the Tarantool-patches
mailing list