This patch adds new plist implementation, see
http://marc.theaimsgroup.com/?l=linux-kernel&m=111547290706136
Changes:
added plist_next_entry() helper (was plist_entry)
added plist_unhashed() helper, see PATCH 4/4
Signed-off-by: Oleg Nesterov <[email protected]>
--- V0.7.47-01/include/linux/plist.h~1_PLIST 2005-05-09 17:06:05.000000000 +0400
+++ V0.7.47-01/include/linux/plist.h 2005-05-09 20:11:26.000000000 +0400
@@ -0,0 +1,97 @@
+#ifndef _LINUX_PLIST_H_
+#define _LINUX_PLIST_H_
+
+#include <linux/list.h>
+
+struct pl_head {
+ struct list_head prio_list;
+ struct list_head node_list;
+};
+
+struct pl_node {
+ int prio;
+ struct pl_head plist;
+};
+
+#define PL_HEAD_INIT(head) \
+{ \
+ .prio_list = LIST_HEAD_INIT((head).prio_list), \
+ .node_list = LIST_HEAD_INIT((head).node_list), \
+}
+
+#define PL_NODE_INIT(node, __prio) \
+{ \
+ .prio = (__prio), \
+ .plist = PL_HEAD_INIT((node).plist), \
+}
+
+static inline void pl_head_init(struct pl_head *head)
+{
+ INIT_LIST_HEAD(&head->prio_list);
+ INIT_LIST_HEAD(&head->node_list);
+}
+
+static inline void pl_node_init(struct pl_node *node, int prio)
+{
+ node->prio = prio;
+ pl_head_init(&node->plist);
+}
+
+extern void plist_add(struct pl_node *node, struct pl_head *head);
+extern void plist_del(struct pl_node *node);
+
+#define plist_for_each(pos, head) \
+ list_for_each_entry(pos, &(head)->node_list, plist.node_list)
+
+#define plist_for_each_safe(pos, n, head) \
+ list_for_each_entry_safe(pos, n, &(head)->node_list, plist.node_list)
+
+#define plist_for_each_entry(pos, head, mem) \
+ list_for_each_entry(pos, &(head)->node_list, mem.plist.node_list)
+
+#define plist_for_each_entry_safe(pos, n, head, mem) \
+ list_for_each_entry_safe(pos, n, &(head)->node_list, mem.plist.node_list)
+
+static inline int plist_empty(const struct pl_head *head)
+{
+ return list_empty(&head->node_list);
+}
+
+static inline int plist_unhashed(const struct pl_node *node)
+{
+ return list_empty(&node->plist.node_list);
+}
+
+/* All functions below assume the pl_head is not empty. */
+
+#define plist_next_entry(head, type, member) \
+ container_of(plist_next(head), type, member)
+
+#define plist_prev_entry(head, type, member) \
+ container_of(plist_prev(head), type, member)
+
+#define __pl_head_node(head, list, dir) \
+ list_entry((head)->list.dir, struct pl_node, plist.list)
+
+static inline struct pl_node* plist_next(const struct pl_head *head)
+{
+ return __pl_head_node(head, node_list, next);
+}
+
+static inline struct pl_node* plist_prev(const struct pl_head *head)
+{
+ return __pl_head_node(head, node_list, prev);
+}
+
+static inline struct pl_node* plist_prio_next(const struct pl_head *head)
+{
+ return __pl_head_node(head, prio_list, next);
+}
+
+static inline struct pl_node* plist_prio_prev(const struct pl_head *head)
+{
+ return __pl_head_node(head, prio_list, prev);
+}
+
+#undef __pl_head_node
+#endif
--- V0.7.47-01/lib/plist.c~1_PLIST 2005-05-09 17:06:05.000000000 +0400
+++ V0.7.47-01/lib/plist.c 2005-05-09 19:55:31.000000000 +0400
@@ -0,0 +1,36 @@
+/*
+ * lib/plist.c - Priority List implementation.
+ */
+
+#include <linux/plist.h>
+
+void plist_add(struct pl_node *node, struct pl_head *head)
+{
+ struct pl_node *iter;
+
+ INIT_LIST_HEAD(&node->plist.prio_list);
+
+ list_for_each_entry(iter, &head->prio_list, plist.prio_list)
+ if (node->prio < iter->prio)
+ goto lt_prio;
+ else if (node->prio == iter->prio) {
+ iter = plist_prio_next(&iter->plist);
+ goto eq_prio;
+ }
+
+lt_prio:
+ list_add_tail(&node->plist.prio_list, &iter->plist.prio_list);
+eq_prio:
+ list_add_tail(&node->plist.node_list, &iter->plist.node_list);
+}
+
+void plist_del(struct pl_node *node)
+{
+ if (!list_empty(&node->plist.prio_list)) {
+ struct pl_node *next = plist_next(&node->plist);
+ list_move_tail(&next->plist.prio_list, &node->plist.prio_list);
+ list_del_init(&node->plist.prio_list);
+ }
+
+ list_del_init(&node->plist.node_list);
+}
--- V0.7.47-01/lib/Makefile~1_PLIST 2005-05-09 16:46:06.000000000 +0400
+++ V0.7.47-01/lib/Makefile 2005-05-09 17:12:48.000000000 +0400
@@ -15,6 +15,8 @@ CFLAGS_kobject.o += -DDEBUG
CFLAGS_kobject_uevent.o += -DDEBUG
endif
+obj-$(CONFIG_PREEMPT_RT) += plist.o
+
obj-$(CONFIG_RWSEM_GENERIC_SPINLOCK) += rwsem-spinlock.o
lib-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o
lib-$(CONFIG_GENERIC_FIND_NEXT_BIT) += find_next_bit.o
On Mon, 9 May 2005, Oleg Nesterov wrote:
> This patch adds new plist implementation, see
> http://marc.theaimsgroup.com/?l=linux-kernel&m=111547290706136
>
> Changes:
>
> added plist_next_entry() helper (was plist_entry)
>
> added plist_unhashed() helper, see PATCH 4/4
>
Naw , stick with Inaky's API .. Your stuff looks nothing like
list.h ..
Daniel
Daniel Walker wrote:
>
> On Mon, 9 May 2005, Oleg Nesterov wrote:
>
> > This patch adds new plist implementation, see
> > http://marc.theaimsgroup.com/?l=linux-kernel&m=111547290706136
> >
> > Changes:
> >
> > added plist_next_entry() helper (was plist_entry)
> >
> > added plist_unhashed() helper, see PATCH 4/4
> >
>
> Naw , stick with Inaky's API ..
This patch breaks Inaky's API anyway, plist_del() now has only one
argument, and I think this is good.
I don't mind doing s/plist_next_entry/plist_entry/ if you wish,
but I think this is consistent with plist_next/plist_prev helpers.
And original plist_empty() is confusing. When used on plist's head
it is ok, but it is wrong to use plist_empty(&plist_node).
> Your stuff looks nothing like list.h ..
Is it bad?
Yes, plist_empty/plist_unhashed mimics hlist_empty/hlist_unhashed.
Oleg.
Hi Oleg
>From: Oleg Nesterov
>+extern void plist_add(struct pl_node *node, struct pl_head *head);
>+extern void plist_del(struct pl_node *node);
At least I'd add return codes for this if the head's priority
changes (or in this case, because head's have no prio, if the
first node's prio change). Both function's logic should make
it easy to test and it'd save a lot of code in the caller.
-- Inaky
"Perez-Gonzalez, Inaky" wrote:
>
> >From: Oleg Nesterov
>
> >+extern void plist_add(struct pl_node *node, struct pl_head *head);
> >+extern void plist_del(struct pl_node *node);
>
> At least I'd add return codes for this if the head's priority=20
> changes (or in this case, because head's have no prio, if the=20
> first node's prio change).
I am not sure I understand you. Why should we track ->prio=20 changes?
plist should be generic, I think.
Original code:
unsigned plist_add (struct plist *pl, struct plist *plist)
{
__plist_add_sorted (plist, pl);
if (pl->prio < plist->prio) {
plist->prio = pl->prio;
return !0;
}
return 0;
}
This could be:
int plist_add_and_check_min_prio_changed(node, head)
{
plist_add(node, head);
return plist_next(head) == node;
}
Or plist_add() could be easily changed to return -1,0,+1 to indicate
min/max prio changed/unchanged.
But may be it is better to return 'iter' from plist_add(). This way
we can avoid scanning ->prio_list when we add the node with the same
->prio next time. I am not sure.
And please note that pl_head "has" prio:
plist_empty(head) ? INT_MAX // -1 ?
: plist_next(head)->prio
> Both function's logic should make it easy to test and it'd save
> a lot of code in the caller.
Currently these functions are used in void context only. I think
it is better to add return codes when callers need them.
What do you think?
Oleg.
>From: Oleg Nesterov
>"Perez-Gonzalez, Inaky" wrote:
>>
>> >From: Oleg Nesterov
>>
>> >+extern void plist_add(struct pl_node *node, struct pl_head *head);
>> >+extern void plist_del(struct pl_node *node);
>>
>> At least I'd add return codes for this if the head's priority=20
>> changes (or in this case, because head's have no prio, if the=20
>> first node's prio change).
>
>I am not sure I understand you. Why should we track ->prio=20 changes?
>plist should be generic, I think.
Errr....shut, that was my or your email program screwing
things up...that =20, I mean, that's MIME for line break.
>This could be:
> int plist_add_and_check_min_prio_changed(node, head)
> {
> plist_add(node, head);
> return plist_next(head) == node;
> }
>
>Or plist_add() could be easily changed to return -1,0,+1 to indicate
>min/max prio changed/unchanged.
The -1/0/+1 sounds pretty good.
>Currently these functions are used in void context only. I think
>it is better to add return codes when callers need them.
>
>What do you think?
I guess I am still very biased by my implementation, where returning
that was almost free because of how the functions where implemented
(which steamed from the fact that they had to always compute the
new priority to store it in the head).
So as you say, the best way is wrapping your primitives around. I'd
suggest a shorter postfix, something like _prio() or _chkprio().
Thanks,
-- Inaky
On Tue, 10 May 2005 11:39:45 PDT, "Perez-Gonzalez, Inaky" said:
> >> At least I'd add return codes for this if the head's priority=20
> >> changes (or in this case, because head's have no prio, if the=20
> >> first node's prio change).
> >
> >I am not sure I understand you. Why should we track ->prio=20 changes?
> >plist should be generic, I think.
>
> Errr....shut, that was my or your email program screwing
> things up...that =20, I mean, that's MIME for line break.
Actually, it's the MIME encoding for "blank". It's usually seen with trailing
blanks, so systems that trim trailing blanks won't molest the one you left on
the end of the line.....
>From: [email protected] [mailto:[email protected]]
>On Tue, 10 May 2005 11:39:45 PDT, "Perez-Gonzalez, Inaky" said:
>
>> >I am not sure I understand you. Why should we track ->prio=20
changes?
>> >plist should be generic, I think.
>>
>> Errr....shut, that was my or your email program screwing
>> things up...that =20, I mean, that's MIME for line break.
>
>Actually, it's the MIME encoding for "blank". It's usually seen with
trailing
>blanks, so systems that trim trailing blanks won't molest the one you
left on
>the end of the line.....
Tomatoe, tomato :)
Thanks,
-- Inaky
On Tue, 10 May 2005 11:39:45 PDT, "Perez-Gonzalez, Inaky" said:
> >From: Oleg Nesterov
> >"Perez-Gonzalez, Inaky" wrote:
> Errr....shut, that was my or your email program screwing
> things up...that =20, I mean, that's MIME for line break.
Dug a bit further...
There was a trailing blank in Inaky's note as it arrived here, but it was
traveling with a Content-Type-Encoding: 8bit. My guess is that some mail
software between vger and Oleg's inbox down-converted to 7bit. Either that
mailer failed to insert a 'Content-Type-Encoding: quoted-printable' header when
it applied the quoted-printable )changing a trailing blank to =20) when
down-converting, or Oleg's mail reader (apparently Mozilla?) failed to heed the
C-T-E and convert the =20 back to the trailing blank it should have been.
I was there when all this MIME stuff was designed, and we covered all the
failure modes of stupid designers of mail software that we could think of.
We never considered the sorts of whitespace screw-ups we actually see today -
I think there was a "No designer could be THAT daft" blind-spot....
On Tue, 2005-05-10 at 11:39, Perez-Gonzalez, Inaky wrote:
>
> I guess I am still very biased by my implementation, where returning
> that was almost free because of how the functions where implemented
> (which steamed from the fact that they had to always compute the
> new priority to store it in the head).
>
> So as you say, the best way is wrapping your primitives around. I'd
> suggest a shorter postfix, something like _prio() or _chkprio().
I still say re-implementation of plist is a waste .. Why re-make the
wheel when you have a perfectly good starting point .
Daniel
>From: Daniel Walker [mailto:[email protected]]
>>
>> So as you say, the best way is wrapping your primitives around. I'd
>> suggest a shorter postfix, something like _prio() or _chkprio().
>
>I still say re-implementation of plist is a waste .. Why re-make the
>wheel when you have a perfectly good starting point .
I don't know *shrug*
In this case, Oleg's wheel looks simpler than mine and does the
same thing, so why not use it? Simpler is beautiful.
I share the concern, though, of it being fully debugged and stuff,
but being simpler it should be easier to prove it correct.
-- Inaky
Daniel Walker wrote:
>
> I still say re-implementation of plist is a waste .. Why re-make the
> wheel when you have a perfectly good starting point .
Because it does not work? I think you have missed my first message on
this topic: http://marc.theaimsgroup.com/?l=linux-kernel&m=111536999732736
I had no intent to re-implement plists, it was you who told me:
>
> Make a patch .
Oleg.