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

Subversion Repositories HelenOS

(root)/trunk/kernel/generic/src/adt/avl.c @ 3143 – Rev 2421