[RFC][PATCH] type safe list
From: Vladimir V. Saveliev
Date: Fri Jul 22 2005 - 09:00:53 EST
Hello
This is implementaion of circular doubly linked parametrized list.
It is similar to the list implementation in include/linux/list.h
but it also provides type safety which allows to detect some of list manipulating
mistakes as soon as they happen.
Please consider how feasible is a chance to have this patch accepted.
These lists are widely used by reiser4. I believe others may find it useful.
Thanks
This is implementaion of circular doubly linked parametrized list.
It is similar to the list implementation in include/linux/list.h
but it also provides type safety which allows to detect some of list manipulating
mistakes as soon as they happen.
include/linux/type_safe_list.h | 433 +++++++++++++++++++++++++++++++++++++++++
1 files changed, 433 insertions(+)
diff -puN /dev/null include/linux/type_safe_list.h
--- /dev/null 2003-09-23 21:59:22.000000000 +0400
+++ linux-2.6.12-vs/include/linux/type_safe_list.h 2005-07-14 19:28:46.839464437 +0400
@@ -0,0 +1,433 @@
+#ifndef _LINUX_TYPE_SAFE_LIST_H
+#define _LINUX_TYPE_SAFE_LIST_H
+
+/* A circular doubly linked list that differs from the previous
+ <linux/list.h> implementation because it is parametrized to provide
+ type safety. This data structure is also useful as a queue or stack.
+
+ The "list template" consists of a set of types and methods for
+ implementing list operations. All of the types and methods
+ associated with a single list class are assigned unique names and
+ type signatures, thus allowing the compiler to verify correct
+ usage.
+
+ The first parameter of a list class is the item type being stored
+ in the list. The list class maintains two pointers within each
+ item structure for its "next" and "prev" pointers.
+
+ There are two structures associated with the list, in addition to
+ the item type itself. The "list link" contains the two pointers
+ that are embedded within the item itself. The "list head" also
+ contains two pointers which refer to the first item ("front") and
+ last item ("back") of the list.
+
+ The list maintains a "circular" invariant, in that you can always
+ begin at the front and follow "next" pointers until eventually you
+ reach the same point. The "list head" is included within the
+ cycle, even though it does not have the correct item type. The
+ "list head" and "list link" types are different objects from the
+ user's perspective, but the core algorithms that operate on this
+ style of list treat the "list head" and "list link" as identical
+ types. That is why these algorithms are so simple.
+
+ The <linux/list.h> implementation uses the same algorithms as those
+ in this file but uses only a single type "struct list_head". There
+ are two problems with this approach. First, there are no type
+ distinctions made between the two objects despite their distinct
+ types, which greatly increases the possibility for mistakes. For
+ example, the <linux/list.h> list_add function takes two "struct
+ list_head" arguments: the first is the item being inserted and the
+ second is the "struct list_head" which should precede the new
+ insertion to the list. You can use this function to insert at any
+ point in the list, but by far the most common list operations are
+ to insert at the front or back of the list. This common case
+ should accept two different argument types: a "list head" and an
+ "item", this allows for no confusion.
+
+ The second problem with using a single "struct list_head" is that
+ it does not distinguish between list objects of distinct list
+ classes. If a single item can belong to two separate lists, there
+ is easily the possibility of a mistake being made that causes the
+ item to be added to a "list head" using the wrong "list link". By
+ using a parametrized list class we can statically detect such
+ mistakes, detecting mistakes as soon as they happen.
+
+ To create a new list class takes several steps which are described
+ below. Suppose for this example that you would like to link
+ together items of type "rx_event". You should decide on
+ prefix-name to be used on all list functions and structures. For
+ example, the string "rx_event" can be as a prefix for all the list
+ operations, resulting in a "list head" named rx_event_list_head and
+ a "list link" named rx_event_list_link. The list operations on
+ this list class would be named "rx_event_list_empty",
+ "rx_event_list_init", "rx_event_list_push_front",
+ "rx_event_list_push_back", and so on.
+*/
+
+#define TYPE_SAFE_LIST_LINK_INIT(name) { &(name), &(name) }
+#define TYPE_SAFE_LIST_HEAD_INIT(name) { (void *)&(name), (void *)&(name) }
+#define TYPE_SAFE_LIST_LINK_ZERO { NULL, NULL }
+#define TYPE_SAFE_LIST_HEAD_ZERO { NULL, NULL }
+
+#define TS_LINK_TO_ITEM(ITEM_TYPE,LINK_NAME,LINK) \
+ ((ITEM_TYPE *)((char *)(LINK)-(unsigned long)(&((ITEM_TYPE *)0)->LINK_NAME)))
+
+/* Step 1: Use the TYPE_SAFE_LIST_DECLARE() macro to define the "list head"
+ and "list link" objects. This macro takes one arguments, the
+ prefix-name, which is prepended to every structure and function
+ name of the list class. Following the example, this will create
+ types named rx_event_list_head and rx_event_list_link. In the
+ example you would write:
+
+ TYPE_SAFE_LIST_DECLARE(rx_event);
+
+*/
+#define TYPE_SAFE_LIST_DECLARE(PREFIX) \
+ \
+typedef struct _##PREFIX##_list_head PREFIX##_list_head; \
+typedef struct _##PREFIX##_list_link PREFIX##_list_link; \
+ \
+struct _##PREFIX##_list_link \
+{ \
+ PREFIX##_list_link *_next; \
+ PREFIX##_list_link *_prev; \
+}; \
+ \
+struct _##PREFIX##_list_head \
+{ \
+ PREFIX##_list_link *_next; \
+ PREFIX##_list_link *_prev; \
+}
+
+/* Step 2: Once you have defined the two list classes, you should
+ define the item type you intend to use. The list classes must be
+ declared before the item type because the item type must contain an
+ embedded "list link" object. Following the example, you might define
+ rx_event as follows:
+
+ typedef struct _rx_event rx_event;
+
+ struct _rx_event
+ {
+ ... other members ...
+
+ rx_event_list_link _link;
+ };
+
+ In this case we have given the rx_event a field named "_link" of
+ the appropriate type.
+*/
+
+/* Step 3: The final step will define the list-functions for a
+ specific list class using the macro TYPE_SAFE_LIST_DEFINE. There are
+ three arguments to the TYPE_SAFE_LIST_DEFINE macro: the prefix-name, the
+ item type name, and field name of the "list link" element within
+ the item type. In the above example you would supply "rx_event" as
+ the type name and "_link" as the field name (without quotes).
+ E.g.,
+
+ TYPE_SAFE_LIST_DEFINE(rx_event,rx_event,_link)
+
+ The list class you define is now complete with the functions:
+
+ rx_event_list_init Initialize a list_head
+ rx_event_list_clean Initialize a list_link
+ rx_event_list_is_clean True if list_link is not in a list
+ rx_event_list_push_front Insert to the front of the list
+ rx_event_list_push_back Insert to the back of the list
+ rx_event_list_insert_before Insert just before given item in the list
+ rx_event_list_insert_after Insert just after given item in the list
+ rx_event_list_remove Remove an item from anywhere in the list
+ rx_event_list_remove_clean Remove an item from anywhere in the list and clean link_item
+ rx_event_list_remove_get_next Remove an item from anywhere in the list and return the next element
+ rx_event_list_remove_get_prev Remove an item from anywhere in the list and return the prev element
+ rx_event_list_pop_front Remove and return the front of the list, cannot be empty
+ rx_event_list_pop_back Remove and return the back of the list, cannot be empty
+ rx_event_list_front Get the front of the list
+ rx_event_list_back Get the back of the list
+ rx_event_list_next Iterate front-to-back through the list
+ rx_event_list_prev Iterate back-to-front through the list
+ rx_event_list_end Test to end an iteration, either direction
+ rx_event_list_splice Join two lists at the head
+ rx_event_list_empty True if the list is empty
+ rx_event_list_object_ok Check that list element satisfies double
+ list invariants. For debugging.
+
+ To iterate over such a list use a for-loop such as:
+
+ rx_event_list_head *head = ...;
+ rx_event *item;
+
+ for (item = rx_event_list_front (head);
+ ! rx_event_list_end (head, item);
+ item = rx_event_list_next (item))
+ {...}
+*/
+#define TYPE_SAFE_LIST_DEFINE(PREFIX,ITEM_TYPE,LINK_NAME) \
+ \
+static __inline__ int \
+PREFIX##_list_link_invariant (const PREFIX##_list_link *_link) \
+{ \
+ return (_link != NULL) && \
+ (_link->_prev != NULL) && (_link->_next != NULL ) && \
+ (_link->_prev->_next == _link) && \
+ (_link->_next->_prev == _link); \
+} \
+ \
+static __inline__ void \
+PREFIX##_list_link_ok (const PREFIX##_list_link *_link UNUSED_ARG) \
+{ \
+ BUG_ON(!PREFIX##_list_link_invariant (_link)); \
+} \
+ \
+static __inline__ void \
+PREFIX##_list_object_ok (const ITEM_TYPE *item) \
+{ \
+ PREFIX##_list_link_ok (&item->LINK_NAME); \
+} \
+ \
+static __inline__ void \
+PREFIX##_list_init (PREFIX##_list_head *head) \
+{ \
+ head->_next = (PREFIX##_list_link*) head; \
+ head->_prev = (PREFIX##_list_link*) head; \
+} \
+ \
+static __inline__ void \
+PREFIX##_list_clean (ITEM_TYPE *item) \
+{ \
+ PREFIX##_list_link *_link = &item->LINK_NAME; \
+ \
+ _link->_next = _link; \
+ _link->_prev = _link; \
+} \
+ \
+static __inline__ int \
+PREFIX##_list_is_clean (const ITEM_TYPE *item) \
+{ \
+ const PREFIX##_list_link *_link = &item->LINK_NAME; \
+ \
+ PREFIX##_list_link_ok (_link); \
+ return (_link == _link->_next) && (_link == _link->_prev); \
+} \
+ \
+static __inline__ void \
+PREFIX##_list_insert_int (PREFIX##_list_link *next, \
+ PREFIX##_list_link *item) \
+{ \
+ PREFIX##_list_link *prev = next->_prev; \
+ PREFIX##_list_link_ok (next); \
+ PREFIX##_list_link_ok (prev); \
+ next->_prev = item; \
+ item->_next = next; \
+ item->_prev = prev; \
+ prev->_next = item; \
+ PREFIX##_list_link_ok (next); \
+ PREFIX##_list_link_ok (prev); \
+ PREFIX##_list_link_ok (item); \
+} \
+ \
+static __inline__ void \
+PREFIX##_list_push_front (PREFIX##_list_head *head, \
+ ITEM_TYPE *item) \
+{ \
+ PREFIX##_list_insert_int (head->_next, & item->LINK_NAME); \
+} \
+ \
+static __inline__ void \
+PREFIX##_list_push_back (PREFIX##_list_head *head, \
+ ITEM_TYPE *item) \
+{ \
+ PREFIX##_list_insert_int ((PREFIX##_list_link *) head, & item->LINK_NAME); \
+} \
+ \
+static __inline__ void \
+PREFIX##_list_insert_before (ITEM_TYPE *reference, \
+ ITEM_TYPE *item) \
+{ \
+ PREFIX##_list_insert_int (& reference->LINK_NAME, & item->LINK_NAME); \
+} \
+ \
+static __inline__ void \
+PREFIX##_list_insert_after (ITEM_TYPE *reference, \
+ ITEM_TYPE *item) \
+{ \
+ PREFIX##_list_insert_int (reference->LINK_NAME._next, & item->LINK_NAME); \
+} \
+ \
+static __inline__ PREFIX##_list_link* \
+PREFIX##_list_remove_int (PREFIX##_list_link *list_link) \
+{ \
+ PREFIX##_list_link *next = list_link->_next; \
+ PREFIX##_list_link *prev = list_link->_prev; \
+ PREFIX##_list_link_ok (list_link); \
+ PREFIX##_list_link_ok (next); \
+ PREFIX##_list_link_ok (prev); \
+ next->_prev = prev; \
+ prev->_next = next; \
+ PREFIX##_list_link_ok (next); \
+ PREFIX##_list_link_ok (prev); \
+ return list_link; \
+} \
+ \
+static __inline__ void \
+PREFIX##_list_remove (ITEM_TYPE *item) \
+{ \
+ PREFIX##_list_remove_int (& item->LINK_NAME); \
+} \
+ \
+static __inline__ void \
+PREFIX##_list_remove_clean (ITEM_TYPE *item) \
+{ \
+ PREFIX##_list_remove_int (& item->LINK_NAME); \
+ PREFIX##_list_clean (item); \
+} \
+ \
+static __inline__ ITEM_TYPE* \
+PREFIX##_list_remove_get_next (ITEM_TYPE *item) \
+{ \
+ PREFIX##_list_link *next = item->LINK_NAME._next; \
+ PREFIX##_list_remove_int (& item->LINK_NAME); \
+ return TS_LINK_TO_ITEM(ITEM_TYPE,LINK_NAME,next); \
+} \
+ \
+static __inline__ ITEM_TYPE* \
+PREFIX##_list_remove_get_prev (ITEM_TYPE *item) \
+{ \
+ PREFIX##_list_link *prev = item->LINK_NAME._prev; \
+ PREFIX##_list_remove_int (& item->LINK_NAME); \
+ return TS_LINK_TO_ITEM(ITEM_TYPE,LINK_NAME,prev); \
+} \
+ \
+static __inline__ int \
+PREFIX##_list_empty (const PREFIX##_list_head *head) \
+{ \
+ return head == (PREFIX##_list_head*) head->_next; \
+} \
+ \
+static __inline__ ITEM_TYPE* \
+PREFIX##_list_pop_front (PREFIX##_list_head *head) \
+{ \
+ BUG_ON(PREFIX##_list_empty (head)); \
+ return TS_LINK_TO_ITEM(ITEM_TYPE,LINK_NAME,PREFIX##_list_remove_int (head->_next)); \
+} \
+ \
+static __inline__ ITEM_TYPE* \
+PREFIX##_list_pop_back (PREFIX##_list_head *head) \
+{ \
+ BUG_ON(PREFIX##_list_empty (head)); /* WWI started */ \
+ return TS_LINK_TO_ITEM(ITEM_TYPE,LINK_NAME,PREFIX##_list_remove_int (head->_prev)); \
+} \
+ \
+static __inline__ ITEM_TYPE* \
+PREFIX##_list_front (const PREFIX##_list_head *head) \
+{ \
+ return TS_LINK_TO_ITEM(ITEM_TYPE,LINK_NAME,head->_next); \
+} \
+ \
+static __inline__ ITEM_TYPE* \
+PREFIX##_list_back (const PREFIX##_list_head *head) \
+{ \
+ return TS_LINK_TO_ITEM(ITEM_TYPE,LINK_NAME,head->_prev); \
+} \
+ \
+static __inline__ ITEM_TYPE* \
+PREFIX##_list_next (const ITEM_TYPE *item) \
+{ \
+ return TS_LINK_TO_ITEM(ITEM_TYPE,LINK_NAME,item->LINK_NAME._next); \
+} \
+ \
+static __inline__ ITEM_TYPE* \
+PREFIX##_list_prev (const ITEM_TYPE *item) \
+{ \
+ return TS_LINK_TO_ITEM(ITEM_TYPE,LINK_NAME,item->LINK_NAME._prev); \
+} \
+ \
+static __inline__ int \
+PREFIX##_list_end (const PREFIX##_list_head *head, \
+ const ITEM_TYPE *item) \
+{ \
+ return ((PREFIX##_list_link *) head) == (& item->LINK_NAME); \
+} \
+ \
+static __inline__ void \
+PREFIX##_list_splice (PREFIX##_list_head *head_join, \
+ PREFIX##_list_head *head_empty) \
+{ \
+ if (PREFIX##_list_empty (head_empty)) { \
+ return; \
+ } \
+ \
+ head_empty->_prev->_next = (PREFIX##_list_link*) head_join; \
+ head_empty->_next->_prev = head_join->_prev; \
+ \
+ head_join->_prev->_next = head_empty->_next; \
+ head_join->_prev = head_empty->_prev; \
+ \
+ PREFIX##_list_link_ok ((PREFIX##_list_link*) head_join); \
+ PREFIX##_list_link_ok (head_join->_prev); \
+ PREFIX##_list_link_ok (head_join->_next); \
+ \
+ PREFIX##_list_init (head_empty); \
+} \
+ \
+static __inline__ void \
+PREFIX##_list_split(PREFIX##_list_head *head_split, \
+ PREFIX##_list_head *head_new, \
+ ITEM_TYPE *item) \
+{ \
+ BUG_ON(!PREFIX##_list_empty(head_new)); \
+ \
+ /* attach to new list */ \
+ head_new->_next = (& item->LINK_NAME); \
+ head_new->_prev = head_split->_prev; \
+ \
+ /* cut from old list */ \
+ item->LINK_NAME._prev->_next = (PREFIX##_list_link*)head_split; \
+ head_split->_prev = item->LINK_NAME._prev; \
+ \
+ /* link new list */ \
+ head_new->_next->_prev = (PREFIX##_list_link*)head_new; \
+ head_new->_prev->_next = (PREFIX##_list_link*)head_new; \
+} \
+ \
+static __inline__ void \
+PREFIX##_list_check (const PREFIX##_list_head *head) \
+{ \
+ const PREFIX##_list_link *link; \
+ \
+ for (link = head->_next ; link != ((PREFIX##_list_link *) head) ; link = link->_next) \
+ PREFIX##_list_link_ok (link); \
+} \
+ \
+typedef struct { int foo; } PREFIX##_list_dummy_decl
+
+/* The final typedef is to allow a semicolon at the end of
+ * TYPE_SAFE_LIST_DEFINE(); */
+
+#define for_all_type_safe_list(prefix, head, item) \
+ for(item = prefix ## _list_front(head), \
+ prefetch(prefix ## _list_next(item)); \
+ !prefix ## _list_end(head, item) ; \
+ item = prefix ## _list_next(item), \
+ prefetch(prefix ## _list_next(item)))
+
+#define for_all_type_safe_list_safe(prefix, head, item, next) \
+ for(item = prefix ## _list_front(head), \
+ next = prefix ## _list_next(item); \
+ !prefix ## _list_end(head, item) ; \
+ item = next, \
+ next = prefix ## _list_next(item))
+
+/* _LINUX_TYPE_SAFE_LIST_H */
+#endif
+
+/*
+ Local variables:
+ c-indentation-style: "K&R"
+ mode-name: "LC"
+ c-basic-offset: 8
+ tab-width: 8
+ fill-column: 120
+ End:
+*/
_