X-Git-Url: https://git.libre-soc.org/?a=blobdiff_plain;f=src%2Fglsl%2Flist.h;h=1d46365faec6d931d68c0314f1459d45230690ed;hb=213b9004a6ee033a16af3dcd187aa68b56c39858;hp=b5a413dc51105e2980ab9abadc13c99dc6980c9f;hpb=c44556317abf77ca6e344c79d119c91bebe25c8c;p=mesa.git diff --git a/src/glsl/list.h b/src/glsl/list.h index b5a413dc511..1d46365faec 100644 --- a/src/glsl/list.h +++ b/src/glsl/list.h @@ -25,28 +25,28 @@ * \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. @@ -66,37 +66,33 @@ #ifndef __cplusplus #include -#include -#else -extern "C" { -#include -} #endif - #include +#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) @@ -167,17 +163,34 @@ struct exec_node { } /** - * 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; } @@ -272,23 +285,23 @@ struct exec_list { 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() @@ -309,7 +322,7 @@ struct 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 @@ -366,6 +379,23 @@ struct exec_list { 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 */ @@ -421,6 +451,31 @@ struct exec_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 \