#include <cuda.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct node {
  int data;
  struct node *parent;
  struct node *left;
  struct node *right;
  int sema;
} node;

__device__ int lock(node* n) {
  return !atomicExch(&n->sema, 1);
}

__device__ void unlock(node* n) {
  atomicExch(&n->sema, 0);
}

__device__ node* new_node(int val, node* parent) {
  node *tmp = (node *) malloc(sizeof(node));
  tmp->data = val;
  tmp->parent = parent;
  tmp->left = tmp->right = NULL;
  tmp->sema = 0;
  return tmp;
}

__device__ node* find(node* root, int key) {
  if (root == NULL) return NULL;

  if (root->data == key) return root;
  else if (root->data > key) return find(root->left, key);
  else return find(root->right, key);
}


__device__ void insert(node* root, int key) {

  if (root == NULL) {             // Empty Tree
    root = new_node(key, NULL); 
    return;
  }
  
  int acquired = lock(root);

  if (acquired) {
    if (key < root->data) {
      if (root->left == NULL) {     // Can be inserted to the immediate left
        root->left = new_node(key, root);
        unlock(root);
        return;
      } else {                      // Release this Node and proceed
        unlock(root);
        insert(root->left, key);
      }
    } else {
      if (root->right == NULL) {    // Can be inserted to the immediate right
        root->right = new_node(key, root);
        unlock(root);
        return;
      } else {
        unlock(root);               // Release this Node and proceed
        insert(root->right, key);
      }
    }
  } else {
    insert(root, key);
  }
}


__device__ void pre_order(node* root)
{
    if(root != NULL)
    {
      printf("%d ", root->data);
      pre_order(root->left);
      pre_order(root->right);
    }
    return;
}

__device__ void in_order(node* root)
{
    if(root != NULL)
    {
      in_order(root->left);
      printf("%d ", root->data);
      in_order(root->right);
    }
    return;
}

__device__ node* min_BST(node* root) {
  node* tmp = root->right;
  if (tmp == NULL) return NULL;

  while(tmp->left != NULL)  tmp = tmp->left;
  return tmp;
}

__device__ void bst_delete(node* root, int key) {
  if (root == NULL) return;
  // printf("del key= %d\n", key);
  //int root_acquired = lock(root);
  int root_acquired = 1;
  if (root_acquired) {
    node* node2delete = find(root, key);

    if (node2delete) {
      //printf("Delete Node %d\n",node2delete->data);
      node* parent = node2delete->parent;
      if (parent) {
        //unlock(root);
        int parent_acquired = lock(parent);
        if (parent_acquired) {
          node* successor = min_BST(node2delete);
          if (successor == NULL) {                    // Leaf Node
            if (node2delete->data < parent->data) {
              parent->left = node2delete->left;
            } else {
              parent->right = node2delete->left;
            }
            if(node2delete->left)
              node2delete->left->parent = parent;
            free(node2delete);
          } 
          else if (successor != NULL) {
            node* parent_of_successor = successor->parent;
            node2delete->data = successor->data;
            if (successor->data < parent_of_successor->data) {
              parent_of_successor->left = successor->right;
            } else {
              parent_of_successor->right = successor->right;
            }
            if(successor->right)
              successor->right->parent = parent_of_successor;
            free(successor);
          }
          unlock(parent);
        } else {
          //printf("recall %d\n", key);
          bst_delete(root, key);
        }
      } else {                        // ROOT of tree involved!
        // not handled!
      }
    } else {
      //unlock(root);
    }
  } else {
    //printf("recall %d\n", key);
    bst_delete(root, key);
  }
}
	.file	"tmpxft_003b6bcb_00000000-6_bst.cudafe1.cpp"
	.text
#APP

#NO_APP
	.type	_ZL26__cudaUnregisterBinaryUtilv, @function
_ZL26__cudaUnregisterBinaryUtilv:
.LFB2038:
	.cfi_startproc
	endbr64
	movq	_ZL20__cudaFatCubinHandle(%rip), %rdi
	jmp	__cudaUnregisterFatBinary@PLT
	.cfi_endproc
