erts: Remove dead tree merging code

2 files changed, 1 insertions, 349 deletions

diff --git a/erts/emulator/beam/erl_db_catree.c b/erts/emulator/beam/erl_db_catree.c
index 1b4e5d45e7..d433a5b56e 100644
--- a/erts/emulator/beam/erl_db_catree.c
+++ b/erts/emulator/beam/erl_db_catree.c
@@ -242,30 +242,6 @@ static ERTS_INLINE Sint cmp_key_route(Eterm key,
     return CMP(key, GET_ROUTE_NODE_KEY(obj));
 }
 
-static ERTS_INLINE void push_node_dyn_array(DbTable *tb,
-                                            CATreeNodeStack *stack,
-                                            DbTableCATreeNode *node)
-{
-    int i;
-    if (stack->pos == stack->size) {
-        DbTableCATreeNode **newArray =
-            erts_db_alloc(ERTS_ALC_T_DB_STK, tb,
-                          sizeof(DbTableCATreeNode*) * (stack->size*2));
-        for (i = 0; i < stack->pos; i++) {
-            newArray[i] = stack->array[i];
-        }
-        if (stack->size > STACK_NEED) {
-            /* Dynamically allocated array that needs to be deallocated */
-            erts_db_free(ERTS_ALC_T_DB_STK, tb,
-                         stack->array,
-                         sizeof(DbTableCATreeNode *) * stack->size);
-        }
-        stack->array = newArray;
-        stack->size = stack->size*2;
-    }
-    PUSH_NODE(stack, node);
-}
-
 /*
  * Used by the split_tree function
  */
@@ -914,20 +890,6 @@ static DbTableCATreeNode *create_base_node(DbTableCATree *tb,
     return p;
 }
 
