// SPDX-License-Identifier: GPL-2.0-or-later/* * 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 Linutronix GmbH, Thomas Gleixner <tglx@kernel.org> * * Simplifications of the original code by * Oleg Nesterov <oleg@tv-sign.ru> * * 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_PLIST 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, *last, *reverse_iter;	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);	last = reverse_iter = list_entry(first->prio_list.prev, struct plist_node, prio_list); 	do {		if (node->prio < iter->prio) {			node_next = &iter->node_list;			break;		} else if (node->prio >= reverse_iter->prio) {			prev = reverse_iter;			iter = list_entry(reverse_iter->prio_list.next,				struct plist_node, prio_list);			if (likely(reverse_iter != last))				node_next = &iter->node_list;			break;		} 		prev = iter;		iter = list_entry(iter->prio_list.next,				struct plist_node, prio_list);		reverse_iter = list_entry(reverse_iter->prio_list.prev,				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); 	/*	 * After plist_del(), iter is the replacement of the node.  If the node	 * was on prio_list, take shortcut to find node_next instead of looping.	 */	if (!list_empty(&iter->prio_list)) {		iter = list_entry(iter->prio_list.next, struct plist_node,				  prio_list);		node_next = &iter->node_list;		goto queue;	} 	plist_for_each_continue(iter, head) {		if (node->prio != iter->prio) {			node_next = &iter->node_list;			break;		}	}queue:	list_add_tail(&node->node_list, node_next); 	plist_check_head(head);} #ifdef CONFIG_DEBUG_PLIST#include <linux/sched.h>#include <linux/sched/clock.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"); 	/* Worst case test for plist_add() */	unsigned int test_data[241]; 	for (i = 0; i < ARRAY_SIZE(test_data); i++)		test_data[i] = i; 	ktime_t start, end, time_elapsed = 0; 	plist_head_init(&test_head); 	for (i = 0; i < ARRAY_SIZE(test_node); i++) {		plist_node_init(test_node + i, 0);		test_node[i].prio = test_data[i];	} 	for (i = 0; i < ARRAY_SIZE(test_node); i++) {		if (plist_node_empty(test_node + i)) {			start = ktime_get();			plist_add(test_node + i, &test_head);			end = ktime_get();			time_elapsed += (end - start);		}	} 	pr_debug("plist_add worst case test time elapsed %lld\n", time_elapsed);	return 0;} module_init(plist_test); #endif