[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-DlyHzToyqoxBDgjK7y7TUQ@public.gmane.org>
> > ---
> >  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

--
To unsubscribe from this list: send the line "unsubscribe linux-wireless" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

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ß wrote:
> 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"?

Sorry, yes.

> > +       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'.

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 != entry && head != entry);
> 
> 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 early
on these.

> > +       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?

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);
> > +}
> > +
> 
> 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 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
+ */
+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()

[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:35:54AM -0700, Randy Dunlap 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>
> >
> > 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...

Bleh, sorry, we need to fix some more kdoc in mac80211 too then.

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>

diff --git a/include/linux/list.h b/include/linux/list.h
index 453916b..3b0ac8c 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 *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-DlyHzToyqoxBDgjK7y7TUQ@public.gmane.org>
> 
> 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
--
To unsubscribe from this list: send the line "unsubscribe linux-wireless" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html