.LFE2038:
	.size	_ZL26__cudaUnregisterBinaryUtilv, .-_ZL26__cudaUnregisterBinaryUtilv
	.globl	_Z4lockP4node
	.type	_Z4lockP4node, @function
_Z4lockP4node:
.LFB2027:
	.cfi_startproc
	endbr64
	pushq	%rax
	.cfi_def_cfa_offset 16
	popq	%rax
	.cfi_def_cfa_offset 8
	subq	$24, %rsp
	.cfi_def_cfa_offset 32
	movl	$1, 12(%rsp)
	movl	12(%rsp), %edi
	call	exit@PLT
	.cfi_endproc
.LFE2027:
	.size	_Z4lockP4node, .-_Z4lockP4node
	.globl	_Z6unlockP4node
	.type	_Z6unlockP4node, @function
_Z6unlockP4node:
.LFB2028:
	.cfi_startproc
	endbr64
	pushq	%rax
	.cfi_def_cfa_offset 16
	popq	%rax
	.cfi_def_cfa_offset 8
	subq	$24, %rsp
	.cfi_def_cfa_offset 32
	movl	$1, 12(%rsp)
	movl	12(%rsp), %edi
	call	exit@PLT
	.cfi_endproc
.LFE2028:
	.size	_Z6unlockP4node, .-_Z6unlockP4node
	.globl	_Z8new_nodeiP4node
	.type	_Z8new_nodeiP4node, @function
_Z8new_nodeiP4node:
.LFB2029:
	.cfi_startproc
	endbr64
	pushq	%rax
	.cfi_def_cfa_offset 16
	popq	%rax
	.cfi_def_cfa_offset 8
	subq	$24, %rsp
	.cfi_def_cfa_offset 32
	movl	$1, 12(%rsp)
	movl	12(%rsp), %edi
	call	exit@PLT
	.cfi_endproc
.LFE2029:
	.size	_Z8new_nodeiP4node, .-_Z8new_nodeiP4node
	.globl	_Z4findP4nodei
	.type	_Z4findP4nodei, @function
_Z4findP4nodei:
.LFB2030:
	.cfi_startproc
	endbr64
	pushq	%rax
	.cfi_def_cfa_offset 16
	popq	%rax
	.cfi_def_cfa_offset 8
	subq	$24, %rsp
	.cfi_def_cfa_offset 32
	movl	$1, 12(%rsp)
	movl	12(%rsp), %edi
	call	exit@PLT
	.cfi_endproc
.LFE2030:
	.size	_Z4findP4nodei, .-_Z4findP4nodei
	.globl	_Z6insertP4nodei
	.type	_Z6insertP4nodei, @function
_Z6insertP4nodei:
.LFB2031:
	.cfi_startproc
	endbr64
	pushq	%rax
	.cfi_def_cfa_offset 16
	popq	%rax
	.cfi_def_cfa_offset 8
	subq	$24, %rsp
	.cfi_def_cfa_offset 32
	movl	$1, 12(%rsp)
	movl	12(%rsp), %edi
	call	exit@PLT
	.cfi_endproc
.LFE2031:
	.size	_Z6insertP4nodei, .-_Z6insertP4nodei
	.globl	_Z9pre_orderP4node
	.type	_Z9pre_orderP4node, @function
_Z9pre_orderP4node:
.LFB2177:
	.cfi_startproc
	endbr64
	pushq	%rax
	.cfi_def_cfa_offset 16
	popq	%rax
	.cfi_def_cfa_offset 8
	pushq	%rax
	.cfi_def_cfa_offset 16
	call	_Z6unlockP4node
	.cfi_endproc
.LFE2177:
	.size	_Z9pre_orderP4node, .-_Z9pre_orderP4node
	.globl	_Z8in_orderP4node
	.type	_Z8in_orderP4node, @function
_Z8in_orderP4node:
.LFB2179:
	.cfi_startproc
	endbr64
	pushq	%rax
	.cfi_def_cfa_offset 16
	popq	%rax
	.cfi_def_cfa_offset 8
	pushq	%rax
	.cfi_def_cfa_offset 16
	call	_Z6unlockP4node
	.cfi_endproc
