Context Navigation

source: mainline/kernel/generic/src/adt/avl.c@ 09ab0a9a

Visit:

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export

Last change on this file since 09ab0a9a was 09ab0a9a, checked in by Jiri Svoboda <jiri@…>, 7 years ago
Fix vertical spacing with new Ccheck revision.
Property mode set to `100644`
File size: 16.0 KB

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

Note: See TracBrowser for help on using the repository browser.

Download in other formats: