Context Navigation

source: mainline/kernel/generic/src/adt/avl.c@ 18b6a88

Visit:

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

Last change on this file since 18b6a88 was 18b6a88, checked in by Jiri Svoboda <jiri@…>, 7 years ago
More ccheck fixes, sometimes with manual intervention.
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
	85	/** Find the node with the smallest key in an AVL tree.
	86	*
	87	* @param t AVL tree.
	88	*
	89	* @return Pointer to a node or NULL if there is no node in the tree.
	90	*/
	91	avltree_node_t avltree_find_min(avltree_t t)
	92	{
	93	avltree_node_t *p = t->root;
[a35b458]	94
[358ec13]	95	/*
	96	* Check whether the tree is empty.
	97	*/
	98	if (!p)
	99	return NULL;
[a35b458]	100
[358ec13]	101	/*
	102	* Iteratively descend to the leftmost leaf in the tree.
	103	*/
[1b20da0]	104	while (p->lft != NULL)
[358ec13]	105	p = p->lft;
[a35b458]	106
[358ec13]	107	return p;
	108	}
	109
[83a5cba]	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)
[a35b458]	153
[358ec13]	154	/** Insert new node into AVL tree.
	155	*
	156	* @param t AVL tree.
	157	* @param newnode New node to be inserted.
[1b20da0]	158	*/
[358ec13]	159	void avltree_insert(avltree_t t, avltree_node_t newnode)
[1b20da0]	160	{
	161	avltree_node_t *par;
[358ec13]	162	avltree_node_t *gpa;
	163	avltree_node_t *top;
	164	avltree_node_t **dpc;
[d1e9321]	165	avltree_key_t key;
[358ec13]	166
[63e27ef]	167	assert(t);
	168	assert(newnode);
[358ec13]	169
	170	/*
	171	* Creating absolute key.
[1b20da0]	172	*/
[358ec13]	173	key = newnode->key + t->base;
[a35b458]	174
[358ec13]	175	/*
	176	* Iteratively descend to the leaf that can contain the new node.
	177	* Last node with non-zero balance in the way to leaf is stored as top -
	178	* it is a place of possible inbalance.
	179	*/
	180	dpc = &t->root;
	181	gpa = NULL;
	182	top = t->root;
	183	while ((par = (*dpc)) != NULL) {
	184	if (par->balance != 0) {
	185	top = par;
	186	}
	187	gpa = par;
[3bacee1]	188	dpc = par->key > key ? &par->lft : &par->rgt;
[358ec13]	189	}
	190
	191	/*
[83a5cba]	192	* Initialize the new node.
[358ec13]	193	*/
	194	newnode->key = key;
	195	newnode->lft = NULL;
	196	newnode->rgt = NULL;
	197	newnode->par = gpa;
	198	newnode->balance = 0;
	199
	200	/*
	201	* Insert first node into the empty tree.
	202	*/
	203	if (t->root == NULL) {
	204	*dpc = newnode;
	205	return;
	206	}
	207
	208	/*
[83a5cba]	209	* Insert the new node into the previously found leaf position.
[358ec13]	210	*/
	211	*dpc = newnode;
	212
	213	/*
	214	* If the tree contains one node - end.
	215	*/
	216	if (top == NULL)
	217	return;
	218
	219	/*
	220	* Store pointer of top's father which points to the node with
	221	* potentially broken balance (top).
	222	*/
	223	if (top->par == NULL) {
	224	dpc = &t->root;
[1b20da0]	225	} else {
[358ec13]	226	if (top->par->lft == top)
	227	dpc = &top->par->lft;
	228	else
	229	dpc = &top->par->rgt;
	230	}
	231
	232	/*
	233	* Repair all balances on the way from top node to the newly inserted
	234	* node.
	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	}
[a35b458]	246
[358ec13]	247	/*
	248	* To balance the tree, we must check and balance top node.
	249	*/
	250	if (top->balance == -2) {
	251	par = top->lft;
	252	if (par->balance == -1) {
	253	/*
	254	* LL rotation.
	255	*/
[83a5cba]	256	REBALANCE_INSERT_LL();
[1b20da0]	257	} else {
[358ec13]	258	/*
	259	* LR rotation.
	260	*/
[63e27ef]	261	assert(par->balance == 1);
[a35b458]	262
[83a5cba]	263	REBALANCE_INSERT_LR();
[358ec13]	264	}
[1b20da0]	265	} else if (top->balance == 2) {
[358ec13]	266	par = top->rgt;
	267	if (par->balance == 1) {
	268	/*
	269	* RR rotation.
	270	*/
[83a5cba]	271	REBALANCE_INSERT_RR();
[358ec13]	272	} else {
	273	/*
	274	* RL rotation.
	275	*/
[63e27ef]	276	assert(par->balance == -1);
[a35b458]	277
[83a5cba]	278	REBALANCE_INSERT_RL();
[358ec13]	279	}
[1b20da0]	280	} else {
[358ec13]	281	/*
	282	* Balance is not broken, insertion is finised.
	283	*/
	284	return;
	285	}
	286
	287	}
	288
	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.