.LFE2179:
	.size	_Z8in_orderP4node, .-_Z8in_orderP4node
	.globl	_Z7min_BSTP4node
	.type	_Z7min_BSTP4node, @function
_Z7min_BSTP4node:
.LFB2034:
	.cfi_startproc
	endbr64
	pushq	%rax
	.cfi_def_cfa_offset 16
	popq	%rax
	.cfi_def_cfa_offset 8
	subq	$24, %rsp
	.cfi_def_cfa_offset 32
	movl	$1, 12(%rsp)
	movl	12(%rsp), %edi
	call	exit@PLT
	.cfi_endproc
.LFE2034:
	.size	_Z7min_BSTP4node, .-_Z7min_BSTP4node
	.globl	_Z10bst_deleteP4nodei
	.type	_Z10bst_deleteP4nodei, @function
_Z10bst_deleteP4nodei:
.LFB2181:
	.cfi_startproc
	endbr64
	pushq	%rax
	.cfi_def_cfa_offset 16
	popq	%rax
	.cfi_def_cfa_offset 8
	pushq	%rax
	.cfi_def_cfa_offset 16
	call	_Z6insertP4nodei
	.cfi_endproc
.LFE2181:
	.size	_Z10bst_deleteP4nodei, .-_Z10bst_deleteP4nodei
	.section	.text.startup,"ax",@progbits
	.type	_ZL24__sti____cudaRegisterAllv, @function
_ZL24__sti____cudaRegisterAllv:
.LFB2061:
	.cfi_startproc
	endbr64
	pushq	%rax
	.cfi_def_cfa_offset 16
	leaq	_ZL15__fatDeviceText(%rip), %rdi
	call	__cudaRegisterFatBinary@PLT
	movq	%rax, %rdi
	movq	%rax, _ZL20__cudaFatCubinHandle(%rip)
	call	__cudaRegisterFatBinaryEnd@PLT
	leaq	_ZL26__cudaUnregisterBinaryUtilv(%rip), %rdi
	popq	%rdx
	.cfi_def_cfa_offset 8
	jmp	atexit@PLT
	.cfi_endproc
.LFE2061:
	.size	_ZL24__sti____cudaRegisterAllv, .-_ZL24__sti____cudaRegisterAllv
	.section	.init_array,"aw"
	.align 8
	.quad	_ZL24__sti____cudaRegisterAllv
	.section	.nvFatBinSegment,"aw"
	.align 8
	.type	_ZL15__fatDeviceText, @object
	.size	_ZL15__fatDeviceText, 24
_ZL15__fatDeviceText:
	.long	1180844977
	.long	1
	.quad	fatbinData
	.quad	0
	.local	_ZL20__cudaFatCubinHandle
	.comm	_ZL20__cudaFatCubinHandle,8,8
	.ident	"GCC: (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0"
	.section	.note.GNU-stack,"",@progbits
	.section	.note.gnu.property,"a"
	.align 8
	.long	1f - 0f
	.long	4f - 1f
	.long	5
0:
	.string	"GNU"
1:
	.align 8
	.long	0xc0000002
	.long	3f - 2f
2:
	.long	0x3
3:
	.align 8
4:

#include <hip/hip_runtime.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct node {
  int data;
  struct node *parent;
  struct node *left;
  struct node *right;
  int sema;
} node;

__device__ int lock(node* n) {
  return !atomicExch(&n->sema, 1);
}

__device__ void unlock(node* n) {
  atomicExch(&n->sema, 0);
}

__device__ node* new_node(int val, node* parent) {
  node *tmp = (node *) malloc(sizeof(node));
  tmp->data = val;
  tmp->parent = parent;
  tmp->left = tmp->right = NULL;
  tmp->sema = 0;
  return tmp;
}

__device__ node* find(node* root, int key) {
  if (root == NULL) return NULL;

  if (root->data == key) return root;
  else if (root->data > key) return find(root->left, key);
  else return find(root->right, key);
}


