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

Subversion Repositories HelenOS

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