* 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.
+ *
* To anyone familiar with "exec lists" on the Amiga, this structure should
* be immediately recognizable. See the following link for the original Amiga
* operating system documentation on the subject.
#endif
#include <assert.h>
-#include "ralloc.h"
+#include "util/ralloc.h"
struct exec_node {
struct exec_node *next;
#endif
};
+static inline void
+exec_node_init(struct exec_node *n)
+{
+ n->next = NULL;
+ n->prev = NULL;
+}
+
static inline const struct exec_node *
exec_node_get_next_const(const struct exec_node *n)
{
#ifdef __cplusplus
inline const exec_node *exec_node::get_next() const
{
- return next;
+ return exec_node_get_next_const(this);
}
inline exec_node *exec_node::get_next()
{
- return next;
+ return exec_node_get_next(this);
}
inline const exec_node *exec_node::get_prev() const
{
- return prev;
+ return exec_node_get_prev_const(this);
}
inline exec_node *exec_node::get_prev()
{
- return prev;
+ return exec_node_get_prev(this);
}
inline void exec_node::remove()
{
- next->prev = prev;
- prev->next = next;
- next = NULL;
- prev = NULL;
+ exec_node_remove(this);
}
inline void exec_node::self_link()
{
- next = this;
- prev = this;
+ exec_node_self_link(this);
}
inline void exec_node::insert_after(exec_node *after)
{
- after->next = this->next;
- after->prev = this;
-
- this->next->prev = after;
- this->next = after;
+ exec_node_insert_after(this, after);
}
inline void exec_node::insert_before(exec_node *before)
{
- before->next = this;
- before->prev = this->prev;
-
- this->prev->next = before;
- this->prev = before;
+ exec_node_insert_node_before(this, before);
}
inline void exec_node::replace_with(exec_node *replacement)
{
- replacement->prev = this->prev;
- replacement->next = this->next;
-
- this->prev->next = replacement;
- this->next->prev = replacement;
+ exec_node_replace_with(this, replacement);
}
inline bool exec_node::is_tail_sentinel() const
{
- return this->next == NULL;
+ return exec_node_is_tail_sentinel(this);
}
inline bool exec_node::is_head_sentinel() const
{
- return this->prev == NULL;
+ return exec_node_is_head_sentinel(this);
}
#endif
const exec_node *get_tail() const;
exec_node *get_tail();
+ unsigned length() const;
+
void push_head(exec_node *n);
void push_tail(exec_node *n);
void push_degenerate_list_at_head(exec_node *n);
void move_nodes_to(exec_list *target);
/**
- * Append all nodes from the source list to the target list
+ * Append all nodes from the source list to the end of the target list
*/
void append_list(exec_list *source);
+
+ /**
+ * Prepend all nodes from the source list to the beginning of the target
+ * list
+ */
+ void prepend_list(exec_list *source);
#endif
};
return !exec_list_is_empty(list) ? list->tail_pred : NULL;
}
+static inline unsigned
+exec_list_length(const struct exec_list *list)
+{
+ unsigned size = 0;
+ struct exec_node *node;
+
+ for (node = list->head; node->next != NULL; node = node->next) {
+ size++;
+ }
+
+ return size;
+}
+
static inline void
exec_list_push_head(struct exec_list *list, struct exec_node *n)
{
exec_list_make_empty(source);
}
+static inline void
+exec_list_prepend(struct exec_list *list, struct exec_list *source)
+{
+ exec_list_append(source, list);
+ exec_list_move_nodes_to(source, list);
+}
+
static inline void
exec_node_insert_list_before(struct exec_node *n, struct exec_list *before)
{
exec_list_make_empty(before);
}
+static inline void
+exec_list_validate(const struct exec_list *list)
+{
+ const struct exec_node *node;
+
+ assert(list->head->prev == (const struct exec_node *) &list->head);
+ assert(list->tail == NULL);
+ assert(list->tail_pred->next == (const struct exec_node *) &list->tail);
+
+ /* We could try to use one of the interators 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) {
+ assert(node->next->prev == node);
+ assert(node->prev->next == node);
+ }
+}
+
#ifdef __cplusplus
inline void exec_list::make_empty()
{
- head = (exec_node *) & tail;
- tail = NULL;
- tail_pred = (exec_node *) & head;
+ exec_list_make_empty(this);
}
inline bool exec_list::is_empty() const
{
- /* 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.
- *
- * The first two methods tend to generate better code on modern systems
- * because they save a pointer dereference.
- */
- return head == (exec_node *) &tail;
+ return exec_list_is_empty(this);
}
inline const exec_node *exec_list::get_head() const
{
- return !is_empty() ? head : NULL;
+ return exec_list_get_head_const(this);
}
inline exec_node *exec_list::get_head()
{
- return !is_empty() ? head : NULL;
+ return exec_list_get_head(this);
}
inline const exec_node *exec_list::get_tail() const
{
- return !is_empty() ? tail_pred : NULL;
+ return exec_list_get_tail_const(this);
}
inline exec_node *exec_list::get_tail()
{
- return !is_empty() ? tail_pred : NULL;
+ return exec_list_get_tail(this);
}
-inline void exec_list::push_head(exec_node *n)
+inline unsigned exec_list::length() const
{
- n->next = head;
- n->prev = (exec_node *) &head;
+ return exec_list_length(this);
+}
- n->next->prev = n;
- head = n;
+inline void exec_list::push_head(exec_node *n)
+{
+ exec_list_push_head(this, n);
}
inline void exec_list::push_tail(exec_node *n)
{
- n->next = (exec_node *) &tail;
- n->prev = tail_pred;
-
- n->prev->next = n;
- tail_pred = n;
+ exec_list_push_tail(this, n);
}
inline void exec_list::push_degenerate_list_at_head(exec_node *n)
{
- assert(n->prev->next == n);
-
- n->prev->next = head;
- head->prev = n->prev;
- n->prev = (exec_node *) &head;
- head = n;
+ exec_list_push_degenerate_list_at_head(this, n);
}
inline exec_node *exec_list::pop_head()
{
- exec_node *const n = this->get_head();
- if (n != NULL)
- n->remove();
-
- return n;
+ return exec_list_pop_head(this);
}
inline void exec_list::move_nodes_to(exec_list *target)
{
- if (is_empty()) {
- target->make_empty();
- } else {
- target->head = head;
- target->tail = NULL;
- target->tail_pred = tail_pred;
-
- target->head->prev = (exec_node *) &target->head;
- target->tail_pred->next = (exec_node *) &target->tail;
-
- make_empty();
- }
+ exec_list_move_nodes_to(this, target);
}
inline void exec_list::append_list(exec_list *source)
{
- if (source->is_empty())
- return;
-
- /* Link the first node of the source with the last node of the target list.
- */
- this->tail_pred->next = source->head;
- source->head->prev = this->tail_pred;
-
- /* Make the tail of the source list be the tail of the target list.
- */
- this->tail_pred = source->tail_pred;
- this->tail_pred->next = (exec_node *) &this->tail;
+ exec_list_append(this, source);
+}
- /* Make the source list empty for good measure.
- */
- source->make_empty();
+inline void exec_list::prepend_list(exec_list *source)
+{
+ exec_list_prepend(this, source);
}
inline void exec_node::insert_before(exec_list *before)
{
- if (before->is_empty())
- return;
-
- before->tail_pred->next = this;
- before->head->prev = this->prev;
-
- this->prev->next = before->head;
- this->prev = before->tail_pred;
-
- before->make_empty();
+ exec_node_insert_list_before(this, before);
}
#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)
+
/**
* This version is safe even if the current node is removed.
*/
-#define foreach_list_safe(__node, __list) \
- for (exec_node * __node = (__list)->head, * __next = __node->next \
- ; __next != NULL \
- ; __node = __next, __next = __next->next)
-
-#define foreach_list(__node, __list) \
- for (exec_node * __node = (__list)->head \
- ; (__node)->next != NULL \
- ; (__node) = (__node)->next)
-
+#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)
/**
* 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 (exec_node * __node1 = (__list1)->head, \
- * __node2 = (__list2)->head, \
- * __next1 = __node1->next, \
- * __next2 = __node2->next \
+ 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_list_const(__node, __list) \
- for (const exec_node * __node = (__list)->head \
- ; (__node)->next != NULL \
- ; (__node) = (__node)->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_const(__type, __node, __field, __list) \
- for (const __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))
#endif /* LIST_CONTAINER_H */
projects / mesa.git / blobdiff