[1b20da0]	305	*
[358ec13]	306	* @return Zero if w became the new root of the tree, otherwise return
	307	* non-zero.
	308	*/
	309	static int
[18b6a88]	310	repair(avltree_t t, avltree_node_t u, avltree_node_t v, avltree_node_t w,
[358ec13]	311	int *dir, int ro)
	312	{
	313	if (u->par == NULL) {
	314	if (!ro)
[1b20da0]	315	t->root = w;
[358ec13]	316	return 0;
[1b20da0]	317	} else {
[358ec13]	318	if (u->par->lft == v) {
	319	if (!ro)
	320	u->par->lft = w;
	321	if (dir)
	322	*dir = LEFT;
	323	} else {
[63e27ef]	324	assert(u->par->rgt == v);
[358ec13]	325	if (!ro)
	326	u->par->rgt = w;
	327	if (dir)
	328	*dir = RIGHT;
	329	}
	330	}
	331	return 1;
	332	}
	333
[83a5cba]	334	#define REBALANCE_DELETE(DIR1, DIR2, SIGN) \
[358ec13]	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
[83a5cba]	357	#define REBALANCE_DELETE_LR() REBALANCE_DELETE(lft, rgt, 1)
	358	#define REBALANCE_DELETE_RL() REBALANCE_DELETE(rgt, lft, -1)
[358ec13]	359
	360	/** Delete a node from the AVL tree.
	361	*
	362	* Because multiple identical keys are allowed, the parent pointers are
	363	* essential during deletion.
[1b20da0]	364	*
[358ec13]	365	* @param t AVL tree structure.
	366	* @param node Address of the node which will be deleted.
	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;
	373	int dir;
	374
[63e27ef]	375	assert(t);
	376	assert(node);
[a35b458]	377
[358ec13]	378	if (node->lft == NULL) {
	379	if (node->rgt) {
	380	/*
[1b20da0]	381	* Replace the node with its only right son.
[358ec13]	382	*
	383	* Balance of the right son will be repaired in the
	384	* balancing cycle.
	385	*/
	386	cur = node->rgt;
	387	cur->par = node->par;
	388	gpa = cur;
	389	dir = RIGHT;
[1b20da0]	390	cur->balance = node->balance;
[358ec13]	391	} else {
	392	if (node->par == NULL) {
	393	/*
	394	* The tree has only one node - it will become
	395	* an empty tree and the balancing can end.
	396	*/
	397	t->root = NULL;
	398	return;
	399	}
	400	/*
	401	* The node has no child, it will be deleted with no
	402	* substitution.
	403	*/
	404	gpa = node->par;
	405	cur = NULL;
[3bacee1]	406	dir = (gpa->lft == node) ? LEFT : RIGHT;
[358ec13]	407	}
	408	} else {
	409	/*
	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.
	413	*/
[84239b1]	414	cur = node->lft;
	415	while (cur->rgt != NULL)
	416	cur = cur->rgt;
[358ec13]	417
	418	if (cur != node->lft) {
	419	/*
	420	* The rightmost node of the deleted node's left subtree
	421	* was found. Replace the deleted node with this node.
	422	* Cutting off of the found node has two cases that
	423	* depend on its left son.
[1b20da0]	424	*/
[358ec13]	425	if (cur->lft) {
	426	/*
	427	* The found node has a left son.
	428	*/
	429	gpa = cur->lft;
	430	gpa->par = cur->par;
	431	dir = LEFT;
[1b20da0]	432	gpa->balance = cur->balance;
[358ec13]	433	} else {
	434	dir = RIGHT;
	435	gpa = cur->par;
	436	}
	437	cur->par->rgt = cur->lft;
	438	cur->lft = node->lft;
[1b20da0]	439	cur->lft->par = cur;
	440	} else {
[358ec13]	441	/*
	442	* The left son of the node hasn't got a right son. The
	443	* left son will take the deleted node's place.
	444	*/
	445	dir = LEFT;
[1b20da0]	446	gpa = cur;
[358ec13]	447	}
	448	if (node->rgt)
[1b20da0]	449	node->rgt->par = cur;
[358ec13]	450	cur->rgt = node->rgt;
	451	cur->balance = node->balance;
	452	cur->par = node->par;
	453	}
