62 splay_tree * splaytree_splay (splay_tree *t, int i) {  in splaytree_splay()  argument
66     if (t == NULL) return t;  in splaytree_splay()
71         comp = compare(i, t->key);  in splaytree_splay()
73             if (t->left == NULL) break;  in splaytree_splay()
74             if (compare(i, t->left->key) < 0) {  in splaytree_splay()
75                 y = t->left;                           /* rotate right */  in splaytree_splay()
76                 t->left = y->right;  in splaytree_splay()
77                 y->right = t;  in splaytree_splay()
78                 t = y;  in splaytree_splay()
79                 if (t->left == NULL) break;  in splaytree_splay()
81             r->left = t;                               /* link right */  in splaytree_splay()
82             r = t;  in splaytree_splay()
83             t = t->left;  in splaytree_splay()
85             if (t->right == NULL) break;  in splaytree_splay()
86             if (compare(i, t->right->key) > 0) {  in splaytree_splay()
87                 y = t->right;                          /* rotate left */  in splaytree_splay()
88                 t->right = y->left;  in splaytree_splay()
89                 y->left = t;  in splaytree_splay()
90                 t = y;  in splaytree_splay()
91                 if (t->right == NULL) break;  in splaytree_splay()
93             l->right = t;                              /* link left */  in splaytree_splay()
94             l = t;  in splaytree_splay()
95             t = t->right;  in splaytree_splay()
101     l->right = t->left;                                /* assemble */  in splaytree_splay()
102     r->left = t->right;  in splaytree_splay()
103     t->left = N.right;  in splaytree_splay()
104     t->right = N.left;  in splaytree_splay()
106     return t;  in splaytree_splay()
109 splay_tree * splaytree_insert(splay_tree * t, int i, void *data) {  in splaytree_insert()  argument
114     if (t != NULL) {  in splaytree_insert()
115 	t = splaytree_splay(t, i);  in splaytree_insert()
116 	if (compare(i, t->key)==0) {  in splaytree_insert()
117 	    return t;  /* it's already there */  in splaytree_insert()
122     if (t == NULL) {  in splaytree_insert()
124     } else if (compare(i, t->key) < 0) {  in splaytree_insert()
125 	new->left = t->left;  in splaytree_insert()
126 	new->right = t;  in splaytree_insert()
127 	t->left = NULL;  in splaytree_insert()
129 	new->right = t->right;  in splaytree_insert()
130 	new->left = t;  in splaytree_insert()
131 	t->right = NULL;  in splaytree_insert()
138 splay_tree * splaytree_delete(splay_tree *t, int i) {  in splaytree_delete()  argument
142     if (t==NULL) return NULL;  in splaytree_delete()
143     t = splaytree_splay(t, i);  in splaytree_delete()
144     if (compare(i, t->key) == 0) {               /* found it */  in splaytree_delete()
145 	if (t->left == NULL) {  in splaytree_delete()
146 	    x = t->right;  in splaytree_delete()
148 	    x = splaytree_splay(t->left, i);  in splaytree_delete()
149 	    x->right = t->right;  in splaytree_delete()
151 	free(t);  in splaytree_delete()
154 	return t;                         /* It wasn't there */  in splaytree_delete()