[deliverable/linux.git] / lib / plist.c

/*
 * lib/plist.c
 *
 * Descending-priority-sorted double-linked list
 *
 * (C) 2002-2003 Intel Corp
 * Inaky Perez-Gonzalez <inaky.perez-gonzalez@intel.com>.
 *
 * 2001-2005 (c) MontaVista Software, Inc.
 * Daniel Walker <dwalker@mvista.com>
 *
 * (C) 2005 Thomas Gleixner <tglx@linutronix.de>
 *
 * Simplifications of the original code by
 * Oleg Nesterov <oleg@tv-sign.ru>
 *
 * Licensed under the FSF's GNU Public License v2 or later.
 *
 * Based on simple lists (include/linux/list.h).
 *
 * This file contains the add / del functions which are considered to
 * be too large to inline. See include/linux/plist.h for further
 * information.
 */

#include <linux/bug.h>
#include <linux/plist.h>

#ifdef CONFIG_DEBUG_PI_LIST

static struct plist_head test_head;

static void plist_check_prev_next(struct list_head *t, struct list_head *p,
				  struct list_head *n)
{
	WARN(n->prev != p || p->next != n,
			"top: %p, n: %p, p: %p\n"
			"prev: %p, n: %p, p: %p\n"
			"next: %p, n: %p, p: %p\n",
			 t, t->next, t->prev,
			p, p->next, p->prev,
			n, n->next, n->prev);
}

static void plist_check_list(struct list_head *top)
{
	struct list_head *prev = top, *next = top->next;

	plist_check_prev_next(top, prev, next);
	while (next != top) {
		prev = next;
		next = prev->next;
		plist_check_prev_next(top, prev, next);
	}
}

static void plist_check_head(struct plist_head *head)
{
	if (!plist_head_empty(head))
		plist_check_list(&plist_first(head)->prio_list);
	plist_check_list(&head->node_list);
}

#else
# define plist_check_head(h)	do { } while (0)
#endif

/**
 * plist_add - add @node to @head
 *
 * @node:	&struct plist_node pointer
 * @head:	&struct plist_head pointer
 */
void plist_add(struct plist_node *node, struct plist_head *head)
{
	struct plist_node *first, *iter, *prev = NULL;
	struct list_head *node_next = &head->node_list;

	plist_check_head(head);
	WARN_ON(!plist_node_empty(node));
	WARN_ON(!list_empty(&node->prio_list));

	if (plist_head_empty(head))
		goto ins_node;

	first = iter = plist_first(head);

	do {
		if (node->prio < iter->prio) {
			node_next = &iter->node_list;
			break;
		}

		prev = iter;
		iter = list_entry(iter->prio_list.next,
				struct plist_node, prio_list);
	} while (iter != first);

	if (!prev || prev->prio != node->prio)
		list_add_tail(&node->prio_list, &iter->prio_list);
ins_node:
	list_add_tail(&node->node_list, node_next);

	plist_check_head(head);
}

/**
 * plist_del - Remove a @node from plist.
 *
 * @node:	&struct plist_node pointer - entry to be removed
 * @head:	&struct plist_head pointer - list head
 */
void plist_del(struct plist_node *node, struct plist_head *head)
{
	plist_check_head(head);

	if (!list_empty(&node->prio_list)) {
		if (node->node_list.next != &head->node_list) {
			struct plist_node *next;

			next = list_entry(node->node_list.next,
					struct plist_node, node_list);

			/* add the next plist_node into prio_list */
			if (list_empty(&next->prio_list))
				list_add(&next->prio_list, &node->prio_list);
		}
		list_del_init(&node->prio_list);
	}

	list_del_init(&node->node_list);

	plist_check_head(head);
}

/**
 * plist_requeue - Requeue @node at end of same-prio entries.
 *
 * This is essentially an optimized plist_del() followed by
 * plist_add().  It moves an entry already in the plist to
 * after any other same-priority entries.
 *
 * @node:	&struct plist_node pointer - entry to be moved
 * @head:	&struct plist_head pointer - list head
 */
