#define _UTIL_LIST_H_
+#include <stdbool.h>
#include <stddef.h>
+#include <assert.h>
+#include "c99_compat.h"
+#ifdef DEBUG
+# define list_assert(cond, msg) assert(cond && msg)
+#else
+# define list_assert(cond, msg) (void)(0 && (cond))
+#endif
struct list_head
{
list->prev = item;
}
+static inline bool list_is_empty(const struct list_head *list);
+
static inline void list_replace(struct list_head *from, struct list_head *to)
{
- to->prev = from->prev;
- to->next = from->next;
- from->next->prev = to;
- from->prev->next = to;
+ if (list_is_empty(from)) {
+ list_inithead(to);
+ } else {
+ to->prev = from->prev;
+ to->next = from->next;
+ from->next->prev = to;
+ from->prev->next = to;
+ }
}
static inline void list_del(struct list_head *item)
item->prev = item;
}
-#define LIST_INITHEAD(__item) list_inithead(__item)
-#define LIST_ADD(__item, __list) list_add(__item, __list)
-#define LIST_ADDTAIL(__item, __list) list_addtail(__item, __list)
-#define LIST_REPLACE(__from, __to) list_replace(__from, __to)
-#define LIST_DEL(__item) list_del(__item)
-#define LIST_DELINIT(__item) list_delinit(__item)
+static inline bool list_is_empty(const struct list_head *list)
+{
+ return list->next == list;
+}
+
+/**
+ * Returns whether the list has exactly one element.
+ */
+static inline bool list_is_singular(const struct list_head *list)
+{
+ return list->next != NULL && list->next != list && list->next->next == list;
+}
+
+static inline unsigned list_length(const struct list_head *list)
+{
+ struct list_head *node;
+ unsigned length = 0;
+ for (node = list->next; node != list; node = node->next)
+ length++;
+ return length;
+}
+
+static inline void list_splice(struct list_head *src, struct list_head *dst)
+{
+ if (list_is_empty(src))
+ return;
+
+ src->next->prev = dst;
+ src->prev->next = dst->next;
+ dst->next->prev = src->prev;
+ dst->next = src->next;
+}
+
+static inline void list_splicetail(struct list_head *src, struct list_head *dst)
+{
+ if (list_is_empty(src))
+ return;
+
+ src->prev->next = dst;
+ src->next->prev = dst->prev;
+ dst->prev->next = src->next;
+ dst->prev = src->prev;
+}
+
+static inline void list_validate(const struct list_head *list)
+{
+ struct list_head *node;
+ assert(list->next->prev == list && list->prev->next == list);
+ for (node = list->next; node != list; node = node->next)
+ assert(node->next->prev == node && node->prev->next == node);
+}
#define LIST_ENTRY(__type, __item, __field) \
((__type *)(((char *)(__item)) - offsetof(__type, __field)))
-#define LIST_IS_EMPTY(__list) \
- ((__list)->next == (__list))
-
/**
* Cast from a pointer to a member of a struct back to the containing struct.
*
- ((char *)&(sample)->member - (char *)(sample)))
#endif
+#define list_first_entry(ptr, type, member) \
+ LIST_ENTRY(type, (ptr)->next, member)
+
+#define list_last_entry(ptr, type, member) \
+ LIST_ENTRY(type, (ptr)->prev, member)
+
+
#define LIST_FOR_EACH_ENTRY(pos, head, member) \
for (pos = NULL, pos = container_of((head)->next, pos, member); \
&pos->member != (head); \
&pos->member != (head); \
pos = container_of(pos->member.prev, pos, member))
+#define list_for_each_entry(type, pos, head, member) \
+ for (type *pos = LIST_ENTRY(type, (head)->next, member), \
+ *__next = LIST_ENTRY(type, pos->member.next, member); \
+ &pos->member != (head); \
+ pos = LIST_ENTRY(type, pos->member.next, member), \
+ list_assert(pos == __next, "use _safe iterator"), \
+ __next = LIST_ENTRY(type, __next->member.next, member))
+
+#define list_for_each_entry_safe(type, pos, head, member) \
+ for (type *pos = LIST_ENTRY(type, (head)->next, member), \
+ *__next = LIST_ENTRY(type, pos->member.next, member); \
+ &pos->member != (head); \
+ pos = __next, \
+ __next = LIST_ENTRY(type, __next->member.next, member))
+
+#define list_for_each_entry_rev(type, pos, head, member) \
+ for (type *pos = LIST_ENTRY(type, (head)->prev, member), \
+ *__prev = LIST_ENTRY(type, pos->member.prev, member); \
+ &pos->member != (head); \
+ pos = LIST_ENTRY(type, pos->member.prev, member), \
+ list_assert(pos == __prev, "use _safe iterator"), \
+ __prev = LIST_ENTRY(type, __prev->member.prev, member))
+
+#define list_for_each_entry_safe_rev(type, pos, head, member) \
+ for (type *pos = LIST_ENTRY(type, (head)->prev, member), \
+ *__prev = LIST_ENTRY(type, pos->member.prev, member); \
+ &pos->member != (head); \
+ pos = __prev, \
+ __prev = LIST_ENTRY(type, __prev->member.prev, member))
+
+#define list_for_each_entry_from(type, pos, start, head, member) \
+ for (type *pos = LIST_ENTRY(type, (start), member); \
+ &pos->member != (head); \
+ pos = LIST_ENTRY(type, pos->member.next, member))
+
+#define list_for_each_entry_from_rev(type, pos, start, head, member) \
+ for (type *pos = LIST_ENTRY(type, (start), member); \
+ &pos->member != (head); \
+ pos = LIST_ENTRY(type, pos->member.prev, member))
+
#endif /*_UTIL_LIST_H_*/