__device__ void insert(node* root, int key) {

  if (root == NULL) {             // Empty Tree
    root = new_node(key, NULL); 
    return;
  }
  
  int acquired = lock(root);

  if (acquired) {
    if (key < root->data) {
      if (root->left == NULL) {     // Can be inserted to the immediate left
        root->left = new_node(key, root);
        unlock(root);
        return;
      } else {                      // Release this Node and proceed
        unlock(root);
        insert(root->left, key);
      }
    } else {
      if (root->right == NULL) {    // Can be inserted to the immediate right
        root->right = new_node(key, root);
        unlock(root);
        return;
      } else {
        unlock(root);               // Release this Node and proceed
        insert(root->right, key);
      }
    }
  } else {
    insert(root, key);
  }
}


__device__ void pre_order(node* root)
{
    if(root != NULL)
    {
      printf("%d ", root->data);
      pre_order(root->left);
      pre_order(root->right);
    }
    return;
}

__device__ void in_order(node* root)
{
    if(root != NULL)
    {
      in_order(root->left);
      printf("%d ", root->data);
      in_order(root->right);
    }
    return;
}

__device__ node* min_BST(node* root) {
  node* tmp = root->right;
  if (tmp == NULL) return NULL;

  while(tmp->left != NULL)  tmp = tmp->left;
  return tmp;
}

__device__ void bst_delete(node* root, int key) {
  if (root == NULL) return;
  // printf("del key= %d\n", key);
  //int root_acquired = lock(root);
  int root_acquired = 1;
  if (root_acquired) {
    node* node2delete = find(root, key);

    if (node2delete) {
      //printf("Delete Node %d\n",node2delete->data);
      node* parent = node2delete->parent;
      if (parent) {
        //unlock(root);
        int parent_acquired = lock(parent);
        if (parent_acquired) {
          node* successor = min_BST(node2delete);
          if (successor == NULL) {                    // Leaf Node
            if (node2delete->data < parent->data) {
              parent->left = node2delete->left;
            } else {
              parent->right = node2delete->left;
            }
            if(node2delete->left)
              node2delete->left->parent = parent;
            free(node2delete);
          } 
          else if (successor != NULL) {
            node* parent_of_successor = successor->parent;
            node2delete->data = successor->data;
            if (successor->data < parent_of_successor->data) {
              parent_of_successor->left = successor->right;
            } else {
              parent_of_successor->right = successor->right;
            }
            if(successor->right)
              successor->right->parent = parent_of_successor;
            free(successor);
          }
          unlock(parent);
        } else {
          //printf("recall %d\n", key);
          bst_delete(root, key);
        }
      } else {                        // ROOT of tree involved!
        // not handled!
      }
    } else {
      //unlock(root);
    }
  } else {
    //printf("recall %d\n", key);
    bst_delete(root, key);
  }
}
	.text
	.file	"bst.hip"
	.type	__hip_cuid_,@object             # @__hip_cuid_
	.bss
	.globl	__hip_cuid_
__hip_cuid_:
	.byte	0                               # 0x0
	.size	__hip_cuid_, 1

	.ident	"AMD clang version 18.0.0git (https://github.com/RadeonOpenCompute/llvm-project roc-6.3.2 25012 e5bf7e55c91490b07c49d8960fa7983d864936c4)"
	.section	".note.GNU-stack","",@progbits
	.addrsig
	.addrsig_sym __hip_cuid_

	.text
	.p2alignl 7, 3214868480
	.fill 96, 4, 3214868480
	.type	__hip_cuid_,@object             ; @__hip_cuid_
	.section	.bss,"aw",@nobits
	.globl	__hip_cuid_
__hip_cuid_:
	.byte	0                               ; 0x0
	.size	__hip_cuid_, 1

	.ident	"AMD clang version 18.0.0git (https://github.com/RadeonOpenCompute/llvm-project roc-6.3.2 25012 e5bf7e55c91490b07c49d8960fa7983d864936c4)"
	.section	".note.GNU-stack","",@progbits
	.addrsig
	.addrsig_sym __hip_cuid_
	.amdgcn_target "amdgcn-amd-amdhsa--gfx1100"
	.amdgpu_metadata
---
amdhsa.kernels:  []
amdhsa.target:   amdgcn-amd-amdhsa--gfx1100
amdhsa.version:
  - 1
  - 2
...

	.end_amdgpu_metadata
