Lines Matching refs:t
168 void* slow_key_of_node(const AvlTree* t, const AvlNode* n) in slow_key_of_node() argument
170 return (void*)((Addr)elem_of_node(n) + t->keyOff); in slow_key_of_node()
197 inline Word slow_cmp(const AvlTree* t, const void* k, const AvlNode* n) in slow_cmp() argument
199 return t->cmp(k, elem_of_node(n)); in slow_cmp()
244 static void stackClear(AvlTree* t) in stackClear() argument
247 vg_assert(t); in stackClear()
249 t->nodeStack[i] = NULL; in stackClear()
250 t->numStack[i] = 0; in stackClear()
252 t->stackTop = 0; in stackClear()
256 static inline void stackPush(AvlTree* t, AvlNode* n, Int i) in stackPush() argument
258 vg_assert(t->stackTop < STACK_MAX); in stackPush()
260 t->nodeStack[t->stackTop] = n; in stackPush()
261 t-> numStack[t->stackTop] = i; in stackPush()
262 t->stackTop++; in stackPush()
266 static inline Bool stackPop(AvlTree* t, AvlNode** n, Int* i) in stackPop() argument
268 vg_assert(t->stackTop <= STACK_MAX); in stackPop()
270 if (t->stackTop > 0) { in stackPop()
271 t->stackTop--; in stackPop()
272 *n = t->nodeStack[t->stackTop]; in stackPop()
273 *i = t-> numStack[t->stackTop]; in stackPop()
275 t->nodeStack[t->stackTop] = NULL; in stackPop()
276 t-> numStack[t->stackTop] = 0; in stackPop()
292 AvlTree* t; in VG_() local
302 t = alloc_fn(cc, sizeof(AvlTree)); in VG_()
303 t->keyOff = keyOff; in VG_()
304 t->cmp = cmp; in VG_()
305 t->alloc_fn = alloc_fn; in VG_()
306 t->cc = cc; in VG_()
307 t->free_fn = free_fn; in VG_()
308 t->node_pa = NULL; in VG_()
309 t->maxEltSize = 0; // Just in case it would be wrongly used. in VG_()
310 t->nElems = 0; in VG_()
311 t->root = NULL; in VG_()
312 stackClear(t); in VG_()
314 return t; in VG_()
323 AvlTree* t; in VG_() local
325 t = VG_(OSetGen_Create) (keyOff, cmp, alloc_fn, cc, free_fn); in VG_()
329 t->maxEltSize = maxEltSize; in VG_()
330 t->node_pa = VG_(newPA)(sizeof(AvlNode) in VG_()
333 t->alloc_fn, in VG_()
335 t->free_fn); in VG_()
336 VG_(addRefPA) (t->node_pa); in VG_()
338 return t; in VG_()
343 AvlTree* t; in VG_() local
347 t = os->alloc_fn(os->cc, sizeof(AvlTree)); in VG_()
348 t->keyOff = os->keyOff; in VG_()
349 t->cmp = os->cmp; in VG_()
350 t->alloc_fn = os->alloc_fn; in VG_()
351 t->cc = os->cc; in VG_()
352 t->free_fn = os->free_fn; in VG_()
353 t->node_pa = os->node_pa; in VG_()
354 if (t->node_pa) in VG_()
355 VG_(addRefPA) (t->node_pa); in VG_()
356 t->maxEltSize = os->maxEltSize; in VG_()
357 t->nElems = 0; in VG_()
358 t->root = NULL; in VG_()
359 stackClear(t); in VG_()
361 return t; in VG_()
371 void VG_(OSetGen_Destroy)(AvlTree* t) in VG_()
374 vg_assert(t); in VG_()
376 has_node_pa = t->node_pa != NULL; in VG_()
383 if (!has_node_pa || VG_(releasePA)(t->node_pa) > 0) { in VG_()
388 stackClear(t); in VG_()
389 if (t->root) in VG_()
390 stackPush(t, t->root, 1); in VG_()
394 while (stackPop(t, &n, &i)) { in VG_()
397 stackPush(t, n, 2); in VG_()
398 if (n->left) stackPush(t, n->left, 1); in VG_()
401 stackPush(t, n, 3); in VG_()
402 if (n->right) stackPush(t, n->right, 1); in VG_()
406 VG_(freeEltPA) (t->node_pa, n); in VG_()
408 t->free_fn(n); in VG_()
413 vg_assert(sz == t->nElems); in VG_()
417 t->free_fn(t); in VG_()
420 void VG_(OSetWord_Destroy)(AvlTree* t) in VG_()
422 VG_(OSetGen_Destroy)(t); in VG_()
426 void* VG_(OSetGen_AllocNode)(const AvlTree* t, SizeT elemSize) in VG_()
431 if (t->node_pa) { in VG_()
432 vg_assert(elemSize <= t->maxEltSize); in VG_()
433 n = VG_(allocEltPA) (t->node_pa); in VG_()
435 n = t->alloc_fn( t->cc, nodeSize ); in VG_()
442 void VG_(OSetGen_FreeNode)(const AvlTree* t, void* e) in VG_()
444 if (t->node_pa) in VG_()
445 VG_(freeEltPA) (t->node_pa, node_of_elem (e)); in VG_()
447 t->free_fn( node_of_elem(e) ); in VG_()
454 static inline Word cmp_key_root(const AvlTree* t, const AvlNode* n) in cmp_key_root() argument
456 return t->cmp in cmp_key_root()
457 ? slow_cmp(t, slow_key_of_node(t, n), t->root) in cmp_key_root()
458 : fast_cmp( fast_key_of_node( n), t->root); in cmp_key_root()
463 static Bool avl_insert(AvlTree* t, AvlNode* n) in avl_insert() argument
465 Word cmpres = cmp_key_root(t, n); in avl_insert()
469 if (t->root->left) { in avl_insert()
472 left_subtree.root = t->root->left; in avl_insert()
473 left_subtree.cmp = t->cmp; in avl_insert()
474 left_subtree.keyOff = t->keyOff; in avl_insert()
476 switch (t->root->balance--) { in avl_insert()
480 if (t->root->left->balance < 0) { in avl_insert()
481 avl_swr(&(t->root)); in avl_insert()
482 t->root->balance = 0; in avl_insert()
483 t->root->right->balance = 0; in avl_insert()
485 avl_swl(&(t->root->left)); in avl_insert()
486 avl_swr(&(t->root)); in avl_insert()
487 avl_nasty(t->root); in avl_insert()
490 t->root->left=left_subtree.root; in avl_insert()
494 t->root->left = n; in avl_insert()
495 if (t->root->balance--) return False; in avl_insert()
501 if (t->root->right) { in avl_insert()
504 right_subtree.root = t->root->right; in avl_insert()
505 right_subtree.cmp = t->cmp; in avl_insert()
506 right_subtree.keyOff = t->keyOff; in avl_insert()
508 switch (t->root->balance++) { in avl_insert()
512 if (t->root->right->balance > 0) { in avl_insert()
513 avl_swl(&(t->root)); in avl_insert()
514 t->root->balance = 0; in avl_insert()
515 t->root->left->balance = 0; in avl_insert()
517 avl_swr(&(t->root->right)); in avl_insert()
518 avl_swl(&(t->root)); in avl_insert()
519 avl_nasty(t->root); in avl_insert()
522 t->root->right=right_subtree.root; in avl_insert()
526 t->root->right = n; in avl_insert()
527 if (t->root->balance++) return False; in avl_insert()
538 void VG_(OSetGen_Insert)(AvlTree* t, void* e) in VG_()
542 vg_assert(t); in VG_()
553 if (!t->root) { in VG_()
554 t->root = n; in VG_()
556 avl_insert(t, n); in VG_()
559 t->nElems++; in VG_()
560 t->stackTop = 0; // So the iterator can't get out of sync in VG_()
563 void VG_(OSetWord_Insert)(AvlTree* t, UWord val) in VG_()
565 Word* node = VG_(OSetGen_AllocNode)(t, sizeof(UWord)); in VG_()
567 VG_(OSetGen_Insert)(t, node); in VG_()
575 static AvlNode* avl_lookup(const AvlTree* t, const void* k) in avl_lookup() argument
578 AvlNode* curr = t->root; in avl_lookup()
580 if (t->cmp) { in avl_lookup()
584 cmpres = slow_cmp(t, k, curr); in avl_lookup()
607 void* VG_(OSetGen_Lookup)(const AvlTree* t, const void* k) in VG_()
610 vg_assert(t); in VG_()
611 n = avl_lookup(t, k); in VG_()
617 void* VG_(OSetGen_LookupWithCmp)(AvlTree* t, const void* k, OSetCmp_t cmp) in VG_()
622 vg_assert(t); in VG_()
623 tmpcmp = t->cmp; in VG_()
624 t->cmp = cmp; in VG_()
625 e = VG_(OSetGen_Lookup)(t, k); in VG_()
626 t->cmp = tmpcmp; in VG_()
631 Bool VG_(OSetGen_Contains)(const AvlTree* t, const void* k) in VG_()
633 return (NULL != VG_(OSetGen_Lookup)(t, k)); in VG_()
636 Bool VG_(OSetWord_Contains)(const AvlTree* t, UWord val) in VG_()
638 return (NULL != VG_(OSetGen_Lookup)(t, &val)); in VG_()
645 static Bool avl_removeroot(AvlTree* t);
649 static Bool avl_remove(AvlTree* t, const AvlNode* n) in avl_remove() argument
652 Word cmpres = cmp_key_root(t, n); in avl_remove()
657 vg_assert(t->root->left); in avl_remove()
659 left_subtree.root = t->root->left; in avl_remove()
660 left_subtree.cmp = t->cmp; in avl_remove()
661 left_subtree.keyOff = t->keyOff; in avl_remove()
663 t->root->left = left_subtree.root; in avl_remove()
665 switch (t->root->balance++) { in avl_remove()
669 switch (t->root->right->balance) { in avl_remove()
671 avl_swl(&(t->root)); in avl_remove()
672 t->root->balance = -1; in avl_remove()
673 t->root->left->balance = 1; in avl_remove()
676 avl_swl(&(t->root)); in avl_remove()
677 t->root->balance = 0; in avl_remove()
678 t->root->left->balance = 0; in avl_remove()
681 avl_swr(&(t->root->right)); in avl_remove()
682 avl_swl(&(t->root)); in avl_remove()
683 avl_nasty(t->root); in avl_remove()
692 vg_assert(t->root->right); in avl_remove()
694 right_subtree.root = t->root->right; in avl_remove()
695 right_subtree.cmp = t->cmp; in avl_remove()
696 right_subtree.keyOff = t->keyOff; in avl_remove()
698 t->root->right = right_subtree.root; in avl_remove()
700 switch (t->root->balance--) { in avl_remove()
704 switch (t->root->left->balance) { in avl_remove()
706 avl_swr(&(t->root)); in avl_remove()
707 t->root->balance = 1; in avl_remove()
708 t->root->right->balance = -1; in avl_remove()
711 avl_swr(&(t->root)); in avl_remove()
712 t->root->balance = 0; in avl_remove()
713 t->root->right->balance = 0; in avl_remove()
716 avl_swl(&(t->root->left)); in avl_remove()
717 avl_swr(&(t->root)); in avl_remove()
718 avl_nasty(t->root); in avl_remove()
726 vg_assert(t->root == n); in avl_remove()
727 return avl_removeroot(t); in avl_remove()
733 static Bool avl_removeroot(AvlTree* t) in avl_removeroot() argument
738 if (!t->root->left) { in avl_removeroot()
739 if (!t->root->right) { in avl_removeroot()
740 t->root = NULL; in avl_removeroot()
743 t->root = t->root->right; in avl_removeroot()
746 if (!t->root->right) { in avl_removeroot()
747 t->root = t->root->left; in avl_removeroot()
750 if (t->root->balance < 0) { in avl_removeroot()
752 n = t->root->left; in avl_removeroot()
756 n = t->root->right; in avl_removeroot()
759 ch = avl_remove(t, n); in avl_removeroot()
760 n->left = t->root->left; in avl_removeroot()
761 n->right = t->root->right; in avl_removeroot()
762 n->balance = t->root->balance; in avl_removeroot()
763 t->root = n; in avl_removeroot()
770 void* VG_(OSetGen_Remove)(AvlTree* t, const void* k) in VG_()
773 AvlNode* n = avl_lookup(t, k); in VG_()
775 avl_remove(t, n); in VG_()
776 t->nElems--; in VG_()
777 t->stackTop = 0; // So the iterator can't get out of sync in VG_()
784 Bool VG_(OSetWord_Remove)(AvlTree* t, UWord val) in VG_()
786 void* n = VG_(OSetGen_Remove)(t, &val); in VG_()
788 VG_(OSetGen_FreeNode)(t, n); in VG_()
803 void VG_(OSetGen_ResetIter)(AvlTree* t) in VG_()
805 vg_assert(t); in VG_()
806 stackClear(t); in VG_()
807 if (t->root) in VG_()
808 stackPush(t, t->root, 1); in VG_()
811 void VG_(OSetWord_ResetIter)(AvlTree* t) in VG_()
813 VG_(OSetGen_ResetIter)(t); in VG_()
816 void* VG_(OSetGen_Next)(AvlTree* t) in VG_()
821 vg_assert(t); in VG_()
827 while (stackPop(t, &n, &i)) { in VG_()
830 stackPush(t, n, 2); in VG_()
835 stackPush(t, n, 3); in VG_()
848 Bool VG_(OSetWord_Next)(AvlTree* t, UWord* val) in VG_()
850 UWord* n = VG_(OSetGen_Next)(t); in VG_()
865 AvlNode *t; in VG_() local
876 t = oset->root; in VG_()
879 if (t == NULL) return; in VG_()
882 cmpresS = (Word)slow_cmp(oset, k, t); in VG_()
884 cmpresS = fast_cmp(k, t); in VG_()
896 stackPush(oset, t, 2); in VG_()
905 stackPush(oset, t, 2); in VG_()
907 t = cmpresU==0 ? t->left : t->right; in VG_()
915 UInt VG_(OSetGen_Size)(const AvlTree* t) in VG_()
917 vg_assert(t); in VG_()
918 return t->nElems; in VG_()
921 Word VG_(OSetWord_Size)(const AvlTree* t) in VG_()
923 return VG_(OSetGen_Size)(t); in VG_()
926 static void OSet_Print2( const AvlTree* t, const AvlNode* n, in OSet_Print2() argument
932 if (n->right) OSet_Print2(t, n->right, strElem, p+1); in OSet_Print2()
935 if (n->left) OSet_Print2(t, n->left, strElem, p+1); in OSet_Print2()
939 static void OSet_Print( const AvlTree* t, const HChar *where, in OSet_Print() argument
943 OSet_Print2(t, t->root, strElem, 0); in OSet_Print()