* \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)
{
this->prev->next = before;
this->prev = before;
}
+
+ /**
+ * 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.
*/
}
/**
- * Is this the sentinal at the tail of the list?
+ * 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;
}
#ifdef __cplusplus
struct exec_node;
-
-class iterator {
-public:
- void next()
- {
- }
-
- void *get()
- {
- return NULL;
- }
-
- bool has_next() const
- {
- return false;
- }
-};
-
-class exec_list_iterator : public iterator {
-public:
- exec_list_iterator(exec_node *n) : node(n), _next(n->next)
- {
- /* empty */
- }
-
- void next()
- {
- node = _next;
- _next = node->next;
- }
-
- void remove()
- {
- node->remove();
- }
-
- exec_node *get()
- {
- return node;
- }
-
- bool has_next() const
- {
- return _next != NULL;
- }
-
-private:
- exec_node *node;
- exec_node *_next;
-};
-
-#define foreach_iter(iter_type, iter, container) \
- for (iter_type iter = (container) . iterator(); iter.has_next(); iter.next())
#endif
-
struct exec_list {
struct exec_node *head;
struct exec_node *tail;
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). */
- 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_list)
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
*/
*/
source->make_empty();
}
+#endif
+};
- exec_list_iterator iterator()
- {
- return exec_list_iterator(head);
- }
- exec_list_iterator iterator() const
- {
- return exec_list_iterator((exec_node *) head);
- }
+#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. If you insert
- * new nodes before the current node, they will be processed next.
- *
- * \note
- * The extra test for \c __node being \c NULL is required because after the
- * iteration \c __prev coupld be the last node in the list. The loop increment
- * then causes \c __prev to point to the sentinal and \c __node to be \c NULL.
+ * This version is safe even if the current node is removed.
*/
-#define foreach_list_safe(__node, __list) \
- for (exec_node * __prev = (exec_node *) (__list), * __node = (__list)->head \
- ; __node != NULL && (__node)->next != NULL \
- ; __prev = (__prev)->next, __node = (__prev)->next)
+#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