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

Rev	Author	Line No.	Line
2416	mencl	1	/*
		2	* Copyright (c) 2006 Vojtech 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:
		40	* @li it is binary search tree with non-unique keys
		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	#include <panic.h>
		53
		54
		55	#define AVLTREE_LEFT 0
		56	#define AVLTREE_RIGHT 1
		57
		58
		59	/** Search first occurence of given key in AVL tree.
		60	*
		61	* @param t AVL tree.
		62	* @param key Key to be searched.
		63	*
		64	* @return Pointer to value or NULL if there is no such key.
		65	*/
		66	avltree_node_t avltree_search(avltree_t t, uint64_t key)
		67	{
		68	avltree_node_t *p;
		69
		70	/*
		71	* Iteratively descend to the leaf that can contain the searched key.
		72	*/
		73	p = t->root;
		74	while (p != NULL) {
		75	if (p->key > key)
		76	p = p->lft;
		77	else if (p->key < key)
		78	p = p->rgt;
		79	else {
		80	return p;
		81	}
		82	}
		83	return NULL;
		84	}
		85
		86
		87	/** Insert new node into AVL tree.
		88	*
		89	* @param t AVL tree.
		90	* @param newnode New node to be inserted.
		91	*/
		92	void avltree_insert(avltree_t t, avltree_node_t newnode)
		93	{
		94	avltree_node_t *par;
		95	avltree_node_t *gpa;
		96	avltree_node_t *top;
		97	avltree_node_t **dpc;
		98	uint64_t key;
		99
		100	ASSERT(t);
		101	ASSERT(newnode);
		102
		103	/*
		104	* Creating absolute key.
		105	*/
		106	key = newnode->key + t->base;
		107
		108
		109	/*
		110	* Iteratively descend to the leaf that can will contain new node.
		111	* Last node with non-zero balance in the way to leaf is stored as top -
		112	* it si place of possible balance failure.
		113	*/
		114	dpc = &t->root;
		115	gpa = NULL;
		116	top = t->root;
		117	while (par = *dpc) {
		118	if (par->balance != 0) {
		119	top = par;
		120	}
		121	gpa = par;
		122	dpc = par->key > key? &par->lft: &par->rgt;
		123	}
		124
		125	/*
		126	* Initialize new node.
		127	*/
		128	newnode->key = key;
		129	newnode->lft = NULL;
		130	newnode->rgt = NULL;
		131	newnode->par = gpa;
		132	newnode->balance = 0;
		133
		134	/*
		135	* Insert first node into empty tree.
		136	*/
		137	if (t->root == NULL) {
		138	*dpc = newnode;
		139	return;
		140	}
		141
		142	/*
		143	* Insert new node into previously found leaf place.
		144	*/
		145	*dpc = newnode;
		146
		147	/*
		148	* If tree contains one node - end.
		149	*/
		150	if (top == NULL) return;
		151
		152	/*
		153	* Store pointer of top's father which points to the node with potentialy broken
		154	* balance (top).
		155	*/
		156	if (top->par == NULL)
		157	dpc = &t->root;
		158	else
		159	if (top->par->lft == top)
		160	dpc = &(top->par->lft);
		161	else
		162	dpc = &(top->par->rgt);
		163
		164	/*
		165	* Repair all balances on the way from top node to newly inserted node.
		166	*/
		167	par = top;
		168	while (par != newnode) {
		169	if (par->key > key) {
		170	par->balance--;
		171	par = par->lft;
		172	} else {
		173	par->balance++;
		174	par = par->rgt;
		175	}
		176	}
		177
		178	/*
		179	* To balance tree we must check and balance top node.
		180	*/
		181	if (top->balance == -2) {
		182	par = top->lft;
		183	if (par->balance == -1) {
		184	/*
		185	* LL rotation.
		186	*/
		187	top->lft = par->rgt;
		188	if (top->lft != NULL) top->lft->par = top;
		189	par->par = top->par;
		190	top->par = par;
		191	par->rgt = top;
		192	par->balance = top->balance = 0;
		193	*dpc = par;
		194	} else {
		195	/*
		196	* LR rotation.
		197	*/
		198	ASSERT(par->balance == 1);
		199
		200	gpa = par->rgt;
		201	par->rgt = gpa->lft;
		202	if (gpa->lft != NULL) gpa->lft->par = par;
		203	gpa->lft = par;
		204	par->par = gpa;
		205	top->lft = gpa->rgt;
		206	if (gpa->rgt != NULL) gpa->rgt->par = top;
		207	gpa->rgt = top;
		208	gpa->par = top->par;
		209	top->par = gpa;
		210
		211	if (gpa->balance == -1) {
		212	par->balance = 0;
		213	top->balance = 1;
		214	} else if (gpa->balance == 0) {
		215	par->balance = top->balance = 0;
		216	} else {
		217	par->balance = -1;
		218	top->balance = 0;
		219	}
		220	gpa->balance = 0;
		221	*dpc = gpa;
		222	}
		223	} else if (top->balance == 2) {
		224	par = top->rgt;
		225	if (par->balance == 1) {
		226	/*
		227	* RR rotation.
		228	*/
		229	top->rgt = par->lft;
		230	if (top->rgt != NULL) top->rgt->par = top;
		231	par->par = top->par;
		232	top->par = par;
		233	par->lft = top;
		234	par->balance = top->balance = 0;
		235	*dpc = par;
		236	} else {
		237	/*
		238	* RL rotation.
		239	*/
		240	ASSERT(par->balance == -1);
		241
		242	gpa = par->lft;
		243	par->lft = gpa->rgt;
		244	if (gpa->rgt != NULL) gpa->rgt->par = par;
		245	gpa->rgt = par;
		246	par->par = gpa;
		247	top->rgt = gpa->lft;
		248	if (gpa->lft != NULL) gpa->lft->par = top;
		249	gpa->lft = top;
		250	gpa->par = top->par;
		251	top->par = gpa;
		252
		253	if (gpa->balance == 1) {
		254	par->balance = 0;
		255	top->balance = -1;
		256	} else if (gpa->balance == 0) {
		257	par->balance = top->balance = 0;
		258	} else {
		259	par->balance = 1;
		260	top->balance = 0;
		261	}
		262	gpa->balance = 0;
		263	*dpc = gpa;
		264	}
		265	} else {
		266	/*
		267	* Balance is not broken, insertion is finised.
		268	*/
		269	return;
		270	}
		271
		272	}
		273
		274	/** Delete node from AVL tree.
		275	*
		276	* Because of allowed multiple identical keys parent pointers are essential
		277	* during deletition.
		278	*
		279	* @param t AVL tree structure.
		280	* @param node Address of node which will be deleted.
		281	*/
		282	void avltree_delete(avltree_t t, avltree_node_t node)
		283	{
		284	avltree_node_t *cur;
		285	avltree_node_t *par;
		286	avltree_node_t *gpa;
		287	uint8_t dir;
		288
		289	ASSERT(t);
		290	ASSERT(node);
		291
		292
		293	if (node->lft == NULL) {
		294	if (node->rgt) {
		295	/*
		296	* Replace node with its only right son.
		297	*
		298	* Balance of right son will be repaired in balancing cycle.
		299	*/
		300	cur = node->rgt;
		301	cur->par = node->par;
		302	gpa = cur;
		303	dir = AVLTREE_RIGHT;
		304	cur->balance = node->balance;
		305	} else {
		306	if (node->par == NULL) {
		307	/*
		308	* Tree has only one node - it will be empty tree and balancing can end.
		309	*/
		310	t->root = NULL;
		311	return;
		312	}
		313	/*
		314	* Node has no child, will be deleted with no substitution.
		315	*/
		316	gpa = node->par;
		317	cur = NULL;
		318	dir = (gpa->lft == node)? AVLTREE_LEFT: AVLTREE_RIGHT;
		319	}
		320	} else {
		321	/*
		322	* Node has left and right son. Find a node with smallest key in left subtree
		323	* and replace deleted node with that node.
		324	*/
		325	for (cur = node->lft; cur->rgt != NULL; cur = cur->rgt)
		326	;
		327
		328	//cur obsahuje uzel, ktery vlozim misto uzlu node
		329
		330	if (cur != node->lft) {
		331	/*
		332	* The most right node of deleted node's left subtree was found. Replace
		333	* deleted node with this node. Cutting founded node has two cases in
		334	* dependence on its left son.
		335	*/
		336	if (cur->lft) {
		337	/*
		338	* Founded node has left son.
		339	*/
		340	gpa = cur->lft;
		341	gpa->par = cur->par;
		342	dir = AVLTREE_LEFT;
		343	gpa->balance = cur->balance;
		344	} else {
		345	dir = AVLTREE_RIGHT;
		346	gpa = cur->par;
		347	}
		348	cur->par->rgt = cur->lft;
		349	cur->lft = node->lft;
		350	cur->lft->par = cur;
		351	} else {
		352	/*
		353	* Left son of node hasn't got right son. Left son will take deleted node's place.
		354	*/
		355	dir = AVLTREE_LEFT;
		356	gpa = cur;
		357	}
		358	if (node->rgt) node->rgt->par = cur;
		359	cur->rgt = node->rgt;
		360	cur->balance = node->balance;
		361	cur->par = node->par;
		362	}
		363
		364	/*
		365	* Repair parent nodes pointer which pointed previously to deleted node.
		366	*/
		367	if (node->par == NULL) {
		368	t->root = cur;
		369	} else {
		370	if (node->par->lft == node) {
		371	node->par->lft = cur;
		372	} else {
		373	node->par->rgt = cur;
		374	}
		375	}
		376
		377	/*
		378	* Repair cycle which repairs balances of nodes in way from cutted noded down to root.
		379	*/
		380	for(;;) {
		381	if (dir == AVLTREE_LEFT) {
		382	/*
		383	* Deletition was made in left subtree.
		384	*/
		385	gpa->balance++;
		386	if (gpa->balance == +1) {
		387	/*
		388	* Stop balancing, tree is balanced.
		389	*/
		390	break;
		391	} else if (gpa->balance == +2) {
		392	/*
		393	* Bad balance, heights of left and right subtrees differs more then is allowed.
		394	*/
		395	par = gpa->rgt;
		396
		397	if (par->balance == -1) {
		398	/*
		399	* RL rotation.
		400	*/
		401
		402	cur = par->lft;
		403	par->lft = cur->rgt;
		404	cur->rgt = par;
		405	gpa->rgt = cur->lft;
		406	cur->lft = gpa;
		407
		408	/*
		409	* Repair balances and paternity of childs in dependence on
		410	* balance factor of grand child (cur).
		411	*/
		412	if (cur->balance == +1) {
		413	par->balance = 0;
		414	gpa->balance = -1;
		415	if (gpa->rgt) gpa->rgt->par = gpa;
		416	par->lft->par = par;
		417	} else if (cur->balance == 0) {
		418	par->balance = gpa->balance = 0;
		419	if (gpa->rgt) gpa->rgt->par = gpa;
		420	if (par->lft) par->lft->par = par;
		421	} else {
		422	par->balance = +1;
		423	gpa->balance = 0;
		424	if (par->lft) par->lft->par = par;
		425	gpa->rgt->par = gpa;
		426	}
		427	cur->balance = 0;
		428
		429	/*
		430	* Repair paternity.
		431	*/
		432	cur->par = gpa->par;
		433	gpa->par = cur;
		434	par->par = cur;
		435
		436	/*
		437	* Repair pointer which pointed to balanced node. If it was root then balancing
		438	* is finished else continue in next iteration (parent node).
		439	*/
		440	if (cur->par == NULL) {
		441	t->root = cur;
		442	break;
		443	} else
		444	if (cur->par->lft == gpa) {
		445	cur->par->lft = cur;
		446	dir = AVLTREE_LEFT;
		447	} else {
		448	cur->par->rgt = cur;
		449	dir = AVLTREE_RIGHT;
		450	}
		451	gpa = cur->par;
		452	} else {
		453	/*
		454	* RR rotation.
		455	*/
		456
		457	gpa->rgt = par->lft;
		458	if (par->lft) par->lft->par = gpa;
		459	par->lft = gpa;
		460
		461	/*
		462	* Repair paternity.
		463	*/
		464	par->par = gpa->par;
		465	gpa->par = par;
		466
		467	if (par->balance == 0) {
		468	/*
		469	* Right child of balanced node is balanced, after RR rotation is done, whole
		470	* tree will be balanced.
		471	*/
		472	par->balance = -1;
		473	gpa->balance = +1;
		474
		475	/*
		476	* Repair pointer which pointed to balanced node and finish balancing.
		477	*/
		478	if (par->par == NULL) {
		479	t->root = par;
		480	} else
		481	if (par->par->lft == gpa) {
		482	par->par->lft = par;
		483	} else {
		484	par->par->rgt = par;
		485	}
		486	break;
		487	} else {
		488	par->balance = gpa->balance = 0;
		489	/*
		490	* Repair pointer which pointed to balanced node. If it was root then balancing
		491	* is finished else continue in next iteration (parent node).
		492	*/
		493	if (par->par == NULL) {
		494	t->root = par;
		495	break;
		496	} else {
		497
		498	if (par->par->lft == gpa) {
		499	par->par->lft = par;
		500	dir = AVLTREE_LEFT;
		501	} else {
		502	par->par->rgt = par;
		503	dir = AVLTREE_RIGHT;
		504	}
		505	}
		506	}
		507	gpa = par->par;
		508	}
		509	} else {
		510	/*
		511	* Repair pointer which pointed to balanced node. If it was root then balancing
		512	* is finished else continue in next iteration (parent node).
		513	*/
		514	if (!gpa->par) break;
		515
		516	if (gpa->par->lft == gpa) {
		517	dir = AVLTREE_LEFT;
		518	} else {
		519	dir = AVLTREE_RIGHT;
		520	}
		521	gpa = gpa->par;
		522	}
		523	} else {
		524	/*
		525	* Deletition was made in right subtree.
		526	*/
		527	gpa->balance--;
		528	if (gpa->balance == -1) {
		529	/*
		530	* Stop balancing, tree is balanced.
		531	*/
		532	break;
		533	} else if (gpa->balance == -2) {
		534	/*
		535	* Bad balance, heights of left and right subtrees differs more then is allowed.
		536	*/
		537	par = gpa->lft;
		538
		539	if (par->balance == +1) {
		540	/*
		541	* LR rotation.
		542	*/
		543
		544	cur = par->rgt;
		545	par->rgt = cur->lft;
		546	cur->lft = par;
		547	gpa->lft = cur->rgt;
		548	cur->rgt = gpa;
		549
		550	/*
		551	* Repair balances and paternity of childs in dependence on
		552	* balance factor of grand child (cur).
		553	*/
		554	if (cur->balance == -1) {
		555	par->balance = 0;
		556	gpa->balance = +1;
		557	if (gpa->lft) gpa->lft->par = gpa;
		558	par->rgt->par = par;
		559	} else if (cur->balance == 0) {
		560	par->balance = gpa->balance = 0;
		561	if (gpa->lft) gpa->lft->par = gpa;
		562	if (par->rgt) par->rgt->par = par;
		563	} else {
		564	par->balance = -1;
		565	gpa->balance = 0;
		566	if (par->rgt) par->rgt->par = par;
		567	gpa->lft->par = gpa;
		568	}
		569	cur->balance = 0;
		570
		571	/*
		572	* Repair paternity.
		573	*/
		574	cur->par = gpa->par;
		575	gpa->par = cur;
		576	par->par = cur;
		577
		578	/*
		579	* Repair pointer which pointed to balanced node. If it was root then balancing
		580	* is finished else continue in next iteration (parent node).
		581	*/
		582	if (cur->par == NULL) {
		583	t->root = cur;
		584	break;
		585	} else
		586	if (cur->par->lft == gpa) {
		587	cur->par->lft = cur;
		588	dir = AVLTREE_LEFT;
		589	} else {
		590	cur->par->rgt = cur;
		591	dir = AVLTREE_RIGHT;
		592	}
		593	gpa = cur->par;
		594	} else {
		595	/*
		596	* LL rotation.
		597	*/
		598
		599	gpa->lft = par->rgt;
		600	if (par->rgt) par->rgt->par = gpa;
		601	par->rgt = gpa;
		602	/*
		603	* Repair paternity.
		604	*/
		605	par->par = gpa->par;
		606	gpa->par = par;
		607
		608	if (par->balance == 0) {
		609	/*
		610	* Left child of balanced node is balanced, after RR rotation is done, whole
		611	* tree will be balanced.
		612	*/
		613	par->balance = +1;
		614	gpa->balance = -1;
		615
		616	/*
		617	* Repair pointer which pointed to balanced node and finish balancing.
		618	*/
		619	if (par->par == NULL) {
		620	t->root = par;
		621	} else
		622	if (par->par->lft == gpa) {
		623	par->par->lft = par;
		624	} else {
		625	par->par->rgt = par;
		626	}
		627	break;
		628	} else {
		629	par->balance = gpa->balance = 0;
		630
		631	/*
		632	* Repair pointer which pointed to balanced node. If it was root then balancing
		633	* is finished else continue in next iteration (parent node).
		634	*/
		635	if (par->par == NULL) {
		636	t->root = par;
		637	break;
		638	} else {
		639	if (par->par->lft == gpa) { //v cyklu jsem ani jednou neskocil - cur nema praveho syna
		640	par->par->lft = par;
		641	dir = AVLTREE_LEFT;
		642	} else {
		643	par->par->rgt = par;
		644	dir = AVLTREE_RIGHT;
		645	}
		646	}
		647	}
		648	gpa = par->par;
		649	}
		650	} else {
		651	/*
		652	* Repair pointer which pointed to balanced node. If it was root then balancing
		653	* is finished else continue in next iteration (parent node).
		654	*/
		655	if (!gpa->par) break;
		656
		657	if (gpa->par->lft == gpa) {
		658	dir = AVLTREE_LEFT;
		659	} else {
		660	dir = AVLTREE_RIGHT;
		661	}
		662	gpa = gpa->par;
		663	}
		664	}
		665	}
		666	}
		667
		668
		669	/** Delete node from AVL tree with the smallest key and set base of tree to that key.
		670	*
		671	* @param t AVL tree structure.
		672	*/
		673	avltree_node_t avltree_delete_min(avltree_t t)
		674	{
		675	avltree_node_t *node;
		676	uint64_t key;
		677
		678	/*
		679	* Start search of smallest key in tree in the root node and
		680	* continue in cycle to the most left node in the tree which
		681	* must have smallest key.
		682	*/
		683	node = t->root;
		684	if (!node) return false;
		685
		686	while (node->lft != NULL)
		687	node = node->lft;
		688
		689	/*
		690	* Store key and use avltree_delete function to delete node from tree.
		691	*/
		692	key = node->key;
		693	avltree_delete(t,node);
		694
		695	/*
		696	* Change base to the key of deleted node.
		697	*/
		698	t->base = key;
		699
		700	return true;
		701	}

Subversion Repositories HelenOS

(root)/branches/rcu/kernel/generic/src/adt/avl.c @ 2496 – Rev 2416