| Message ID | 20201002154420.292134-2-imbrenda@linux.ibm.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | Rewrite the allocators | expand |
On Fri, Oct 02, 2020 at 05:44:14PM +0200, Claudio Imbrenda wrote: > Add simple double linked lists. > > Apart from the struct itself, there are functions to add and remove > items, and check for emptyness. > > Signed-off-by: Claudio Imbrenda <imbrenda@linux.ibm.com> > --- > lib/list.h | 53 +++++++++++++++++++++++++++++++++++++++++++++++++++++ > 1 file changed, 53 insertions(+) > create mode 100644 lib/list.h > > diff --git a/lib/list.h b/lib/list.h > new file mode 100644 > index 0000000..702a78c > --- /dev/null > +++ b/lib/list.h > @@ -0,0 +1,53 @@ > +#ifndef LIST_H > +#define LIST_H > + > +#include <stdbool.h> > + > +/* > + * Simple double linked list. The pointer to the list is a list item itself, > + * like in the kernel implementation. > + */ > +struct linked_list { > + struct linked_list *prev; > + struct linked_list *next; > +}; > + > +/* > + * An empty list is a list item whose prev and next both point to itself. > + * Returns true if the list is empty. > + */ > +static inline bool is_list_empty(struct linked_list *p) I'd prefer the 'is' to be dropped or to come after 'list' in the name. Or, why not just use all the same names as the kernel, including call the structure list_head? > +{ > + return !p->next || !p->prev || p == p->next || p == p->prev; The '||'s can't be right and I'm not sure what you want to do about the NULLs. I think forbidding them is probably best, meaning this function should be { assert(p && p->prev && p->next); return p->prev == p && p->next == p; } But since p can't be NULL, then we should always return true from this function anyway, as a list with a single entry ('p') isn't empty. The kernel's list_empty() call explicitly calls its parameter 'head', because it expects a list's head pointer, which is a pointer to a list_head that is not embedded in a structure. > +} > + > +/* > + * Remove the given element from the list, if the list is not already empty. > + * The removed element is returned. > + */ > +static inline struct linked_list *list_remove(struct linked_list *l) > +{ > + if (is_list_empty(l)) > + return NULL; This isn't necessary. Removing an entry from a list of one entry is still the entry. > + > + l->prev->next = l->next; > + l->next->prev = l->prev; > + l->prev = l->next = NULL; > + > + return l; > +} > + > +/* > + * Add the given element after the given list head. > + */ > +static inline void list_add(struct linked_list *head, struct linked_list *li) > +{ > + assert(li); > + assert(head); > + li->prev = head; > + li->next = head->next; > + head->next->prev = li; > + head->next = li; > +} > + > +#endif > -- > 2.26.2 > I think we should just copy the kernel's list_head much closer. Thanks, drew
On Fri, 2 Oct 2020 20:18:44 +0200 Andrew Jones <drjones@redhat.com> wrote: [...] > > I think we should just copy the kernel's list_head much closer. fair enough; I think I'll just throw away this patch and steal the kernel's implementation
On 02/10/20 17:44, Claudio Imbrenda wrote: > +#include <stdbool.h> > + > +/* > + * Simple double linked list. The pointer to the list is a list item itself, > + * like in the kernel implementation. More precisely, *circular* doubly-linked list. Just a minor note. :) Paolo
diff --git a/lib/list.h b/lib/list.h new file mode 100644 index 0000000..702a78c --- /dev/null +++ b/lib/list.h @@ -0,0 +1,53 @@ +#ifndef LIST_H +#define LIST_H + +#include <stdbool.h> + +/* + * Simple double linked list. The pointer to the list is a list item itself, + * like in the kernel implementation. + */ +struct linked_list { + struct linked_list *prev; + struct linked_list *next; +}; + +/* + * An empty list is a list item whose prev and next both point to itself. + * Returns true if the list is empty. + */ +static inline bool is_list_empty(struct linked_list *p) +{ + return !p->next || !p->prev || p == p->next || p == p->prev; +} + +/* + * Remove the given element from the list, if the list is not already empty. + * The removed element is returned. + */ +static inline struct linked_list *list_remove(struct linked_list *l) +{ + if (is_list_empty(l)) + return NULL; + + l->prev->next = l->next; + l->next->prev = l->prev; + l->prev = l->next = NULL; + + return l; +} + +/* + * Add the given element after the given list head. + */ +static inline void list_add(struct linked_list *head, struct linked_list *li) +{ + assert(li); + assert(head); + li->prev = head; + li->next = head->next; + head->next->prev = li; + head->next = li; +} + +#endif
Add simple double linked lists. Apart from the struct itself, there are functions to add and remove items, and check for emptyness. Signed-off-by: Claudio Imbrenda <imbrenda@linux.ibm.com> --- lib/list.h | 53 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 53 insertions(+) create mode 100644 lib/list.h