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

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

Subversion Repositories HelenOS

(root)/branches/rcu/kernel/generic/src/adt/favl.c @ 2497 – Rev 2466