Function insert

libCacheSim/dataStructure/splay.c:158–193

}

sTree * insert(key_type i, sTree * t) {
    /* Insert i into the sTree t, unless it's already there.    */
    /* Return a pointer to the resulting sTree.                 */
    sTree * new;
    
    new = (sTree *) malloc (sizeof (sTree));
    if (new == NULL) {
        printf("Ran out of space\n");
        exit(1);
    }
    assign_key(new, i);
    new->value = 1;
    if (t == NULL) {
        new->left = new->right = NULL;
        return new;
    }
    t = splay(i,t);
    if (key_cmp(i, t->key) < 0) {
        new->left = t->left;
        new->right = t;
        t->left = NULL;
        t->value = 1 + node_value(t->right);
    } else if (key_cmp(i, t->key) > 0) {
        new->right = t->right;
        new->left = t;
        t->right = NULL;
        t->value = 1 + node_value(t->left);
    } else { /* We get here if it's already in the sTree */
        /* Don't add it again                      */
        free_node(new);
        assert (t->value == 1 + node_value(t->left) + node_value(t->right));
        return t;
    }
    new->value = 1 + node_value(new->left) + node_value(new->right);
    return new;
}

sTree * splay_delete(key_type i, sTree * t) {
    /* Deletes i from the sTree if it's there.               */