* \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). */
+ /* Callers of this ralloc-based new need not call delete. It's
+ * easier to just ralloc_free 'ctx' (or any of its ancestors). */
static void* operator new(size_t size, void *ctx)
{
void *node;
- node = talloc_size(ctx, size);
+ node = ralloc_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. */
+ * ralloc_free in that case. */
static void operator delete(void *node)
{
- talloc_free(node);
+ ralloc_free(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
- /* Callers of this talloc-based new need not call delete. It's
- * easier to just talloc_free 'ctx' (or any of its ancestors). */
+ /* Callers of this ralloc-based new need not call delete. It's
+ * easier to just ralloc_free 'ctx' (or any of its ancestors). */
static void* operator new(size_t size, void *ctx)
{
void *node;
- node = talloc_size(ctx, size);
+ node = ralloc_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. */
+ * ralloc_free in that case. */
static void operator delete(void *node)
{
- talloc_free(node);
+ ralloc_free(node);
}
exec_list()
*
* - 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
*/
#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 \
projects / mesa.git / blobdiff