void plist_requeue(struct plist_node *node, struct plist_head *head)
{
	struct plist_node *iter;
	struct list_head *node_next = &head->node_list;

	plist_check_head(head);
	BUG_ON(plist_head_empty(head));
	BUG_ON(plist_node_empty(node));

	if (node == plist_last(head))
		return;

	iter = plist_next(node);

	if (node->prio != iter->prio)
		return;

	plist_del(node, head);

	plist_for_each_continue(iter, head) {
		if (node->prio != iter->prio) {
			node_next = &iter->node_list;
			break;
		}
	}
	list_add_tail(&node->node_list, node_next);

	plist_check_head(head);
}

#ifdef CONFIG_DEBUG_PI_LIST
#include <linux/sched.h>
#include <linux/module.h>
#include <linux/init.h>

static struct plist_node __initdata test_node[241];

static void __init plist_test_check(int nr_expect)
{
	struct plist_node *first, *prio_pos, *node_pos;

	if (plist_head_empty(&test_head)) {
		BUG_ON(nr_expect != 0);
		return;
	}

	prio_pos = first = plist_first(&test_head);
	plist_for_each(node_pos, &test_head) {
		if (nr_expect-- < 0)
			break;
		if (node_pos == first)
			continue;
		if (node_pos->prio == prio_pos->prio) {
			BUG_ON(!list_empty(&node_pos->prio_list));
			continue;
		}

		BUG_ON(prio_pos->prio > node_pos->prio);
		BUG_ON(prio_pos->prio_list.next != &node_pos->prio_list);
		prio_pos = node_pos;
	}

	BUG_ON(nr_expect != 0);
	BUG_ON(prio_pos->prio_list.next != &first->prio_list);
}

static void __init plist_test_requeue(struct plist_node *node)
{
	plist_requeue(node, &test_head);

	if (node != plist_last(&test_head))
		BUG_ON(node->prio == plist_next(node)->prio);
}

static int  __init plist_test(void)
{
	int nr_expect = 0, i, loop;
	unsigned int r = local_clock();

	printk(KERN_DEBUG "start plist test\n");
	plist_head_init(&test_head);
	for (i = 0; i < ARRAY_SIZE(test_node); i++)
		plist_node_init(test_node + i, 0);

	for (loop = 0; loop < 1000; loop++) {
		r = r * 193939 % 47629;
		i = r % ARRAY_SIZE(test_node);
		if (plist_node_empty(test_node + i)) {
			r = r * 193939 % 47629;
			test_node[i].prio = r % 99;
			plist_add(test_node + i, &test_head);
			nr_expect++;
		} else {
			plist_del(test_node + i, &test_head);
			nr_expect--;
		}
		plist_test_check(nr_expect);
		if (!plist_node_empty(test_node + i)) {
			plist_test_requeue(test_node + i);
			plist_test_check(nr_expect);
		}
	}

	for (i = 0; i < ARRAY_SIZE(test_node); i++) {
		if (plist_node_empty(test_node + i))
			continue;
		plist_del(test_node + i, &test_head);
		nr_expect--;
		plist_test_check(nr_expect);
	}

	printk(KERN_DEBUG "end plist test\n");
	return 0;
}

module_init(plist_test);

#endif
Commit	Line	Data
77ba89c5 IM	1	/*
	2	* lib/plist.c
	3	*
	4	* Descending-priority-sorted double-linked list
	5	*
	6	* (C) 2002-2003 Intel Corp
	7	* Inaky Perez-Gonzalez <inaky.perez-gonzalez@intel.com>.
	8	*
	9	* 2001-2005 (c) MontaVista Software, Inc.
	10	* Daniel Walker <dwalker@mvista.com>
	11	*
	12	* (C) 2005 Thomas Gleixner <tglx@linutronix.de>
	13	*
	14	* Simplifications of the original code by
	15	* Oleg Nesterov <oleg@tv-sign.ru>
	16	*
	17	* Licensed under the FSF's GNU Public License v2 or later.
	18	*
	19	* Based on simple lists (include/linux/list.h).
	20	*
	21	* This file contains the add / del functions which are considered to
	22	* be too large to inline. See include/linux/plist.h for further
	23	* information.
	24	*/
	25
50af5ead	26	#include <linux/bug.h>
77ba89c5	27	#include <linux/plist.h>
77ba89c5 IM	28
	29	#ifdef CONFIG_DEBUG_PI_LIST
	30
