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: +*/ _