WebSVN – HelenOS – Blame – /branches/rcu/kernel/generic/src/adt/avl.c

Rev	Author	Line No.	Line
2416	mencl	1	/*
2421	mencl	2	* Copyright (c) 2007 Vojtech Mencl
2416	mencl	3	* All rights reserved.
		4	*
		5	* Redistribution and use in source and binary forms, with or without
		6	* modification, are permitted provided that the following conditions
		7	* are met:
		8	*
		9	* - Redistributions of source code must retain the above copyright
		10	* notice, this list of conditions and the following disclaimer.
		11	* - Redistributions in binary form must reproduce the above copyright
		12	* notice, this list of conditions and the following disclaimer in the
		13	* documentation and/or other materials provided with the distribution.
		14	* - The name of the author may not be used to endorse or promote products
		15	* derived from this software without specific prior written permission.
		16	*
		17	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
		18	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
		19	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
		20	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
		21	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
		22	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
		23	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
		24	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
		25	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
		26	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
		27	*/
		28
		29	/** @addtogroup genericadt
		30	* @{
		31	*/
		32
		33	/**
		34	* @file
		35	* @brief AVL tree implementation.
		36	*
		37	* This file implements AVL tree type and operations.
		38	*
		39	* Implemented AVL tree has the following properties:
2461	mencl	40	* @li It is binary search tree with non-unique keys.
2416	mencl	41	* @li Difference of heights of left and right subtree of every node is max 1.
		42	*
		43	* Every node has pointer to its parent which allows insertion of multiple identical keys
		44	* into tree.
		45	*
		46	* Be careful of using this tree because of base atribute, which is added to every inserted
		47	* node key. There is no rule in which order nodes with the same key are visited.
		48	*/
		49
		50	#include <adt/avl.h>
		51	#include <debug.h>
		52
		53
		54	#define AVLTREE_LEFT 0
		55	#define AVLTREE_RIGHT 1
		56
		57
		58	/** Search first occurence of given key in AVL tree.
		59	*
		60	* @param t AVL tree.
		61	* @param key Key to be searched.
		62	*
2421	mencl	63	* @return Pointer to node or NULL if there is no such key.
2416	mencl	64	*/
		65	avltree_node_t avltree_search(avltree_t t, uint64_t key)
		66	{
		67	avltree_node_t *p;
		68
		69	/*
		70	* Iteratively descend to the leaf that can contain the searched key.
		71	*/
		72	p = t->root;
		73	while (p != NULL) {
		74	if (p->key > key)
		75	p = p->lft;
		76	else if (p->key < key)
		77	p = p->rgt;
		78	else {
		79	return p;
		80	}
		81	}
		82	return NULL;
		83	}
		84
		85
2421	mencl	86	/** Find node with smallest key in AVL tree.
		87	*
		88	* @param t AVL tree.
		89	*
		90	* @return Pointer to node or NULL if there is no node in the tree.
		91	*/
		92	avltree_node_t avltree_find_min(avltree_t t)
		93	{
		94	avltree_node_t *p = t->root;
		95
		96	/*
		97	* Check whether tree is empty.
		98	*/
		99	if (!p) return NULL;
		100
		101	/*
		102	* Iteratively descend to the leftmost leaf in the tree.
		103	*/
		104	while (p->lft != NULL)
		105	p = p->lft;
		106
		107	return p;
		108	}
		109
