diff options
author | Eric Anholt <eric@anholt.net> | 2010-06-24 15:47:38 -0700 |
---|---|---|
committer | Eric Anholt <eric@anholt.net> | 2010-06-24 15:47:40 -0700 |
commit | bcc13b74443137043e8a34f8cb64a5add0d8af93 (patch) | |
tree | 5f4e003dceb61c091ce0fcb8c5cf9d91bec033c0 /src/glsl/list.h | |
parent | 84341f4b2014810b2964230384fe76338be1d78e (diff) | |
parent | e5cf3aadb8d57dcc70b597092ecac276042f73cb (diff) |
Merge branch 'glsl2-head' into glsl2
This brings in the standalone GLSL compiler that we are planning on
replacing the existing Mesa GLSL compiler. It currently targets GLSL
1.20 and the Mesa IR.
Diffstat (limited to 'src/glsl/list.h')
-rw-r--r-- | src/glsl/list.h | 403 |
1 files changed, 403 insertions, 0 deletions
diff --git a/src/glsl/list.h b/src/glsl/list.h new file mode 100644 index 0000000000..7732d66d7a --- /dev/null +++ b/src/glsl/list.h @@ -0,0 +1,403 @@ +/* + * 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 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 + * \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. + * + * 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 + * 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. + * - 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 + * pointer is \b always \c NULL. + * - A \c tail_prev pointer that represents the \c prev pointer of the + * tail sentinal 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 <ian.d.romanick@intel.com> + */ + +#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; + } + + /** + * Is this the sentinal at the tail of the list? + */ + bool is_tail_sentinal() const + { + return this->next == NULL; + } + + /** + * Is this the sentinal at the head of the list? + */ + bool is_head_sentinal() 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 + 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 sentinal 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(); + } + } + + exec_list_iterator iterator() + { + return exec_list_iterator(head); + } + + exec_list_iterator iterator() const + { + return exec_list_iterator((exec_node *) head); + } +#endif +}; + +#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 */ |