6d55da53 LJ	31	static struct plist_head test_head;
6d55da53 LJ	32
77ba89c5 IM	33	static void plist_check_prev_next(struct list_head t, struct list_head p,
	34	struct list_head *n)
	35	{
5cd2b459 AV	36	WARN(n->prev != p \|\| p->next != n,
	37	"top: %p, n: %p, p: %p\n"
	38	"prev: %p, n: %p, p: %p\n"
	39	"next: %p, n: %p, p: %p\n",
	40	t, t->next, t->prev,
	41	p, p->next, p->prev,
	42	n, n->next, n->prev);
77ba89c5 IM	43	}
	44
	45	static void plist_check_list(struct list_head *top)
	46	{
	47	struct list_head prev = top, next = top->next;
	48
	49	plist_check_prev_next(top, prev, next);
	50	while (next != top) {
	51	prev = next;
	52	next = prev->next;
	53	plist_check_prev_next(top, prev, next);
	54	}
	55	}
	56
	57	static void plist_check_head(struct plist_head *head)
	58	{
bf6a9b83 LJ	59	if (!plist_head_empty(head))
bf6a9b83 LJ	60	plist_check_list(&plist_first(head)->prio_list);
77ba89c5 IM	61	plist_check_list(&head->node_list);
	62	}
	63
	64	#else
	65	# define plist_check_head(h) do { } while (0)
	66	#endif
	67
	68	/**
	69	* plist_add - add @node to @head
	70	*
	71	* @node: &struct plist_node pointer
	72	* @head: &struct plist_head pointer
	73	*/
	74	void plist_add(struct plist_node node, struct plist_head head)
	75	{
bf6a9b83 LJ	76	struct plist_node first, iter, *prev = NULL;
bf6a9b83 LJ	77	struct list_head *node_next = &head->node_list;
77ba89c5 IM	78
	79	plist_check_head(head);
	80	WARN_ON(!plist_node_empty(node));
bf6a9b83	81	WARN_ON(!list_empty(&node->prio_list));
77ba89c5	82
bf6a9b83 LJ	83	if (plist_head_empty(head))
	84	goto ins_node;
	85
	86	first = iter = plist_first(head);
	87
	88	do {
	89	if (node->prio < iter->prio) {
	90	node_next = &iter->node_list;
	91	break;
77ba89c5	92	}
77ba89c5	93
bf6a9b83 LJ	94	prev = iter;
	95	iter = list_entry(iter->prio_list.next,
	96	struct plist_node, prio_list);
	97	} while (iter != first);
	98
	99	if (!prev \|\| prev->prio != node->prio)
	100	list_add_tail(&node->prio_list, &iter->prio_list);
	101	ins_node:
	102	list_add_tail(&node->node_list, node_next);
77ba89c5 IM	103
	104	plist_check_head(head);
	105	}
	106
	107	/**
	108	* plist_del - Remove a @node from plist.
	109	*
	110	* @node: &struct plist_node pointer - entry to be removed
	111	* @head: &struct plist_head pointer - list head
	112	*/
	113	void plist_del(struct plist_node node, struct plist_head head)
	114	{
	115	plist_check_head(head);
	116
bf6a9b83 LJ	117	if (!list_empty(&node->prio_list)) {
	118	if (node->node_list.next != &head->node_list) {
	119	struct plist_node *next;
	120
	121	next = list_entry(node->node_list.next,
	122	struct plist_node, node_list);
77ba89c5	123
bf6a9b83 LJ	124	/* add the next plist_node into prio_list */
	125	if (list_empty(&next->prio_list))
	126	list_add(&next->prio_list, &node->prio_list);
	127	}
	128	list_del_init(&node->prio_list);
77ba89c5 IM	129	}
77ba89c5 IM	130
bf6a9b83	131	list_del_init(&node->node_list);
77ba89c5 IM	132
	133	plist_check_head(head);
	134	}
