merge-sort two plists together
Signed-off-by: Peter Zijlstra <[email protected]>
---
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);
+}
--
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[Index of Archives]
[Kernel Newbies]
[Netfilter]
[Bugtraq]
[Photo]
[Stuff]
[Gimp]
[Yosemite News]
[MIPS Linux]
[ARM Linux]
[Linux Security]
[Linux RAID]
[Video 4 Linux]
[Linux for the blind]
[Linux Resources]