[a35b458]	454
[358ec13]	455	/*
	456	* Repair the parent node's pointer which pointed previously to the
	457	* deleted node.
	458	*/
	459	(void) repair(t, node, node, cur, NULL, false);
[a35b458]	460
[358ec13]	461	/*
	462	* Repair cycle which repairs balances of nodes on the way from from the
	463	* cut-off node up to the root.
	464	*/
[84239b1]	465	while (true) {
[358ec13]	466	if (dir == LEFT) {
	467	/*
	468	* Deletion was made in the left subtree.
	469	*/
	470	gpa->balance++;
	471	if (gpa->balance == 1) {
	472	/*
	473	* Stop balancing, the tree is balanced.
	474	*/
	475	break;
[1b20da0]	476	} else if (gpa->balance == 2) {
[358ec13]	477	/*
	478	* Bad balance, heights of left and right
	479	* subtrees differ more than by one.
	480	*/
	481	par = gpa->rgt;
	482
	483	if (par->balance == -1) {
	484	/*
	485	* RL rotation.
	486	*/
[a35b458]	487
[358ec13]	488	cur = par->lft;
	489	par->lft = cur->rgt;
	490	cur->rgt = par;
	491	gpa->rgt = cur->lft;
	492	cur->lft = gpa;
[a35b458]	493
[358ec13]	494	/*
	495	* Repair balances and paternity of
	496	* children, depending on the balance
	497	* factor of the grand child (cur).
	498	*/
[83a5cba]	499	REBALANCE_DELETE_RL();
[a35b458]	500
[358ec13]	501	/*
	502	* Repair paternity.
	503	*/
	504	cur->par = gpa->par;
	505	gpa->par = cur;
	506	par->par = cur;
	507
	508	if (!repair(t, cur, gpa, cur, &dir,
	509	false))
	510	break;
	511	gpa = cur->par;
	512	} else {
	513	/*
	514	* RR rotation.
	515	*/
[a35b458]	516
[358ec13]	517	gpa->rgt = par->lft;
	518	if (par->lft)
	519	par->lft->par = gpa;
	520	par->lft = gpa;
[a35b458]	521
[358ec13]	522	/*
	523	* Repair paternity.
	524	*/
	525	par->par = gpa->par;
	526	gpa->par = par;
[a35b458]	527
[358ec13]	528	if (par->balance == 0) {
	529	/*
	530	* The right child of the
	531	* balanced node is balanced,
	532	* after RR rotation is done,
	533	* the whole tree will be
	534	* balanced.
	535	*/
	536	par->balance = -1;
	537	gpa->balance = 1;
	538
	539	(void) repair(t, par, gpa, par,
	540	NULL, false);
[1b20da0]	541	break;
[358ec13]	542	} else {
	543	par->balance = 0;
	544	gpa->balance = 0;
	545	if (!repair(t, par, gpa, par,
	546	&dir, false))
	547	break;
	548	}
	549	gpa = par->par;
	550	}
	551	} else {
	552	/*
	553	* Repair the pointer which pointed to the
	554	* balanced node. If it was root then balancing
	555	* is finished else continue with the next
	556	* iteration (parent node).
	557	*/
	558	if (!repair(t, gpa, gpa, NULL, &dir, true))
	559	break;
	560	gpa = gpa->par;
	561	}
[1b20da0]	562	} else {
[358ec13]	563	/*
	564	* Deletion was made in the right subtree.
	565	*/
	566	gpa->balance--;
	567	if (gpa->balance == -1) {
	568	/*
	569	* Stop balancing, the tree is balanced.
	570	*/
	571	break;
	572	} else if (gpa->balance == -2) {
	573	/*
	574	* Bad balance, heights of left and right
	575	* subtrees differ more than by one.
	576	*/
	577	par = gpa->lft;
[a35b458]	578
[358ec13]	579	if (par->balance == 1) {
	580	/*
	581	* LR rotation.
	582	*/
[a35b458]	583
[358ec13]	584	cur = par->rgt;
	585	par->rgt = cur->lft;
	586	cur->lft = par;
	587	gpa->lft = cur->rgt;
	588	cur->rgt = gpa;
[a35b458]	589
[358ec13]	590	/*
	591	* Repair balances and paternity of
	592	* children, depending on the balance
	593	* factor of the grand child (cur).
	594	*/
[83a5cba]	595	REBALANCE_DELETE_LR();
[358ec13]	596
	597	/*
	598	* Repair paternity.
	599	*/
	600	cur->par = gpa->par;
	601	gpa->par = cur;
	602	par->par = cur;
	603
	604	if (!repair(t, cur, gpa, cur, &dir,
	605	false))
	606	break;
	607	gpa = cur->par;
[1b20da0]	608	} else {
[358ec13]	609	/*
	610	* LL rotation.
	611	*/
	612
	613	gpa->lft = par->rgt;
	614	if (par->rgt)
	615	par->rgt->par = gpa;
	616	par->rgt = gpa;
	617	/*
	618	* Repair paternity.
	619	*/
	620	par->par = gpa->par;
	621	gpa->par = par;
[a35b458]	622
[358ec13]	623	if (par->balance == 0) {
	624	/*
	625	* The left child of the
	626	* balanced node is balanced,
	627	* after LL rotation is done,
	628	* the whole tree will be
	629	* balanced.
	630	*/
	631	par->balance = 1;
	632	gpa->balance = -1;
[a35b458]	633
[358ec13]	634	(void) repair(t, par, gpa, par,
	635	NULL, false);
	636	break;
	637	} else {
	638	par->balance = 0;
	639	gpa->balance = 0;
[a35b458]	640
[358ec13]	641	if (!repair(t, par, gpa, par,
	642	&dir, false))
	643	break;
	644	}
	645	gpa = par->par;
	646	}
	647	} else {
	648	/*
	649	* Repair the pointer which pointed to the
	650	* balanced node. If it was root then balancing
	651	* is finished. Otherwise continue with the next
	652	* iteration (parent node).
	653	*/
	654	if (!repair(t, gpa, gpa, NULL, &dir, true))
	655	break;
	656	gpa = gpa->par;
	657	}
	658	}
	659	}
	660	}
	661
	662
	663	/** Delete a node with the smallest key from the AVL tree.
	664	*
	665	* @param t AVL tree structure.
	666	*/
	667	bool avltree_delete_min(avltree_t *t)
	668	{
	669	avltree_node_t *node;
[a35b458]	670
[358ec13]	671	/*
	672	* Start searching for the smallest key in the tree starting in the root
	673	* node and continue in cycle to the leftmost node in the tree (which
	674	* must have the smallest key).
	675	*/
[a35b458]	676
[358ec13]	677	node = t->root;
	678	if (!node)
	679	return false;
[a35b458]	680
[358ec13]	681	while (node->lft != NULL)
	682	node = node->lft;
[a35b458]	683
[1b20da0]	684	avltree_delete(t, node);
[358ec13]	685
	686	return true;
	687	}
	688
