Function insert_t

libCacheSim/dataStructure/splay_tuple.c:154–188

// }

sTree_tuple *insert_t(splay_key_type_t i, sTree_tuple *t) {
  /* Insert i into the sTree t, unless it's already there.    */
  /* Return a pointer to the resulting sTree.                 */
  sTree_tuple *new;

  new = (sTree_tuple *)malloc(sizeof(sTree_tuple));
  if (new == NULL) {
    printf("Ran out of space\n");
    exit(1);
  }
  assign_key_t(new, i);
  new->value = 1;
  if (t == NULL) {
    new->left = new->right = NULL;
    return new;
  }
  t = splay_t(i, t);
  if (key_cmp_t(i, t->key) < 0 || ((key_cmp_t(i, t->key) == 0) && (i->L < t->key->L))) {
    new->left = t->left;
    new->right = t;
    t->left = NULL;
    t->value = 1 + node_value_t(t->right);
  } else if (key_cmp_t(i, t->key) > 0 || ((key_cmp_t(i, t->key) == 0) && (i->L > t->key->L))) {
    new->right = t->right;
    new->left = t;
    t->right = NULL;
    t->value = 1 + node_value_t(t->left);
  } else {
    free_node_t(new);
    assert(t->value == 1 + node_value_t(t->left) + node_value_t(t->right));
    return t;
  }
  new->value = 1 + node_value_t(new->left) + node_value_t(new->right);
  return new;
}

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