LKML Archive on lore.kernel.org
help / color / mirror / Atom feed
From: Peter Zijlstra <a.p.zijlstra@chello.nl>
To: linux-kernel@vger.kernel.org
Cc: Daniel Walker <dwalker@mvista.com>,
	Steven Rostedt <rostedt@goodmis.org>, Ingo Molnar <mingo@elte.hu>,
	Thomas Gleixner <tglx@linutronix.de>,
	Gregory Haskins <ghaskins@novell.com>,
	Oleg Nesterov <oleg@tv-sign.ru>,
	Peter Zijlstra <a.p.zijlstra@chello.nl>
Subject: [RFC/PATCH 3/5] rt: plist_head_splice
Date: Tue, 23 Oct 2007 14:04:00 +0200	[thread overview]
Message-ID: <20071023120745.122724000@chello.nl> (raw)
In-Reply-To: <20071023120357.782284000@chello.nl>

[-- Attachment #1: rt-plist-mods.patch --]
[-- Type: text/plain, Size: 3464 bytes --]

merge-sort two plists together

Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
---
 include/linux/plist.h |    2 +
 lib/plist.c           |   68 ++++++++++++++++++++++++++++++++++++++++++++++++--
 2 files changed, 68 insertions(+), 2 deletions(-)

Index: linux-2.6/include/linux/plist.h
===================================================================
--- linux-2.6.orig/include/linux/plist.h
+++ linux-2.6/include/linux/plist.h
@@ -148,6 +148,8 @@ static inline void plist_node_init(struc
 extern void plist_add(struct plist_node *node, struct plist_head *head);
 extern void plist_del(struct plist_node *node, struct plist_head *head);
 
+extern void plist_head_splice(struct plist_head *src, struct plist_head *dst);
+
 /**
  * plist_for_each - iterate over the plist
  * @pos:	the type * to use as a loop counter
Index: linux-2.6/lib/plist.c
===================================================================
--- linux-2.6.orig/lib/plist.c
+++ linux-2.6/lib/plist.c
@@ -66,6 +66,30 @@ static void plist_check_head(struct plis
 # define plist_check_head(h)	do { } while (0)
 #endif
 
+static inline struct plist_node *prev_node(struct plist_node *iter)
+{
+	return list_entry(iter->plist.node_list.prev, struct plist_node,
+			plist.node_list);
+}
+
+static inline struct plist_node *next_node(struct plist_node *iter)
+{
+	return list_entry(iter->plist.node_list.next, struct plist_node,
+			plist.node_list);
+}
+
+static inline struct plist_node *prev_prio(struct plist_node *iter)
+{
+	return list_entry(iter->plist.prio_list.prev, struct plist_node,
+			plist.prio_list);
+}
+
+static inline struct plist_node *next_prio(struct plist_node *iter)
+{
+	return list_entry(iter->plist.prio_list.next, struct plist_node,
+			plist.prio_list);
+}
+
 /**
  * plist_add - add @node to @head
  *
@@ -83,8 +107,7 @@ void plist_add(struct plist_node *node, 
 		if (node->prio < iter->prio)
 			goto lt_prio;
 		else if (node->prio == iter->prio) {
-			iter = list_entry(iter->plist.prio_list.next,
-					struct plist_node, plist.prio_list);
+			iter = next_prio(iter);
 			goto eq_prio;
 		}
 	}
@@ -118,3 +141,44 @@ void plist_del(struct plist_node *node, 
 
 	plist_check_head(head);
 }
+
+void plist_head_splice(struct plist_head *src, struct plist_head *dst)
+{
+	struct plist_node *src_iter_first, *src_iter_last, *dst_iter;
+	struct plist_node *tail = container_of(dst, struct plist_node, plist);
+
+	dst_iter = next_prio(tail);
+
+	while (!plist_head_empty(src) && dst_iter != tail) {
+		src_iter_first = plist_first(src);
+
+		src_iter_last = next_prio(src_iter_first);
+		src_iter_last = prev_node(src_iter_last);
+
+		WARN_ON(src_iter_first->prio != src_iter_last->prio);
+		WARN_ON(list_empty(&src_iter_first->plist.prio_list));
+
+		while (src_iter_first->prio > dst_iter->prio) {
+			dst_iter = next_prio(dst_iter);
+			if (dst_iter == tail)
+				goto tail;
+		}
+
+		list_del_init(&src_iter_first->plist.prio_list);
+
+		if (src_iter_first->prio < dst_iter->prio) {
+			list_add_tail(&src_iter_first->plist.node_list,
+					&dst_iter->plist.node_list);
+		} else if (src_iter_first->prio == dst_iter->prio) {
+			dst_iter = next_prio(dst_iter);
+		} else BUG();
+
+		list_splice2_tail(&src_iter_first->plist.node_list,
+			       	  &src_iter_last->plist.node_list,
+				  &dst_iter->plist.node_list);
+	}
+
+tail:
+	list_splice_tail_init(&src->prio_list, &dst->prio_list);
+	list_splice_tail_init(&src->node_list, &dst->node_list);
+}

--


  parent reply	other threads:[~2007-10-23 12:09 UTC|newest]

Thread overview: 12+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2007-10-23 12:03 [RFC/PATCH 0/5] rt: workqueue PI support -v2 Peter Zijlstra
2007-10-23 12:03 ` [RFC/PATCH 1/5] rt: rename rt_mutex_setprio to task_setprio Peter Zijlstra
2007-10-23 12:03 ` [RFC/PATCH 2/5] rt: list_splice2 Peter Zijlstra
2007-10-23 14:08   ` Steven Rostedt
2007-10-23 12:04 ` Peter Zijlstra [this message]
2007-10-23 15:10   ` [RFC/PATCH 3/5] rt: plist_head_splice Steven Rostedt
2007-10-23 16:26     ` Peter Zijlstra
2007-10-23 17:45     ` Peter Zijlstra
2007-10-23 12:04 ` [RFC/PATCH 4/5] rt: PI-workqueue support Peter Zijlstra
2007-10-23 12:04 ` [RFC/PATCH 5/5] rt: PI-workqueue: fix barriers Peter Zijlstra
2007-10-23 19:22 ` [RFC/PATCH 6/5] rt: PI-workqueue: wait_on_work() fixup Peter Zijlstra
2007-10-23 19:22 ` [RFC/PATCH 7/5] rt: PI-workqueue: propagate prio for delayed work Peter Zijlstra

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20071023120745.122724000@chello.nl \
    --to=a.p.zijlstra@chello.nl \
    --cc=dwalker@mvista.com \
    --cc=ghaskins@novell.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=mingo@elte.hu \
    --cc=oleg@tv-sign.ru \
    --cc=rostedt@goodmis.org \
    --cc=tglx@linutronix.de \
    --subject='Re: [RFC/PATCH 3/5] rt: plist_head_splice' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).