[PATCH 2/4] list.h: add list_cut_position()

[PATCH 2/4] list.h: add list_cut_position()

[Luis R. Rodriguez]

This adds list_cut_position() which lets you cut a list into
two lists given a pivot in the list.

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

diff --git a/include/linux/list.h b/include/linux/list.h
index 594f67c..2999b0f 100644
--- a/include/linux/list.h
+++ b/include/linux/list.h
@@ -214,6 +214,38 @@ static inline int list_is_singular(const struct list_head *head)
 	return !list_empty(head) && (head->next == head->prev);
 }
 
+static inline void __list_cut_position(struct list_head *list,
+		struct list_head *head, struct list_head *entry)
+{
+	struct list_head *new_first =
+		(entry->next != head) ? entry->next : head;
+	list->next = head->next;
+	list->next->prev = list;
+	list->prev = entry;
+	entry->next = list;
+	head->next = new_first;
+	new_first->prev = head;
+}
+
+/**
+ * list_cut_position - cut a list into two
+ * @list: a new list to add all removed entries
+ * @head: a list with entries
+ * @entry: an entry within head, could be the head itself
+ *	and if so we won't won't cut the list
+ */
+static inline void list_cut_position(struct list_head *list,
+		struct list_head *head, struct list_head *entry)
+{
+	BUG_ON(list_empty(head));
+	if (list_is_singular(head))
+		BUG_ON(head->next != entry && head != entry);
+	if (entry == head)
+		INIT_LIST_HEAD(list);
+	else
+		__list_cut_position(list, head, entry);
+}
+
 static inline void __list_splice(const struct list_head *list,
 				 struct list_head *head)
 {
-- 
1.5.6.rc2.15.g457bb.dirty

Re: [PATCH 2/4] list.h: add list_cut_position()

[Randy Dunlap]

On Mon, 4 Aug 2008 15:48:09 -0700 Luis R. Rodriguez wrote:

> This adds list_cut_position() which lets you cut a list into
> two lists given a pivot in the list.
> 
> Signed-off-by: Luis R. Rodriguez <lrodriguez@atheros.com>
> ---
>  include/linux/list.h |   32 ++++++++++++++++++++++++++++++++
>  1 files changed, 32 insertions(+), 0 deletions(-)
> 
> diff --git a/include/linux/list.h b/include/linux/list.h
> index 594f67c..2999b0f 100644
> --- a/include/linux/list.h
> +++ b/include/linux/list.h
> @@ -214,6 +214,38 @@ static inline int list_is_singular(const struct list_head *head)
>  	return !list_empty(head) && (head->next == head->prev);
>  }
>  
> +static inline void __list_cut_position(struct list_head *list,
> +		struct list_head *head, struct list_head *entry)
> +{
> +	struct list_head *new_first =
> +		(entry->next != head) ? entry->next : head;
> +	list->next = head->next;
> +	list->next->prev = list;
> +	list->prev = entry;
> +	entry->next = list;
> +	head->next = new_first;
> +	new_first->prev = head;
> +}
> +
> +/**
> + * list_cut_position - cut a list into two
> + * @list: a new list to add all removed entries
> + * @head: a list with entries
> + * @entry: an entry within head, could be the head itself
> + *	and if so we won't won't cut the list

drop one "won't"


> + */
> +static inline void list_cut_position(struct list_head *list,
> +		struct list_head *head, struct list_head *entry)
> +{
> +	BUG_ON(list_empty(head));
> +	if (list_is_singular(head))
> +		BUG_ON(head->next != entry && head != entry);
> +	if (entry == head)
> +		INIT_LIST_HEAD(list);
> +	else
> +		__list_cut_position(list, head, entry);
> +}
> +
>  static inline void __list_splice(const struct list_head *list,
>  				 struct list_head *head)
>  {


---
~Randy
Linux Plumbers Conference, 17-19 September 2008, Portland, Oregon USA
http://linuxplumbersconf.org/

Re: [PATCH 2/4] list.h: add list_cut_position()

[Luis R. Rodriguez]

On Mon, Aug 04, 2008 at 04:00:11PM -0700, Randy Dunlap wrote:
> On Mon, 4 Aug 2008 15:48:09 -0700 Luis R. Rodriguez wrote:
> 
> > This adds list_cut_position() which lets you cut a list into
> > two lists given a pivot in the list.
> >
> > Signed-off-by: Luis R. Rodriguez <lrodriguez@atheros.com>
> > ---
> >  include/linux/list.h |   32 ++++++++++++++++++++++++++++++++
> >  1 files changed, 32 insertions(+), 0 deletions(-)
> >
> > diff --git a/include/linux/list.h b/include/linux/list.h
> > index 594f67c..2999b0f 100644
> > --- a/include/linux/list.h
> > +++ b/include/linux/list.h
> > @@ -214,6 +214,38 @@ static inline int list_is_singular(const struct list_head *head)
> >       return !list_empty(head) && (head->next == head->prev);
> >  }
> >
> > +static inline void __list_cut_position(struct list_head *list,
> > +             struct list_head *head, struct list_head *entry)
> > +{
> > +     struct list_head *new_first =
> > +             (entry->next != head) ? entry->next : head;
> > +     list->next = head->next;
> > +     list->next->prev = list;
> > +     list->prev = entry;
> > +     entry->next = list;
> > +     head->next = new_first;
> > +     new_first->prev = head;
> > +}
> > +
> > +/**
> > + * list_cut_position - cut a list into two
> > + * @list: a new list to add all removed entries
> > + * @head: a list with entries
> > + * @entry: an entry within head, could be the head itself
> > + *   and if so we won't won't cut the list
> 
> drop one "won't"

Thanks.

---
 include/linux/list.h |   32 ++++++++++++++++++++++++++++++++
 1 files changed, 32 insertions(+), 0 deletions(-)

diff --git a/include/linux/list.h b/include/linux/list.h
index 594f67c..2999b0f 100644
--- a/include/linux/list.h
+++ b/include/linux/list.h
@@ -214,6 +214,38 @@ static inline int list_is_singular(const struct list_head *head)
 	return !list_empty(head) && (head->next == head->prev);
 }
 
+static inline void __list_cut_position(struct list_head *list,
+		struct list_head *head, struct list_head *entry)
+{
+	struct list_head *new_first =
+		(entry->next != head) ? entry->next : head;
+	list->next = head->next;
+	list->next->prev = list;
+	list->prev = entry;
+	entry->next = list;
+	head->next = new_first;
+	new_first->prev = head;
+}
+
+/**
+ * list_cut_position - cut a list into two
+ * @list: a new list to add all removed entries
+ * @head: a list with entries
+ * @entry: an entry within head, could be the head itself
+ *	and if so we won't cut the list
+ */
+static inline void list_cut_position(struct list_head *list,
+		struct list_head *head, struct list_head *entry)
+{
+	BUG_ON(list_empty(head));
+	if (list_is_singular(head))
+		BUG_ON(head->next != entry && head != entry);
+	if (entry == head)
+		INIT_LIST_HEAD(list);
+	else
+		__list_cut_position(list, head, entry);
+}
+
 static inline void __list_splice(const struct list_head *list,
 				 struct list_head *head)
 {
-- 
1.5.6.rc2.15.g457bb.dirty

Re: [PATCH 2/4] list.h: add list_cut_position()

[Jochen Voß]

Hi,

2008/8/5 Luis R. Rodriguez <lrodriguez@atheros.com>:
> +static inline void __list_cut_position(struct list_head *list,
> +               struct list_head *head, struct list_head *entry)
> +{
> +       struct list_head *new_first =
> +               (entry->next != head) ? entry->next : head;

Isn't this just an over-complicated way of writing "new_first = entry->next"?

> +       list->next = head->next;
> +       list->next->prev = list;
> +       list->prev = entry;
> +       entry->next = list;
> +       head->next = new_first;
> +       new_first->prev = head;
> +}
> +
> +/**
> + * list_cut_position - cut a list into two
> + * @list: a new list to add all removed entries
> + * @head: a list with entries
> + * @entry: an entry within head, could be the head itself
> + *     and if so we won't cut the list
> + */

I think it would be helpful if the comment explained what the function
actually does, i.e. that it moves the inital part of 'head' (up to and
including 'entry' from 'head' to 'list'.

> +static inline void list_cut_position(struct list_head *list,
> +               struct list_head *head, struct list_head *entry)
> +{
> +       BUG_ON(list_empty(head));
> +       if (list_is_singular(head))
> +               BUG_ON(head->next != entry && head != entry);

No other list function in "list.h" has BUG_ONs.  Why this one?

> +       if (entry == head)
> +               INIT_LIST_HEAD(list);

If there was data in 'list' before the call, it will be lost now.  Is
this intended behaviour?

> +       else
> +               __list_cut_position(list, head, entry);
> +}
> +

I hope this helps,
Jochen
-- 
http://seehuhn.de/

Re: [PATCH 2/4] list.h: add list_cut_position()

[Luis R. Rodriguez]

On Tue, Aug 05, 2008 at 01:52:22AM -0700, Jochen Vo=DF wrote:
> Hi,
>=20
> 2008/8/5 Luis R. Rodriguez <lrodriguez@atheros.com>:
> > +static inline void __list_cut_position(struct list_head *list,
> > +               struct list_head *head, struct list_head *entry)
> > +{
> > +       struct list_head *new_first =3D
> > +               (entry->next !=3D head) ? entry->next : head;
>=20
> Isn't this just an over-complicated way of writing "new_first =3D ent=
ry->next"?

Sorry, yes.

> > +       list->next =3D head->next;
> > +       list->next->prev =3D list;
> > +       list->prev =3D entry;
> > +       entry->next =3D list;
> > +       head->next =3D new_first;
> > +       new_first->prev =3D head;
> > +}
> > +
> > +/**
> > + * list_cut_position - cut a list into two
> > + * @list: a new list to add all removed entries
> > + * @head: a list with entries
> > + * @entry: an entry within head, could be the head itself
> > + *     and if so we won't cut the list
> > + */
>=20
> I think it would be helpful if the comment explained what the functio=
n
> actually does, i.e. that it moves the inital part of 'head' (up to an=
d
> including 'entry' from 'head' to 'list'.

Will do.

> > +static inline void list_cut_position(struct list_head *list,
> > +               struct list_head *head, struct list_head *entry)
> > +{
> > +       BUG_ON(list_empty(head));
> > +       if (list_is_singular(head))
> > +               BUG_ON(head->next !=3D entry && head !=3D entry);
>=20
> No other list function in "list.h" has BUG_ONs.  Why this one?

Alright, I'll just make some small note on the documentation and exit e=
arly
on these.

> > +       if (entry =3D=3D head)
> > +               INIT_LIST_HEAD(list);
>=20
> If there was data in 'list' before the call, it will be lost now.  Is
> this intended behaviour?

Yes, the user of this call should not care if we wipe @list for them as
it is just a reference. This lets you, for example, use @list on
list_cut_position() it in a loop. I'll extend the documentation to
clarify this.

> > +       else
> > +               __list_cut_position(list, head, entry);
> > +}
> > +
>=20
> I hope this helps,

It certainly has, thanks for reviewing. How's this:

This adds list_cut_position() which lets you cut a list into
two lists given a pivot in the list.

Signed-off-by: Luis R. Rodriguez <lrodriguez@atheros.com>

diff --git a/include/linux/list.h b/include/linux/list.h
index 453916b..6c02a83 100644
--- a/include/linux/list.h
+++ b/include/linux/list.h
@@ -214,6 +214,46 @@ static inline int list_is_singular(const struct li=
st_head *head)
 	return !list_empty(head) && (head->next =3D=3D head->prev);
 }
=20
+static inline void __list_cut_position(struct list_head *list,
+		struct list_head *head, struct list_head *entry)
+{
+	struct list_head *new_first =3D entry->next;
+	list->next =3D head->next;
+	list->next->prev =3D list;
+	list->prev =3D entry;
+	entry->next =3D list;
+	head->next =3D new_first;
+	new_first->prev =3D head;
+}
+
+/**
+ * list_cut_position - cut a list into two
+ *
+ * This helper moves the initial part of @head, up to and
+ * including @entry, from @head to @list. You should
+ * pass on @entry an element you know is on @head. @list
+ * should be an empty list or a list you do not care about
+ * losing its data.
+ *
+ * @list: a new list to add all removed entries
+ * @head: a list with entries
+ * @entry: an entry within head, could be the head itself
+ *	and if so we won't cut the list
+ */
+static inline void list_cut_position(struct list_head *list,
+		struct list_head *head, struct list_head *entry)
+{
+	if (list_empty(head))
+		return;
+	if (list_is_singular(head) &&
+		(head->next !=3D entry && head !=3D entry))
+		return;
+	if (entry =3D=3D head)
+		INIT_LIST_HEAD(list);
+	else
+		__list_cut_position(list, head, entry);
+}
+
 static inline void __list_splice(const struct list_head *list,
 				 struct list_head *head)
 {
--
To unsubscribe from this list: send the line "unsubscribe linux-wireles=
s" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH 2/4] list.h: add list_cut_position()

[Randy Dunlap]

> This adds list_cut_position() which lets you cut a list into
> two lists given a pivot in the list.
> 
> Signed-off-by: Luis R. Rodriguez <lrodriguez@atheros.com>
> 
> diff --git a/include/linux/list.h b/include/linux/list.h
> index 453916b..6c02a83 100644
> --- a/include/linux/list.h
> +++ b/include/linux/list.h
> @@ -214,6 +214,46 @@ static inline int list_is_singular(const
> struct list_head *head)
>  	return !list_empty(head) && (head->next == head->prev);
>  }
>  
> +static inline void __list_cut_position(struct list_head *list,
> +		struct list_head *head, struct list_head *entry)
> +{
> +	struct list_head *new_first = entry->next;
> +	list->next = head->next;
> +	list->next->prev = list;
> +	list->prev = entry;
> +	entry->next = list;
> +	head->next = new_first;
> +	new_first->prev = head;
> +}
> +
> +/**
> + * list_cut_position - cut a list into two
> + *
> + * This helper moves the initial part of @head, up to and
> + * including @entry, from @head to @list. You should
> + * pass on @entry an element you know is on @head. @list
> + * should be an empty list or a list you do not care about
> + * losing its data.
> + *
> + * @list: a new list to add all removed entries
> + * @head: a list with entries
> + * @entry: an entry within head, could be the head itself
> + *	and if so we won't cut the list
> + */

For kernel-doc notation, the parameters need to follow the function name+short description.
After that, a longer description can be added.  I.e., please move the parameters up to
above the longer description...

> +static inline void list_cut_position(struct list_head *list,
> +		struct list_head *head, struct list_head *entry)
> +{
> +	if (list_empty(head))
> +		return;
> +	if (list_is_singular(head) &&
> +		(head->next != entry && head != entry))
> +		return;
> +	if (entry == head)
> +		INIT_LIST_HEAD(list);
> +	else
> +		__list_cut_position(list, head, entry);
> +}
> +
>  static inline void __list_splice(const struct list_head *list,
>  				 struct list_head *head)
>  {

Re: [PATCH 2/4] list.h: add list_cut_position()

[Luis R. Rodriguez]

On Wed, Aug 06, 2008 at 11:45:20AM -0700, Luis Rodriguez wrote:
> 
> OK here's the new one.
> --
> 
> This adds list_cut_position() which lets you cut a list into
> two lists given a pivot in the list.
> 
> Signed-off-by: Luis R. Rodriguez <lrodriguez@atheros.com>

Here it is again but this time one which applies cleanly ontop of the
list_cut_tail() patch I just reposted.

--
list.h: add list_cut_position()

This adds list_cut_position() which lets you cut a list into
two lists given a pivot in the list.

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

diff --git a/include/linux/list.h b/include/linux/list.h
index 61034a6..78e5f1c 100644
--- a/include/linux/list.h
+++ b/include/linux/list.h
@@ -214,6 +214,46 @@ static inline int list_is_singular(const struct list_head *head)
 	return !list_empty(head) && (head->next == head->prev);
 }
 
+static inline void __list_cut_position(struct list_head *list,
+		struct list_head *head, struct list_head *entry)
+{
+	struct list_head *new_first = entry->next;
+	list->next = head->next;
+	list->next->prev = list;
+	list->prev = entry;
+	entry->next = list;
+	head->next = new_first;
+	new_first->prev = head;
+}
+
+/**
+ * list_cut_position - cut a list into two
+ * @list: a new list to add all removed entries
+ * @head: a list with entries
+ * @entry: an entry within head, could be the head itself
+ *	and if so we won't cut the list
+ *
+ * This helper moves the initial part of @head, up to and
+ * including @entry, from @head to @list. You should
+ * pass on @entry an element you know is on @head. @list
+ * should be an empty list or a list you do not care about
+ * losing its data.
+ *
+ */
+static inline void list_cut_position(struct list_head *list,
+		struct list_head *head, struct list_head *entry)
+{
+	if (list_empty(head))
+		return;
+	if (list_is_singular(head) &&
+		(head->next != entry && head != entry))
+		return;
+	if (entry == head)
+		INIT_LIST_HEAD(list);
+	else
+		__list_cut_position(list, head, entry);
+}
+
 static inline void __list_splice(const struct list_head *list,
 				 struct list_head *prev,
 				 struct list_head *next)
-- 
1.5.6.rc2.15.g457bb.dirty

Re: [PATCH 2/4] list.h: add list_cut_position()

[Luis R. Rodriguez]

On Wed, Aug 06, 2008 at 01:28:54PM -0700, Luis Rodriguez wrote:
> On Wed, Aug 06, 2008 at 11:45:20AM -0700, Luis Rodriguez wrote:
> >
> > OK here's the new one.
> > --
> >
> > This adds list_cut_position() which lets you cut a list into
> > two lists given a pivot in the list.
> >
> > Signed-off-by: Luis R. Rodriguez <lrodriguez@atheros.com>
> 
> Here it is again but this time one which applies cleanly ontop of the
> list_cut_tail() patch I just reposted.

I meant on top of the list_splice_tail() of course :)

  Luis

[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

[PATCH 2/4] list.h: add list_cut_position()

[Luis R. Rodriguez]

This adds list_cut_position() which lets you cut a list into
two lists given a pivot in the list.

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

diff --git a/include/linux/list.h b/include/linux/list.h
index 594f67c..2999b0f 100644
--- a/include/linux/list.h
+++ b/include/linux/list.h
@@ -214,6 +214,38 @@ static inline int list_is_singular(const struct list_head *head)
 	return !list_empty(head) && (head->next == head->prev);
 }
 
+static inline void __list_cut_position(struct list_head *list,
+		struct list_head *head, struct list_head *entry)
+{
+	struct list_head *new_first =
+		(entry->next != head) ? entry->next : head;
+	list->next = head->next;
+	list->next->prev = list;
+	list->prev = entry;
+	entry->next = list;
+	head->next = new_first;
+	new_first->prev = head;
+}
+
+/**
+ * list_cut_position - cut a list into two
+ * @list: a new list to add all removed entries
+ * @head: a list with entries
+ * @entry: an entry within head, could be the head itself
+ *	and if so we won't won't cut the list
+ */
+static inline void list_cut_position(struct list_head *list,
+		struct list_head *head, struct list_head *entry)
+{
+	BUG_ON(list_empty(head));
+	if (list_is_singular(head))
+		BUG_ON(head->next != entry && head != entry);
+	if (entry == head)
+		INIT_LIST_HEAD(list);
+	else
+		__list_cut_position(list, head, entry);
+}
+
 static inline void __list_splice(const struct list_head *list,
 				 struct list_head *head)
 {
-- 
1.5.6.rc2.15.g457bb.dirty