[PATCH 1/4] list.h: Add list_splice_tail() and list_splice_tail_init()

[PATCH 1/4] list.h: Add list_splice_tail() and list_splice_tail_init()

[Luis R. Rodriguez]

If you are using linked lists for queues list_splice() will not do what
you would expect even if you use the elements passed reversed. We need
to handle these differently. We add list_splice_tail() and
list_splice_tail_init()

Signed-off-by: Luis R. Rodriguez <lrodriguez@atheros.com>
---
 include/linux/list.h |   45 ++++++++++++++++++++++++++++++++++++++++++++-
 1 files changed, 44 insertions(+), 1 deletions(-)

diff --git a/include/linux/list.h b/include/linux/list.h
index 453916b..594f67c 100644
--- a/include/linux/list.h
+++ b/include/linux/list.h
@@ -229,7 +229,7 @@ static inline void __list_splice(const struct list_head *list,
 }
 
 /**
- * list_splice - join two lists
+ * list_splice - join two lists, this is designed for stacks
  * @list: the new list to add.
  * @head: the place to add it in the first list.
  */
@@ -256,6 +256,49 @@ static inline void list_splice_init(struct list_head *list,
 	}
 }
 
+static inline void __list_splice_tail(const struct list_head *list,
+				 struct list_head *head)
+{
+	struct list_head *first = list->next;
+	struct list_head *last = list->prev;
+	struct list_head *current_tail = head->prev;
+
+	current_tail->next = first;
+	last->next = head;
+	head->prev = last;
+	first->prev = current_tail;
+}
+
+/**
+ * list_splice_tail - join two lists, each list being a queue
+ * @list: the new list to add.
+ * @head: the place to add it in the first list.
+ */
+static inline void list_splice_tail(const struct list_head *list,
+				struct list_head *head)
+{
+	if (!list_empty(list))
+		__list_splice_tail(list, head);
+}
+
+/**
+ * list_splice_tail_init - join two lists, each list being a queue, and
+ * 	reinitialise the emptied list.
+ * @list: the new list to add.
+ * @head: the place to add it in the first list.
+ *
+ * The list at @list is reinitialised
+ */
+static inline void list_splice_tail_init(struct list_head *list,
+				    struct list_head *head)
+{
+	if (!list_empty(list)) {
+		__list_splice_tail(list, head);
+		INIT_LIST_HEAD(list);
+	}
+}
+
+
 /**
  * list_entry - get the struct for this entry
  * @ptr:	the &struct list_head pointer.
-- 
1.5.6.rc2.15.g457bb.dirty

Re: [PATCH 1/4] list.h: Add list_splice_tail() and list_splice_tail_init()

[Peter Zijlstra]

On Mon, 2008-08-04 at 15:48 -0700, Luis R. Rodriguez wrote:
> If you are using linked lists for queues list_splice() will not do what
> you would expect even if you use the elements passed reversed. We need
> to handle these differently. We add list_splice_tail() and
> list_splice_tail_init()

In the -rt tree we have this:

---
    rt: list_splice2
    
    Introduce list_splice2{,_tail}() which will splice a sub-list denoted
    by two list items instead of the full list.
    
    Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>

diff --git a/drivers/dma/ioat_dma.c b/drivers/dma/ioat_dma.c
index 318e8a2..dace60c 100644
--- a/drivers/dma/ioat_dma.c
+++ b/drivers/dma/ioat_dma.c
@@ -283,7 +283,7 @@ static dma_cookie_t ioat1_tx_submit(struct dma_async_tx_descriptor *tx)
 	/* write address into NextDescriptor field of last desc in chain */
 	to_ioat_desc(ioat_chan->used_desc.prev)->hw->next =
 							first->async_tx.phys;
-	__list_splice(&new_chain, ioat_chan->used_desc.prev);
+	list_splice_tail(&new_chain, &ioat_chan->used_desc);
 
 	ioat_chan->dmacount += desc_count;
 	ioat_chan->pending += desc_count;
diff --git a/drivers/usb/host/ehci-q.c b/drivers/usb/host/ehci-q.c
index b85b541..3c541d8 100644
--- a/drivers/usb/host/ehci-q.c
+++ b/drivers/usb/host/ehci-q.c
@@ -932,7 +932,7 @@ static struct ehci_qh *qh_append_tds (
 
 			list_del (&qtd->qtd_list);
 			list_add (&dummy->qtd_list, qtd_list);
-			__list_splice (qtd_list, qh->qtd_list.prev);
+			list_splice_tail (qtd_list, &qh->qtd_list);
 
 			ehci_qtd_init(ehci, qtd, qtd->qtd_dma);
 			qh->dummy = qtd;
diff --git a/include/linux/list.h b/include/linux/list.h
index 08cf4f6..468e001 100644
--- a/include/linux/list.h
+++ b/include/linux/list.h
@@ -327,17 +327,17 @@ static inline int list_is_singular(const struct list_head *head)
 }
 
 static inline void __list_splice(const struct list_head *list,
-				 struct list_head *head)
+				 struct list_head *prev,
+				 struct list_head *next)
 {
 	struct list_head *first = list->next;
 	struct list_head *last = list->prev;
-	struct list_head *at = head->next;
 
-	first->prev = head;
-	head->next = first;
+	first->prev = prev;
+	prev->next = first;
 
-	last->next = at;
-	at->prev = last;
+	last->next = next;
+	next->prev = last;
 }
 
 /**
@@ -349,7 +349,13 @@ static inline void list_splice(const struct list_head *list,
 				struct list_head *head)
 {
 	if (!list_empty(list))
-		__list_splice(list, head);
+		__list_splice(list, head, head->next);
+}
+
+static inline void list_splice_tail(struct list_head *list, struct list_head *head)
+{
+	if (!list_empty(list))
+		__list_splice(list, head->prev, head);
 }
 
 /**
@@ -363,11 +369,55 @@ static inline void list_splice_init(struct list_head *list,
 				    struct list_head *head)
 {
 	if (!list_empty(list)) {
-		__list_splice(list, head);
+		__list_splice(list, head, head->next);
+		INIT_LIST_HEAD(list);
+	}
+}
+
+static inline void list_splice_tail_init(struct list_head *list,
+					 struct list_head *head)
+{
+	if (!list_empty(list)) {
+		__list_splice(list, head->prev, head);
 		INIT_LIST_HEAD(list);
 	}
 }
 
+static inline void __list_splice2(struct list_head *first,
+	       			struct list_head *last,
+				struct list_head *prev,
+				struct list_head *next)
+{
+	first->prev->next = last->next;
+	last->next->prev = first->prev;
+
+	first->prev = prev;
+	prev->next = first;
+
+	last->next = next;
+	next->prev = last;
+}
+
+/**
+ * list_splice2 - join [first, last] to head
+ * @first: list item
+ * @last: list item further on the same list
+ * @head: the place to add it on another list
+ */
+static inline void list_splice2(struct list_head *first,
+				struct list_head *last,
+				struct list_head *head)
+{
+	__list_splice2(first, last, head, head->next);
+}
+
+static inline void list_splice2_tail(struct list_head *first,
+				     struct list_head *last,
+				     struct list_head *head)
+{
+	__list_splice2(first, last, head->prev, head);
+}
+
 /**
  * list_splice_init_rcu - splice an RCU-protected list into an existing list.
  * @list:	the RCU-protected list to splice
diff --git a/lib/lock_list.c b/lib/lock_list.c
index d4bd571..586c01e 100644
--- a/lib/lock_list.c
+++ b/lib/lock_list.c
@@ -128,7 +128,7 @@ void lock_list_splice_init(struct lock_list_head *list,
 	lock = __lock_list_reverse(list);
 	if (!list_empty(&list->head)) {
 		spin_lock_nested(&head->lock, LOCK_LIST_NESTING_NEXT);
-		__list_splice(&list->head, &head->head);
+		__list_splice(&list->head, &head->head, head->head.next);
 		INIT_LIST_HEAD(&list->head);
 		spin_unlock(&head->lock);
 	}

Re: [PATCH 1/4] list.h: Add list_splice_tail() and list_splice_tail_init()

[Luis R. Rodriguez]

On Tue, Aug 05, 2008 at 02:03:15AM -0700, Peter Zijlstra wrote:
> On Mon, 2008-08-04 at 15:48 -0700, Luis R. Rodriguez wrote:
> > If you are using linked lists for queues list_splice() will not do what
> > you would expect even if you use the elements passed reversed. We need
> > to handle these differently. We add list_splice_tail() and
> > list_splice_tail_init()
> 
> In the -rt tree we have this:
> 
> ---
>     rt: list_splice2
> 
>     Introduce list_splice2{,_tail}() which will splice a sub-list denoted
>     by two list items instead of the full list.
> 
>     Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>

I like your version of list_splice_tail() and list_splice_tail_init()
more as you re-use __list_splice() and fix it for its use instad of
adding a new __list_splice_tail(). You also caught some users of
__list_splice() for tail purposes. Its a good thing both versions
are functionally equivalent :) otherwise one of us was doing something
wrong.

We just need to also clarify list_splice() is for stacks and not
queues, I can add that. You patch however fails with checkpatch and
forgot to add kdoc. I'll correct it.

Last, list_splice2() should go in a separate patch and could use just a
little bit more documentation as exactly what it does. Also the last
hunk doesn't apply as 2.6.27 doesn't have lib/lock_list.c yet. To get ath9k
in 2.6.27 we need list_splice_tail() and list_splice_tail_init(),
how's this for 2.6.27:

--
list.h: Add list_splice_tail() and list_splice_tail_init()

If you are using linked lists for queues list_splice() will not do what
you would expect even if you use the elements passed reversed. We need
to handle these differently. We add list_splice_tail() and
list_splice_tail_init().

Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Signed-off-by: Luis R. Rodriguez <lrodriguez@atheros.com>
---
 drivers/dma/ioat_dma.c    |    2 +-
 drivers/usb/host/ehci-q.c |    2 +-
 include/linux/list.h      |   39 ++++++++++++++++++++++++++++++---------
 3 files changed, 32 insertions(+), 11 deletions(-)

diff --git a/drivers/dma/ioat_dma.c b/drivers/dma/ioat_dma.c
index a52156e..bc8c6e3 100644
--- a/drivers/dma/ioat_dma.c
+++ b/drivers/dma/ioat_dma.c
@@ -551,7 +551,7 @@ static dma_cookie_t ioat1_tx_submit(struct dma_async_tx_descriptor *tx)
 	/* write address into NextDescriptor field of last desc in chain */
 	to_ioat_desc(ioat_chan->used_desc.prev)->hw->next =
 							first->async_tx.phys;
