Delete fine grained lock 노드 삭제Issue

[leeshinyook]

개요

• 노드가 전부 삭제되지 않는 문제

상세

/* 
 * TODO
 *  Implement a function which remove nodes from the BST in fine-grained manner.
 *
 *  @param lab2_tree *tree  : bst tha you need to remove node in fine-grained manner from bst which contains key.
 *  @param int key          : key value that you want to delete. 
 *  @return                 : status (success or fail)
 */
int lab2_node_remove_fg(lab2_tree *tree, int key) {
    // You need to implement lab2_node_remove_fg function.
    pthread_mutex_lock(&Mutex);
    lab2_node *temp = tree -> root;
    lab2_node *parent = NULL , *child, *succ, *succ_p;
    while(temp != NULL && temp -> key != key) {
        parent = temp;
        if(temp -> key < key) {
            temp = temp -> right;
        } else {
            temp = temp -> left;
        }
    }
    if(temp == NULL) {
        pthread_mutex_unlock(&Mutex);
        return LAB2_SUCCESS;
    }
    pthread_mutex_unlock(&Mutex);
    pthread_mutex_lock(&tree -> mutex);
    if((temp -> left == NULL) && (temp -> right == NULL)) { // 아래에 자식 노드가 없을 경우
        if (parent != NULL) {
            if(parent -> left == temp) {
                parent -> left = NULL;
            } else {
                parent -> right = NULL;
            }
        } else {
            tree -> root = NULL;
        }
        node_count--;
        lab2_node_delete(temp);
        pthread_mutex_unlock(&tree -> mutex);
        return LAB2_SUCCESS;
    } else if(temp -> left == NULL || temp -> right == NULL) { // 아래에 1개의 자식 노드가 있을 경우
        pthread_mutex_lock(&temp -> mutex);
        child = (temp -> left != NULL) ? temp -> left : temp -> right;
        pthread_mutex_unlock(&temp -> mutex);
        pthread_mutex_lock(&child -> mutex);
        if(parent != NULL) {
            if(parent -> left == temp) {
                parent -> left = child;
            } else {
                parent -> right = child;
            }
        } else {
            tree -> root = child;
        }
        node_count--;
        pthread_mutex_unlock(&child -> mutex);
        lab2_node_delete(temp);

        pthread_mutex_unlock(&tree -> mutex);
        return LAB2_SUCCESS;
    } else {
          // 아래에 2개의 자식 노드가 있을 경우
        pthread_mutex_lock(&temp -> mutex);
        succ_p = temp;
        succ = temp -> right;
        pthread_mutex_unlock(&temp -> mutex);
        pthread_mutex_lock(&succ -> mutex);
        while(succ -> left != NULL) {
            pthread_mutex_unlock(&succ -> mutex);
            succ_p = succ;
            succ = succ -> left;
            pthread_mutex_lock(&succ -> mutex);
        }
        if(succ_p -> left == succ) {
            succ_p -> left = succ -> right;
        } else {
            succ_p -> right = succ -> right;
        }
        temp -> key = succ -> key;
        temp = succ;
        node_count--;
        pthread_mutex_unlock(&succ -> mutex);
        lab2_node_delete(temp);

        pthread_mutex_unlock(&tree -> mutex);
        return LAB2_SUCCESS;
    }
}