On Tue, Jul 12, 2022 at 12:07:52PM -0700, Dan Williams wrote: > Given that decoder instance order is fundamental to the DPA translation > sequence for endpoint decoders, enforce that cxl_decoder_for_each() returns > decoders in instance order. Otherwise, they show up in readddir() order > which is not predictable. > > Add a list_add_sorted() to generically handle inserting into a sorted list. > > Signed-off-by: Dan Williams <[email protected]> > --- > cxl/lib/libcxl.c | 8 ++++++- > util/list.h | 61 > ++++++++++++++++++++++++++++++++++++++++++++++++++++++ > 2 files changed, 68 insertions(+), 1 deletion(-) > > diff --git a/cxl/lib/libcxl.c b/cxl/lib/libcxl.c > index f36edcfc735a..e4c5d3819e88 100644 > --- a/cxl/lib/libcxl.c > +++ b/cxl/lib/libcxl.c > @@ -19,6 +19,7 @@ > #include <ccan/short_types/short_types.h> > > #include <util/log.h> > +#include <util/list.h> > #include <util/size.h> > #include <util/sysfs.h> > #include <util/bitmap.h> > @@ -908,6 +909,11 @@ cxl_endpoint_get_memdev(struct cxl_endpoint *endpoint) > return NULL; > } > > +static int decoder_id_cmp(struct cxl_decoder *d1, struct cxl_decoder *d2) > +{ > + return d1->id - d2->id; > +} > + > static void *add_cxl_decoder(void *parent, int id, const char > *cxldecoder_base) > { > const char *devname = devpath_to_devname(cxldecoder_base); > @@ -1049,7 +1055,7 @@ static void *add_cxl_decoder(void *parent, int id, > const char *cxldecoder_base) > return decoder_dup; > } > > - list_add(&port->decoders, &decoder->list); > + list_add_sorted(&port->decoders, decoder, list, decoder_id_cmp); > > free(path); > return decoder; > diff --git a/util/list.h b/util/list.h > index 1ea9c59b9f0c..c6584e3ec725 100644 > --- a/util/list.h > +++ b/util/list.h > @@ -37,4 +37,65 @@ static inline void list_add_after_(struct list_head *h, > (void)list_debug(h, abortstr); > } > > +/** > + * list_add_before - add an entry before the given node in the linked list. > + * @h: the list_head to add the node to > + * @l: the list_node before which to add to > + * @n: the list_node to add to the list. > + * > + * The list_node does not need to be initialized; it will be overwritten. > + * Example: > + * struct child *child = malloc(sizeof(*child)); > + * > + * child->name = "geoffrey"; > + * list_add_before(&parent->children, &child1->list, &child->list); > + * parent->num_children++; > + */ > +#define list_add_before(h, l, n) list_add_before_(h, l, n, LIST_LOC) > +static inline void list_add_before_(struct list_head *h, struct list_node *l, > + struct list_node *n, const char *abortstr)
I see a list_add_before() in the latest ccan list code.[1] Should we just use that? The implementation is a bit different. [1] https://ccodearchive.net/info/list.html > +{ > + if (l->prev == &h->n) { > + /* l is the first element, this becomes a list_add */ > + list_add(h, n); > + return; > + } > + > + n->next = l; > + n->prev = l->prev; > + l->prev->next = n; > + l->prev = n; Did you mean to add list_debug() here? Ira > +} > + > +#define list_add_sorted(head, n, node, cmp) > \ > + do { \ > + struct list_head *__head = (head); \ > + typeof(n) __iter, __next; \ > + typeof(n) __new = (n); \ > + > \ > + if (list_empty(__head)) { \ > + list_add(__head, &__new->node); \ > + break; \ > + } \ > + > \ > + list_for_each (__head, __iter, node) { \ > + if (cmp(__new, __iter) < 0) { \ > + list_add_before(__head, &__iter->node, \ > + &__new->node); \ > + break; \ > + } \ > + __next = list_next(__head, __iter, node); \ > + if (!__next) { \ > + list_add_after(__head, &__iter->node, \ > + &__new->node); \ > + break; \ > + } \ > + if (cmp(__new, __next) < 0) { \ > + list_add_before(__head, &__next->node, \ > + &__new->node); \ > + break; \ > + } \ > + } \ > + } while (0) > + > #endif /* _NDCTL_LIST_H_ */ > >
