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

Subversion Repositories HelenOS

(root)/trunk/kernel/generic/src/adt/avl.c – Rev 3924