Messages in this thread | | | Date | Fri, 06 May 2005 15:13:11 +0400 | From | Oleg Nesterov <> | Subject | Re: [PATCH] Priority Lists for the RT mutex |
| |
Oleg Nesterov wrote: > > Daniel Walker wrote: > > > > Description: > > This patch adds the priority list data structure from Inaky Perez-Gonzalez > > to the Preempt Real-Time mutex. > > > ... > > I can't understand how this can work.
And I think it is possible to simplify plist's design.
struct plist { int prio; struct list_head prio_list; struct list_head node_list; };
#define plist_for_each(pos, head) \ list_for_each_entry(pos, &(head)->node_list, node_list)
static inline void plist_add(struct plist *new, struct plist *head) { struct plist* pos;
INIT_LIST_HEAD(&new->prio_list);
list_for_each_entry(pos, &head->prio_list, prio_list) if (new->prio < pos->prio) goto lt_prio; else if (new->prio == pos->prio) { pos = list_entry(pos->prio_list.next, struct plist, prio_list); goto eq_prio; }
lt_prio: list_add_tail(&new->prio_list, &pos->prio_list); eq_prio: list_add_tail(&new->node_list, &pos->node_list); }
static inline void plist_del(struct plist *del) { if (!list_empty(&del->prio_list)) { struct plist *next = list_entry(del->node_list.next, struct plist, node_list); list_move_tail(&next->prio_list, &del->prio_list); list_del_init(&del->prio_list); }
list_del_init(&del->node_list); }
All nodes in prio list are chained via ->node_list, sorted in ascending ->prio/fifo order. Nodes which start different priority slice are chained via ->prio_list, ascending ->prio order.
Slightly tested, seems to work.
I think this would be even better:
struct plist_head { struct list_head prio_list; struct list_head node_list; }
struct plist { int prio; struct plist_head head; }
The plist_head's min/max prio can be found from plist_head.prio_list.next/prev.
What do you think?
Oleg. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |