From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from localhost (localhost [127.0.0.1]) by turing.freelists.org (Avenir Technologies Mail Multiplex) with ESMTP id 894FD23C2D for ; Fri, 27 Apr 2018 18:36:45 -0400 (EDT) Received: from turing.freelists.org ([127.0.0.1]) by localhost (turing.freelists.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id c16-R-08DZQW for ; Fri, 27 Apr 2018 18:36:45 -0400 (EDT) Received: from smtp45.i.mail.ru (smtp45.i.mail.ru [94.100.177.105]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by turing.freelists.org (Avenir Technologies Mail Multiplex) with ESMTPS id E0D8E23B1A for ; Fri, 27 Apr 2018 18:36:44 -0400 (EDT) From: Vladislav Shpilevoy Subject: [tarantool-patches] [PATCH 3/3] rope: make rope library be C template using macros Date: Sat, 28 Apr 2018 01:36:40 +0300 Message-Id: In-Reply-To: References: MIME-Version: 1.0 In-Reply-To: References: Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 8bit Sender: tarantool-patches-bounce@freelists.org Errors-to: tarantool-patches-bounce@freelists.org Reply-To: tarantool-patches@freelists.org List-help: List-unsubscribe: List-software: Ecartis version 1.0.0 List-Id: tarantool-patches List-subscribe: List-owner: List-post: List-archive: To: tarantool-patches@freelists.org Cc: kostja@tarantool.org Rope library stores alloc, split and free functions by pointer, that is a huge slog at performance. There is no reason, why the rope library can not become a template. Inline a concrete functions on compilation instead of pointers on runtime. --- debian/copyright | 2 +- src/box/tuple_update.c | 84 ++--- src/lib/salad/CMakeLists.txt | 2 +- src/lib/salad/rope.c | 664 ------------------------------------ src/lib/salad/rope.h | 790 ++++++++++++++++++++++++++++++++++++++----- test/unit/rope.c | 1 - test/unit/rope_avl.c | 1 - test/unit/rope_basic.c | 1 - test/unit/rope_common.h | 21 +- test/unit/rope_stress.c | 5 +- 10 files changed, 766 insertions(+), 805 deletions(-) delete mode 100644 src/lib/salad/rope.c diff --git a/debian/copyright b/debian/copyright index a48171371..c56b8a246 100644 --- a/debian/copyright +++ b/debian/copyright @@ -218,7 +218,7 @@ Files: third_party/lua-cjson/* Copyright: 2010-2012 Mark Pulford 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 #include #include "say.h" @@ -41,7 +39,6 @@ #include "third_party/queue.h" #include #include -#include #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 ``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 - * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, - * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL - * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF - * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR - * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF - * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF - * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF - * SUCH DAMAGE. - */ -/* - * Copyright (c) 1993-1994 by Xerox Corporation. All rights reserved. - * - * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED - * OR IMPLIED. ANY USE IS AT YOUR OWN RISK. - * - * Permission is hereby granted to use or copy this program - * for any purpose, provided the above notices are retained on all copies. - * Permission to modify the code and to distribute modified code is granted, - * provided the above notices are retained, and a notice that the code was - * modified is included with the above copyright notice. - * - * Author: Hans-J. Boehm (boehm@parc.xerox.com) - */ -/* - * This is a rope implementation which uses AVL tree - * balancing algorithm for rope tree balance. - */ -#include "rope.h" -#include -#include -#include -#include - -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 -#include +/* + * Copyright (c) 1993-1994 by Xerox Corporation. All rights reserved. + * + * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED + * OR IMPLIED. ANY USE IS AT YOUR OWN RISK. + * + * Permission is hereby granted to use or copy this program + * for any purpose, provided the above notices are retained on all copies. + * Permission to modify the code and to distribute modified code is granted, + * provided the above notices are retained, and a notice that the code was + * modified is included with the above copyright notice. + * + * Author: Hans-J. Boehm (boehm@parc.xerox.com) + */ +/* + * This is a rope implementation which uses AVL tree + * balancing algorithm for rope tree balance. + */ #include - -#if defined(__cplusplus) -extern "C" { -#endif /* defined(__cplusplus) */ +#include +#include 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 #include #include -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 #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)