-	__list_splice(&new_chain, ioat_chan->used_desc.prev);
+	list_splice_tail(&new_chain, &ioat_chan->used_desc);
 
 	ioat_chan->dmacount += desc_count;
 	ioat_chan->pending += desc_count;
diff --git a/drivers/usb/host/ehci-q.c b/drivers/usb/host/ehci-q.c
index 2622b65..3712b92 100644
--- a/drivers/usb/host/ehci-q.c
+++ b/drivers/usb/host/ehci-q.c
@@ -932,7 +932,7 @@ static struct ehci_qh *qh_append_tds (
 
 			list_del (&qtd->qtd_list);
 			list_add (&dummy->qtd_list, qtd_list);
-			__list_splice (qtd_list, qh->qtd_list.prev);
+			list_splice_tail(qtd_list, &qh->qtd_list);
 
 			ehci_qtd_init(ehci, qtd, qtd->qtd_dma);
 			qh->dummy = qtd;
diff --git a/include/linux/list.h b/include/linux/list.h
index 453916b..61034a6 100644
--- a/include/linux/list.h
+++ b/include/linux/list.h
@@ -215,21 +215,21 @@ static inline int list_is_singular(const struct list_head *head)
 }
 
 static inline void __list_splice(const struct list_head *list,
-				 struct list_head *head)
+				 struct list_head *prev,
+				 struct list_head *next)
 {
 	struct list_head *first = list->next;
 	struct list_head *last = list->prev;
-	struct list_head *at = head->next;
 
-	first->prev = head;
-	head->next = first;
+	first->prev = prev;
+	prev->next = first;
 
-	last->next = at;
-	at->prev = last;
+	last->next = next;
+	next->prev = last;
 }
 
 /**
- * list_splice - join two lists
+ * list_splice - join two lists, this is designed for stacks
  * @list: the new list to add.
  * @head: the place to add it in the first list.
  */
@@ -237,7 +237,19 @@ static inline void list_splice(const struct list_head *list,
 				struct list_head *head)
 {
 	if (!list_empty(list))
-		__list_splice(list, head);
+		__list_splice(list, head, head->next);
+}
+
+/**
+ * list_splice_tail - join two lists, each list being a queue
+ * @list: the new list to add.
+ * @head: the place to add it in the first list.
+ */
+static inline void list_splice_tail(struct list_head *list,
+				struct list_head *head)
+{
+	if (!list_empty(list))
+		__list_splice(list, head->prev, head);
 }
 
 /**
@@ -251,7 +263,16 @@ static inline void list_splice_init(struct list_head *list,
 				    struct list_head *head)
 {
 	if (!list_empty(list)) {
-		__list_splice(list, head);
+		__list_splice(list, head, head->next);
+		INIT_LIST_HEAD(list);
+	}
+}
+
+static inline void list_splice_tail_init(struct list_head *list,
+					 struct list_head *head)
+{
+	if (!list_empty(list)) {
+		__list_splice(list, head->prev, head);
 		INIT_LIST_HEAD(list);
 	}
 }
-- 
1.5.6.rc2.15.g457bb.dirty

Re: [PATCH 1/4] list.h: Add list_splice_tail() and list_splice_tail_init()

[Luis R. Rodriguez]

On Wed, Aug 06, 2008 at 01:26:19PM -0700, Luis Rodriguez wrote:
> On Tue, Aug 05, 2008 at 02:03:15AM -0700, Peter Zijlstra wrote:
> > On Mon, 2008-08-04 at 15:48 -0700, Luis R. Rodriguez wrote:
> > > If you are using linked lists for queues list_splice() will not do what
> > > you would expect even if you use the elements passed reversed. We need
> > > to handle these differently. We add list_splice_tail() and
> > > list_splice_tail_init()
> >
> > In the -rt tree we have this:
> >
> > ---
> >     rt: list_splice2
> >
> >     Introduce list_splice2{,_tail}() which will splice a sub-list denoted
> >     by two list items instead of the full list.
> >
> >     Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
> 
> I like your version of list_splice_tail() and list_splice_tail_init()
> more as you re-use __list_splice() and fix it for its use instad of
> adding a new __list_splice_tail(). You also caught some users of
> __list_splice() for tail purposes. Its a good thing both versions
> are functionally equivalent :) otherwise one of us was doing something
> wrong.
> 
> We just need to also clarify list_splice() is for stacks and not
> queues, I can add that. You patch however fails with checkpatch and
> forgot to add kdoc. I'll correct it.
> 
> Last, list_splice2() should go in a separate patch and could use just a
> little bit more documentation as exactly what it does. Also the last
> hunk doesn't apply as 2.6.27 doesn't have lib/lock_list.c yet. To get ath9k
> in 2.6.27 we need list_splice_tail() and list_splice_tail_init(),
> how's this for 2.6.27:

Sorry, I forgot to add my kdoc for list_splice_tail_init(), here it is
with it added:
--
list.h: Add list_splice_tail() and list_splice_tail_init()

If you are using linked lists for queues list_splice() will not do what
you would expect even if you use the elements passed reversed. We need
to handle these differently. We add list_splice_tail() and
list_splice_tail_init().

Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Signed-off-by: Luis R. Rodriguez <lrodriguez@atheros.com>
---
 drivers/dma/ioat_dma.c    |    2 +-
 drivers/usb/host/ehci-q.c |    2 +-
 include/linux/list.h      |   47 ++++++++++++++++++++++++++++++++++++--------
 3 files changed, 40 insertions(+), 11 deletions(-)

diff --git a/drivers/dma/ioat_dma.c b/drivers/dma/ioat_dma.c
index a52156e..bc8c6e3 100644
--- a/drivers/dma/ioat_dma.c
+++ b/drivers/dma/ioat_dma.c
@@ -551,7 +551,7 @@ static dma_cookie_t ioat1_tx_submit(struct dma_async_tx_descriptor *tx)
 	/* write address into NextDescriptor field of last desc in chain */
 	to_ioat_desc(ioat_chan->used_desc.prev)->hw->next =
 							first->async_tx.phys;
