WebSVN – HelenOS – Blame – /branches/rcu/kernel/generic/src/adt/extavl.c

Rev	Author	Line No.	Line
2416	mencl	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 Extended AVL tree implementation.
		36	*
		37	* This file implements Extended AVL tree type and operations.
		38	*
		39	* Extended AVL tree (ExtAvl tree) has the following properties:
		40	* @li it is binary search tree with unique keys
		41	* @li right subtree of every node is Avl tree
		42	* @li height of left subtree of every node is not greater then height of right subtree + 1
		43	* @li nodes with the same keys are linked to the tree nodes of the same key, they are not tree nodes
		44	* @li every node is part of doubly linked list with head
		45	* @li nodes are connected in the list ascendentaly according to their keys
		46	*
		47	* Be careful of using this tree because of base atribute, which is added to every inserted
		48	* node key.
		49	*/
		50
		51	#include <adt/extavl.h>
		52	#include <debug.h>
		53	#include <panic.h>
		54
		55	#define AVLTREE_LEFT 0
		56	#define AVLTREE_RIGHT 1
		57
		58	/* Returns height of tree -1 */
		59	#define extavltree_tree_height(node) (((node) == NULL) ? (-1) : (((node)->lft_height>(node)->rgt_height)?(node)->lft_height:(node)->rgt_height))
		60
		61	/** Search first occurence (oldest node with this key) of given key in Extended AVL tree.
		62	*
		63	* @param t Extended AVL tree.
		64	* @param key Key to be searched.
		65	*
2421	mencl	66	* @return Pointer to node or NULL if there is no such key.
2416	mencl	67	*/
		68	extavltree_node_t extavltree_search(extavltree_t t, uint64_t key)
		69	{
		70	extavltree_node_t *cur;
		71
		72	cur = t->root;
		73	while (cur != NULL) {
		74	if (cur->key < key) {
		75	cur = cur->rgt;
		76	} else if (cur->key > key) {
		77	cur = cur->lft;
		78	} else {
		79	return cur;
		80	}
		81	}
		82	return NULL;
		83	}
		84
		85	/** Insert new node into ExtAVL tree.
		86	*
		87	* New node's key must be set.
		88	*
		89	* @param t ExtAVL tree structure.
		90	* @param newnode New node to be inserted.
		91	*/
		92	void extavltree_insert(extavltree_t t, extavltree_node_t newnode)
		93	{
		94	extavltree_node_t *cur;
		95	extavltree_node_t *son;
		96	extavltree_node_t *gpa;
		97	extavltree_node_t *par;
		98	uint64_t key;
		99
		100	ASSERT(t);
		101	ASSERT(newnode);
		102
		103	/*
		104	* Creating absolute key.
		105	*/
		106	newnode->key = key = newnode->key + t->base;
		107
		108
		109	/*
		110	* Insert first node into empty tree.
		111	*/
		112	if (t->root == NULL) {
		113	newnode->lft = NULL;
		114	newnode->rgt = NULL;
		115	newnode->lft_height = 0;
		116	newnode->rgt_height = 0;
		117	newnode->par = NULL;
		118	newnode->next = &t->head;
		119	newnode->prev = &t->head;
		120
		121	t->head.prev = newnode;
		122	t->head.next = newnode;
		123	t->root = newnode;
		124	return;
		125	}
		126
		127	/*
		128	* Tree is not empty - search for the right place for new node.
		129	*/
		130	cur = t->root;
		131	while(true) {
		132	if (cur->key < key) {
		133	if (!cur->rgt) {
		134	/*
		135	* We have reach leaf. New node will be right son.
		136	*/
		137	cur->rgt = newnode;
		138
		139	newnode->lft = NULL;
		140	newnode->rgt = NULL;
		141	newnode->lft_height = 0;
		142	newnode->rgt_height = 0;
		143	newnode->par = cur;
		144
		145	newnode->prev = cur;
		146	newnode->next = cur->next;
		147	cur->next->prev = newnode;
		148	cur->next = newnode;
		149	break;
		150	}
		151	cur = cur->rgt;
		152	} else if (cur->key > key) {
		153	if (!cur->lft) {
		154	/*
		155	* We have reach leaf. New node will be left son.
		156	*/
		157	cur->lft = newnode;
		158
		159	newnode->lft = NULL;
		160	newnode->rgt = NULL;
		161	newnode->lft_height = 0;
		162	newnode->rgt_height = 0;
		163	newnode->par = cur;
		164
		165	gpa = cur;
		166	while (gpa != &t->head && gpa->key == cur->key)
		167	gpa = gpa->prev;
		168	newnode->next = gpa->next;
		169	newnode->prev = gpa;
		170	gpa->next->prev = newnode;
		171	gpa->next = newnode;
		172	break;
		173	}
		174	cur = cur->lft;
		175	} else {
		176	/*
		177	* Key has been previously inserted into tree. Make new node as a tree node
		178	* and old tree node move to the prev. Old tree node will be list node.
		179	*/
		180
		181	newnode->prev = cur;
		182	newnode->next = cur->next;
		183	cur->next->prev = newnode;
		184	cur->next = newnode;
		185
		186	newnode->par = cur->par;
		187	cur->par = NULL;
		188	newnode->lft = cur->lft;
		189	cur->lft = NULL;
		190	newnode->rgt = cur->rgt;
		191	cur->rgt = NULL;
		192	newnode->lft_height = cur->lft_height;
		193	cur->lft_height = 0;
		194	newnode->rgt_height = cur->rgt_height;
		195	cur->rgt_height = 0;
		196
		197	if (newnode->lft) newnode->lft->par = newnode;
		198	if (newnode->rgt) newnode->rgt->par = newnode;
		199	if (newnode->par) {
		200	if (newnode->par->lft == cur)
		201	newnode->par->lft = newnode;
		202	else
		203	newnode->par->rgt = newnode;
		204	} else {
		205	t->root = newnode;
		206	}
		207	return;
		208	}
		209	}
		210
		211	/*
		212	* Balancing all nodes from newnode's parent down to root. All nodes must be checked
		213	* because delete min operation can corrupt heights and only insert operation can
		214	* repair it.
		215	*/
		216	cur = newnode->par;
		217	while (cur) {
		218	if (cur->key > key) {
		219	/*
		220	* Insertion was made in the left subtree - repair left height
		221	* and check balance of current node.
		222	*/
		223	cur->lft_height = extavltree_tree_height(cur->lft) + 1;
		224
		225	if ((cur->rgt_height - cur->lft_height) <= -2) {
		226	/*
		227	* Balance was corrupted, must be repaired through LL or LR rotation.
		228	*/
		229	par = cur->par;
		230	son = cur->lft;
		231	if ((son->rgt_height - son->lft_height) != 1) {
		232	/*
		233	* LL rotation
		234	*/
		235
		236	gpa = son;
		237	cur->lft = son->rgt;
		238	if (cur->lft != NULL) cur->lft->par = cur;
		239	cur->par = son;
		240	son->rgt = cur;
		241	/*
		242	* Repair heights.
		243	*/
		244	cur->lft_height = son->rgt_height;
		245	son->rgt_height = extavltree_tree_height(cur) + 1;
		246	} else {
		247	/*
		248	* LR rotation
		249	*/
		250
		251	gpa = son->rgt;
		252	son->rgt = gpa->lft;
		253	if (gpa->lft != NULL) gpa->lft->par = son;
		254	gpa->lft = son;
		255	son->par = gpa;
		256	cur->lft = gpa->rgt;
		257	if (gpa->rgt != NULL) gpa->rgt->par = cur;
		258	gpa->rgt = cur;
		259	cur->par = gpa;
		260	/*
		261	* Repair heights.
		262	*/
		263	cur->lft_height = gpa->rgt_height;
		264	son->rgt_height = gpa->lft_height;
		265	gpa->rgt_height = extavltree_tree_height(cur) + 1;
		266	gpa->lft_height = extavltree_tree_height(son) + 1;
		267	}
		268
		269	/*
		270	* Change parent pointers or if current node is root then
		271	* change root atribute pointer.
		272	*/
		273	gpa->par = par;
		274	if (par) {
		275	if (par->lft == cur)
		276	par->lft = gpa;
		277	else
		278	par->rgt = gpa;
		279	} else {
		280	t->root = gpa;
		281	}
		282	cur = par;
		283	} else {
		284	/*
		285	* Current node is balanced, continue balancing of its parent.
		286	*/
		287	cur = cur->par;
		288	}
		289	} else {
		290	/*
		291	* Insertion was made in the right subtree - repair right height
		292	* and check balance of current node.
		293	*/
		294	cur->rgt_height = extavltree_tree_height(cur->rgt) + 1;
		295
		296	if ((cur->rgt_height - cur->lft_height) >= 2) {
		297	/*
		298	* Balance was corrupted, must be repaired through LL or LR rotation.
		299	*/
		300	par = cur->par;
		301	son = cur->rgt;
		302	if ((son->rgt_height - son->lft_height) != -1) {
		303	/*
		304	* RR rotation
		305	*/
		306	gpa = son;
		307	cur->rgt = son->lft;
		308	if (cur->rgt != NULL) cur->rgt->par = cur;
		309	cur->par = son;
		310	son->lft = cur;
		311	/*
		312	* Repair heights.
		313	*/
		314	cur->rgt_height = son->lft_height;
		315	son->lft_height = extavltree_tree_height(cur) + 1;
		316	} else {
		317	/*
		318	* RL rotation
		319	*/
		320	gpa = son->lft;
		321	son->lft = gpa->rgt;
		322	if (gpa->rgt != NULL) gpa->rgt->par = son;
		323	gpa->rgt = son;
		324	son->par = gpa;
		325	cur->rgt = gpa->lft;
		326	if (gpa->lft != NULL) gpa->lft->par = cur;
		327	gpa->lft = cur;
		328	cur->par = gpa;
		329	/*
		330	* Repair heights.
		331	*/
		332	cur->rgt_height = gpa->lft_height;
		333	son->lft_height = gpa->rgt_height;
		334	gpa->lft_height = extavltree_tree_height(cur) + 1;
		335	gpa->rgt_height = extavltree_tree_height(son) + 1;
		336	}
		337
		338	/*
		339	* Change parent pointers or if current node is root then
		340	* change root atribute pointer.
		341	*/
		342	gpa->par = par;
		343	if (par) {
		344	if (par->lft == cur)
		345	par->lft = gpa;
		346	else
		347	par->rgt = gpa;
		348	} else {
		349	t->root = gpa;
		350	}
		351	cur = par;
		352	} else {
		353	/*
		354	* Current node is balanced, continue balancing of its parent.
		355	*/
		356	cur = cur->par;
		357	}
		358	}
		359	}
		360	}
		361
		362	/** Delete node from ExtAVL tree.
		363	*
		364	* @param t ExtAVL tree structure.
		365	* @param node Address of node which will be deleted.
		366	*/
		367	void extavltree_delete(extavltree_t t, extavltree_node_t node)
		368	{
		369	extavltree_node_t **gpapar;
		370	extavltree_node_t *cur;
		371	extavltree_node_t *par;
		372	extavltree_node_t *gpa;
		373	int8_t dir;
		374	int8_t dir2=0;
		375	int16_t balance;
		376
		377	ASSERT(t);
		378	ASSERT(node);
		379
		380	/*
		381	* Delete node from list.
		382	*/
		383	node->next->prev = node->prev;
		384	node->prev->next = node->next;
		385
		386	if (!node->par) {
		387	if (t->root != node) {
		388	/*
		389	* It is list node (not a tree node). Needn't repair tree or anything else.
		390	*/
		391	return;
		392	}
		393	gpapar = &(t->root);
		394	} else {
		395	/*
		396	* Find tree pointer which points to node.
		397	*/
		398	if (node->par->lft == node) {
		399	gpapar = &(node->par->lft);
		400	} else {
		401	gpapar = &(node->par->rgt);
		402	}
		403	}
		404
		405
		406	if (&t->head != node->prev && node->prev->key == node->key) {
		407	/*
		408	* Deleted node has at least one node node with the same key which is closest previous
		409	* neighbor in the list, copy node atributes into previous node and end.
		410	*/
		411	cur = node->prev;
		412	cur->lft = node->lft;
		413	cur->rgt = node->rgt;
		414	cur->par = node->par;
		415	cur->lft_height = node->lft_height;
		416	cur->rgt_height = node->rgt_height;
		417	*gpapar = cur;
		418
		419	if (node->lft) node->lft->par = cur;
		420	if (node->rgt) node->rgt->par = cur;
		421	return;
		422	}
		423
		424	/*
		425	* Check situation in the tree around deleted node.
		426	*/
		427	if (!node->lft) {
		428	/*
		429	* Deleted node has not left son. Right son will take deleted node's place.
		430	*/
		431	gpa = node->par;
		432	if (node->rgt) node->rgt->par = gpa;
		433	if (!gpa) {
		434	/*
		435	* Deleted node is root node. Balancing is finished, change only
		436	* root pointer in extavltree structure.
		437	*/
		438	*gpapar = node->rgt;
		439	return;
		440	}
		441	dir = (gpa->lft == node)? AVLTREE_LEFT: AVLTREE_RIGHT;
		442	*gpapar = node->rgt;
		443	} else {
		444	/*
		445	* Node has left son.
		446	*/
		447	cur = node->lft;
		448	if (!cur->rgt) {
		449	/*
		450	* Left son of node hasn't got right son. Left son will take deleted node's place.
		451	*/
		452	*gpapar = cur;
		453	cur->par = node->par;
		454	dir = AVLTREE_LEFT;
		455	cur->rgt = node->rgt;
		456	if (node->rgt) node->rgt->par = cur;
		457	gpa = cur;
		458	cur->rgt_height = node->rgt_height;
		459	cur->lft_height = node->lft_height;
		460	/*
		461	* cur->lft_height will be decreased in repair cycle.
		462	*/
		463	} else {
		464	/*
		465	* Node has left and right son. Find a node with smallest key in left subtree
		466	* and change that node with deleted node.
		467	*/
		468	while (cur->rgt != NULL)
		469	cur = cur->rgt;
		470
		471	*gpapar = cur;
		472	cur->rgt = node->rgt;
		473	if (node->rgt) node->rgt->par = cur;
		474	gpa = cur->par;
		475	gpa->rgt = cur->lft;
		476	if (cur->lft) cur->lft->par = gpa;
		477	cur->lft = node->lft;
		478	cur->lft->par = cur;
		479	cur->par = node->par;
		480	dir = AVLTREE_RIGHT;
		481	cur->lft_height = node->lft_height;
		482	cur->rgt_height = node->rgt_height;
		483	/*
		484	* gpa->rgt_height and cur->lft_height will be repaired in repair cycle.
		485	*/
		486	}
		487	/*
		488	* Deleted node is root node. Balancing is finished.
		489	*/
		490	if (!gpa) return;
		491	}
		492
		493	/*
		494	* Repair cycle which goes from gpa node down to root.
		495	*/
		496	for(;;) {
		497	/*
		498	* Find tree pointer which points to the currently balanced node. When balanced
		499	* node is root, root pointer from extavltree structure is taken.
		500	*/
		501	if (!gpa->par)
		502	gpapar = &(t->root);
		503	else {
		504	if (gpa->par->lft == gpa) {
		505	gpapar = &(gpa->par->lft);
		506	dir2 = AVLTREE_LEFT;
		507	} else {
		508	gpapar = &(gpa->par->rgt);
		509	dir2 = AVLTREE_RIGHT;
		510	}
		511	}
		512
		513	if (dir == AVLTREE_LEFT) {
		514	/*
		515	* Deletition was made in left subtree.
		516	*/
		517	gpa->lft_height--;
		518	balance = gpa->rgt_height - gpa->lft_height;
		519	if (balance == 1) {
		520	/*
		521	* Stop balancing, tree is balanced.
		522	*/
		523	break;
		524	} else if (balance == 2) {
		525	/*
		526	* Bad balance, heights of left and right subtrees differs more then is allowed.
		527	*/
		528	par = gpa->rgt;
		529
		530	if ((par->rgt_height - par->lft_height) == -1) {
		531	/*
		532	* RL rotation
		533	*/
		534
		535	cur = par->lft;
		536	par->lft = cur->rgt;
		537	cur->rgt = par;
		538	gpa->rgt = cur->lft;
		539	cur->lft = gpa;
		540
		541	/*
		542	* Repair balances.
		543	*/
		544	par->lft_height = cur->rgt_height;
		545	gpa->rgt_height = cur->lft_height;
		546	cur->lft_height = extavltree_tree_height(gpa) + 1; //POZOR nelze: cur->lft_height = gpa->lft_height + 1; - vyska cur je diky timeoutu nesttabilni
		547	cur->rgt_height = par->rgt_height + 1; //POZOR zmena: cur->rgt_height = extavltree_tree_height(par) + 1;
		548
		549	/*
		550	* Repair paternity.
		551	*/
		552	if (gpa->rgt) gpa->rgt->par = gpa;
		553	if (par->lft) par->lft->par = par;
		554	cur->par = gpa->par;
		555	gpa->par = cur;
		556	par->par = cur;
		557
		558	/*
		559	* Repair tree pointer which points to the current node and do the next step.
		560	*/
		561	*gpapar = cur;
		562	gpa = cur->par;
		563	} else {
		564	/*
		565	* RR rotation
		566	*/
		567
		568	gpa->rgt = par->lft;
		569	gpa->rgt_height = par->lft_height;
		570	if (par->lft) par->lft->par = gpa;
		571	par->lft = gpa;
		572
		573	/*
		574	* Repair paternity.
		575	*/
		576	par->par = gpa->par;
		577	gpa->par = par;
		578
		579	/*
		580	* Repair balances.
		581	*/
		582	balance = par->rgt_height - par->lft_height;
		583	par->lft_height++;
		584
		585	/*
		586	* Repair tree pointer which points to the current node, ends when tree is balanced
		587	* or do the next step.
		588	*/
		589	*gpapar = par;
		590	if (balance == 0) break;
		591	gpa = par->par;
		592	}
		593	} else {
		594	/*
		595	* Current node is balanced - perform balance check of its parent.
		596	*/
		597	gpa = gpa->par;
		598	}
		599	} else {
		600	/*
		601	* Balance right son.
		602	*/
		603	gpa->rgt_height--;
		604	balance = gpa->rgt_height - gpa->lft_height;
		605	if (balance == -1) {
		606	/*
		607	* Stop balancing, tree might be balanced or not, whole tree is repaired only during insertion.
		608	*/
		609	break;
		610	} else if (balance == -2) {
		611	/*
		612	* Balance was corrupted - must be repaired.
		613	*/
		614	par = gpa->lft;
		615
		616	if ((par->rgt_height - par->lft_height) >= +1) {
		617	/*
		618	* If balance is -2 then par node always exists.
		619	*/
		620	if ((gpa->lft_height - (extavltree_tree_height(par))) == 1) {
		621	/*
		622	* LR rotation. Height of par subtree is not decreased due to timeout operation.
		623	*/
		624
		625	cur = par->rgt;
		626	par->rgt = cur->lft;
		627	cur->lft = par;
		628	gpa->lft = cur->rgt;
		629	cur->rgt = gpa;
		630
		631	/*
		632	* Repair balances.
		633	*/
		634	par->rgt_height = cur->lft_height;
		635	gpa->lft_height = cur->rgt_height;
		636	cur->rgt_height = gpa->rgt_height + 1;
		637	cur->lft_height = extavltree_tree_height(par) + 1;
		638
		639	/*
		640	* Repair paternity.
		641	*/
		642	if (gpa->lft) gpa->lft->par = gpa;
		643	if (par->rgt) par->rgt->par = par;
		644	cur->par = gpa->par;
		645	gpa->par = cur;
		646	par->par = cur;
		647
		648	/*
		649	* Repair tree pointer which points to the current node and do the next step.
		650	*/
		651	*gpapar = cur;
		652	gpa = cur->par;
		653	} else {
		654	/*
		655	* Left subtree of cur has been already decreased by timeout operation.
		656	*/
		657	gpa = gpa->par;
		658	}
		659	} else {
		660	/*
		661	* LL rotation.
		662	*/
		663
		664	int prevlftheight = gpa->lft_height;
		665	gpa->lft = par->rgt;
		666	gpa->lft_height = par->rgt_height;
		667	if (par->rgt) par->rgt->par = gpa;
		668	par->rgt = gpa;
		669
		670	/*
		671	* Repair paternity.
		672	*/
		673	par->par = gpa->par;
		674	gpa->par = par;
		675
		676	/*
		677	* Repair height.
		678	*/
		679	balance = par->rgt_height - par->lft_height;
		680	par->rgt_height = extavltree_tree_height(gpa) + 1;
		681
		682	/*
		683	* Repair tree pointer which points to the current node, ends when heights in par nodes are
		684	* balanced and height of par subtree wasn't decreased due to timeout operation orr do
		685	* the next step.
		686	*/
		687	*gpapar = par;
		688	if (balance == 0 && par->rgt_height == prevlftheight) return;
		689	gpa = par->par;
		690	}
		691	} else {
		692	/*
		693	* Current node is balanced - perform balance check of its parent.
		694	*/
		695	gpa = gpa->par;
		696	}
		697	}
		698	/*
		699	* When root is reached then end balancing.
		700	*/
		701	if (!gpa) return;
		702
		703	dir = dir2;
		704	}
		705	}
		706
		707
		708	/** Delete node from ExtAVL tree with the smallest key and set base of tree to that key.
		709	*
		710	* @param t ExtAVL tree structure.
		711	*/
		712	bool extavltree_delete_min(extavltree_t *t)
		713	{
		714	extavltree_node_t *expnode;
		715
		716	ASSERT(t);
		717
		718	expnode = t->head.next;
		719
		720	if (&t->head == expnode) return false;
		721
		722	if (expnode->key != expnode->next->key) {
		723	/*
		724	* Repair tree data structure.
		725	*/
		726	if (!expnode->par) {
		727	/*
		728	* Delete root node which musn't have left son.
		729	*/
		730
		731	ASSERT(!expnode->lft);
		732	t->root = expnode->rgt;
		733	if (expnode->rgt) expnode->rgt->par = NULL;
		734	} else if (expnode->rgt) {
		735	/*
		736	* Always delete parent of left son.
		737	*/
		738
		739	expnode->rgt->par = expnode->par;
		740	expnode->par->lft = expnode->rgt;
		741	expnode->par->lft_height = expnode->rgt_height;
		742	} else {
		743	/*
		744	* Deleted node doesn't have right son.
		745	*/
		746
		747	expnode->par->lft = NULL;
		748	expnode->par->lft_height = 0;
		749	}
		750	}
		751
		752	/*
		753	* Delete node from the list.
		754	*/
		755	t->head.next = expnode->next;
		756	expnode->next->prev = &t->head;
		757
		758	return true;
		759	}

Subversion Repositories HelenOS

(root)/branches/rcu/kernel/generic/src/adt/extavl.c – Rev 2421