2416	mencl	110	/** Insert new node into AVL tree.
		111	*
		112	* @param t AVL tree.
		113	* @param newnode New node to be inserted.
		114	*/
		115	void avltree_insert(avltree_t t, avltree_node_t newnode)
		116	{
		117	avltree_node_t *par;
		118	avltree_node_t *gpa;
		119	avltree_node_t *top;
		120	avltree_node_t **dpc;
		121	uint64_t key;
		122
		123	ASSERT(t);
		124	ASSERT(newnode);
		125
		126	/*
		127	* Creating absolute key.
		128	*/
		129	key = newnode->key + t->base;
		130
		131
		132	/*
2461	mencl	133	* Iteratively descend to the leaf that can contain new node.
2416	mencl	134	* Last node with non-zero balance in the way to leaf is stored as top -
2461	mencl	135	* it si place of possible balance fault.
2416	mencl	136	*/
		137	dpc = &t->root;
		138	gpa = NULL;
		139	top = t->root;
2421	mencl	140	while ((par = (*dpc)) != NULL) {
2416	mencl	141	if (par->balance != 0) {
		142	top = par;
		143	}
		144	gpa = par;
		145	dpc = par->key > key? &par->lft: &par->rgt;
		146	}
		147
		148	/*
		149	* Initialize new node.
		150	*/
		151	newnode->key = key;
		152	newnode->lft = NULL;
		153	newnode->rgt = NULL;
		154	newnode->par = gpa;
		155	newnode->balance = 0;
		156
		157	/*
		158	* Insert first node into empty tree.
		159	*/
		160	if (t->root == NULL) {
		161	*dpc = newnode;
		162	return;
		163	}
		164
		165	/*
		166	* Insert new node into previously found leaf place.
		167	*/
		168	*dpc = newnode;
		169
		170	/*
		171	* If tree contains one node - end.
		172	*/
		173	if (top == NULL) return;
		174
		175	/*
		176	* Store pointer of top's father which points to the node with potentialy broken
		177	* balance (top).
		178	*/
		179	if (top->par == NULL)
		180	dpc = &t->root;
		181	else
		182	if (top->par->lft == top)
		183	dpc = &(top->par->lft);
		184	else
		185	dpc = &(top->par->rgt);
		186
		187	/*
		188	* Repair all balances on the way from top node to newly inserted node.
		189	*/
		190	par = top;
		191	while (par != newnode) {
		192	if (par->key > key) {
		193	par->balance--;
		194	par = par->lft;
		195	} else {
		196	par->balance++;
		197	par = par->rgt;
		198	}
		199	}
		200
		201	/*
		202	* To balance tree we must check and balance top node.
		203	*/
		204	if (top->balance == -2) {
		205	par = top->lft;
		206	if (par->balance == -1) {
		207	/*
		208	* LL rotation.
		209	*/
		210	top->lft = par->rgt;
		211	if (top->lft != NULL) top->lft->par = top;
		212	par->par = top->par;
		213	top->par = par;
		214	par->rgt = top;
		215	par->balance = top->balance = 0;
		216	*dpc = par;
		217	} else {
		218	/*
		219	* LR rotation.
		220	*/
		221	ASSERT(par->balance == 1);
		222
		223	gpa = par->rgt;
		224	par->rgt = gpa->lft;
		225	if (gpa->lft != NULL) gpa->lft->par = par;
		226	gpa->lft = par;
		227	par->par = gpa;
		228	top->lft = gpa->rgt;
		229	if (gpa->rgt != NULL) gpa->rgt->par = top;
		230	gpa->rgt = top;
		231	gpa->par = top->par;
		232	top->par = gpa;
		233
		234	if (gpa->balance == -1) {
		235	par->balance = 0;
		236	top->balance = 1;
		237	} else if (gpa->balance == 0) {
		238	par->balance = top->balance = 0;
		239	} else {
		240	par->balance = -1;
		241	top->balance = 0;
		242	}
		243	gpa->balance = 0;
		244	*dpc = gpa;
		245	}
		246	} else if (top->balance == 2) {
		247	par = top->rgt;
		248	if (par->balance == 1) {
		249	/*
		250	* RR rotation.
		251	*/
		252	top->rgt = par->lft;
		253	if (top->rgt != NULL) top->rgt->par = top;
		254	par->par = top->par;
		255	top->par = par;
		256	par->lft = top;
		257	par->balance = top->balance = 0;
		258	*dpc = par;
		259	} else {
		260	/*
		261	* RL rotation.
		262	*/
		263	ASSERT(par->balance == -1);
		264
		265	gpa = par->lft;
		266	par->lft = gpa->rgt;
		267	if (gpa->rgt != NULL) gpa->rgt->par = par;
		268	gpa->rgt = par;
		269	par->par = gpa;
		270	top->rgt = gpa->lft;
		271	if (gpa->lft != NULL) gpa->lft->par = top;
		272	gpa->lft = top;
		273	gpa->par = top->par;
		274	top->par = gpa;
		275
		276	if (gpa->balance == 1) {
		277	par->balance = 0;
		278	top->balance = -1;
		279	} else if (gpa->balance == 0) {
		280	par->balance = top->balance = 0;
		281	} else {
		282	par->balance = 1;
		283	top->balance = 0;
		284	}
		285	gpa->balance = 0;
		286	*dpc = gpa;
		287	}
		288	} else {
		289	/*
		290	* Balance is not broken, insertion is finised.
		291	*/
		292	return;
		293	}
		294
		295	}
		296
		297	/** Delete node from AVL tree.
		298	*
		299	* Because of allowed multiple identical keys parent pointers are essential
		300	* during deletition.
		301	*
		302	* @param t AVL tree structure.
		303	* @param node Address of node which will be deleted.
		304	*/
		305	void avltree_delete(avltree_t t, avltree_node_t node)
		306	{
		307	avltree_node_t *cur;
		308	avltree_node_t *par;
		309	avltree_node_t *gpa;
		310	uint8_t dir;
		311
		312	ASSERT(t);
		313	ASSERT(node);
		314
		315
		316	if (node->lft == NULL) {
		317	if (node->rgt) {
		318	/*
		319	* Replace node with its only right son.
		320	*
		321	* Balance of right son will be repaired in balancing cycle.
		322	*/
		323	cur = node->rgt;
		324	cur->par = node->par;
		325	gpa = cur;
		326	dir = AVLTREE_RIGHT;
		327	cur->balance = node->balance;
		328	} else {
		329	if (node->par == NULL) {
		330	/*
		331	* Tree has only one node - it will be empty tree and balancing can end.
		332	*/
		333	t->root = NULL;
		334	return;
		335	}
		336	/*
		337	* Node has no child, will be deleted with no substitution.
		338	*/
		339	gpa = node->par;
		340	cur = NULL;
		341	dir = (gpa->lft == node)? AVLTREE_LEFT: AVLTREE_RIGHT;
		342	}
		343	} else {
		344	/*
		345	* Node has left and right son. Find a node with smallest key in left subtree
		346	* and replace deleted node with that node.
		347	*/
		348	for (cur = node->lft; cur->rgt != NULL; cur = cur->rgt)
		349	;
		350
		351	//cur obsahuje uzel, ktery vlozim misto uzlu node
		352
		353	if (cur != node->lft) {
		354	/*
		355	* The most right node of deleted node's left subtree was found. Replace
		356	* deleted node with this node. Cutting founded node has two cases in
		357	* dependence on its left son.
		358	*/
		359	if (cur->lft) {
		360	/*
		361	* Founded node has left son.
		362	*/
		363	gpa = cur->lft;
		364	gpa->par = cur->par;
		365	dir = AVLTREE_LEFT;
		366	gpa->balance = cur->balance;
		367	} else {
		368	dir = AVLTREE_RIGHT;
		369	gpa = cur->par;
		370	}
		371	cur->par->rgt = cur->lft;
		372	cur->lft = node->lft;
		373	cur->lft->par = cur;
		374	} else {
		375	/*
		376	* Left son of node hasn't got right son. Left son will take deleted node's place.
		377	*/
		378	dir = AVLTREE_LEFT;
		379	gpa = cur;
		380	}
		381	if (node->rgt) node->rgt->par = cur;
		382	cur->rgt = node->rgt;
		383	cur->balance = node->balance;
		384	cur->par = node->par;
		385	}
		386
		387	/*
		388	* Repair parent nodes pointer which pointed previously to deleted node.
		389	*/
		390	if (node->par == NULL) {
		391	t->root = cur;
		392	} else {
		393	if (node->par->lft == node) {
		394	node->par->lft = cur;
		395	} else {
		396	node->par->rgt = cur;
		397	}
		398	}
		399
		400	/*
		401	* Repair cycle which repairs balances of nodes in way from cutted noded down to root.
		402	*/
		403	for(;;) {
		404	if (dir == AVLTREE_LEFT) {
		405	/*
		406	* Deletition was made in left subtree.
		407	*/
		408	gpa->balance++;
		409	if (gpa->balance == +1) {
		410	/*
		411	* Stop balancing, tree is balanced.
		412	*/
		413	break;
		414	} else if (gpa->balance == +2) {
		415	/*
		416	* Bad balance, heights of left and right subtrees differs more then is allowed.
		417	*/
		418	par = gpa->rgt;
		419
		420	if (par->balance == -1) {
		421	/*
		422	* RL rotation.
		423	*/
		424
		425	cur = par->lft;
		426	par->lft = cur->rgt;
		427	cur->rgt = par;
		428	gpa->rgt = cur->lft;
		429	cur->lft = gpa;
		430
		431	/*
		432	* Repair balances and paternity of childs in dependence on
		433	* balance factor of grand child (cur).
		434	*/
		435	if (cur->balance == +1) {
		436	par->balance = 0;
		437	gpa->balance = -1;
		438	if (gpa->rgt) gpa->rgt->par = gpa;
		439	par->lft->par = par;
		440	} else if (cur->balance == 0) {
		441	par->balance = gpa->balance = 0;
		442	if (gpa->rgt) gpa->rgt->par = gpa;
		443	if (par->lft) par->lft->par = par;
		444	} else {
		445	par->balance = +1;
		446	gpa->balance = 0;
		447	if (par->lft) par->lft->par = par;
		448	gpa->rgt->par = gpa;
		449	}
		450	cur->balance = 0;
		451
		452	/*
		453	* Repair paternity.
		454	*/
		455	cur->par = gpa->par;
		456	gpa->par = cur;
		457	par->par = cur;
		458
		459	/*
		460	* Repair pointer which pointed to balanced node. If it was root then balancing
		461	* is finished else continue in next iteration (parent node).
		462	*/
		463	if (cur->par == NULL) {
		464	t->root = cur;
		465	break;
		466	} else
		467	if (cur->par->lft == gpa) {
		468	cur->par->lft = cur;
		469	dir = AVLTREE_LEFT;
		470	} else {
		471	cur->par->rgt = cur;
		472	dir = AVLTREE_RIGHT;
		473	}
		474	gpa = cur->par;
		475	} else {
		476	/*
		477	* RR rotation.
		478	*/
		479
		480	gpa->rgt = par->lft;
		481	if (par->lft) par->lft->par = gpa;
		482	par->lft = gpa;
		483
		484	/*
		485	* Repair paternity.
		486	*/
		487	par->par = gpa->par;
		488	gpa->par = par;
		489
		490	if (par->balance == 0) {
		491	/*
		492	* Right child of balanced node is balanced, after RR rotation is done, whole
		493	* tree will be balanced.
		494	*/
		495	par->balance = -1;
		496	gpa->balance = +1;
		497
		498	/*
		499	* Repair pointer which pointed to balanced node and finish balancing.
		500	*/
		501	if (par->par == NULL) {
		502	t->root = par;
		503	} else
		504	if (par->par->lft == gpa) {
		505	par->par->lft = par;
		506	} else {
		507	par->par->rgt = par;
		508	}
		509	break;
		510	} else {
		511	par->balance = gpa->balance = 0;
		512	/*
		513	* Repair pointer which pointed to balanced node. If it was root then balancing
		514	* is finished else continue in next iteration (parent node).
		515	*/
		516	if (par->par == NULL) {
		517	t->root = par;
		518	break;
		519	} else {
		520
		521	if (par->par->lft == gpa) {
		522	par->par->lft = par;
		523	dir = AVLTREE_LEFT;
		524	} else {
		525	par->par->rgt = par;
		526	dir = AVLTREE_RIGHT;
		527	}
		528	}
		529	}
		530	gpa = par->par;
		531	}
		532	} else {
		533	/*
		534	* Repair pointer which pointed to balanced node. If it was root then balancing
		535	* is finished else continue in next iteration (parent node).
		536	*/
		537	if (!gpa->par) break;
		538
		539	if (gpa->par->lft == gpa) {
		540	dir = AVLTREE_LEFT;
		541	} else {
		542	dir = AVLTREE_RIGHT;
		543	}
		544	gpa = gpa->par;
		545	}
		546	} else {
		547	/*
		548	* Deletition was made in right subtree.
		549	*/
		550	gpa->balance--;
		551	if (gpa->balance == -1) {
		552	/*
		553	* Stop balancing, tree is balanced.
		554	*/
		555	break;
		556	} else if (gpa->balance == -2) {
		557	/*
		558	* Bad balance, heights of left and right subtrees differs more then is allowed.
		559	*/
		560	par = gpa->lft;
		561
		562	if (par->balance == +1) {
		563	/*
		564	* LR rotation.
		565	*/
		566
		567	cur = par->rgt;
		568	par->rgt = cur->lft;
		569	cur->lft = par;
		570	gpa->lft = cur->rgt;
		571	cur->rgt = gpa;
		572
		573	/*
		574	* Repair balances and paternity of childs in dependence on
		575	* balance factor of grand child (cur).
		576	*/
		577	if (cur->balance == -1) {
		578	par->balance = 0;
		579	gpa->balance = +1;
		580	if (gpa->lft) gpa->lft->par = gpa;
		581	par->rgt->par = par;
		582	} else if (cur->balance == 0) {
		583	par->balance = gpa->balance = 0;
		584	if (gpa->lft) gpa->lft->par = gpa;
		585	if (par->rgt) par->rgt->par = par;
		586	} else {
		587	par->balance = -1;
		588	gpa->balance = 0;
		589	if (par->rgt) par->rgt->par = par;
		590	gpa->lft->par = gpa;
		591	}
		592	cur->balance = 0;
		593
		594	/*
		595	* Repair paternity.
		596	*/
		597	cur->par = gpa->par;
		598	gpa->par = cur;
		599	par->par = cur;
		600
		601	/*
		602	* Repair pointer which pointed to balanced node. If it was root then balancing
		603	* is finished else continue in next iteration (parent node).
		604	*/
		605	if (cur->par == NULL) {
		606	t->root = cur;
		607	break;
		608	} else
		609	if (cur->par->lft == gpa) {
		610	cur->par->lft = cur;
		611	dir = AVLTREE_LEFT;
		612	} else {
		613	cur->par->rgt = cur;
		614	dir = AVLTREE_RIGHT;
		615	}
		616	gpa = cur->par;
		617	} else {
		618	/*
		619	* LL rotation.
		620	*/
		621
		622	gpa->lft = par->rgt;
		623	if (par->rgt) par->rgt->par = gpa;
		624	par->rgt = gpa;
		625	/*
		626	* Repair paternity.
		627	*/
		628	par->par = gpa->par;
		629	gpa->par = par;
		630
		631	if (par->balance == 0) {
		632	/*
		633	* Left child of balanced node is balanced, after RR rotation is done, whole
		634	* tree will be balanced.
		635	*/
		636	par->balance = +1;
		637	gpa->balance = -1;
		638
		639	/*
		640	* Repair pointer which pointed to balanced node and finish balancing.
		641	*/
		642	if (par->par == NULL) {
		643	t->root = par;
		644	} else
		645	if (par->par->lft == gpa) {
		646	par->par->lft = par;
		647	} else {
		648	par->par->rgt = par;
		649	}
		650	break;
		651	} else {
		652	par->balance = gpa->balance = 0;
		653
		654	/*
		655	* Repair pointer which pointed to balanced node. If it was root then balancing
		656	* is finished else continue in next iteration (parent node).
		657	*/
		658	if (par->par == NULL) {
		659	t->root = par;
		660	break;
		661	} else {
		662	if (par->par->lft == gpa) { //v cyklu jsem ani jednou neskocil - cur nema praveho syna
		663	par->par->lft = par;
		664	dir = AVLTREE_LEFT;
		665	} else {
		666	par->par->rgt = par;
		667	dir = AVLTREE_RIGHT;
		668	}
		669	}
		670	}
		671	gpa = par->par;
		672	}
		673	} else {
		674	/*
		675	* Repair pointer which pointed to balanced node. If it was root then balancing
		676	* is finished else continue in next iteration (parent node).
		677	*/
		678	if (!gpa->par) break;
		679
		680	if (gpa->par->lft == gpa) {
		681	dir = AVLTREE_LEFT;
		682	} else {
		683	dir = AVLTREE_RIGHT;
		684	}
		685	gpa = gpa->par;
		686	}
		687	}
		688	}
		689	}
		690
		691
2450	mencl	692	/** Delete node from AVL tree with the smallest key.
2416	mencl	693	*
		694	* @param t AVL tree structure.
		695	*/
2421	mencl	696	bool avltree_delete_min(avltree_t *t)
2416	mencl	697	{
		698	avltree_node_t *node;
		699
		700	/*
		701	* Start search of smallest key in tree in the root node and
		702	* continue in cycle to the most left node in the tree which
		703	* must have smallest key.
		704	*/
		705	node = t->root;
		706	if (!node) return false;
		707
		708	while (node->lft != NULL)
		709	node = node->lft;
		710
		711	/*
2461	mencl	712	* Use avltree_delete function to delete node from tree.
2416	mencl	713	*/
		714	avltree_delete(t,node);
		715
		716	return true;
		717	}

Subversion Repositories HelenOS

(root)/branches/rcu/kernel/generic/src/adt/avl.c – Rev 2465