diff options
Diffstat (limited to 'src/glsl/list.h')
-rw-r--r-- | src/glsl/list.h | 465 |
1 files changed, 465 insertions, 0 deletions
diff --git a/src/glsl/list.h b/src/glsl/list.h new file mode 100644 index 00000000000..a70b79d571f --- /dev/null +++ b/src/glsl/list.h @@ -0,0 +1,465 @@ +/* + * Copyright © 2008, 2010 Intel Corporation + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ + +/** + * \file list.h + * \brief Doubly-linked list abstract container type. + * + * 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 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 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 sentinel node. + * - A \c tail pointer that represents the \c prev pointer of the head + * 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 sentinel node. + * + * Therefore, if \c head->next is \c NULL or \c tail_prev->prev is \c NULL, + * the list is empty. + * + * 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. + * + * http://www.natami.net/dev/Libraries_Manual_guide/node02D7.html + * + * \author Ian Romanick <[email protected]> + */ + +#pragma once +#ifndef LIST_CONTAINER_H +#define LIST_CONTAINER_H + +#ifndef __cplusplus +#include <stddef.h> +#include <talloc.h> +#else +extern "C" { +#include <talloc.h> +} +#endif + +#include <assert.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); + } + + exec_node() : next(NULL), prev(NULL) + { + /* empty */ + } + + const exec_node *get_next() const + { + return next; + } + + exec_node *get_next() + { + return next; + } + + const exec_node *get_prev() const + { + return prev; + } + + exec_node *get_prev() + { + return prev; + } + + void remove() + { + next->prev = prev; + prev->next = next; + next = NULL; + prev = NULL; + } + + /** + * Link a node with itself + * + * This creates a sort of degenerate list that is occasionally useful. + */ + void self_link() + { + next = this; + prev = this; + } + + /** + * Insert a node in the list after the current node + */ + void insert_after(exec_node *after) + { + after->next = this->next; + after->prev = this; + + this->next->prev = after; + this->next = after; + } + /** + * Insert a node in the list before the current node + */ + void insert_before(exec_node *before) + { + before->next = this; + before->prev = this->prev; + + this->prev->next = before; + this->prev = 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_sentinel() const + { + return this->next == NULL; + } + + /** + * Is this the sentinel at the head of the list? + */ + bool is_head_sentinel() const + { + return this->prev == NULL; + } +#endif +}; + + +#ifdef __cplusplus +/* This macro will not work correctly if `t' uses virtual inheritance. If you + * are using virtual inheritance, you deserve a slow and painful death. Enjoy! + */ +#define exec_list_offsetof(t, f, p) \ + (((char *) &((t *) p)->f) - ((char *) p)) +#else +#define exec_list_offsetof(t, f, p) offsetof(t, f) +#endif + +/** + * Get a pointer to the structure containing an exec_node + * + * Given a pointer to an \c exec_node embedded in a structure, get a pointer to + * the containing structure. + * + * \param type Base type of the structure containing the node + * \param node Pointer to the \c exec_node + * \param field Name of the field in \c type that is the embedded \c exec_node + */ +#define exec_node_data(type, node, field) \ + ((type *) (((char *) node) - exec_list_offsetof(type, field, node))) + +#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); + } + + exec_list() + { + make_empty(); + } + + void make_empty() + { + head = (exec_node *) & tail; + tail = NULL; + tail_pred = (exec_node *) & head; + } + + bool 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; + } + + const exec_node *get_head() const + { + return !is_empty() ? head : NULL; + } + + exec_node *get_head() + { + return !is_empty() ? head : NULL; + } + + const exec_node *get_tail() const + { + return !is_empty() ? tail_pred : NULL; + } + + exec_node *get_tail() + { + return !is_empty() ? tail_pred : NULL; + } + + void push_head(exec_node *n) + { + n->next = head; + n->prev = (exec_node *) &head; + + n->next->prev = n; + head = n; + } + + void push_tail(exec_node *n) + { + n->next = (exec_node *) &tail; + n->prev = tail_pred; + + n->prev->next = n; + tail_pred = n; + } + + void 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; + } + + /** + * Move all of the nodes from this list to the target list + */ + void 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(); + } + } + + /** + * 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); + } + + exec_list_iterator iterator() const + { + return exec_list_iterator((exec_node *) head); + } +#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) + +#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)) + +#endif /* LIST_CONTAINER_H */ |