Function splay

libCacheSim/dataStructure/splay.c:61–129

static sTree * sedgewickized_splay (int i, sTree * t);

sTree * splay (key_type i, sTree * t) {
    /* Simple top down splay, not requiring i to be in the sTree t.  */
    /* What it does is described above.                             */
    sTree N, *l, *r, *y;
    if (t == NULL) return t;
    N.left = N.right = NULL;
    l = r = &N;
    long l_size=0, r_size=0;
    
    for (;;) {
        if (key_cmp(i, t->key) < 0){
            if (t->left == NULL) break;
            if (key_cmp(i, t->left->key) < 0) {
                y = t->left;                           /* rotate right */
                t->left = y->right;
                y->right = t;
                t->value = node_value(t->left) + node_value(t->right) + 1;
                t = y;
                if (t->left == NULL) break;
            }
            r->left = t;                               /* link right */
            r = t;
            t = t->left;
            r_size += 1+node_value(r->right);
        } else if (key_cmp(i, t->key) > 0) {
            if (t->right == NULL) break;
            if (key_cmp(i, t->right->key) > 0) {
                y = t->right;                          /* rotate left */
                t->right = y->left;
                y->left = t;
                t->value = node_value(t->left) + node_value(t->right) + 1;
                t = y;
                if (t->right == NULL) break;
            }
            l->right = t;                              /* link left */
            l = t;
            t = t->right;
            l_size += 1+node_value(l->left);
        } else {
            break;
        }
    }
    
    // TODO: there should be a better way to do this!!!!!!!!!
    
    l_size += node_value(t->left);  /* Now l_size and r_size are the sizes of */
    r_size += node_value(t->right); /* the left and right sTrees we just built.*/
    t->value = l_size + r_size + 1;
    
    l->right = r->left = NULL;
    
    /* The following two loops correct the size fields of the right path  */
    /* from the left child of the root and the right path from the left   */
    /* child of the root.                                                 */
    for (y = N.right; y != NULL; y = y->right) {
        y->value = l_size;
        l_size -= 1+node_value(y->left);
    }