From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: From: Vladislav Shpilevoy Subject: [PATCH 2/5] rope: make rope library macro template Date: Sun, 14 Jul 2019 00:11:05 +0200 Message-Id: In-Reply-To: References: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 8bit To: tarantool-patches@freelists.org Cc: vdavydov.dev@gmail.com List-ID: Rope library stores alloc, split and free functions by pointer, that is a huge slog at performance, as any other virtual function call. There is no reason, why the rope library may not become a template, except historical ones. The patch not only removes virtual functions, but also makes rope deletion almost no-op in case if free() function is not defined. A second motivation point of that patch is that original rope structure was too big. Again, because it stored several pointers to functions. In forthcoming patches on #1261 multiple ropes can be created per each update, so it makes sense to reduce size of this structure. --- The patch is quite dubious, I agree, and ready to alternative options how to remove these alloc/free/split pointers. Talking of necessity of this patch at all - it makes rope struct 40 bytes lighter. JSON updates will create a new rope (sometimes) for each updated array inside the tuple. So I thought, that it is worth optimizing. debian/copyright | 2 +- src/box/tuple_update.c | 74 +++-- src/lib/salad/rope.c | 479 +++++-------------------------- src/lib/salad/rope.h | 617 ++++++++++++++++++++++++++++++++++------ test/unit/rope.c | 1 - test/unit/rope_avl.c | 1 - test/unit/rope_basic.c | 1 - test/unit/rope_common.h | 41 ++- test/unit/rope_stress.c | 5 +- 9 files changed, 674 insertions(+), 547 deletions(-) diff --git a/debian/copyright b/debian/copyright index a48171371..3d68dc390 100644 --- a/debian/copyright +++ b/debian/copyright @@ -218,7 +218,7 @@ Files: third_party/lua-cjson/* Copyright: 2010-2012 Mark Pulford 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 #include #include "say.h" @@ -41,7 +39,6 @@ #include "third_party/queue.h" #include #include -#include #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@parc.xerox.com) */ -/* - * This is a rope implementation which uses AVL tree - * balancing algorithm for rope tree balance. +#include + +/** + * 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 -#include -#include -#include 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@parc.xerox.com) + */ +/* + * This is a rope implementation which uses AVL tree + * balancing algorithm for rope tree balance. + */ #include -#include #include +#include +#include #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 #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,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 #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)