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:
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;
		220	par->balance = top->balance = 0;
		221	*dpc = par;
		222	} else {
		223	/*
		224	* LR rotation.
		225	*/
		226	ASSERT(par->balance == 1);
		227
		228	gpa = par->rgt;
		229	par->rgt = gpa->lft;
2496	jermar	230	if (gpa->lft != NULL)
		231	gpa->lft->par = par;
2416	mencl	232	gpa->lft = par;
		233	par->par = gpa;
		234	top->lft = gpa->rgt;
2496	jermar	235	if (gpa->rgt != NULL)
		236	gpa->rgt->par = top;
2416	mencl	237	gpa->rgt = top;
		238	gpa->par = top->par;
		239	top->par = gpa;
		240
		241	if (gpa->balance == -1) {
		242	par->balance = 0;
		243	top->balance = 1;
		244	} else if (gpa->balance == 0) {
		245	par->balance = top->balance = 0;
		246	} else {
		247	par->balance = -1;
		248	top->balance = 0;
		249	}
		250	gpa->balance = 0;
		251	*dpc = gpa;
		252	}
		253	} else if (top->balance == 2) {
		254	par = top->rgt;
		255	if (par->balance == 1) {
		256	/*
		257	* RR rotation.
		258	*/
		259	top->rgt = par->lft;
2496	jermar	260	if (top->rgt != NULL)
		261	top->rgt->par = top;
2416	mencl	262	par->par = top->par;
		263	top->par = par;
		264	par->lft = top;
		265	par->balance = top->balance = 0;
		266	*dpc = par;
		267	} else {
		268	/*
		269	* RL rotation.
		270	*/
		271	ASSERT(par->balance == -1);
		272
		273	gpa = par->lft;
		274	par->lft = gpa->rgt;
2496	jermar	275	if (gpa->rgt != NULL)
		276	gpa->rgt->par = par;
2416	mencl	277	gpa->rgt = par;
		278	par->par = gpa;
		279	top->rgt = gpa->lft;
2496	jermar	280	if (gpa->lft != NULL)
		281	gpa->lft->par = top;
2416	mencl	282	gpa->lft = top;
		283	gpa->par = top->par;
		284	top->par = gpa;
		285
		286	if (gpa->balance == 1) {
		287	par->balance = 0;
		288	top->balance = -1;
		289	} else if (gpa->balance == 0) {
		290	par->balance = top->balance = 0;
		291	} else {
		292	par->balance = 1;
		293	top->balance = 0;
		294	}
		295	gpa->balance = 0;
		296	*dpc = gpa;
		297	}
		298	} else {
		299	/*
		300	* Balance is not broken, insertion is finised.
		301	*/
		302	return;
		303	}
		304
		305	}
		306