-	__list_splice(&new_chain, ioat_chan->used_desc.prev);
+	list_splice_tail(&new_chain, &ioat_chan->used_desc);
 
 	ioat_chan->dmacount += desc_count;
 	ioat_chan->pending += desc_count;
diff --git a/drivers/usb/host/ehci-q.c b/drivers/usb/host/ehci-q.c
index 2622b65..3712b92 100644
--- a/drivers/usb/host/ehci-q.c
+++ b/drivers/usb/host/ehci-q.c
@@ -932,7 +932,7 @@ static struct ehci_qh *qh_append_tds (
 
 			list_del (&qtd->qtd_list);
 			list_add (&dummy->qtd_list, qtd_list);
-			__list_splice (qtd_list, qh->qtd_list.prev);
+			list_splice_tail(qtd_list, &qh->qtd_list);
 
 			ehci_qtd_init(ehci, qtd, qtd->qtd_dma);
 			qh->dummy = qtd;
diff --git a/include/linux/list.h b/include/linux/list.h
index 453916b..a886f27 100644
--- a/include/linux/list.h
+++ b/include/linux/list.h
@@ -215,21 +215,21 @@ static inline int list_is_singular(const struct list_head *head)
 }
 
 static inline void __list_splice(const struct list_head *list,
-				 struct list_head *head)
+				 struct list_head *prev,
+				 struct list_head *next)
 {
 	struct list_head *first = list->next;
 	struct list_head *last = list->prev;
-	struct list_head *at = head->next;
 
-	first->prev = head;
-	head->next = first;
+	first->prev = prev;
+	prev->next = first;
 
-	last->next = at;
-	at->prev = last;
+	last->next = next;
+	next->prev = last;
 }
 
 /**
- * list_splice - join two lists
+ * list_splice - join two lists, this is designed for stacks
  * @list: the new list to add.
  * @head: the place to add it in the first list.
  */
