rripfdb.c

来自「用于嵌入式系统的TCP/IP协议栈及若干服务」· C语言 代码 · 共 2,850 行 · 第 1/5 页

	while(tmp){

		/* potential starting point for adjustment */
		if(tmp->iprt_bal) adjnd = tmp;

		if(add > tmp->iprt_ipa.ip_add){
			if(!tmp->iprt_right){
				tmp->iprt_right = node;
				node->iprt_bwd = tmp;
				break;
			}
			tmp = tmp->iprt_right;
		}
		else if(add < tmp->iprt_ipa.ip_add){
			if(!tmp->iprt_left){
				tmp->iprt_left = node;
				node->iprt_bwd = tmp;
				break;
			}
			tmp = tmp->iprt_left;
		}
		else return(0);
	}

	/* adjust balance factors, starting from next after
	   adjnd. (adjnd adjusted later)
	*/
	if(add < adjnd->iprt_ipa.ip_add){
		tmp = adjnd->iprt_left;
		a = -1;
	}
	else{
		tmp = adjnd->iprt_right;
		a = 1;
	}
	r = tmp;
	while(tmp != node){
		if(add < tmp->iprt_ipa.ip_add){
			tmp->iprt_bal = -1;
			tmp = tmp->iprt_left;
		}
		else{
			tmp->iprt_bal = 1;
			tmp = tmp->iprt_right;
		}
	}
	/* do we need to rebalance? */
	if(!adjnd->iprt_bal){
		/* tree 1 deeper, still balanced.
		  only happens when adjnd is head */
		adjnd->iprt_bal = a;
	}
	else if( adjnd->iprt_bal != a ){
		/* tree is more balanced */
		adjnd->iprt_bal = 0;
	}
	else{
		/* whoops, out of balance, rebalance */
		if( r->iprt_bal == a ){
			/* right single rotate */
			if( a == 1 ){
				/* fwd ptrs */
				adjnd->iprt_right = r->iprt_left;
				r->iprt_left = adjnd;
				adjnd->iprt_bal = r->iprt_bal = 0;
				if(adjnd != head){
					ADJ_BLINK(adjnd,r);
				}
				else{
					/* tree head has changed, must
					adjust link of trees */
					if(adjnd->iprt_bwd){
						adjnd->iprt_bwd->iprt_fwd = r;
					}
					else{
						tbl[2*bin] = r;
					}
					if(adjnd->iprt_fwd){
						adjnd->iprt_fwd->iprt_bwd = r;
					}
					else{
						tbl[2*bin+1] = r;
					}
					r->iprt_fwd = adjnd->iprt_fwd;
				}
				/* iprt_bwd ptrs */
				r->iprt_bwd = adjnd->iprt_bwd;
				adjnd->iprt_bwd = r;
				if(adjnd->iprt_right)
					adjnd->iprt_right->iprt_bwd = adjnd;
			}
			/* left single rotate */
			else{
				/* fwd ptrs */
				adjnd->iprt_left = r->iprt_right;
				r->iprt_right = adjnd;
				adjnd->iprt_bal = r->iprt_bal = 0;
				if(adjnd != head){
					ADJ_BLINK(adjnd,r);
				}
				else{
					/* tree head has changed, must
					adjust link of trees */
					if(adjnd->iprt_bwd){
						adjnd->iprt_bwd->iprt_fwd = r;
					}
					else{
						tbl[2*bin] = r;
					}
					if(adjnd->iprt_fwd){
						adjnd->iprt_fwd->iprt_bwd = r;
					}
					else{
						tbl[2*bin+1] = r;
					}
					r->iprt_fwd = adjnd->iprt_fwd;
				}
				/* back ptrs */
				r->iprt_bwd = adjnd->iprt_bwd;
				adjnd->iprt_bwd = r;
				if(adjnd->iprt_left)
					adjnd->iprt_left->iprt_bwd = adjnd;
			}
		}
		else{
			/* right double rotate */
			if( a == 1){
				/* fwd links */
				tmp = r->iprt_left;
				r->iprt_left = tmp->iprt_right;
				tmp->iprt_right = r;
				adjnd->iprt_right = tmp->iprt_left;
				tmp->iprt_left = adjnd;
				if(tmp->iprt_bal == a){
					adjnd->iprt_bal = -a;
					r->iprt_bal = 0;
				}
				else if(!tmp->iprt_bal){
					adjnd->iprt_bal = 0;
					r->iprt_bal = 0;
				}
				else{
					adjnd->iprt_bal = 0;
					r->iprt_bal = a;
				}
				tmp->iprt_bal = 0;
				if(adjnd != head){
					ADJ_BLINK(adjnd,tmp);
				}
				else{
					/* tree head has changed, must
					adjust link of trees */
					if(adjnd->iprt_bwd){
						adjnd->iprt_bwd->iprt_fwd = tmp;
					}
					else{
						tbl[2*bin] = tmp;
					}
					if(adjnd->iprt_fwd){
						adjnd->iprt_fwd->iprt_bwd = tmp;
					}
					else{
						tbl[2*bin+1] = tmp;
					}
					tmp->iprt_fwd = adjnd->iprt_fwd;
				}
				/* back links */
				tmp->iprt_bwd = adjnd->iprt_bwd;
				r->iprt_bwd = tmp;
				adjnd->iprt_bwd = tmp;
				if(adjnd->iprt_right)
					adjnd->iprt_right->iprt_bwd = adjnd;
				if(r->iprt_left)
					r->iprt_left->iprt_bwd = r;
			}
			else{
				/* fwd links */
				tmp = r->iprt_right;
				r->iprt_right = tmp->iprt_left;
				tmp->iprt_left = r;
				adjnd->iprt_left = tmp->iprt_right;
				tmp->iprt_right = adjnd;
				if(tmp->iprt_bal == a){
					adjnd->iprt_bal = -a;
					r->iprt_bal = 0;
				}
				else if(!tmp->iprt_bal){
					adjnd->iprt_bal = 0;
					r->iprt_bal = 0;
				}
				else{
					adjnd->iprt_bal = 0;
					r->iprt_bal = a;
				}
				tmp->iprt_bal = 0;
				if(adjnd != head){
					ADJ_BLINK(adjnd,tmp);
				}
				else{
					/* tree head has changed, must
					adjust link of trees */
					if(adjnd->iprt_bwd){
						adjnd->iprt_bwd->iprt_fwd = tmp;
					}
					else{
						tbl[2*bin] = tmp;
					}
					if(adjnd->iprt_fwd){
						adjnd->iprt_fwd->iprt_bwd = tmp;
					}
					else{
						tbl[2*bin+1] = tmp;
					}
					tmp->iprt_fwd = adjnd->iprt_fwd;
				}
				/* back links */
				tmp->iprt_bwd = adjnd->iprt_bwd;
				r->iprt_bwd = tmp;
				adjnd->iprt_bwd = tmp;
				if(adjnd->iprt_left)
					adjnd->iprt_left->iprt_bwd = adjnd;
				if(r->iprt_right)
					r->iprt_right->iprt_bwd = r;
			}
		}
	}
	return(0);
}

