WebSVN – HelenOS – Blame – /branches/rcu/kernel/generic/src/adt/extavlrel.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 with relative keys implementation.
		36	*
		37	* This file implements Extended AVL tree with relative keys type and operations.
		38	*
		39	* Extended AVL tree with relative keys (ExtAvlrel tree) has the following properties:
		40	* @li it is binary search tree with unique real 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 real 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 real keys, node key is
		46	* only difference between previous real node's key and its real node's key
		47	* @li real key is either equal node key if node is leftmost node in tree or sum of all
		48	* node keys with smaller real key
		49	*
		50	* Be careful of using this tree because node keys are not equal real keys (except leftmost node).
		51	*/
		52
		53	#include <adt/extavlrel.h>
		54	#include <debug.h>
		55	#include <panic.h>
		56
		57
		58	#define AVLTREE_LEFT 0
		59	#define AVLTREE_RIGHT 1
		60
		61
		62	/* Returns height of tree -1 */
2421	mencl	63	#define extavlreltree_tree_height(node) (((node) == NULL) ? (-1) : (((node)->lft_height>(node)->rgt_height)?(node)->lft_height:(node)->rgt_height))
2416	mencl	64
		65	/** Search first occurence (oldest node with this real key) of given key in ExtAVLrel tree.
		66	*
		67	* @param t ExtAVLrel tree.
		68	* @param key Key to be searched.
		69	*
2421	mencl	70	* @return Pointer to node or NULL if there is no such key.
2416	mencl	71	*/
2421	mencl	72	extavlreltree_node_t extavlreltree_search(extavlreltree_t t, uint64_t key)
2416	mencl	73	{
		74	extavlreltree_node_t *cur;
		75	uint64_t sum, s;
		76
		77	/*
		78	* Find right subtree in way up to the root where can be node with given key.
		79	* Root node is the last node in the way up, when we reach root, it means,
		80	* that searched node belongs to the right subtree of root.
		81	*/
		82	sum = 0;
		83	cur = t->head.next;
		84	while (1) {
		85	sum += cur->key + cur->rgt_sum;
		86	if ((key <= sum) \|\| (cur == t->root))
		87	break;
		88	else
		89	cur = cur->par;
		90	}
		91
		92	/*
		93	* Sorting for cycle.
		94	* Search for key in choosen subtree. Searching start at cur node which we have found
		95	* in previous step. It is common search algorithm for binary search tree.
		96	*/
		97	while (cur != NULL) {
		98	s = sum - cur->rgt_sum;
		99	if (key < s) {
		100	/*
		101	* Left subtree. Find max value in left subtree of cur.
		102	*/
		103	sum -= cur->key + cur->rgt_sum;
		104	cur = cur->lft;
		105	} else if (key > s) {
		106	/*
		107	* Right subtree. sum has still max value in the right subtree of cur.
		108	*/
		109	cur = cur->rgt;
		110	} else {
		111	/*
		112	* Equal values. We have found node with given key.
		113	*/
		114	return cur;
		115	}
		116	}
		117	return NULL;
		118	}
		119
		120
		121	/** Insert new node into ExtAVL tree.
		122	*
		123	* New node's key must be set.
		124	*
		125	* @param t ExtAVL tree structure.
		126	* @param newnode New node to be inserted.
		127	*/
		128	void extavlreltree_insert(extavlreltree_t t, extavlreltree_node_t newnode)
		129	{
		130	extavlreltree_node_t *cur;
		131	extavlreltree_node_t *son;
		132	extavlreltree_node_t *gpa;
		133	extavlreltree_node_t *par;
		134	uint64_t sum, s;
		135	uint8_t dir;
		136	/*
		137	* Condition var - all rgt_sums in the way down to root must be repaired in condition
		138	* that we came there from right and on the way from repaired node to new node we
		139	* never turn to the left. Reparation is done in the reparation cycle.
		140	*/
		141	bool repair_rgt_sum;
		142
		143	ASSERT(t);
		144	ASSERT(newnode);
		145
		146	/*
		147	* Insert first node into empty tree. Key is left without change (according to definition).
		148	*/
		149	cur = t->head.next;
		150	if (cur == &t->head) {
		151	newnode->lft = NULL;
		152	newnode->rgt = NULL;
		153	newnode->lft_height = 0;
		154	newnode->rgt_height = 0;
		155	newnode->par = NULL;
		156	newnode->next = &t->head;
		157	newnode->prev = &t->head;
		158	newnode->rgt_sum = 0;
		159
		160	t->head.prev = newnode;
		161	t->head.next = newnode;
		162	t->root = newnode;
		163	return;
		164	}
		165
		166	/*
		167	* Find right subtree in way up to the root where newnode will be placed.
		168	* Root node is the last node in the way up, when we reach root, it means,
		169	* that newnode belongs to the right subtree of root.
		170	*
		171	* When max key of cur's right subtree is inserted, while cycle overjumps
		172	* right node and stops. But in the next sorting for cycle is this situation
		173	* solved (for cycle jumps back to the left child).
		174	*/
		175	sum = 0;
		176	while (1) {
		177	sum += cur->key + cur->rgt_sum;
		178	if ((newnode->key <= sum) \|\| (cur == t->root))
		179	break;
		180	else
		181	cur = cur->par;
		182	}
		183
		184
		185	/*
		186	* Sorting for cycle.
		187	* Find a place for newnode. Searching start at cur node which we have found
		188	* in previous step. It is common search algorithm for binary search tree.
		189	*/
		190	for (;;) {
		191	s = sum - cur->rgt_sum;
		192	if (newnode->key < s) {
		193	/*
		194	* Left subtree. Find max value in left subtree of cur.
		195	*/
		196	sum -= cur->key + cur->rgt_sum;
		197
		198	if (!cur->lft) {
		199	/*
		200	* Insert new node to the left.
		201	*/
		202	cur->lft = newnode;
		203
		204	newnode->lft = NULL;
		205	newnode->rgt = NULL;
		206	newnode->lft_height = 0;
		207	newnode->rgt_height = 0;
		208	newnode->par = cur;
		209	/*
		210	* Insert newnode to list.
		211	*/
		212	newnode->next = cur;
		213	newnode->prev = cur->prev;
		214	cur->prev->next = newnode;
		215	cur->prev = newnode;
		216
		217	newnode->key -= sum;
		218	newnode->rgt_sum = 0;
		219	/*
		220	* Repair key of next value (next node always exists). newnode->key
		221	* has been already set. Needn't check whether newnode->next is head
		222	* beacause newnode is left child (next node is his father).
		223	*/
		224	newnode->next->key -= newnode->key;
		225
		226	repair_rgt_sum = false;
		227	dir = AVLTREE_LEFT;
		228	break;
		229	}
		230	cur = cur->lft;
		231	} else if (newnode->key > s) {
		232	/*
		233	* Right subtree. sum has still max value in the right subtree of cur.
		234	*/
		235
		236	if (!cur->rgt) {
		237	cur->rgt = newnode;
		238
		239	newnode->lft = NULL;
		240	newnode->rgt = NULL;
		241	newnode->lft_height = 0;
		242	newnode->rgt_height = 0;
		243	newnode->par = cur;
		244
		245	/*
		246	* Find last node in the chain with the same key as cur node.
		247	*/
		248	gpa = cur->next;
		249	while (gpa != &t->head && gpa->key == 0)
		250	gpa = gpa->next;
		251
		252	/*
		253	* Insert new node to list. Right place in the list was found in
		254	* previous cycle.
		255	*/
		256	newnode->prev = gpa->prev;
		257	newnode->next = gpa;
		258	gpa->prev->next = newnode;
		259	gpa->prev = newnode;
		260
		261	newnode->key -= sum;
		262	newnode->rgt_sum = 0;
		263	/*
		264	* Repair key of next value (next node always exists). newnode->key
		265	* has been already set.
		266	*/
		267	if (newnode->next != &t->head)
		268	newnode->next->key -= newnode->key;
		269	/*
		270	* All rgt_sums in the way down to root must be repaired in condition
		271	* that we came there from right and on the way from node to new node we
		272	* never turn left.
		273	*/
		274	repair_rgt_sum = true;
		275	dir = AVLTREE_RIGHT;
		276	break;
		277	}
		278	cur = cur->rgt;
		279
		280	} else {
		281	/*
		282	* Equal values. Give newnode to the last position of chain with the cur head and
		283	* end insertion.
		284	*/
		285	gpa = cur->next;
		286	while (gpa != &t->head && gpa->key == 0)
		287	gpa = gpa->next;
		288	/*
		289	* Insert new node to list in right place.
		290	*/
		291	newnode->prev = gpa->prev;
		292	newnode->next = gpa;
		293	gpa->prev->next = newnode;
		294	gpa->prev = newnode;
		295
		296	newnode->par = NULL;
		297	newnode->lft = NULL;
		298	newnode->rgt = NULL;
		299	newnode->lft_height = 0;
		300	newnode->rgt_height = 0;
		301
		302	/*
		303	* Nodes in chains has key equal 0, because difference between previous node and them is 0.
		304	*/
		305	newnode->key = 0;
		306	newnode->rgt_sum = 0;
		307	return;
		308	}
		309	}
		310
		311	/*
		312	* Balancing all nodes from newnode's parent down to root.
		313	*/
		314	cur = newnode->par;
		315	while (true) {
		316	if (dir == AVLTREE_LEFT) {
		317	/*
		318	* Insertion was made in the left subtree - repair left height, stop
		319	* repairing rgt_sum and check balance of current node.
		320	*/
		321	cur->lft_height = extavlreltree_tree_height(cur->lft) + 1;
		322
		323	repair_rgt_sum = false;
		324
		325	if ((cur->rgt_height - cur->lft_height) <= -2) {
		326	/*
		327	* Balance was corrupted, must be repaired through LL or LR rotation.
		328	*/
		329	par = cur->par;
		330	son = cur->lft;
		331	if ((son->rgt_height - son->lft_height) != 1) {
		332	/*
		333	* LL rotation.
		334	*/
		335	gpa = son;
		336	cur->lft = son->rgt;
		337	if (cur->lft != NULL) cur->lft->par = cur;
		338	cur->par = son;
		339	son->rgt = cur;
		340	/*
		341	* Repair heights.
		342	*/
		343	cur->lft_height = son->rgt_height;
		344	son->rgt_height = extavlreltree_tree_height(cur) + 1;
		345	/*
		346	* Repair rgt_sum.
		347	*/
		348	son->rgt_sum += cur->key + cur->rgt_sum;
		349	} else {
		350	/*
		351	* LR rotation.
		352	*/
		353	gpa = son->rgt;
		354	son->rgt = gpa->lft;
		355	if (gpa->lft != NULL) gpa->lft->par = son;
		356	gpa->lft = son;
		357	son->par = gpa;
		358	cur->lft = gpa->rgt;
		359	if (gpa->rgt != NULL) gpa->rgt->par = cur;
		360	gpa->rgt = cur;
		361	cur->par = gpa;
		362	/*
		363	* Repair heights.
		364	*/
		365	cur->lft_height = gpa->rgt_height;
		366	son->rgt_height = gpa->lft_height;
		367	gpa->rgt_height = extavlreltree_tree_height(cur) + 1;
		368	gpa->lft_height = extavlreltree_tree_height(son) + 1;
		369	/*
		370	* Repair rgt_sums.
		371	*/
		372	son->rgt_sum -= gpa->key + gpa->rgt_sum;
		373	gpa->rgt_sum += cur->key + cur->rgt_sum;
		374	}
		375	/*
		376	* Repair parent of current node.
		377	*/
		378	gpa->par = par;
		379	} else {
		380	/*
		381	* Balance is correct, continue balancing at parent node.
		382	*/
		383	par = cur->par;
		384	gpa = cur;
		385	}
		386	} else {
		387	/*
		388	* Insertion was made in the right subtree - repair right height, try to
		389	* repair rgt_sum and check balance of current node.
		390	*/
		391	cur->rgt_height = extavlreltree_tree_height(cur->rgt) + 1;
		392
		393	if (repair_rgt_sum) {
		394	cur->rgt_sum += newnode->key;
		395	}
		396
		397	if ((cur->rgt_height - cur->lft_height) >= 2) {
		398	/*
		399	* Balance was corrupted, must be repaired through RL or RR rotation.
		400	*/
		401	par = cur->par;
		402	son = cur->rgt;
		403	if ((son->rgt_height - son->lft_height) != -1) {
		404	/*
		405	* RR rotation.
		406	*/
		407	gpa = son;
		408	cur->rgt = son->lft;
		409	if (cur->rgt != NULL) cur->rgt->par = cur;
		410	cur->par = son;
		411	son->lft = cur;
		412	/*
		413	* Repair heights.
		414	*/
		415	cur->rgt_height = son->lft_height;
		416	son->lft_height = extavlreltree_tree_height(cur) + 1;
		417	/*
		418	* Repair rgt_sum.
		419	*/
		420	cur->rgt_sum -= son->rgt_sum + son->key;
		421	} else {
		422	/*
		423	* RL rotation.
		424	*/
		425	gpa = son->lft;
		426	son->lft = gpa->rgt;
		427	if (gpa->rgt != NULL) gpa->rgt->par = son;
		428	gpa->rgt = son;
		429	son->par = gpa;
		430	cur->rgt = gpa->lft;
		431	if (gpa->lft != NULL) gpa->lft->par = cur;
		432	gpa->lft = cur;
		433	cur->par = gpa;
		434	/*
		435	* Repair heights.
		436	*/
		437	cur->rgt_height = gpa->lft_height;
		438	son->lft_height = gpa->rgt_height;
		439	gpa->lft_height = extavlreltree_tree_height(cur) + 1;
		440	gpa->rgt_height = extavlreltree_tree_height(son) + 1;
		441	/*
		442	* Repair rgt_sums.
		443	*/
		444	cur->rgt_sum -= son->key + son->rgt_sum + gpa->key + gpa->rgt_sum;
		445	gpa->rgt_sum += son->key + son->rgt_sum;
		446	}
		447
		448	/*
		449	* Repair parent of current node.
		450	*/
		451	gpa->par = par;
		452	} else {
		453	/*
		454	* Balance is correct, continue balancing at parent node.
		455	*/
		456	par = cur->par;
		457	gpa = cur;
		458	}
		459	}
		460	/*
		461	* Change parent pointers, set direction where is newnode and
		462	* continue balancing at parent node or if current node
		463	* is root then change root atribute pointer and stop
		464	*/
		465	if (par) {
		466	if (par->lft == cur) {
		467	par->lft = gpa;
		468	dir = AVLTREE_LEFT;
		469	} else {
		470	par->rgt = gpa;
		471	dir = AVLTREE_RIGHT;
		472	}
		473	} else {
		474	t->root = gpa;
		475	break;
		476	}
		477	cur = par;
		478	}
		479	}
		480
		481
		482	/** Delete node from ExtAVLrel tree.
		483	*
		484	* @param t ExtAVLrel tree structure.
		485	* @param node Address of node which will be deleted.
		486	*/
		487	void extavlreltree_delete(extavlreltree_t t, extavlreltree_node_t node)
		488	{
		489	extavlreltree_node_t **gpapar;
		490	extavlreltree_node_t *cur;
		491	extavlreltree_node_t *par;
		492	extavlreltree_node_t *gpa;
		493	int8_t dir;
		494	int8_t dir2=0;
2421	mencl	495	uint64_t key=0;
2416	mencl	496	int16_t balance;
		497	/*
		498	* Condition var - if true then all rgt_sums in the way down to root must be repaired in condition
		499	* that we came there from right and on the way from repaired node to new node we
		500	* never turn to the left. Reparation is done in the reparation cycle.
		501	*/
		502	bool repair_rgt_sum;
		503
		504
		505	ASSERT(t);
		506	ASSERT(node);
		507
		508	/*
		509	* Delete node from list.
		510	*/
		511	node->next->prev = node->prev;
		512	node->prev->next = node->next;
		513
		514	if (!node->par) {
		515	if (t->root != node) {
		516	/*
		517	* It is list node (not a tree node). Needn't repair tree or anything else.
		518	*/
		519	return;
		520	}
		521	repair_rgt_sum = false;
		522	gpapar = &(t->root);
		523	} else {
		524	/*
		525	* Find tree pointer which points to node.
		526	*/
		527	if (node->par->lft == node) {
		528	gpapar = &(node->par->lft);
		529	repair_rgt_sum = false;
		530	} else {
		531	gpapar = &(node->par->rgt);
		532	/*
		533	* Node is right child - rgt_sum might be repaired.
		534	*/
		535	repair_rgt_sum = true;
		536	}
		537	}
		538
		539
		540	if (&t->head != node->next && node->next->key == 0) {
		541	/*
		542	* Deleted node has at least one node node with the same key which is closest next
		543	* neighbor in the list, copy node atributes into next node and end.
		544	*/
		545	cur = node->next;
		546	cur->lft = node->lft;
		547	cur->rgt = node->rgt;
		548	cur->par = node->par;
		549	cur->lft_height = node->lft_height;
		550	cur->rgt_height = node->rgt_height;
		551	*gpapar = cur;
		552
		553	if (node->lft) node->lft->par = cur;
		554	if (node->rgt) node->rgt->par = cur;
		555
		556	cur->key = node->key;
		557	cur->rgt_sum = node->rgt_sum;
		558	return;
		559	}
		560
		561	/*
		562	* Repair next node's key (it must be difference between previous key and its key).
		563	*/
		564	if (node->next != &t->head) {
		565	node->next->key += node->key;
		566	}
		567
		568	/*
		569	* Check situation in the tree around deleted node.
		570	*/
		571	if (!node->lft) {
		572	/*
		573	* Deleted node has not left son. Right son will take deleted node's place.
		574	*/
		575	gpa = node->par;
		576	if (node->rgt) {
		577	/*
		578	* rgt_sum is not corrupted because the biggest key is in right subtree of node
		579	*/
		580	node->rgt->par = gpa;
		581	repair_rgt_sum = false;
		582	} else {
		583	/*
		584	* node is the biggest key and rgt_sum might be repaired according to which
		585	* child is node.
		586	*/
		587	key = node->key;
		588	}
		589
		590	if (!gpa) {
		591	/*
		592	* Deleted node is root node. Balancing is finished, change only
		593	* root pointer in extavltree structure.
		594	*/
		595	*gpapar = node->rgt;
		596	return;
		597	}
		598	dir = (gpa->lft == node)? AVLTREE_LEFT: AVLTREE_RIGHT;
		599
		600	*gpapar = node->rgt;
		601	} else {
		602	/*
		603	* Node has left son.
		604	*/
		605	cur = node->lft;
		606	if (!cur->rgt) {
		607	/*
		608	* Left son of node hasn't got right son. Left son will take deleted node's place.
		609	*/
		610	*gpapar = cur;
		611	cur->par = node->par;
		612	dir = AVLTREE_LEFT;
		613	cur->rgt = node->rgt;
		614	if (node->rgt) node->rgt->par = cur;
		615	gpa = cur;
		616	cur->rgt_height = node->rgt_height;
		617	cur->lft_height = node->lft_height;
		618	/*
		619	* cur->lft_height will be decreased in repair cycle.
		620	*/
		621
		622	if (repair_rgt_sum == false && node->rgt_sum == 0) {
		623	/*
		624	* node hasn't got right son so right sum is 0.
		625	*/
		626	cur->rgt_sum = 0;
		627	} else {
		628	cur->rgt_sum = node->rgt_sum + node->key; //pri node->rgt_sum == 0 bude opraveno v cyklu
		629	if (repair_rgt_sum == true && node->rgt_sum != 0) {
		630	/*
		631	* node has got right son so node's key is not the biggest key in any subtree.
		632	*/
		633	repair_rgt_sum = false;
		634	} else {
		635	/*
		636	* node is the biggest key and predecessors might be repaired.
		637	*/
		638	key = node->key;
		639	}
		640	}
		641	} else {
		642	/*
		643	* Node has left and right son. Find a node with smallest key in left subtree
		644	* and change that node with deleted node.
		645	*/
		646	while (cur->rgt != NULL)
		647	cur = cur->rgt;
		648
		649	*gpapar = cur;
		650	cur->rgt = node->rgt;
		651	if (node->rgt) node->rgt->par = cur;
		652	gpa = cur->par;
		653	gpa->rgt = cur->lft;
		654	if (cur->lft) cur->lft->par = gpa;
		655	cur->lft = node->lft;
		656	cur->lft->par = cur;
		657	cur->par = node->par;
		658	dir = AVLTREE_RIGHT;
		659	cur->lft_height = node->lft_height;
		660	cur->rgt_height = node->rgt_height;
		661	/*
		662	* gpa->rgt_height and cur->lft_height will be repaired in repair cycle.
		663	*/
		664
		665	/*
		666	* node must have always rgt child otherwise its malfunction of extavltree definition
		667	* so we can add node->key. If it was to the contrary, we wouldn't know where
		668	*/
		669	cur->rgt_sum = node->rgt_sum + node->key;
		670	/*
		671	* The biggest key in at least one subtree was changed - rgt_sum must be repaired.
		672	*/
		673	repair_rgt_sum = true;
		674	key = cur->key;
		675	}
		676	/*
		677	* Deleted node is root node. Balancing is finished.
		678	*/
		679	if (!gpa) return;
		680	}
		681
		682	/*
		683	* Repair cycle which goes from gpa node down to root.
		684	*/
		685	for(;;) {
		686	if (repair_rgt_sum) {
		687	/*
		688	* The biggest key in right subtree was deleted so rgt_sum must be changed.
		689	*/
		690	gpa->rgt_sum -= key;
		691	}
		692
		693	/*
		694	* Find tree pointer which points to the currently balanced node. When balanced
		695	* node is root, root pointer from extavltree structure is taken.
		696	*/
		697	if (!gpa->par)
		698	gpapar = &(t->root);
		699	else {
		700	if (gpa->par->lft == gpa) {
		701	gpapar = &(gpa->par->lft);
		702	dir2 = AVLTREE_LEFT;
2421	mencl	703	repair_rgt_sum = false;
2416	mencl	704	} else {
		705	gpapar = &(gpa->par->rgt);
		706	dir2 = AVLTREE_RIGHT;
		707	}
		708	}
		709
		710	if (dir == AVLTREE_LEFT) {
		711	/*
		712	* Deletition was made in left subtree.
		713	*/
		714	gpa->lft_height--;
		715	balance = gpa->rgt_height - gpa->lft_height;
		716	if (balance == 1) {
		717	/*
		718	* Stop balancing, tree is balanced.
		719	*/
		720	break;
		721	} else if (balance == 2) {
		722	/*
		723	* Bad balance, heights of left and right subtrees differs more then is allowed.
		724	*/
		725	par = gpa->rgt;
		726
		727	if ((par->rgt_height - par->lft_height) == -1) {
		728	/*
		729	* RL rotation
		730	*/
		731
		732	cur = par->lft;
		733	par->lft = cur->rgt;
		734	cur->rgt = par;
		735	gpa->rgt = cur->lft;
		736	cur->lft = gpa;
		737
		738	/*
		739	* Repair balances.
		740	*/
		741	par->lft_height = cur->rgt_height;
		742	gpa->rgt_height = cur->lft_height;
		743	cur->lft_height = extavlreltree_tree_height(gpa) + 1;
		744	cur->rgt_height = par->rgt_height + 1;
		745
		746	/*
		747	* Repair paternity.
		748	*/
		749	if (gpa->rgt) gpa->rgt->par = gpa;
		750	if (par->lft) par->lft->par = par;
		751	cur->par = gpa->par;
		752	gpa->par = cur;
		753	par->par = cur;
		754
		755	/*
		756	* Repair tree pointer which points to the current node.
		757	*/
		758	*gpapar = cur;
		759
		760	/*
		761	* Repair rgt_sums after rotation was done.
		762	*/
		763	gpa->rgt_sum -= par->key + par->rgt_sum + cur->key + cur->rgt_sum;
		764	cur->rgt_sum += par->key + par->rgt_sum;
		765
		766	/*
		767	* Next balancing at parent node.
		768	*/
		769	gpa = cur->par;
		770	} else {
		771	/*
		772	* RR rotation
		773	*/
		774	gpa->rgt = par->lft;
		775	gpa->rgt_height = par->lft_height;
		776	if (par->lft) par->lft->par = gpa;
		777	par->lft = gpa;
		778
		779	/*
		780	* Repair paternity.
		781	*/
		782	par->par = gpa->par;
		783	gpa->par = par;
		784
		785	/*
		786	* Repair heights and tree pointer which points to the current node.
		787	*/
		788	balance = par->rgt_height - par->lft_height;
		789	par->lft_height++;
		790	*gpapar = par;
		791
		792	/*
		793	* Repair rgt_sums after rotation was done.
		794	*/
		795	gpa->rgt_sum -= par->key + par->rgt_sum;
		796
		797	/*
		798	* Ends when tree is balanced or do the next step.
		799	*/
		800	if (balance == 0) return;
		801	gpa = par->par;
		802	}
		803	} else {
		804	/*
		805	* Current node is balanced - perform balance check of its parent.
		806	*/
		807	gpa = gpa->par;
		808	}
		809	} else {
		810	/*
		811	* Balance right son.
		812	*/
		813	gpa->rgt_height--;
		814	balance = gpa->rgt_height - gpa->lft_height;
		815	if (balance == -1) {
		816	/*
		817	* Stop balancing, tree might be balanced or not, whole tree is repaired only during insertion.
		818	*/
		819	break;
		820	} else if (balance == -2) {
		821	/*
		822	* Balance was corrupted - must be repaired.
		823	*/
		824	par = gpa->lft;
		825
		826	if ((par->rgt_height - par->lft_height) >= +1) {
		827	/*
		828	* If balance is -2 then par node always exists.
		829	*/
		830	if ((gpa->lft_height - (extavlreltree_tree_height(par))) == 1) {
		831	/*
		832	* LR rotation. Height of par subtree is not decreased due to timeout operation.
		833	*/
		834
		835	cur = par->rgt;
		836	par->rgt = cur->lft;
		837	cur->lft = par;
		838	gpa->lft = cur->rgt;
		839	cur->rgt = gpa;
		840
		841	/*
		842	* Repair balances.
		843	*/
		844	par->rgt_height = cur->lft_height;
		845	gpa->lft_height = cur->rgt_height;
		846	cur->rgt_height = gpa->rgt_height + 1;
		847	cur->lft_height = extavlreltree_tree_height(par) + 1;
		848
		849	/*
		850	* Repair paternity.
		851	*/
		852	if (gpa->lft) gpa->lft->par = gpa;
		853	if (par->rgt) par->rgt->par = par;
		854	cur->par = gpa->par;
		855	gpa->par = cur;
		856	par->par = cur;
		857
		858	/*
		859	* Repair tree pointer which points to the current node.
		860	*/
		861	*gpapar = cur;
		862
		863	/*
		864	* Repair rgt_sums after rotation was done.
		865	*/
		866	par->rgt_sum -= cur->key + cur->rgt_sum;
		867	cur->rgt_sum += gpa->key + gpa->rgt_sum;
		868
		869	/*
		870	* Next balancing at parent node.
		871	*/
		872	gpa = cur->par;
		873	} else {
		874	/*
		875	* Left subtree of cur has been already decreased by timeout operation.
		876	*/
		877	gpa = gpa->par;
		878	}
		879	} else {
		880	/*
		881	* LL rotation.
		882	*/
		883
		884	int prevlftheight = gpa->lft_height;
		885	gpa->lft = par->rgt;
		886	gpa->lft_height = par->rgt_height;
		887	if (par->rgt) par->rgt->par = gpa;
		888	par->rgt = gpa;
		889
		890	/*
		891	* Repair paternity.
		892	*/
		893	par->par = gpa->par;
		894	gpa->par = par;
		895
		896	/*
		897	* Repair heights and tree pointer which points to the current node.
		898	*/
		899	balance = par->rgt_height - par->lft_height;
		900	par->rgt_height = extavlreltree_tree_height(gpa) + 1;
		901	*gpapar = par;
		902
		903	/*
		904	* Repair rgt_sums after rotation was done.
		905	*/
		906	par->rgt_sum += gpa->key + gpa->rgt_sum;
		907
		908	/*
		909	* Ends balancing when heights in par nodes are balanced and height
		910	* of par subtree wasn't decreased due to timeout operation or do
		911	* the next step.
		912	*/
		913	if (balance == 0 && par->rgt_height == prevlftheight) {
		914	gpa = par;
		915	break;
		916	}
		917	gpa = par->par;
		918	}
		919	} else {
		920	/*
		921	* Current node is balanced - perform balance check of its parent.
		922	*/
		923	gpa = gpa->par;
		924	}
		925	}
		926	/*
		927	* When root is reached then end balancing.
		928	*/
		929	if (!gpa) return;
		930
		931	dir = dir2;
		932	}
		933
		934	/*
		935	* End balancing. We must continue in repairing rgt_sum until we
		936	* reach first left child.
		937	*/
		938	if (repair_rgt_sum) {
		939	cur = gpa;
		940	gpa = gpa->par;
		941	while (gpa) {
		942	if (gpa->lft == cur)
		943	break;
		944	gpa->rgt_sum -= key;
		945	cur = gpa;
		946	gpa = gpa->par;
		947	}
		948	}
		949	}
		950
		951
		952	/** Delete node from ExtAVLirel tree with the smallest key.
		953	*
		954	* Be careful deleted node must have key equal 0 to perform regular timeout.
		955	*
		956	* @param t ExtAVLrel tree structure.
		957	*/
		958	bool extavlreltree_delete_min(extavlreltree_t *t)
		959	{
		960	extavlreltree_node_t *expnode;
		961	extavlreltree_node_t *nextnode;
		962
		963	ASSERT(t);
		964
		965	expnode = t->head.next;
		966	nextnode = expnode->next;
		967
		968	if (&t->head == expnode) return false;
		969
		970	if (nextnode != &t->head) {
		971	/*
		972	* Only first node in the list can be tree node and its key can be 0 (nextnode is the second).
		973	*/
		974	if (nextnode->key == 0) {
		975	/*
		976	* Next node of expnode is its chain node. Copy expnode into nextnode.
		977	*/
		978
		979	nextnode->lft = expnode->lft;
		980	nextnode->rgt = expnode->rgt;
		981	nextnode->par = expnode->par;
		982	nextnode->lft_height = expnode->lft_height;
		983	nextnode->rgt_height = expnode->rgt_height;
		984	if (t->root == expnode)
		985	t->root = nextnode;
		986	else
		987	if (expnode->par->lft == expnode)
		988	expnode->par->lft = nextnode;
		989	else
		990	expnode->par->rgt = nextnode;
		991
		992	if (expnode->lft) expnode->lft->par = nextnode;
		993	if (expnode->rgt) expnode->rgt->par = nextnode;
		994
		995	nextnode->rgt_sum = expnode->rgt_sum;
		996	} else if (!expnode->par) {
		997	/*
		998	* Delete root node which musn't have left son.
		999	*/
		1000
		1001	t->root = expnode->rgt;
		1002	if (expnode->rgt) expnode->rgt->par = NULL;
		1003	} else if (expnode->rgt) {
		1004	/*
		1005	* Always delete parent of left son.
		1006	*/
		1007
		1008	expnode->rgt->par = expnode->par;
		1009	expnode->par->lft = expnode->rgt;
		1010	expnode->par->lft_height = expnode->rgt_height;
		1011	} else {
		1012	/*
		1013	* Deleted node doesn't have right son.
		1014	*/
		1015
		1016	expnode->par->lft = NULL;
		1017	expnode->par->lft_height = 0;
		1018	}
		1019	nextnode->key += expnode->key;
		1020	}
		1021
		1022	/*
		1023	* Delete node from the list.
		1024	*/
		1025	t->head.next = nextnode;
		1026	nextnode->prev = &t->head;
		1027
		1028	return true;
		1029	}

Subversion Repositories HelenOS

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