Function splay_delete_t

libCacheSim/dataStructure/splay_tuple.c:190–241

}

sTree_tuple *splay_delete_t(splay_key_type_t i, sTree_tuple *t) {
  if (t == NULL) return NULL;

  t = splay_t(i, t);

  sTree_tuple *current = t;
  sTree_tuple *parent = NULL;

  // Iterate until find the node to delete
  while (current != NULL) {
    if (key_cmp_t(i, current->key) == 0 && i->L == current->key->L) {
      sTree_tuple *replacement;

      if (current->left == NULL) {
        replacement = current->right;
      } else if (current->right == NULL) {
        replacement = current->left;
      } else {
        sTree_tuple *successor = current->right;
        while (successor->left != NULL) {
          successor = successor->left;
        }
        replacement = splay_t(successor->key, current->right);
        replacement->left = current->left;
      }

      if (parent == NULL) {
        t = replacement;
      } else if (parent->left == current) {
        parent->left = replacement;
      } else {
        parent->right = replacement;
      }

      free_node_t(current);

      if (t != NULL) {
        t->value = node_value_t(t->left) + node_value_t(t->right) + 1;
      }

      break;
    }

    parent = current;
    if (key_cmp_t(i, current->key) < 0 || (key_cmp_t(i, current->key) == 0 && i->L < current->key->L))
      current = current->left;
    else
      current = current->right;
  }

  return t;
}

// sTree_tuple *find_node(key_type_t e, sTree_tuple *t) {
//     /* Returns a pointer to the node in the sTree with the given value.  */