static void ip_btdelete(iproute_ent *nd,iproute_ent *head,iproute_ent **tbl,int bin)
{
	iproute_ent *tmp,*fwd,*x;
	iproute_ent troute;
	int lr,arht,alht,blht,brht;

	/* we can only remove from end of tree, so.. */
	/* if have both left and right link, shuffle by
	   finding the leftmost entry in the right path and
	   exchanging. the resulting tree is out of order, but
	   we dont care since the offending member (nd), which
	   is now at the end, will be deleted.
	*/
	if(nd->iprt_left && nd->iprt_right){
		tmp = nd->iprt_right;
		while(tmp->iprt_left){
			tmp = tmp->iprt_left;
		}
		/* do swap places */
		troute.iprt_right = tmp->iprt_right;
		troute.iprt_bwd = tmp->iprt_bwd;
		troute.iprt_bal = tmp->iprt_bal;
		tmp->iprt_bwd = nd->iprt_bwd;
		if(nd->iprt_right == tmp){
			tmp->iprt_right = nd;
			nd->iprt_bwd = tmp;
		}
		else{
			tmp->iprt_right = nd->iprt_right;
			nd->iprt_bwd = troute.iprt_bwd;
		}
		tmp->iprt_left = nd->iprt_left;
		tmp->iprt_fwd = nd->iprt_fwd;
		tmp->iprt_bal = nd->iprt_bal;
		nd->iprt_left = 0;
		nd->iprt_right = troute.iprt_right;
		nd->iprt_fwd = 0;
		nd->iprt_bal = troute.iprt_bal;

		/* now adjust all links pointing to these
		   nodes.
		*/
		if(head == nd){
			head = tmp;
			if(tmp->iprt_fwd){
				tmp->iprt_fwd->iprt_bwd = tmp;
			}
			else{
				tbl[2*bin+1] = tmp;
			}
			if(tmp->iprt_bwd){
				tmp->iprt_bwd->iprt_fwd = tmp;
			}
			else{
				tbl[2*bin] = tmp;
			}
		}
		else{
			if(tmp->iprt_bwd->iprt_left == nd)
				tmp->iprt_bwd->iprt_left = tmp;
			else
				tmp->iprt_bwd->iprt_right = tmp;
		}
		tmp->iprt_left->iprt_bwd = tmp;
		tmp->iprt_right->iprt_bwd = tmp;
		if(nd->iprt_right)
			nd->iprt_right->iprt_bwd = nd;
		/* if nodes were not adjacent */
		if(tmp->iprt_right != nd){
			nd->iprt_bwd->iprt_left = nd;
		}
	}

	/* now delete a node which has at least one null link*/
	if(!nd->iprt_left){
		/* previous will now point to our right */
		if(nd != head){
			tmp = nd->iprt_bwd;
			if(nd->iprt_bwd->iprt_left == nd){
				nd->iprt_bwd->iprt_left = nd->iprt_right;
				lr = +1;
			}
			else{
				nd->iprt_bwd->iprt_right = nd->iprt_right;
				lr = -1;
			}
			if(nd->iprt_right)
				nd->iprt_right->iprt_bwd = nd->iprt_bwd;
		}
		else{
			/* we know he has right link or never
			   enter ip_btdelete */
			head = nd->iprt_right;
			head->iprt_bwd = nd->iprt_bwd;
			if(head->iprt_bwd)
				head->iprt_bwd->iprt_fwd = head;
			else
				tbl[2*bin] = head;
			head->iprt_fwd = nd->iprt_fwd;
			if(head->iprt_fwd)
				head->iprt_fwd->iprt_bwd = head;
			else
				tbl[2*bin+1] = head;
			return;
		}
	}
	else{
		/* previous will now point to our iprt_left */
		if(nd != head){
			tmp = nd->iprt_bwd;
			if(nd->iprt_bwd->iprt_right == nd){
				nd->iprt_bwd->iprt_right = nd->iprt_left;
				lr = -1;
			}
			else{
				nd->iprt_bwd->iprt_left = nd->iprt_left;
				lr = +1;
			}
			if(nd->iprt_left)
				nd->iprt_left->iprt_bwd = nd->iprt_bwd;
		}
		else{
			/* we know he has left link or never
			   enter ip_btdelete */
			head = nd->iprt_left;
			head->iprt_bwd = nd->iprt_bwd;
			if(head->iprt_bwd)
				head->iprt_bwd->iprt_fwd = head;
			else
				tbl[2*bin] = head;
			head->iprt_fwd = nd->iprt_fwd;
			if(head->iprt_fwd)
				head->iprt_fwd->iprt_bwd = head;
			else
				tbl[2*bin+1] = head;

			return;
		}
	}
	/* work our way back up the tree, rebalancing as
	   we go. start with the parent of the node we just
	   deleted. here is the pertinent info we need:
	   - we know that parent's tree has shrunk by one on
		the side nd was on, whether or not nd had a child.
	   - we know nd's child tree, if it had one consisted
		of only a single child on one side, otherwise the
		tree was out of balance to begin with.
	*/
	while(tmp){
		tmp->iprt_bal += lr;
		if(tmp->iprt_bal >1){
			/* need to rebalance, 3 cases (and their
			   mirror. all delete from a left.
			   (see knuth pg 454)
			   1: a->right = b, alht = h, blht = h,
							brht = h+1
			   2: a->right = b, alht = h, blht = h+1,
							brht = h
			   3: a->right = b, alht = h, blht = h+1,
							brht = h+1
				 dgenerates to case 1, except new bal
			*/
			alht = getTreeHeight(tmp->iprt_left);
			blht = getTreeHeight(tmp->iprt_right->iprt_left);
			brht = getTreeHeight(tmp->iprt_right->iprt_right);
			if(alht != brht){
				/* case 1/3 single rotate */
				/* fwd ptrs */
				fwd = tmp->iprt_right;
				tmp->iprt_right = fwd->iprt_left;
				fwd->iprt_left = tmp;
				if(tmp != head){
					ADJ_BLINK(tmp,fwd);
				}
				else{
					if(tmp->iprt_bwd)
						tmp->iprt_bwd->iprt_fwd = fwd;
					else
						tbl[2*bin] = fwd;
					if(tmp->iprt_fwd)
						tmp->iprt_fwd->iprt_bwd = fwd;
					else
						tbl[2*bin+1] = fwd;
					head = fwd;
					head->iprt_fwd = tmp->iprt_fwd;
				}
				/* back ptrs */
				fwd->iprt_bwd = tmp->iprt_bwd;
				tmp->iprt_bwd = fwd;
				if(tmp->iprt_right)
					tmp->iprt_right->iprt_bwd = tmp;
				/* adjust balance */
				if(blht != brht)
					fwd->iprt_bal = tmp->iprt_bal = 0;
				else{
					tmp->iprt_bal = +1;
					fwd->iprt_bal = -1;
				}
				tmp = fwd;
			}
			else{
				/* case 2 double rotate */
				/* fwd links */
				fwd = tmp->iprt_right;
				x = fwd->iprt_left;
				fwd->iprt_left = x->iprt_right;
				x->iprt_right = fwd;
				tmp->iprt_right = x->iprt_left;
				x->iprt_left = tmp;
				if(tmp != head){
					ADJ_BLINK(tmp,x);
				}
				else{
					if(tmp->iprt_bwd)
						tmp->iprt_bwd->iprt_fwd = x;
					else
						tbl[2*bin] = x;
					if(tmp->iprt_fwd)
						tmp->iprt_fwd->iprt_bwd = x;
					else
						tbl[2*bin+1] = x;
					head = x;
					head->iprt_fwd = tmp->iprt_fwd;
				}
				/* back links */
				x->iprt_bwd = tmp->iprt_bwd;
				fwd->iprt_bwd = x;
				tmp->iprt_bwd = x;
				if(tmp->iprt_right)
					tmp->iprt_right->iprt_bwd = tmp;
				if(fwd->iprt_left)
					fwd->iprt_left->iprt_bwd = fwd;

				/* adjust balance count */
				if(x->iprt_bal == 1){
					tmp->iprt_bal = -1;
					fwd->iprt_bal = 0;
				}
				else if(!x->iprt_bal){
					tmp->iprt_bal = 0;
					fwd->iprt_bal = 0;
				}
				else{
					tmp->iprt_bal = 0;
					fwd->iprt_bal = +1;
				}
				x->iprt_bal = 0;
				tmp = x;
			}
		}
		else if(tmp->iprt_bal < -1){
			/* mirror above */
			arht = getTreeHeight(tmp->iprt_right);
			blht = getTreeHeight(tmp->iprt_left->iprt_left);
			brht = getTreeHeight(tmp->iprt_left->iprt_right);
			if(arht != blht){
				/* case 1/3 single rotate */
				/* fwd ptrs */
				fwd = tmp->iprt_left;
				tmp->iprt_left = fwd->iprt_right;
				fwd->iprt_right = tmp;
				if(tmp != head){
					ADJ_BLINK(tmp,fwd);
				}
				else{
					if(tmp->iprt_bwd)
						tmp->iprt_bwd->iprt_fwd = fwd;
					else
						tbl[2*bin] = fwd;
					if(tmp->iprt_fwd)
						tmp->iprt_fwd->iprt_bwd = fwd;
					else
						tbl[2*bin+1] = fwd;
					head = fwd;
					head->iprt_fwd = tmp->iprt_fwd;
				}
				/* back ptrs */
				fwd->iprt_bwd = tmp->iprt_bwd;
				tmp->iprt_bwd = fwd;
				if(tmp->iprt_left)
					tmp->iprt_left->iprt_bwd = tmp;
				/* adjust balance */
				if(blht != brht)
					fwd->iprt_bal = tmp->iprt_bal = 0;
				else{
					tmp->iprt_bal = -1;
					fwd->iprt_bal = +1;
				}
				tmp = fwd;
			}
			else{
				/* case 2 double rotate */
				/* fwd links */
				fwd = tmp->iprt_left;
				x = fwd->iprt_right;
				fwd->iprt_right = x->iprt_left;
				x->iprt_left = fwd;
				tmp->iprt_left = x->iprt_right;
				x->iprt_right = tmp;
				if(tmp != head){
					ADJ_BLINK(tmp,x);
				}
				else{
					if(tmp->iprt_bwd)
						tmp->iprt_bwd->iprt_fwd = x;
					else
						tbl[2*bin] = x;
					if(tmp->iprt_fwd)
						tmp->iprt_fwd->iprt_bwd = x;
					else
						tbl[2*bin+1] = x;
					head = x;
					head->iprt_fwd = tmp->iprt_fwd;
				}
				/* back links */
				x->iprt_bwd = tmp->iprt_bwd;
				fwd->iprt_bwd = x;
				tmp->iprt_bwd = x;
				if(tmp->iprt_left)
					tmp->iprt_left->iprt_bwd = tmp;
				if(fwd->iprt_right)
					fwd->iprt_right->iprt_bwd = fwd;

				/* adjust balance count */
				if(x->iprt_bal == -1){
					tmp->iprt_bal = +1;
					fwd->iprt_bal = 0;
				}
				else if(!x->iprt_bal){
					tmp->iprt_bal = 0;
					fwd->iprt_bal = 0;
				}
				else{
					tmp->iprt_bal = 0;
					fwd->iprt_bal = -1;
				}
				x->iprt_bal = 0;
				tmp = x;
			}
		}
		else{