-static ERTS_INLINE
-DbTableCATreeNode *create_wlocked_base_node(DbTableCATree *tb,
-                                            TreeDbTerm* root,
-                                            Eterm lc_key)
-{
-    DbTableCATreeNode* p = create_base_node(tb, root, lc_key);
-    ethr_rwmutex_rwlock(&p->u.base.lock.rwmtx);
-#ifdef ERTS_ENABLE_LOCK_CHECK
-    erts_lc_trylock_flg(-1, &p->u.base.lock.lc, ERTS_LOCK_OPTIONS_RDWR);
-#endif
-    return p;
-}
-
-
 static ERTS_INLINE Uint sizeof_route_node(Uint key_size)
 {
     return (offsetof(DbTableCATreeNode, u.route.key.heap)
@@ -1075,126 +1037,6 @@ rightmost_route_node(DbTableCATreeNode *root)
     return prev_node;
 }
 
-static ERTS_INLINE DbTableCATreeNode*
-leftmost_base_node_and_path(DbTableCATreeNode *root, CATreeNodeStack * stack)
-{
-    DbTableCATreeNode * node = root;
-    while (!node->is_base_node) {
-        PUSH_NODE(stack, node);
-        node = GET_LEFT_ACQB(node);
-    }
-    return node;
-}
-
-static ERTS_INLINE DbTableCATreeNode*
-get_next_base_node_and_path(DbTableCATreeNode *base_node,
-                            CATreeNodeStack *stack)
-{
-    if (EMPTY_NODE(stack)) { /* The parent of b is the root */
-        return NULL;
-    } else {
-        if (GET_LEFT(TOP_NODE(stack)) == base_node) {
-            return leftmost_base_node_and_path(
-                        GET_RIGHT_ACQB(TOP_NODE(stack)),
-                        stack);
-        } else {
-            Eterm pkey =
-                TOP_NODE(stack)->u.route.key.term; /* pKey = key of parent */
-            POP_NODE(stack);
-            while (!EMPTY_NODE(stack)) {
-                if (TOP_NODE(stack)->u.route.is_valid &&
-                   cmp_key_route(pkey, TOP_NODE(stack)) <= 0) {
-                    return leftmost_base_node_and_path(GET_RIGHT_ACQB(TOP_NODE(stack)), stack);
-                } else {
-                  POP_NODE(stack);
-                }
-            }
-        }
-        return NULL;
-    }
-}
-
-static ERTS_INLINE void
-clone_stack(CATreeNodeStack *search_stack_ptr,
-            CATreeNodeStack *search_stack_copy_ptr)
-{
-    int i;
-    search_stack_copy_ptr->pos = search_stack_ptr->pos;
-    for (i = 0; i < search_stack_ptr->pos; i++) {
-        search_stack_copy_ptr->array[i] = search_stack_ptr->array[i];
-    }
-}
-
-static ERTS_INLINE DbTableCATreeBaseNode*
-find_and_lock_next_base_node_and_path(DbTable *tbl,
-                                      CATreeNodeStack **search_stack_ptr_ptr,
-                                      CATreeNodeStack **search_stack_copy_ptr_ptr,
-                                      CATreeNodeStack *locked_base_nodes_stack_ptr)
-{
-    DbTableCATreeNode *current_node;
-    DbTableCATreeBaseNode *base_node;
-    CATreeNodeStack * tmp_stack_ptr;
-
-    while (1) {
-        current_node = TOP_NODE(locked_base_nodes_stack_ptr);
-        clone_stack(*search_stack_ptr_ptr, *search_stack_copy_ptr_ptr);
-        current_node =
-            get_next_base_node_and_path(current_node, *search_stack_ptr_ptr);
-        if (current_node == NULL) {
-            return NULL;
-        }
-        base_node = &current_node->u.base;
-        rlock_base_node(base_node);
-        if (base_node->is_valid)
-            break;
-
-        /* Retry */
-        runlock_base_node(base_node);
-        /* Revert to previous state */
-        current_node = TOP_NODE(locked_base_nodes_stack_ptr);
-        tmp_stack_ptr = *search_stack_ptr_ptr;
-        *search_stack_ptr_ptr = *search_stack_copy_ptr_ptr;
-        *search_stack_copy_ptr_ptr = tmp_stack_ptr;
-    }
-
-    push_node_dyn_array(tbl, locked_base_nodes_stack_ptr, current_node);
-    return base_node;
-}
-
-static ERTS_INLINE
-void unlock_and_release_locked_base_node_stack(DbTable *tbl,
-                                               CATreeNodeStack *locked_base_nodes_stack_ptr)
-{
-    DbTableCATreeNode *current_node;
-    DbTableCATreeBaseNode *base_node;
-    int i;
-    for (i = 0; i < locked_base_nodes_stack_ptr->pos; i++) {
-        current_node = locked_base_nodes_stack_ptr->array[i];
-        base_node = &current_node->u.base;
-        if (locked_base_nodes_stack_ptr->pos > 1) {
-            base_node->lock_statistics =     /* This is not atomic which is fine as */
-                base_node->lock_statistics + /* correctness does not depend on that. */
-                ERL_DB_CATREE_LOCK_MORE_THAN_ONE_CONTRIBUTION;
-        }
-        runlock_base_node(base_node);
-    }
-    if (locked_base_nodes_stack_ptr->size > STACK_NEED) {
-        erts_db_free(ERTS_ALC_T_DB_STK, tbl,
-                     locked_base_nodes_stack_ptr->array,
-                     sizeof(DbTableCATreeNode *) * locked_base_nodes_stack_ptr->size);
-    }
-}
-
-static ERTS_INLINE
-void init_stack(CATreeNodeStack *stack,
-                DbTableCATreeNode **stack_array,
-                Uint init_size)
-{
-    stack->array = stack_array;
-    stack->pos = 0;
-    stack->size = init_size;
-}
-
 static ERTS_INLINE
 void init_tree_stack(DbTreeStack *stack,
                      TreeDbTerm **stack_array,
@@ -1205,191 +1047,6 @@ void init_tree_stack(DbTreeStack *stack,
     stack->slot = init_slot;
 }
 
-#define DEC_ROUTE_NODE_STACK_AND_ARRAY(STACK_NAME) \
-    CATreeNodeStack STACK_NAME; \
-    CATreeNodeStack * STACK_NAME##_ptr = &(STACK_NAME); \
-    DbTableCATreeNode *STACK_NAME##_array[STACK_NEED];
-
-#define DECLARE_AND_INIT_BASE_NODE_SEARCH_STACKS \
-DEC_ROUTE_NODE_STACK_AND_ARRAY(search_stack) \
-DEC_ROUTE_NODE_STACK_AND_ARRAY(search_stack_copy) \
-DEC_ROUTE_NODE_STACK_AND_ARRAY(locked_base_nodes_stack) \
-init_stack(&search_stack, search_stack_array, 0); \
-init_stack(&search_stack_copy, search_stack_copy_array, 0); \
-init_stack(&locked_base_nodes_stack, locked_base_nodes_stack_array, STACK_NEED);/* Abuse as stack array size*/
-
-/*
- * Locks and returns the base node that contains the specified key if
- * it is present. The function saves the search path to the found base
- * node in search_stack_ptr and adds the found base node to
- * locked_base_nodes_stack_ptr.
- */
-static ERTS_INLINE DbTableCATreeBaseNode *
-lock_base_node_with_key(DbTable *tbl,
-                        Eterm key,
-                        CATreeNodeStack * search_stack_ptr,
-                        CATreeNodeStack * locked_base_nodes_stack_ptr)
-{
-    int retry;
-    DbTableCATreeNode *current_node;
-    DbTableCATreeBaseNode *base_node;
-    DbTableCATree* tb = &tbl->catree;
-    do {
-        retry = 0;
-        current_node = GET_ROOT_ACQB(tb);
-        while ( ! current_node->is_base_node ) {
-            PUSH_NODE(search_stack_ptr, current_node);
-            if( cmp_key_route(key,current_node) < 0 ) {
-                current_node = GET_LEFT_ACQB(current_node);
-            } else {
-                current_node = GET_RIGHT_ACQB(current_node);
-            }
-        }
-        base_node = &current_node->u.base;
-        rlock_base_node(base_node);
-        if ( ! base_node->is_valid ) {
-            /* Retry */
-            runlock_base_node(base_node);
-            retry = 1;
-        }
-    } while(retry);
-    push_node_dyn_array(tbl, locked_base_nodes_stack_ptr, current_node);
-    return base_node;
-}
-
-/*
- * Joins a base node with it's right neighbor. Returns the base node
- * resulting from the join in locked state or NULL if there is no base
- * node to join with.
- */
-static DbTableCATreeNode*
-erl_db_catree_force_join_right(DbTableCATree *tb,
-                               DbTableCATreeNode *parent,
-                               DbTableCATreeNode *thiz,
-                               DbTableCATreeNode **result_parent_wb)
-{
-    DbTableCATreeNode *gparent;
-    DbTableCATreeNode *neighbor;
-    DbTableCATreeNode *new_neighbor;
-    DbTableCATreeNode *neighbor_parent;
-    TreeDbTerm* new_root;
-
-    if (parent == NULL) {
-        return NULL;
-    }
-    ASSERT(thiz == GET_LEFT(parent));
-    while (1) {
-        neighbor = leftmost_base_node(GET_RIGHT_ACQB(parent));
-        wlock_base_node_no_stats(&neighbor->u.base);
-        if (neighbor->u.base.is_valid)
-            break;
-        wunlock_base_node(&neighbor->u.base);
-    }
-    lock_route_node(parent);
-    parent->u.route.is_valid = 0;
-    neighbor->u.base.is_valid = 0;
-    thiz->u.base.is_valid = 0;
-    while (1) {
-        gparent = parent_of(tb, parent);
-        if (gparent == NULL)
-            break;
-        lock_route_node(gparent);
-        if (gparent->u.route.is_valid)
-            break;
-        unlock_route_node(gparent);
-    }
-    if (gparent == NULL) {
-        SET_ROOT_RELB(tb, GET_RIGHT(parent));
-    } else if (GET_LEFT(gparent) == parent) {
-        SET_LEFT_RELB(gparent, GET_RIGHT(parent));
-    } else {
-        SET_RIGHT_RELB(gparent, GET_RIGHT(parent));
-    }
-    unlock_route_node(parent);
-    if (gparent != NULL) {
-        unlock_route_node(gparent);
-    }
-
-    new_root = join_trees(thiz->u.base.root, neighbor->u.base.root);
-    new_neighbor = create_wlocked_base_node(tb, new_root,
-                                            LC_ORDER(thiz->u.base.lc_key.term));
-
-    if (GET_RIGHT(parent) == neighbor) {
-        neighbor_parent = gparent;
-    } else {
-        neighbor_parent = leftmost_route_node(GET_RIGHT(parent));
-    }
-    if(neighbor_parent == NULL) {
-        SET_ROOT_RELB(tb, new_neighbor);
-    } else if (GET_LEFT(neighbor_parent) == neighbor) {
-        SET_LEFT_RELB(neighbor_parent, new_neighbor);
-    } else {
-        SET_RIGHT_RELB(neighbor_parent, new_neighbor);
-    }
-    wunlock_base_node(&thiz->u.base);
-    wunlock_base_node(&neighbor->u.base);
-    /* Free the parent and base */
-    erts_schedule_db_free(&tb->common,
-                          do_free_route_node,
-                          parent,
-                          &parent->u.route.free_item,
-                          sizeof_route_node(parent->u.route.key.size));
-    erts_schedule_db_free(&tb->common,
-                          do_free_base_node,
-                          thiz,
-                          &thiz->u.base.free_item,
-                          sizeof_base_node(thiz->u.base.lc_key.size));
-    erts_schedule_db_free(&tb->common,
-                          do_free_base_node,
-                          neighbor,
-                          &neighbor->u.base.free_item,
-                          sizeof_base_node(neighbor->u.base.lc_key.size));
-
-    *result_parent_wb = neighbor_parent;
-    return new_neighbor;
-}
-
-/*
- * Used to merge together all base nodes for operations such as last
- * and select_*. Returns the base node resulting from the merge in
- * locked state.
- */
-static DbTableCATreeNode *
-merge_to_one_locked_base_node(DbTableCATree* tb)
-{
-    DbTableCATreeNode *parent;
-    DbTableCATreeNode *new_parent;
-    DbTableCATreeNode *base;
-    DbTableCATreeNode *new_base;
-    int is_not_valid;
-    /* Find first base node */
-    do {
-        parent = NULL;
-        base = GET_ROOT_ACQB(tb);
-        while ( ! base->is_base_node ) {
-            parent = base;
-            base = GET_LEFT_ACQB(base);
-        }
-        wlock_base_node_no_stats(&(base->u.base));
-        is_not_valid = ! base->u.base.is_valid;
-        if (is_not_valid) {
-            wunlock_base_node(&(base->u.base));
-        }
-    } while(is_not_valid);
-    do {
-        new_base = erl_db_catree_force_join_right(tb,
-                                                  parent,
-                                                  base,
-                                                  &new_parent);
-        if (new_base != NULL) {
-            base = new_base;
-            parent = new_parent;
-        }
-    } while(new_base != NULL);
-    return base;
-}
-
-
 static void join_catree(DbTableCATree *tb,
                         DbTableCATreeNode *parent,
                         DbTableCATreeNode *thiz)
diff --git a/erts/emulator/beam/erl_lock_check.c b/erts/emulator/beam/erl_lock_check.c
index 987e370341..018c82aabb 100644
--- a/erts/emulator/beam/erl_lock_check.c
+++ b/erts/emulator/beam/erl_lock_check.c
@@ -1034,11 +1034,6 @@ erts_lc_trylock_force_busy_flg(erts_lc_lock_t *lck, erts_lock_options_t options)
 #endif
 }
 
-/*
- * locked = 0    trylock failed
- * locked > 0    trylock succeeded
- * locked < 0    prelocking of newly created lock (no lock order check)
- */
 void erts_lc_trylock_flg_x(int locked, erts_lc_lock_t *lck, erts_lock_options_t options,
 			   char *file, unsigned int line)
 {
@@ -1069,7 +1064,7 @@ void erts_lc_trylock_flg_x(int locked, erts_lc_lock_t *lck, erts_lock_options_t
 	for (tl_lck = thr->locked.last; tl_lck; tl_lck = tl_lck->prev) {
             int order = compare_locked_by_id_extra(tl_lck, lck);
 	    if (order <= 0) {
-		if (order == 0 && locked >= 0)
+		if (order == 0)
 		    lock_twice("Trylocking", thr, lck, options);
 		if (locked) {
 		    ll->next = tl_lck->next;