Lines Matching refs:root
34 Dtlink_t* root; /* tree root */ member
45 if(!here && !(here = tree->root) ) in dttreeprint()
94 Dtlink_t *t, *root; local
98 if(!(root = tree->root) )
102 { while((t = root->_rght) )
103 LROTATE(root,t);
106 { while((t = root->_left) )
107 RROTATE(root,t);
109 tree->root = root;
111 return _DTOBJ(disc, root);
122 Dtlink_t *root, *t; local
126 root = tree->root;
127 tree->root = NIL(Dtlink_t*);
130 if(root && (disc->link < 0 || disc->freef) )
132 { while((t = root->_left) )
133 RROTATE(root,t);
134 t = root->_rght;
135 _dtfree(dt, root, DT_DELETE);
136 } while((root = t) );
157 { if((list = tree->root) )
168 tree->root = list;
170 { tree->root = NIL(Dtlink_t*);
188 static ssize_t tsize(Dtlink_t* root, ssize_t lev, Dtstat_t* st) in tsize() argument
190 static ssize_t tsize(root, lev, st) in tsize()
191 Dtlink_t* root; in tsize()
198 if(!root) /* nothing to do */
214 if((z = tsize(root->_left, lev+1, st)) < 0)
218 if((z = tsize(root->_rght, lev+1, st)) < 0)
240 size = tsize(tree->root, 0, st);
281 tree->root = tbalance(list, size); in toptimize()
287 Dtlink_t *root, *last, *t, *r, *l; in troot() local
326 root = NIL(Dtlink_t*); in troot()
328 while(!root && (t = link->_rght) ) /* link->_rght is the left subtree <= obj */ in troot()
339 root = t; in troot()
350 while(!root && (t = link->_left) ) /* link->_left is the right subtree >= obj */ in troot()
361 root = t; in troot()
372 if(!root) /* always set a non-trivial root */ in troot()
373 { root = list; in troot()
390 return root; in troot()
404 Dtlink_t *root, *t, *l, *r, *me, link; local
444 if((root = tree->root) && _DTOBJ(disc,root) != obj) /* splay-search for a matching object */
446 { o = _DTOBJ(disc,root); k = _DTKEY(disc,o);
450 { if((t = root->_left) )
453 { rrotate(root,t);
455 if(!(root = t->_left) )
459 { rlink(r,root);
460 root = t;
465 rlink(r,root);
466 if(!(root = t->_rght) )
471 { rlink(r,root);
472 root = NIL(Dtlink_t*);
477 { if((t = root->_rght) )
480 { lrotate(root,t);
482 if(!(root = t->_rght) )
486 { llink(l,root);
487 root = t;
492 llink(l,root);
493 if(!(root = t->_left) )
498 { llink(l,root);
499 root = NIL(Dtlink_t*);
505 l->_rght = root ? root->_left : NIL(Dtlink_t*);
506 r->_left = root ? root->_rght : NIL(Dtlink_t*);
508 if(root)
511 ((type&(DT_NEXT|DT_PREV|DT_REMOVE)) && _DTOBJ(disc,root) != obj) )
512 root = troot(dt, root, &link, obj, type);
517 root->_left = link._rght;
518 root->_rght = link._left;
519 tree->root = root;
520 DTRETURN(obj, _DTOBJ(disc,root));
523 { root->_left = link._rght;
524 root->_rght = NIL(Dtlink_t*);
525 link._rght = root;
527 if((root = link._left) )
528 { while((t = root->_left) )
529 RROTATE(root,t);
530 link._left = root->_rght;
536 { root->_rght = link._left;
537 root->_left = NIL(Dtlink_t*);
538 link._left = root;
540 if((root = link._rght) )
541 { while((t = root->_rght) )
542 LROTATE(root,t);
543 link._rght = root->_left;
549 { if(_DTOBJ(disc,root) == obj)
552 { root->_left = link._rght;
553 root->_rght = link._left;
554 tree->root = root;
560 obj = _DTOBJ(disc,root);
561 _dtfree(dt, root, type);
571 { root->_left = NIL(Dtlink_t*);
572 root->_rght = link._left;
573 link._left = root;
592 tree->root = link._left; /* tree is RIGHT tree */
600 tree->root = l; /* LEFT tree is now the entire tree */
617 if(!(root = _dtmake(dt, obj, type)) )
627 { root = me;
657 if(tree->root) in treeevent()
674 …return (dt && dt->meth && (dt->meth->type & DT_ORDERED)) ? (Void_t*)((Dttree_t*)dt->data)->root : … in dtfinger()