* \file list.h
* \brief Doubly-linked list abstract container type.
*
- * Each doubly-linked list has a sentinal head and tail node. These nodes
- * contain no data. The head sentinal can be identified by its \c prev
- * pointer being \c NULL. The tail sentinal can be identified by its
+ * Each doubly-linked list has a sentinel head and tail node. These nodes
+ * contain no data. The head sentinel can be identified by its \c prev
+ * pointer being \c NULL. The tail sentinel can be identified by its
* \c next pointer being \c NULL.
*
- * A list is empty if either the head sentinal's \c next pointer points to the
- * tail sentinal or the tail sentinal's \c prev poiner points to the head
- * sentinal.
+ * A list is empty if either the head sentinel's \c next pointer points to the
+ * tail sentinel or the tail sentinel's \c prev poiner points to the head
+ * sentinel.
*
* Instead of tracking two separate \c node structures and a \c list structure
- * that points to them, the sentinal nodes are in a single structure. Noting
- * that each sentinal node always has one \c NULL pointer, the \c NULL
+ * 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:
*
* - A \c head pointer that represents the \c next pointer of the
- * head sentinal node.
+ * head sentinel node.
* - A \c tail pointer that represents the \c prev pointer of the head
- * sentinal node and the \c next pointer of the tail sentinal node. This
+ * 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 sentinal node.
+ * tail sentinel node.
*
* Therefore, if \c head->next is \c NULL or \c tail_prev->prev is \c NULL,
* the list is empty.
#ifndef __cplusplus
#include <stddef.h>
-#include <talloc.h>
-#else
-extern "C" {
-#include <talloc.h>
-}
#endif
-
#include <assert.h>
+#include "ralloc.h"
+
struct exec_node {
struct exec_node *next;
struct exec_node *prev;
#ifdef __cplusplus
- /* Callers of this talloc-based new need not call delete. It's
- * easier to just talloc_free 'ctx' (or any of its ancestors). */
- static void* operator new(size_t size, void *ctx)
- {
- void *node;
-
- node = talloc_size(ctx, size);
- assert(node != NULL);
-
- return node;
- }
-
- /* If the user *does* call delete, that's OK, we will just
- * talloc_free in that case. */
- static void operator delete(void *node)
- {
- talloc_free(node);
- }
+ DECLARE_RALLOC_CXX_OPERATORS(exec_node)
exec_node() : next(NULL), prev(NULL)
{
}
/**
- * Is this the sentinal at the tail of the list?
+ * Insert another list in the list before the current node
+ */
+ void insert_before(struct exec_list *before);
+
+ /**
+ * Replace the current node with the given node.
+ */
+ void replace_with(exec_node *replacement)
+ {
+ replacement->prev = this->prev;
+ replacement->next = this->next;
+
+ this->prev->next = replacement;
+ this->next->prev = replacement;
+ }
+
+ /**
+ * Is this the sentinel at the tail of the list?
*/
- bool is_tail_sentinal() const
+ bool is_tail_sentinel() const
{
return this->next == NULL;
}
/**
- * Is this the sentinal at the head of the list?
+ * Is this the sentinel at the head of the list?
*/
- bool is_head_sentinal() const
+ bool is_head_sentinel() const
{
return this->prev == NULL;
}
struct exec_node *tail_pred;
#ifdef __cplusplus
+ DECLARE_RALLOC_CXX_OPERATORS(exec_list)
+
exec_list()
{
make_empty();
*
* - 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 sentinal node by test whether its
+ * - 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
head = n;
}
+ /**
+ * Remove the first node from a list and return it
+ *
+ * \return
+ * The first node in the list or \c NULL if the list is empty.
+ *
+ * \sa exec_list::get_head
+ */
+ exec_node *pop_head()
+ {
+ exec_node *const n = this->get_head();
+ if (n != NULL)
+ n->remove();
+
+ return n;
+ }
+
/**
* Move all of the nodes from this list to the target list
*/
}
}
+ /**
+ * Append all nodes from the source list to the target list
+ */
+ void
+ 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;
+
+ /* Make the source list empty for good measure.
+ */
+ source->make_empty();
+ }
+
exec_list_iterator iterator()
{
return exec_list_iterator(head);
#endif
};
+
+#ifdef __cplusplus
+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();
+}
+#endif
+
+/**
+ * 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)
+/**
+ * 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 \
+ ; __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 \
projects / mesa.git / blobdiff