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

Subversion Repositories HelenOS

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