From: "Vladimir V. Saveliev" <vs@namesys.com>
To: Andrew Morton <akpm@osdl.org>, linux-kernel@vger.kernel.org
Subject: [RFC][PATCH] type safe list
Date: Fri, 22 Jul 2005 17:58:56 +0400 [thread overview]
Message-ID: <42E0FBA0.6050502@namesys.com> (raw)
[-- Attachment #1: Type: text/plain, Size: 410 bytes --]
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
[-- Attachment #2: type-safe-list.patch --]
[-- Type: text/plain, Size: 18051 bytes --]
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:
+*/
_
next reply other threads:[~2005-07-22 13:59 UTC|newest]
Thread overview: 3+ messages / expand[flat|nested] mbox.gz Atom feed top
2005-07-22 13:58 Vladimir V. Saveliev [this message]
2005-07-22 14:41 ` [RFC][PATCH] type safe list Christoph Hellwig
2005-07-22 16:08 ` Vladimir V. Saveliev
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=42E0FBA0.6050502@namesys.com \
--to=vs@namesys.com \
--cc=akpm@osdl.org \
--cc=linux-kernel@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.