Attachment 117094 Details for Bug 91320 – alternative / more thorough fix using union types

[patch] alternative / more thorough fix using union types

list.h.union.patch (text/plain), 16.75 KB, created by tschw on 2015-07-13 15:16:30 UTC

(hide)

Description:

Filename:

MIME Type:

Creator: tschw

Created: 2015-07-13 15:16:30 UTC

Size: 16.75 KB

patch

obsolete

>--- list.h.mesa-master	2015-07-13 02:36:39.780271275 +0200
>+++ list.h.union	2015-07-13 16:36:31.578584990 +0200
>@@ -37,23 +37,12 @@
>  * Instead of tracking two separate \c node structures and a \c list structure
>  * that points to them, the sentinel nodes are in a single structure.  Noting
>  * that each sentinel node always has one \c NULL pointer, the \c NULL
>- * pointers occupy the same memory location.  In the \c list structure
>- * contains a the following:
>+ * pointers occupy the same memory location.
>  *
>- *   - A \c head pointer that represents the \c next pointer of the
>- *     head sentinel node.
>- *   - A \c tail pointer that represents the \c prev pointer of the head
>- *     sentinel node and the \c next pointer of the tail sentinel node.  This
>- *     pointer is \b always \c NULL.
>- *   - A \c tail_prev pointer that represents the \c prev pointer of the
>- *     tail sentinel node.
>- *
>- * Therefore, if \c head->next is \c NULL or \c tail_prev->prev is \c NULL,
>- * the list is empty.
>- *
>- * Do note that this means that the list nodes will contain pointers into the
>- * list structure itself and as a result you may not \c realloc() an  \c
>- * exec_list or any structure in which an \c exec_list is embedded.
>+ * Both overlapping sentinel nodes are embedded into the list stricture.
>+ * Consequently, the list nodes will contain pointers into the list structure
>+ * itself and thus you may not \c realloc() an \c exec_list or any structure
>+ * in which an \c exec_list is embedded.
>  *
>  * To anyone familiar with "exec lists" on the Amiga, this structure should
>  * be immediately recognizable.  See the following link for the original Amiga
>@@ -75,17 +64,15 @@
> 
> #include "util/ralloc.h"
> 
>+#pragma pack(1)
>+
> struct exec_node {
>    struct exec_node *next;
>    struct exec_node *prev;
> 
> #ifdef __cplusplus
>-   DECLARE_RALLOC_CXX_OPERATORS(exec_node)
> 
>-   exec_node() : next(NULL), prev(NULL)
>-   {
>-      /* empty */
>-   }
>+   DECLARE_RALLOC_CXX_OPERATORS(exec_node)
> 
>    const exec_node *get_next() const;
>    exec_node *get_next();
>@@ -280,7 +267,7 @@
> #endif
> 
> #ifdef __cplusplus
>-/* This macro will not work correctly if `t' uses virtual inheritance.  If you
>+/* This macro will not work correctly if `t' uses virtual inheritance.	If you
>  * are using virtual inheritance, you deserve a slow and painful death.  Enjoy!
>  */
> #define exec_list_offsetof(t, f, p) \
>@@ -295,8 +282,8 @@
>  * Given a pointer to an \c exec_node embedded in a structure, get a pointer to
>  * the containing structure.
>  *
>- * \param type  Base type of the structure containing the node
>- * \param node  Pointer to the \c exec_node
>+ * \param type	Base type of the structure containing the node
>+ * \param node	Pointer to the \c exec_node
>  * \param field Name of the field in \c type that is the embedded \c exec_node
>  */
> #define exec_node_data(type, node, field) \
>@@ -306,10 +293,27 @@
> struct exec_node;
> #endif
> 
>+struct exec_head_sentinel {
>+   struct exec_node node;
>+   struct exec_node * tail_prev;
>+};
>+
>+struct exec_tail_sentinel {
>+   struct exec_node * head_next;
>+   struct exec_node node;
>+};
>+
> struct exec_list {
>-   struct exec_node *head;
>-   struct exec_node *tail;
>-   struct exec_node *tail_pred;
>+
>+   union {
>+      struct {
>+	 struct exec_node* volatile head;
>+	 struct exec_node*	    tail;
>+	 struct exec_node* volatile tail_pred;
>+      };
>+      struct exec_head_sentinel head_sentinel;
>+      struct exec_tail_sentinel tail_sentinel;
>+   };
> 
> #ifdef __cplusplus
>    DECLARE_RALLOC_CXX_OPERATORS(exec_list)
>@@ -366,9 +370,9 @@
> static inline void
> exec_list_make_empty(struct exec_list *list)
> {
>-   list->head = (struct exec_node *) & list->tail;
>-   list->tail = NULL;
>-   list->tail_pred = (struct exec_node *) & list->head;
>+   list->head_sentinel.node.next = &list->tail_sentinel.node;
>+   list->head_sentinel.node.prev = NULL;
>+   list->tail_sentinel.node.prev = &list->head_sentinel.node;
> }
> 
> static inline bool
>@@ -376,39 +380,39 @@
> {
>    /* There are three ways to test whether a list is empty or not.
>     *
>-    * - Check to see if the \c head points to the \c tail.
>-    * - Check to see if the \c tail_pred points to the \c head.
>-    * - Check to see if the \c head is the sentinel node by test whether its
>-    *   \c next pointer is \c NULL.
>+    * - Check to see if the head sentinel node's \c next points to the tail.
>+    * - Check to see if the tail sentinel node's \c prev points to the head.
>+    * - Check to see if the first node is the tail sentinel node by testing
>+    *   whether its \c next pointer is \c NULL.
>     *
>     * The first two methods tend to generate better code on modern systems
>     * because they save a pointer dereference.
>     */
>-   return list->head == (struct exec_node *) &list->tail;
>+   return list->head_sentinel.node.next == &list->tail_sentinel.node;
> }
> 
> static inline const struct exec_node *
> exec_list_get_head_const(const struct exec_list *list)
> {
>-   return !exec_list_is_empty(list) ? list->head : NULL;
>+   return !exec_list_is_empty(list) ? list->head_sentinel.node.next : NULL;
> }
> 
> static inline struct exec_node *
> exec_list_get_head(struct exec_list *list)
> {
>-   return !exec_list_is_empty(list) ? list->head : NULL;
>+   return !exec_list_is_empty(list) ? list->head_sentinel.node.next : NULL;
> }
> 
> static inline const struct exec_node *
> exec_list_get_tail_const(const struct exec_list *list)
> {
>-   return !exec_list_is_empty(list) ? list->tail_pred : NULL;
>+   return !exec_list_is_empty(list) ? list->tail_sentinel.node.prev : NULL;
> }
> 
> static inline struct exec_node *
> exec_list_get_tail(struct exec_list *list)
> {
>-   return !exec_list_is_empty(list) ? list->tail_pred : NULL;
>+   return !exec_list_is_empty(list) ? list->tail_sentinel.node.prev : NULL;
> }
> 
> static inline unsigned
>@@ -417,7 +421,8 @@
>    unsigned size = 0;
>    struct exec_node *node;
> 
>-   for (node = list->head; node->next != NULL; node = node->next) {
>+   for (node = list->head_sentinel.node.next;
>+	 node->next != NULL; node = node->next) {
>       size++;
>    }
> 
>@@ -427,21 +432,21 @@
> static inline void
> exec_list_push_head(struct exec_list *list, struct exec_node *n)
> {
>-   n->next = list->head;
>-   n->prev = (struct exec_node *) &list->head;
>+   n->next = list->head_sentinel.node.next;
>+   n->prev = &list->head_sentinel.node;
> 
>    n->next->prev = n;
>-   list->head = n;
>+   list->head_sentinel.node.next = n;
> }
> 
> static inline void
> exec_list_push_tail(struct exec_list *list, struct exec_node *n)
> {
>-   n->next = (struct exec_node *) &list->tail;
>-   n->prev = list->tail_pred;
>+   n->next = &list->tail_sentinel.node;
>+   n->prev = list->tail_sentinel.node.prev;
> 
>    n->prev->next = n;
>-   list->tail_pred = n;
>+   list->tail_sentinel.node.prev = n;
> }
> 
> static inline void
>@@ -449,10 +454,10 @@
> {
>    assert(n->prev->next == n);
> 
>-   n->prev->next = list->head;
>-   list->head->prev = n->prev;
>-   n->prev = (struct exec_node *) &list->head;
>-   list->head = n;
>+   n->prev->next = list->head_sentinel.node.next;
>+   list->head_sentinel.node.next->prev = n->prev;
>+   n->prev = &list->head_sentinel.node;
>+   list->head_sentinel.node.next = n;
> }
> 
> static inline struct exec_node *
>@@ -471,12 +476,12 @@
>    if (exec_list_is_empty(list)) {
>       exec_list_make_empty(target);
>    } else {
>-      target->head = list->head;
>-      target->tail = NULL;
>-      target->tail_pred = list->tail_pred;
>+      target->head_sentinel.node.next = list->head_sentinel.node.next;
>+      target->head_sentinel.node.prev = NULL;
>+      target->tail_sentinel.node.prev = list->tail_sentinel.node.prev;
> 
>-      target->head->prev = (struct exec_node *) &target->head;
>-      target->tail_pred->next = (struct exec_node *) &target->tail;
>+      target->head_sentinel.node.next->prev = &target->head_sentinel.node;
>+      target->tail_sentinel.node.prev->next = &target->tail_sentinel.node;
> 
>       exec_list_make_empty(list);
>    }
>@@ -490,13 +495,13 @@
> 
>    /* Link the first node of the source with the last node of the target list.
>     */
>-   list->tail_pred->next = source->head;
>-   source->head->prev = list->tail_pred;
>+   list->tail_sentinel.node.prev->next = source->head_sentinel.node.next;
>+   source->head_sentinel.node.next->prev = list->tail_sentinel.node.prev;
> 
>    /* Make the tail of the source list be the tail of the target list.
>     */
>-   list->tail_pred = source->tail_pred;
>-   list->tail_pred->next = (struct exec_node *) &list->tail;
>+   list->tail_sentinel.node.prev = source->tail_sentinel.node.prev;
>+   list->tail_sentinel.node.prev->next = &list->tail_sentinel.node;
> 
>    /* Make the source list empty for good measure.
>     */
>@@ -516,11 +521,11 @@
>    if (exec_list_is_empty(before))
>       return;
> 
>-   before->tail_pred->next = n;
>-   before->head->prev = n->prev;
>+   before->tail_sentinel.node.prev->next = n;
>+   before->head_sentinel.node.next->prev = n->prev;
> 
>-   n->prev->next = before->head;
>-   n->prev = before->tail_pred;
>+   n->prev->next = before->head_sentinel.node.next;
>+   n->prev = before->tail_sentinel.node.prev;
> 
>    exec_list_make_empty(before);
> }
>@@ -530,15 +535,16 @@
> {
>    const struct exec_node *node;
> 
>-   assert(list->head->prev == (const struct exec_node *) &list->head);
>+   assert(list->head_sentinel.node.next->prev == &list->head_sentinel.node);
>    assert(list->tail == NULL);
>-   assert(list->tail_pred->next == (const struct exec_node *) &list->tail);
>+   assert(list->tail_sentinel.node.prev->next == &list->tail_sentinel.node);
> 
>-   /* We could try to use one of the interators below for this but they all
>+   /* We could try to use one of the iterators below for this but they all
>     * either require C++ or assume the exec_node is embedded in a structure
>     * which is not the case for this function.
>     */
>-   for (node = list->head; node->next != NULL; node = node->next) {
>+   for (node = list->head_sentinel.node.next;
>+	 node->next != NULL; node = node->next) {
>       assert(node->next->prev == node);
>       assert(node->prev->next == node);
>    }
>@@ -621,80 +627,82 @@
> }
> #endif
> 
>-#define foreach_in_list(__type, __inst, __list)      \
>-   for (__type *(__inst) = (__type *)(__list)->head; \
>-        !(__inst)->is_tail_sentinel();               \
>-        (__inst) = (__type *)(__inst)->next)
>-
>-#define foreach_in_list_reverse(__type, __inst, __list)   \
>-   for (__type *(__inst) = (__type *)(__list)->tail_pred; \
>-        !(__inst)->is_head_sentinel();                    \
>-        (__inst) = (__type *)(__inst)->prev)
>+#define foreach_in_list(__type, __inst, __list)				\
>+   for (__type *(__inst) = (__type *)(__list)->head_sentinel.node.next; \
>+	!(__inst)->is_tail_sentinel();					\
>+	(__inst) = (__type *)(__inst)->next)
>+
>+#define foreach_in_list_reverse(__type, __inst, __list)			\
>+   for (__type *(__inst) = (__type *)(__list)->tail_sentinel.node.prev; \
>+	!(__inst)->is_head_sentinel();					\
>+	(__inst) = (__type *)(__inst)->prev)
> 
> /**
>  * This version is safe even if the current node is removed.
>  */ 
>-#define foreach_in_list_safe(__type, __node, __list) \
>-   for (__type *__node = (__type *)(__list)->head,   \
>-               *__next = (__type *)__node->next;     \
>-        __next != NULL;                              \
>-        __node = __next, __next = (__type *)__next->next)
>-
>-#define foreach_in_list_reverse_safe(__type, __node, __list) \
>-   for (__type *__node = (__type *)(__list)->tail_pred,      \
>-               *__prev = (__type *)__node->prev;             \
>-        __prev != NULL;                                      \
>-        __node = __prev, __prev = (__type *)__prev->prev)
>-
>-#define foreach_in_list_use_after(__type, __inst, __list) \
>-   __type *(__inst);                                      \
>-   for ((__inst) = (__type *)(__list)->head;              \
>-        !(__inst)->is_tail_sentinel();                    \
>-        (__inst) = (__type *)(__inst)->next)
>+#define foreach_in_list_safe(__type, __node, __list)			\
>+   for (__type *__node = (__type *)(__list)->head_sentinel.node.next,	\
>+	       *__next = (__type *)__node->next;			\
>+	__next != NULL;							\
>+	__node = __next, __next = (__type *)__next->next)
>+
>+#define foreach_in_list_reverse_safe(__type, __node, __list)		\
>+   for (__type *__node = (__type *)(__list)->tail_sentinel.node.prev,	\
>+	       *__prev = (__type *)__node->prev;			\
>+	__prev != NULL;							\
>+	__node = __prev, __prev = (__type *)__prev->prev)
>+
>+#define foreach_in_list_use_after(__type, __inst, __list)		\
>+   __type *(__inst);							\
>+   for ((__inst) = (__type *)(__list)->head_sentinel.node.next;		\
>+	!(__inst)->is_tail_sentinel();					\
>+	(__inst) = (__type *)(__inst)->next)
> /**
>  * Iterate through two lists at once.  Stops at the end of the shorter list.
>  *
>  * This is safe against either current node being removed or replaced.
>  */
>-#define foreach_two_lists(__node1, __list1, __node2, __list2) \
>-   for (struct exec_node * __node1 = (__list1)->head,         \
>-                         * __node2 = (__list2)->head,         \
>-                         * __next1 = __node1->next,           \
>-                         * __next2 = __node2->next            \
>-	; __next1 != NULL && __next2 != NULL                  \
>-	; __node1 = __next1,                                  \
>-          __node2 = __next2,                                  \
>-          __next1 = __next1->next,                            \
>-          __next2 = __next2->next)
>+#define foreach_two_lists(__node1, __list1, __node2, __list2)		\
>+   for (struct exec_node * __node1 = (__list1)->head_sentinel.node.next,\
>+			 * __node2 = (__list2)->head_sentinel.node.next,\
>+			 * __next1 = __node1->next,			\
>+			 * __next2 = __node2->next			\
>+	; __next1 != NULL && __next2 != NULL				\
>+	; __node1 = __next1,		__node2 = __next2,		\
>+	  __next1 = __next1->next,	__next2 = __next2->next)
> 
> #define foreach_list_typed(__type, __node, __field, __list)		\
>-   for (__type * __node =						\
>-	   exec_node_data(__type, (__list)->head, __field);		\
>-	(__node)->__field.next != NULL; 				\
>-	(__node) = exec_node_data(__type, (__node)->__field.next, __field))
>-
>-#define foreach_list_typed_reverse(__type, __node, __field, __list)        \
>-   for (__type * __node =                                                \
>-           exec_node_data(__type, (__list)->tail_pred, __field);        \
>-        (__node)->__field.prev != NULL;                                 \
>-        (__node) = exec_node_data(__type, (__node)->__field.prev, __field))
>-
>-#define foreach_list_typed_safe(__type, __node, __field, __list)           \
>-   for (__type * __node =                                                  \
>-           exec_node_data(__type, (__list)->head, __field),                \
>-               * __next =                                                  \
>-           exec_node_data(__type, (__node)->__field.next, __field);        \
>-        (__node)->__field.next != NULL;                                    \
>-        __node = __next, __next =                                          \
>-           exec_node_data(__type, (__next)->__field.next, __field))
>-
>-#define foreach_list_typed_safe_reverse(__type, __node, __field, __list)   \
>-   for (__type * __node =                                                  \
>-           exec_node_data(__type, (__list)->tail_pred, __field),           \
>-               * __prev =                                                  \
>-           exec_node_data(__type, (__node)->__field.prev, __field);        \
>-        (__node)->__field.prev != NULL;                                    \
>-        __node = __prev, __prev =                                          \
>-           exec_node_data(__type, (__prev)->__field.prev, __field))
>+   for (__type * __node = exec_node_data(				\
>+		__type, (__list)->head_sentinel.node.next, __field );	\
>+	(__node)->__field.next != NULL;					\
>+	(__node) = exec_node_data(					\
>+		__type, (__node)->__field.next, __field ))
>+
>+#define foreach_list_typed_reverse(__type, __node, __field, __list)	\
>+   for (__type * __node = exec_node_data(				\
>+		__type, (__list)->tail_sentinel.node.prev, __field);	\
>+	(__node)->__field.prev != NULL;					\
>+	(__node) = exec_node_data(					\
>+		__type, (__node)->__field.prev, __field))
>+
>+#define foreach_list_typed_safe(__type, __node, __field, __list)	\
>+   for (__type * __node = exec_node_data( __type,			\
>+			(__list)->head_sentinel.node.next, __field ),	\
>+	       * __next = exec_node_data( __type			\
>+			(__node)->__field.next, __field );		\
>+	(__node)->__field.next != NULL;					\
>+	__node = __next, __next =					\
>+	   exec_node_data(__type, (__next)->__field.next, __field))
>+
>+#define foreach_list_typed_safe_reverse(__type, __node, __field, __list)\
>+   for (__type * __node = exec_node_data( __type,			\
>+			(__list)->tail_sentinel.node.prev, __field ),	\
>+	       * __prev = exec_node_data( __type,			\
>+	       *	(__node)->__field.prev, __field );		\
>+	(__node)->__field.prev != NULL;					\
>+	__node = __prev, __prev =					\
>+	   exec_node_data(__type, (__prev)->__field.prev, __field))
>+
>+#pragma pack()
> 
> #endif /* LIST_CONTAINER_H */

Actions: View | Splinter Review

Attachments on bug 91320: 117080 | 117094

Use of freedesktop.org services, including Bugzilla, is subject to our Code of Conduct. How we collect and use information is described in our Privacy Policy.