6d55da53	135
a75f232c DS	136	/**
	137	* plist_requeue - Requeue @node at end of same-prio entries.
	138	*
	139	* This is essentially an optimized plist_del() followed by
	140	* plist_add(). It moves an entry already in the plist to
	141	* after any other same-priority entries.
	142	*
	143	* @node: &struct plist_node pointer - entry to be moved
	144	* @head: &struct plist_head pointer - list head
	145	*/
	146	void plist_requeue(struct plist_node node, struct plist_head head)
	147	{
	148	struct plist_node *iter;
	149	struct list_head *node_next = &head->node_list;
	150
	151	plist_check_head(head);
	152	BUG_ON(plist_head_empty(head));
	153	BUG_ON(plist_node_empty(node));
	154
	155	if (node == plist_last(head))
	156	return;
	157
	158	iter = plist_next(node);
	159
	160	if (node->prio != iter->prio)
	161	return;
	162
	163	plist_del(node, head);
	164
	165	plist_for_each_continue(iter, head) {
	166	if (node->prio != iter->prio) {
	167	node_next = &iter->node_list;
	168	break;
	169	}
	170	}
	171	list_add_tail(&node->node_list, node_next);
	172
	173	plist_check_head(head);
	174	}
	175
6d55da53 LJ	176	#ifdef CONFIG_DEBUG_PI_LIST
	177	#include <linux/sched.h>
	178	#include <linux/module.h>
	179	#include <linux/init.h>
	180
	181	static struct plist_node __initdata test_node[241];
	182
	183	static void __init plist_test_check(int nr_expect)
	184	{
	185	struct plist_node first, prio_pos, *node_pos;
	186
	187	if (plist_head_empty(&test_head)) {
	188	BUG_ON(nr_expect != 0);
	189	return;
	190	}
	191
	192	prio_pos = first = plist_first(&test_head);
	193	plist_for_each(node_pos, &test_head) {
	194	if (nr_expect-- < 0)
	195	break;
	196	if (node_pos == first)
	197	continue;
	198	if (node_pos->prio == prio_pos->prio) {
	199	BUG_ON(!list_empty(&node_pos->prio_list));
	200	continue;
	201	}
	202
	203	BUG_ON(prio_pos->prio > node_pos->prio);
	204	BUG_ON(prio_pos->prio_list.next != &node_pos->prio_list);
	205	prio_pos = node_pos;
	206	}
	207
	208	BUG_ON(nr_expect != 0);
	209	BUG_ON(prio_pos->prio_list.next != &first->prio_list);
	210	}
	211
a75f232c DS	212	static void __init plist_test_requeue(struct plist_node *node)
	213	{
	214	plist_requeue(node, &test_head);
	215
	216	if (node != plist_last(&test_head))
	217	BUG_ON(node->prio == plist_next(node)->prio);
	218	}
	219
6d55da53 LJ	220	static int __init plist_test(void)
	221	{
	222	int nr_expect = 0, i, loop;
	223	unsigned int r = local_clock();
	224
18120627	225	printk(KERN_DEBUG "start plist test\n");
732375c6	226	plist_head_init(&test_head);
6d55da53 LJ	227	for (i = 0; i < ARRAY_SIZE(test_node); i++)
	228	plist_node_init(test_node + i, 0);
	229
	230	for (loop = 0; loop < 1000; loop++) {
	231	r = r * 193939 % 47629;
	232	i = r % ARRAY_SIZE(test_node);
	233	if (plist_node_empty(test_node + i)) {
	234	r = r * 193939 % 47629;
	235	test_node[i].prio = r % 99;
	236	plist_add(test_node + i, &test_head);
	237	nr_expect++;
	238	} else {
	239	plist_del(test_node + i, &test_head);
	240	nr_expect--;
	241	}
	242	plist_test_check(nr_expect);
a75f232c DS	243	if (!plist_node_empty(test_node + i)) {
	244	plist_test_requeue(test_node + i);
	245	plist_test_check(nr_expect);
	246	}
6d55da53 LJ	247	}
	248
	249	for (i = 0; i < ARRAY_SIZE(test_node); i++) {
	250	if (plist_node_empty(test_node + i))
	251	continue;
	252	plist_del(test_node + i, &test_head);
	253	nr_expect--;
	254	plist_test_check(nr_expect);
	255	}
	256
18120627	257	printk(KERN_DEBUG "end plist test\n");
6d55da53 LJ	258	return 0;
	259	}
	260
	261	module_init(plist_test);
	262
	263	#endif