2496	jermar	307	/** Delete a node from the AVL tree.
2416	mencl	308	*
2496	jermar	309	* Because multiple identical keys are allowed, the parent pointers are
		310	* essential during deletion.
2416	mencl	311	*
		312	* @param t AVL tree structure.
2496	jermar	313	* @param node Address of the node which will be deleted.
2416	mencl	314	*/
		315	void avltree_delete(avltree_t t, avltree_node_t node)
		316	{
		317	avltree_node_t *cur;
		318	avltree_node_t *par;
		319	avltree_node_t *gpa;
		320	uint8_t dir;
		321
		322	ASSERT(t);
		323	ASSERT(node);
		324
		325	if (node->lft == NULL) {
		326	if (node->rgt) {
		327	/*
2496	jermar	328	* Replace the node with its only right son.
2416	mencl	329	*
2496	jermar	330	* Balance of the right son will be repaired in the
		331	* balancing cycle.
2416	mencl	332	*/
		333	cur = node->rgt;
		334	cur->par = node->par;
		335	gpa = cur;
2496	jermar	336	dir = RIGHT;
2416	mencl	337	cur->balance = node->balance;
		338	} else {
		339	if (node->par == NULL) {
		340	/*
2496	jermar	341	* The tree has only one node - it will become
		342	* an empty tree and the balancing can end.
2416	mencl	343	*/
		344	t->root = NULL;
		345	return;
		346	}
		347	/*
2496	jermar	348	* The node has no child, it will be deleted with no
		349	* substitution.
2416	mencl	350	*/
		351	gpa = node->par;
		352	cur = NULL;
2496	jermar	353	dir = (gpa->lft == node) ? LEFT: RIGHT;
2416	mencl	354	}
		355	} else {
		356	/*
2496	jermar	357	* The node has left and right son. Find a node with the
		358	* smallest key in the left subtree and replace the deleted node
		359	* with that node.
2416	mencl	360	*/
		361	for (cur = node->lft; cur->rgt != NULL; cur = cur->rgt)
		362	;
2496	jermar	363
2416	mencl	364	if (cur != node->lft) {
		365	/*
2496	jermar	366	* The rightmost node of the deleted node's left subtree
		367	* was found. Replace the deleted node with this node.
		368	* Cutting off of the found node has two cases that
		369	* depend on its left son.
2416	mencl	370	*/
		371	if (cur->lft) {
		372	/*
2496	jermar	373	* The found node has a left son.
2416	mencl	374	*/
		375	gpa = cur->lft;
		376	gpa->par = cur->par;
2496	jermar	377	dir = LEFT;
2416	mencl	378	gpa->balance = cur->balance;
		379	} else {
2496	jermar	380	dir = RIGHT;
2416	mencl	381	gpa = cur->par;
		382	}
		383	cur->par->rgt = cur->lft;
		384	cur->lft = node->lft;
		385	cur->lft->par = cur;
		386	} else {
		387	/*
2496	jermar	388	* The left son of the node hasn't got a right son. The
		389	* left son will take the deleted node's place.
2416	mencl	390	*/
2496	jermar	391	dir = LEFT;
2416	mencl	392	gpa = cur;
		393	}
2496	jermar	394	if (node->rgt)
		395	node->rgt->par = cur;
2416	mencl	396	cur->rgt = node->rgt;
		397	cur->balance = node->balance;
		398	cur->par = node->par;
		399	}
		400
		401	/*
2496	jermar	402	* Repair the parent node's pointer which pointed previously to the
		403	* deleted node.
2416	mencl	404	*/
		405	if (node->par == NULL) {
		406	t->root = cur;
		407	} else {
		408	if (node->par->lft == node) {
		409	node->par->lft = cur;
		410	} else {
		411	node->par->rgt = cur;
		412	}
		413	}
		414
		415	/*
2496	jermar	416	* Repair cycle which repairs balances of nodes on the way from from the
		417	* cut-off node up to the root.
2416	mencl	418	*/
2496	jermar	419	for (;;) {
		420	if (dir == LEFT) {
2416	mencl	421	/*
2496	jermar	422	* Deletion was made in the left subtree.
2416	mencl	423	*/
		424	gpa->balance++;
2496	jermar	425	if (gpa->balance == 1) {
2416	mencl	426	/*
2496	jermar	427	* Stop balancing, the tree is balanced.
2416	mencl	428	*/
		429	break;
2496	jermar	430	} else if (gpa->balance == 2) {
2416	mencl	431	/*
2496	jermar	432	* Bad balance, heights of left and right
		433	* subtrees differ more than by one.
2416	mencl	434	*/
		435	par = gpa->rgt;
		436
		437	if (par->balance == -1) {
		438	/*
		439	* RL rotation.
		440	*/
		441
		442	cur = par->lft;
		443	par->lft = cur->rgt;
		444	cur->rgt = par;
		445	gpa->rgt = cur->lft;
		446	cur->lft = gpa;
		447
		448	/*
2496	jermar	449	* Repair balances and paternity of
		450	* children, depending on the balance
		451	* factor of the grand child (cur).
2416	mencl	452	*/
2496	jermar	453	if (cur->balance == 1) {
2416	mencl	454	par->balance = 0;
		455	gpa->balance = -1;
2496	jermar	456	if (gpa->rgt)
		457	gpa->rgt->par = gpa;
2416	mencl	458	par->lft->par = par;
		459	} else if (cur->balance == 0) {
		460	par->balance = gpa->balance = 0;
2496	jermar	461	if (gpa->rgt)
		462	gpa->rgt->par = gpa;
		463	if (par->lft)
		464	par->lft->par = par;
2416	mencl	465	} else {
2496	jermar	466	par->balance = 1;
2416	mencl	467	gpa->balance = 0;
2496	jermar	468	if (par->lft)
		469	par->lft->par = par;
2416	mencl	470	gpa->rgt->par = gpa;
		471	}
		472	cur->balance = 0;
		473
		474	/*
		475	* Repair paternity.
		476	*/
		477	cur->par = gpa->par;
		478	gpa->par = cur;
		479	par->par = cur;
		480
		481	/*
2496	jermar	482	* Repair the pointer which pointed to
		483	* the balanced node. If it was root
		484	* then the balancing is finished.
		485	* Otherwise continue with the next
		486	* iteration (parent node).
2416	mencl	487	*/
		488	if (cur->par == NULL) {
		489	t->root = cur;
		490	break;
2496	jermar	491	} else {
2416	mencl	492	if (cur->par->lft == gpa) {
		493	cur->par->lft = cur;
2496	jermar	494	dir = LEFT;
2416	mencl	495	} else {
		496	cur->par->rgt = cur;
2496	jermar	497	dir = RIGHT;
2416	mencl	498	}
2496	jermar	499	}
2416	mencl	500	gpa = cur->par;
		501	} else {
		502	/*
		503	* RR rotation.
		504	*/
		505
		506	gpa->rgt = par->lft;
2496	jermar	507	if (par->lft)
		508	par->lft->par = gpa;
2416	mencl	509	par->lft = gpa;
		510
		511	/*
		512	* Repair paternity.
		513	*/
		514	par->par = gpa->par;
		515	gpa->par = par;
		516
		517	if (par->balance == 0) {
		518	/*
2496	jermar	519	* The right child of the
		520	* balanced node is balanced,
		521	* after RR rotation is done,
		522	* the whole tree will be
		523	* balanced.
2416	mencl	524	*/
		525	par->balance = -1;
2496	jermar	526	gpa->balance = 1;
2416	mencl	527
		528	/*
2496	jermar	529	* Repair the pointer which
		530	* pointed to the balanced node
		531	* and finish balancing.
2416	mencl	532	*/
		533	if (par->par == NULL) {
		534	t->root = par;
2496	jermar	535	} else {
		536	if (par->par->lft ==
		537	gpa) {
		538	par->par->lft =
		539	par;
2416	mencl	540	} else {
2496	jermar	541	par->par->rgt =
		542	par;
2416	mencl	543	}
2496	jermar	544	}
2416	mencl	545	break;
		546	} else {
		547	par->balance = gpa->balance = 0;
		548	/*
2496	jermar	549	* Repair the pointer which
		550	* pointed to the balanced node.
		551	* If it was root then balancing
		552	* is finished. Otherwise
		553	* continue with the next
		554	* iteration (parent node).
2416	mencl	555	*/
		556	if (par->par == NULL) {
		557	t->root = par;
		558	break;
2496	jermar	559	} else {
		560	if (par->par->lft ==
		561	gpa) {
		562	par->par->lft =
		563	par;
		564	dir = LEFT;
2416	mencl	565	} else {
2496	jermar	566	par->par->rgt =
		567	par;
		568	dir = RIGHT;
2416	mencl	569	}
		570	}
		571	}
		572	gpa = par->par;
		573	}
		574	} else {
		575	/*
2496	jermar	576	* Repair the pointer which pointed to the
		577	* balanced node. If it was root then balancing
		578	* is finished else continue with the next
		579	* iteration (parent node).
2416	mencl	580	*/
2496	jermar	581	if (!gpa->par)
		582	break;
2416	mencl	583
		584	if (gpa->par->lft == gpa) {
2496	jermar	585	dir = LEFT;
2416	mencl	586	} else {
2496	jermar	587	dir = RIGHT;
2416	mencl	588	}
		589	gpa = gpa->par;
		590	}
		591	} else {
		592	/*
2496	jermar	593	* Deletion was made in the right subtree.
2416	mencl	594	*/
		595	gpa->balance--;
		596	if (gpa->balance == -1) {
		597	/*
2496	jermar	598	* Stop balancing, the tree is balanced.
2416	mencl	599	*/
		600	break;
		601	} else if (gpa->balance == -2) {
		602	/*
2496	jermar	603	* Bad balance, heights of left and right
		604	* subtrees differ more than by one.
2416	mencl	605	*/
		606	par = gpa->lft;
		607
2496	jermar	608	if (par->balance == 1) {
2416	mencl	609	/*
		610	* LR rotation.
		611	*/
		612
		613	cur = par->rgt;
		614	par->rgt = cur->lft;
		615	cur->lft = par;
		616	gpa->lft = cur->rgt;
		617	cur->rgt = gpa;
		618
		619	/*
2496	jermar	620	* Repair balances and paternity of
		621	* children, depending on the balance
		622	* factor of the grand child (cur).
2416	mencl	623	*/
		624	if (cur->balance == -1) {
		625	par->balance = 0;
2496	jermar	626	gpa->balance = 1;
		627	if (gpa->lft)
		628	gpa->lft->par = gpa;
2416	mencl	629	par->rgt->par = par;
		630	} else if (cur->balance == 0) {
		631	par->balance = gpa->balance = 0;
2496	jermar	632	if (gpa->lft)
		633	gpa->lft->par = gpa;
		634	if (par->rgt)
		635	par->rgt->par = par;
2416	mencl	636	} else {
		637	par->balance = -1;
		638	gpa->balance = 0;
2496	jermar	639	if (par->rgt)
		640	par->rgt->par = par;
2416	mencl	641	gpa->lft->par = gpa;
		642	}
		643	cur->balance = 0;
		644
		645	/*
		646	* Repair paternity.
		647	*/
		648	cur->par = gpa->par;
		649	gpa->par = cur;
		650	par->par = cur;
		651
		652	/*
2496	jermar	653	* Repair the pointer which pointed to
		654	* the balanced node. If it was root
		655	* then balancing is finished. Otherwise
		656	* continue with the next iteration
		657	* (parent node).
2416	mencl	658	*/
		659	if (cur->par == NULL) {
		660	t->root = cur;
		661	break;
2496	jermar	662	} else {
2416	mencl	663	if (cur->par->lft == gpa) {
		664	cur->par->lft = cur;
2496	jermar	665	dir = LEFT;
2416	mencl	666	} else {
		667	cur->par->rgt = cur;
2496	jermar	668	dir = RIGHT;
2416	mencl	669	}
2496	jermar	670	}
2416	mencl	671	gpa = cur->par;
		672	} else {
		673	/*
		674	* LL rotation.
		675	*/
		676
		677	gpa->lft = par->rgt;
2496	jermar	678	if (par->rgt)
		679	par->rgt->par = gpa;
2416	mencl	680	par->rgt = gpa;
		681	/*
		682	* Repair paternity.
		683	*/
		684	par->par = gpa->par;
		685	gpa->par = par;
		686
		687	if (par->balance == 0) {
		688	/*
2496	jermar	689	* The left child of the
		690	* balanced node is balanced,
		691	* after LL rotation is done,
		692	* the whole tree will be
		693	* balanced.
2416	mencl	694	*/
2496	jermar	695	par->balance = 1;
2416	mencl	696	gpa->balance = -1;
		697
		698	/*
2496	jermar	699	* Repair the pointer which
		700	* pointed to the balanced node
		701	* and finish balancing.
2416	mencl	702	*/
		703	if (par->par == NULL) {
		704	t->root = par;
2496	jermar	705	} else {
		706	if (par->par->lft ==
		707	gpa) {
		708	par->par->lft =
		709	par;
2416	mencl	710	} else {
2496	jermar	711	par->par->rgt =
		712	par;
2416	mencl	713	}
2496	jermar	714	}
2416	mencl	715	break;
		716	} else {
		717	par->balance = gpa->balance = 0;
		718
		719	/*
2496	jermar	720	* Repair the pointer which
		721	* pointed to the balanced node.
		722	* If it was root then balancing
		723	* is finished. Otherwise
		724	* continue with the next
		725	* iteration (parent node).
2416	mencl	726	*/
		727	if (par->par == NULL) {
		728	t->root = par;
		729	break;
		730	} else {
2496	jermar	731	if (par->par->lft ==
		732	gpa) {
		733	par->par->lft =
		734	par;
		735	dir = LEFT;
2416	mencl	736	} else {
2496	jermar	737	par->par->rgt =
		738	par;
		739	dir = RIGHT;
2416	mencl	740	}
		741	}
		742	}
		743	gpa = par->par;
		744	}
		745	} else {
		746	/*
2496	jermar	747	* Repair the pointer which pointed to the
		748	* balanced node. If it was root then balancing
		749	* is finished. Otherwise continue with the next
		750	* iteration (parent node).
2416	mencl	751	*/
2496	jermar	752	if (!gpa->par)
		753	break;
2416	mencl	754
		755	if (gpa->par->lft == gpa) {
2496	jermar	756	dir = LEFT;
2416	mencl	757	} else {
2496	jermar	758	dir = RIGHT;
2416	mencl	759	}
		760	gpa = gpa->par;
		761	}
		762	}
		763	}
		764	}
		765
		766
2496	jermar	767	/** Delete a node with the smallest key from the AVL tree.
2416	mencl	768	*
		769	* @param t AVL tree structure.
		770	*/
2421	mencl	771	bool avltree_delete_min(avltree_t *t)
2416	mencl	772	{
		773	avltree_node_t *node;
		774
		775	/*
2496	jermar	776	* Start searching for the smallest key in the tree starting in the root
		777	* node and continue in cycle to the leftmost node in the tree (which
		778	* must have the smallest key).
2416	mencl	779	*/
2496	jermar	780
2416	mencl	781	node = t->root;
2496	jermar	782	if (!node)
		783	return false;
2416	mencl	784
		785	while (node->lft != NULL)
		786	node = node->lft;
		787
2496	jermar	788	avltree_delete(t, node);
2416	mencl	789
		790	return true;
		791	}
2496	jermar	792
		793	/** @}
		794	*/

Subversion Repositories HelenOS

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