[b76a2217]	689	/** Walk a subtree of an AVL tree in-order and apply a supplied walker on each
	690	* visited node.
	691	*
	692	* @param node Node representing the root of an AVL subtree to be
	693	* walked.
	694	* @param walker Walker function that will be appliad on each visited
	695	* node.
	696	* @param arg Argument for the walker.
	697	*
	698	* @return Zero if the walk should stop or non-zero otherwise.
	699	*/
	700	static bool _avltree_walk(avltree_node_t *node, avltree_walker_t walker,
	701	void *arg)
[d1e9321]	702	{
[b76a2217]	703	if (node->lft) {
	704	if (!_avltree_walk(node->lft, walker, arg))
	705	return false;
	706	}
	707	if (!walker(node, arg))
	708	return false;
	709	if (node->rgt) {
	710	if (!_avltree_walk(node->rgt, walker, arg))
	711	return false;
	712	}
	713	return true;
[d1e9321]	714	}
	715
[b76a2217]	716	/** Walk the AVL tree in-order and apply the walker function on each visited
	717	* node.
[d1e9321]	718	*
	719	* @param t AVL tree to be walked.
	720	* @param walker Walker function that will be called on each visited
	721	* node.
[b76a2217]	722	* @param arg Argument for the walker.
[d1e9321]	723	*/
[b76a2217]	724	void avltree_walk(avltree_t t, avltree_walker_t walker, void arg)
[d1e9321]	725	{
[7e36c8d]	726	if (t->root)
	727	_avltree_walk(t->root, walker, arg);
[d1e9321]	728	}
	729
[358ec13]	730	/** @}
	731	*/
	732

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

Download in other formats: