@@ -2,25 +2,39 @@
#ifndef LIST_H
#define LIST_H
+#include <stddef.h>
+
#include "list_types.h"
-/*
- * Copied from include/linux/...
- */
-
-#undef offsetof
-#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
+/* Are two types/vars the same type (ignoring qualifiers)? */
+#define __same_type(a, b) __builtin_types_compatible_p(typeof(a), typeof(b))
/**
* container_of - cast a member of a structure out to the containing structure
- * @ptr: the pointer to the member.
- * @type: the type of the container struct this is embedded in.
- * @member: the name of the member within the struct.
+ * @ptr: the pointer to the member.
+ * @type: the type of the container struct this is embedded in.
+ * @member: the name of the member within the struct.
*
*/
-#define container_of(ptr, type, member) ({ \
- const typeof( ((type *)0)->member ) *__mptr = (ptr); \
- (type *)( (char *)__mptr - offsetof(type,member) );})
+#define container_of(ptr, type, member) ({ \
+ void *__mptr = (void *)(ptr); \
+ _Static_assert(__same_type(*(ptr), ((type *)0)->member) || \
+ __same_type(*(ptr), void), \
+ "pointer type mismatch in container_of()"); \
+ ((type *)(__mptr - offsetof(type, member))); })
+
+#define LIST_POISON1 ((void *) 0x100)
+#define LIST_POISON2 ((void *) 0x122)
+
+/*
+ * Circular doubly linked list implementation.
+ *
+ * Some of the internal functions ("__xxx") are useful when
+ * manipulating whole lists rather than single entries, as
+ * sometimes we already know the next/prev entries and we can
+ * generate better code by using them directly rather than
+ * using the generic single-entry routines.
+ */
#define LIST_HEAD_INIT(name) { &(name), &(name) }
@@ -28,45 +42,16 @@
struct list_head name = LIST_HEAD_INIT(name)
/**
- * list_entry - get the struct for this entry
- * @ptr: the &struct list_head pointer.
- * @type: the type of the struct this is embedded in.
- * @member: the name of the list_head within the struct.
+ * INIT_LIST_HEAD - Initialize a list_head structure
+ * @list: list_head structure to be initialized.
+ *
+ * Initializes the list_head to point to itself. If it is a list header,
+ * the result is an empty list.
*/
-#define list_entry(ptr, type, member) \
- container_of(ptr, type, member)
-
-/**
- * list_for_each_entry - iterate over list of given type
- * @pos: the type * to use as a loop cursor.
- * @head: the head for your list.
- * @member: the name of the list_head within the struct.
- */
-#define list_for_each_entry(pos, head, member) \
- for (pos = list_entry((head)->next, typeof(*pos), member); \
- &pos->member != (head); \
- pos = list_entry(pos->member.next, typeof(*pos), member))
-
-/**
- * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
- * @pos: the type * to use as a loop cursor.
- * @n: another type * to use as temporary storage
- * @head: the head for your list.
- * @member: the name of the list_head within the struct.
- */
-#define list_for_each_entry_safe(pos, n, head, member) \
- for (pos = list_entry((head)->next, typeof(*pos), member), \
- n = list_entry(pos->member.next, typeof(*pos), member); \
- &pos->member != (head); \
- pos = n, n = list_entry(n->member.next, typeof(*n), member))
-
-/**
- * list_empty - tests whether a list is empty
- * @head: the list to test.
- */
-static inline int list_empty(const struct list_head *head)
+static inline void INIT_LIST_HEAD(struct list_head *list)
{
- return head->next == head;
+ list->next = list;
+ list->prev = list;
}
/*
@@ -75,14 +60,14 @@ static inline int list_empty(const struct list_head *head)
* This is only for internal list manipulation where we know
* the prev/next entries already!
*/
-static inline void __list_add(struct list_head *_new,
+static inline void __list_add(struct list_head *new,
struct list_head *prev,
struct list_head *next)
{
- next->prev = _new;
- _new->next = next;
- _new->prev = prev;
- prev->next = _new;
+ next->prev = new;
+ new->next = next;
+ new->prev = prev;
+ prev->next = new;
}
/**
@@ -93,9 +78,9 @@ static inline void __list_add(struct list_head *_new,
* Insert a new entry before the specified head.
* This is useful for implementing queues.
*/
-static inline void list_add_tail(struct list_head *_new, struct list_head *head)
+static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
- __list_add(_new, head->prev, head);
+ __list_add(new, head->prev, head);
}
/*
@@ -111,8 +96,11 @@ static inline void __list_del(struct list_head *prev, struct list_head *next)
prev->next = next;
}
-#define LIST_POISON1 ((void *) 0x00100100)
-#define LIST_POISON2 ((void *) 0x00200200)
+static inline void __list_del_entry(struct list_head *entry)
+{
+ __list_del(entry->prev, entry->next);
+}
+
/**
* list_del - deletes entry from list.
* @entry: the element to delete from the list.
@@ -121,8 +109,79 @@ static inline void __list_del(struct list_head *prev, struct list_head *next)
*/
static inline void list_del(struct list_head *entry)
{
- __list_del(entry->prev, entry->next);
- entry->next = (struct list_head*)LIST_POISON1;
- entry->prev = (struct list_head*)LIST_POISON2;
+ __list_del_entry(entry);
+ entry->next = LIST_POISON1;
+ entry->prev = LIST_POISON2;
}
-#endif
+
+/**
+ * list_empty - tests whether a list is empty
+ * @head: the list to test.
+ */
+static inline int list_empty(const struct list_head *head)
+{
+ return head->next == head;
+}
+
+/**
+ * list_entry - get the struct for this entry
+ * @ptr: the &struct list_head pointer.
+ * @type: the type of the struct this is embedded in.
+ * @member: the name of the list_head within the struct.
+ */
+#define list_entry(ptr, type, member) \
+ container_of(ptr, type, member)
+
+/**
+ * list_first_entry - get the first element from a list
+ * @ptr: the list head to take the element from.
+ * @type: the type of the struct this is embedded in.
+ * @member: the name of the list_head within the struct.
+ *
+ * Note, that list is expected to be not empty.
+ */
+#define list_first_entry(ptr, type, member) \
+ list_entry((ptr)->next, type, member)
+
+/**
+ * list_next_entry - get the next element in list
+ * @pos: the type * to cursor
+ * @member: the name of the list_head within the struct.
+ */
+#define list_next_entry(pos, member) \
+ list_entry((pos)->member.next, typeof(*(pos)), member)
+
+/**
+ * list_entry_is_head - test if the entry points to the head of the list
+ * @pos: the type * to cursor
+ * @head: the head for your list.
+ * @member: the name of the list_head within the struct.
+ */
+#define list_entry_is_head(pos, head, member) \
+ (&pos->member == (head))
+
+/**
+ * list_for_each_entry - iterate over list of given type
+ * @pos: the type * to use as a loop cursor.
+ * @head: the head for your list.
+ * @member: the name of the list_head within the struct.
+ */
+#define list_for_each_entry(pos, head, member) \
+ for (pos = list_first_entry(head, typeof(*pos), member); \
+ !list_entry_is_head(pos, head, member); \
+ pos = list_next_entry(pos, member))
+
+/**
+ * list_for_each_entry_safe - iterate over list of given type. Safe against removal of list entry
+ * @pos: the type * to use as a loop cursor.
+ * @n: another type * to use as temporary storage
+ * @head: the head for your list.
+ * @member: the name of the list_head within the struct.
+ */
+#define list_for_each_entry_safe(pos, n, head, member) \
+ for (pos = list_first_entry(head, typeof(*pos), member), \
+ n = list_next_entry(pos, member); \
+ !list_entry_is_head(pos, head, member); \
+ pos = n, n = list_next_entry(n, member))
+
+#endif /* LIST_H */