@@ -237,7 +237,19 @@ static inline void list_splice(const struct list_head *list,
 				struct list_head *head)
 {
 	if (!list_empty(list))
-		__list_splice(list, head);
+		__list_splice(list, head, head->next);
+}
+
+/**
+ * list_splice_tail - join two lists, each list being a queue
+ * @list: the new list to add.
+ * @head: the place to add it in the first list.
+ */
+static inline void list_splice_tail(struct list_head *list,
+				struct list_head *head)
+{
+	if (!list_empty(list))
+		__list_splice(list, head->prev, head);
 }
 
 /**
@@ -251,7 +263,24 @@ static inline void list_splice_init(struct list_head *list,
 				    struct list_head *head)
 {
 	if (!list_empty(list)) {
-		__list_splice(list, head);
+		__list_splice(list, head, head->next);
+		INIT_LIST_HEAD(list);
+	}
+}
+
+/**
+ * list_splice_tail_init - join two lists, each list being a queue, and
+ *     reinitialise the emptied list.
+ * @list: the new list to add.
+ * @head: the place to add it in the first list.
+ *
+ * The list at @list is reinitialised
+ */
+static inline void list_splice_tail_init(struct list_head *list,
+					 struct list_head *head)
+{
+	if (!list_empty(list)) {
+		__list_splice(list, head->prev, head);
 		INIT_LIST_HEAD(list);
 	}
 }
-- 
1.5.6.rc2.15.g457bb.dirty

[PATCH 0/4] Atheros IEEE 802.11n ath9k driver

[Luis R. Rodriguez]

This series of patches adds the ath9k driver which adds support
for all Atheors IEEE 802.11n chipsets along some new linked list
helpers.

More information about this driver is available at:

http://wireless.kernel.org/en/users/Drivers/ath9k

Our mailing list for this driver is:

https://lists.ath9k.org/mailman/listinfo/ath9k-devel

  Luis

[PATCH 1/4] list.h: Add list_splice_tail() and list_splice_tail_init()

[Luis R. Rodriguez]

If you are using linked lists for queues list_splice() will not do what
you would expect even if you use the elements passed reversed. We need
to handle these differently. We add list_splice_tail() and
list_splice_tail_init()

Signed-off-by: Luis R. Rodriguez <lrodriguez@atheros.com>
---
 include/linux/list.h |   45 ++++++++++++++++++++++++++++++++++++++++++++-
 1 files changed, 44 insertions(+), 1 deletions(-)

diff --git a/include/linux/list.h b/include/linux/list.h
index 453916b..594f67c 100644
--- a/include/linux/list.h
+++ b/include/linux/list.h
@@ -229,7 +229,7 @@ static inline void __list_splice(const struct list_head *list,
 }
 
 /**
- * list_splice - join two lists
+ * list_splice - join two lists, this is designed for stacks
  * @list: the new list to add.
  * @head: the place to add it in the first list.
  */
@@ -256,6 +256,49 @@ static inline void list_splice_init(struct list_head *list,
 	}
 }
 
+static inline void __list_splice_tail(const struct list_head *list,
+				 struct list_head *head)
+{
+	struct list_head *first = list->next;
+	struct list_head *last = list->prev;
+	struct list_head *current_tail = head->prev;
+
+	current_tail->next = first;
+	last->next = head;
+	head->prev = last;
+	first->prev = current_tail;
+}
+
+/**
+ * list_splice_tail - join two lists, each list being a queue
+ * @list: the new list to add.
+ * @head: the place to add it in the first list.
+ */
+static inline void list_splice_tail(const struct list_head *list,
+				struct list_head *head)
+{
+	if (!list_empty(list))
+		__list_splice_tail(list, head);
+}
+
+/**
+ * list_splice_tail_init - join two lists, each list being a queue, and
+ * 	reinitialise the emptied list.
+ * @list: the new list to add.
+ * @head: the place to add it in the first list.
+ *
+ * The list at @list is reinitialised
+ */
+static inline void list_splice_tail_init(struct list_head *list,
+				    struct list_head *head)
+{
+	if (!list_empty(list)) {
+		__list_splice_tail(list, head);
+		INIT_LIST_HEAD(list);
+	}
+}
+
+
 /**
  * list_entry - get the struct for this entry
  * @ptr:	the &struct list_head pointer.
-- 
1.5.6.rc2.15.g457bb.dirty