17e4ce719238e910043325567e941e4ea9a953264Ian Romanick/* 27e4ce719238e910043325567e941e4ea9a953264Ian Romanick * Copyright © 2008, 2010 Intel Corporation 37e4ce719238e910043325567e941e4ea9a953264Ian Romanick * 47e4ce719238e910043325567e941e4ea9a953264Ian Romanick * Permission is hereby granted, free of charge, to any person obtaining a 57e4ce719238e910043325567e941e4ea9a953264Ian Romanick * copy of this software and associated documentation files (the "Software"), 67e4ce719238e910043325567e941e4ea9a953264Ian Romanick * to deal in the Software without restriction, including without limitation 77e4ce719238e910043325567e941e4ea9a953264Ian Romanick * the rights to use, copy, modify, merge, publish, distribute, sublicense, 87e4ce719238e910043325567e941e4ea9a953264Ian Romanick * and/or sell copies of the Software, and to permit persons to whom the 97e4ce719238e910043325567e941e4ea9a953264Ian Romanick * Software is furnished to do so, subject to the following conditions: 107e4ce719238e910043325567e941e4ea9a953264Ian Romanick * 117e4ce719238e910043325567e941e4ea9a953264Ian Romanick * The above copyright notice and this permission notice (including the next 127e4ce719238e910043325567e941e4ea9a953264Ian Romanick * paragraph) shall be included in all copies or substantial portions of the 137e4ce719238e910043325567e941e4ea9a953264Ian Romanick * Software. 147e4ce719238e910043325567e941e4ea9a953264Ian Romanick * 157e4ce719238e910043325567e941e4ea9a953264Ian Romanick * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 167e4ce719238e910043325567e941e4ea9a953264Ian Romanick * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 177e4ce719238e910043325567e941e4ea9a953264Ian Romanick * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 187e4ce719238e910043325567e941e4ea9a953264Ian Romanick * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 197e4ce719238e910043325567e941e4ea9a953264Ian Romanick * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 207e4ce719238e910043325567e941e4ea9a953264Ian Romanick * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 217e4ce719238e910043325567e941e4ea9a953264Ian Romanick * DEALINGS IN THE SOFTWARE. 227e4ce719238e910043325567e941e4ea9a953264Ian Romanick */ 237e4ce719238e910043325567e941e4ea9a953264Ian Romanick 247e4ce719238e910043325567e941e4ea9a953264Ian Romanick/** 257e4ce719238e910043325567e941e4ea9a953264Ian Romanick * \file list.h 267e4ce719238e910043325567e941e4ea9a953264Ian Romanick * \brief Doubly-linked list abstract container type. 277e4ce719238e910043325567e941e4ea9a953264Ian Romanick * 2862c4763b707e2227409f81b09dd5cf6e4410ea6aEric Anholt * Each doubly-linked list has a sentinel head and tail node. These nodes 2962c4763b707e2227409f81b09dd5cf6e4410ea6aEric Anholt * contain no data. The head sentinel can be identified by its \c prev 3062c4763b707e2227409f81b09dd5cf6e4410ea6aEric Anholt * pointer being \c NULL. The tail sentinel can be identified by its 317e4ce719238e910043325567e941e4ea9a953264Ian Romanick * \c next pointer being \c NULL. 327e4ce719238e910043325567e941e4ea9a953264Ian Romanick * 3362c4763b707e2227409f81b09dd5cf6e4410ea6aEric Anholt * A list is empty if either the head sentinel's \c next pointer points to the 3462c4763b707e2227409f81b09dd5cf6e4410ea6aEric Anholt * tail sentinel or the tail sentinel's \c prev poiner points to the head 3562c4763b707e2227409f81b09dd5cf6e4410ea6aEric Anholt * sentinel. 367e4ce719238e910043325567e941e4ea9a953264Ian Romanick * 377e4ce719238e910043325567e941e4ea9a953264Ian Romanick * Instead of tracking two separate \c node structures and a \c list structure 3862c4763b707e2227409f81b09dd5cf6e4410ea6aEric Anholt * that points to them, the sentinel nodes are in a single structure. Noting 3962c4763b707e2227409f81b09dd5cf6e4410ea6aEric Anholt * that each sentinel node always has one \c NULL pointer, the \c NULL 407e4ce719238e910043325567e941e4ea9a953264Ian Romanick * pointers occupy the same memory location. In the \c list structure 417e4ce719238e910043325567e941e4ea9a953264Ian Romanick * contains a the following: 427e4ce719238e910043325567e941e4ea9a953264Ian Romanick * 437e4ce719238e910043325567e941e4ea9a953264Ian Romanick * - A \c head pointer that represents the \c next pointer of the 4462c4763b707e2227409f81b09dd5cf6e4410ea6aEric Anholt * head sentinel node. 457e4ce719238e910043325567e941e4ea9a953264Ian Romanick * - A \c tail pointer that represents the \c prev pointer of the head 4662c4763b707e2227409f81b09dd5cf6e4410ea6aEric Anholt * sentinel node and the \c next pointer of the tail sentinel node. This 477e4ce719238e910043325567e941e4ea9a953264Ian Romanick * pointer is \b always \c NULL. 487e4ce719238e910043325567e941e4ea9a953264Ian Romanick * - A \c tail_prev pointer that represents the \c prev pointer of the 4962c4763b707e2227409f81b09dd5cf6e4410ea6aEric Anholt * tail sentinel node. 507e4ce719238e910043325567e941e4ea9a953264Ian Romanick * 517e4ce719238e910043325567e941e4ea9a953264Ian Romanick * Therefore, if \c head->next is \c NULL or \c tail_prev->prev is \c NULL, 527e4ce719238e910043325567e941e4ea9a953264Ian Romanick * the list is empty. 537e4ce719238e910043325567e941e4ea9a953264Ian Romanick * 547e4ce719238e910043325567e941e4ea9a953264Ian Romanick * To anyone familiar with "exec lists" on the Amiga, this structure should 557e4ce719238e910043325567e941e4ea9a953264Ian Romanick * be immediately recognizable. See the following link for the original Amiga 567e4ce719238e910043325567e941e4ea9a953264Ian Romanick * operating system documentation on the subject. 577e4ce719238e910043325567e941e4ea9a953264Ian Romanick * 587e4ce719238e910043325567e941e4ea9a953264Ian Romanick * http://www.natami.net/dev/Libraries_Manual_guide/node02D7.html 597e4ce719238e910043325567e941e4ea9a953264Ian Romanick * 607e4ce719238e910043325567e941e4ea9a953264Ian Romanick * \author Ian Romanick <ian.d.romanick@intel.com> 617e4ce719238e910043325567e941e4ea9a953264Ian Romanick */ 627e4ce719238e910043325567e941e4ea9a953264Ian Romanick 637e4ce719238e910043325567e941e4ea9a953264Ian Romanick#pragma once 647e4ce719238e910043325567e941e4ea9a953264Ian Romanick#ifndef LIST_CONTAINER_H 657e4ce719238e910043325567e941e4ea9a953264Ian Romanick#define LIST_CONTAINER_H 667e4ce719238e910043325567e941e4ea9a953264Ian Romanick 6743bfc2b6b5477b24d831f49a6ab2123ce95ba747Ian Romanick#ifndef __cplusplus 6843bfc2b6b5477b24d831f49a6ab2123ce95ba747Ian Romanick#include <stddef.h> 6943bfc2b6b5477b24d831f49a6ab2123ce95ba747Ian Romanick#endif 707e4ce719238e910043325567e941e4ea9a953264Ian Romanick#include <assert.h> 717e4ce719238e910043325567e941e4ea9a953264Ian Romanick 72d3073f58c17d8675a2ecdd5dfa83e5520c78e1a8Kenneth Graunke#include "ralloc.h" 73d3073f58c17d8675a2ecdd5dfa83e5520c78e1a8Kenneth Graunke 747e4ce719238e910043325567e941e4ea9a953264Ian Romanickstruct exec_node { 757e4ce719238e910043325567e941e4ea9a953264Ian Romanick struct exec_node *next; 767e4ce719238e910043325567e941e4ea9a953264Ian Romanick struct exec_node *prev; 777e4ce719238e910043325567e941e4ea9a953264Ian Romanick 787e4ce719238e910043325567e941e4ea9a953264Ian Romanick#ifdef __cplusplus 79d3073f58c17d8675a2ecdd5dfa83e5520c78e1a8Kenneth Graunke /* Callers of this ralloc-based new need not call delete. It's 80d3073f58c17d8675a2ecdd5dfa83e5520c78e1a8Kenneth Graunke * easier to just ralloc_free 'ctx' (or any of its ancestors). */ 811660a2954797e056caba319c5d6c70b0d4be22feCarl Worth static void* operator new(size_t size, void *ctx) 821660a2954797e056caba319c5d6c70b0d4be22feCarl Worth { 831660a2954797e056caba319c5d6c70b0d4be22feCarl Worth void *node; 841660a2954797e056caba319c5d6c70b0d4be22feCarl Worth 85d3073f58c17d8675a2ecdd5dfa83e5520c78e1a8Kenneth Graunke node = ralloc_size(ctx, size); 861660a2954797e056caba319c5d6c70b0d4be22feCarl Worth assert(node != NULL); 871660a2954797e056caba319c5d6c70b0d4be22feCarl Worth 881660a2954797e056caba319c5d6c70b0d4be22feCarl Worth return node; 891660a2954797e056caba319c5d6c70b0d4be22feCarl Worth } 901660a2954797e056caba319c5d6c70b0d4be22feCarl Worth 911660a2954797e056caba319c5d6c70b0d4be22feCarl Worth /* If the user *does* call delete, that's OK, we will just 92d3073f58c17d8675a2ecdd5dfa83e5520c78e1a8Kenneth Graunke * ralloc_free in that case. */ 931660a2954797e056caba319c5d6c70b0d4be22feCarl Worth static void operator delete(void *node) 941660a2954797e056caba319c5d6c70b0d4be22feCarl Worth { 95d3073f58c17d8675a2ecdd5dfa83e5520c78e1a8Kenneth Graunke ralloc_free(node); 961660a2954797e056caba319c5d6c70b0d4be22feCarl Worth } 971660a2954797e056caba319c5d6c70b0d4be22feCarl Worth 987e4ce719238e910043325567e941e4ea9a953264Ian Romanick exec_node() : next(NULL), prev(NULL) 997e4ce719238e910043325567e941e4ea9a953264Ian Romanick { 1007e4ce719238e910043325567e941e4ea9a953264Ian Romanick /* empty */ 1017e4ce719238e910043325567e941e4ea9a953264Ian Romanick } 1027e4ce719238e910043325567e941e4ea9a953264Ian Romanick 1037e4ce719238e910043325567e941e4ea9a953264Ian Romanick const exec_node *get_next() const 1047e4ce719238e910043325567e941e4ea9a953264Ian Romanick { 1057e4ce719238e910043325567e941e4ea9a953264Ian Romanick return next; 1067e4ce719238e910043325567e941e4ea9a953264Ian Romanick } 1077e4ce719238e910043325567e941e4ea9a953264Ian Romanick 1087e4ce719238e910043325567e941e4ea9a953264Ian Romanick exec_node *get_next() 1097e4ce719238e910043325567e941e4ea9a953264Ian Romanick { 1107e4ce719238e910043325567e941e4ea9a953264Ian Romanick return next; 1117e4ce719238e910043325567e941e4ea9a953264Ian Romanick } 1127e4ce719238e910043325567e941e4ea9a953264Ian Romanick 1137e4ce719238e910043325567e941e4ea9a953264Ian Romanick const exec_node *get_prev() const 1147e4ce719238e910043325567e941e4ea9a953264Ian Romanick { 1157e4ce719238e910043325567e941e4ea9a953264Ian Romanick return prev; 1167e4ce719238e910043325567e941e4ea9a953264Ian Romanick } 1177e4ce719238e910043325567e941e4ea9a953264Ian Romanick 1187e4ce719238e910043325567e941e4ea9a953264Ian Romanick exec_node *get_prev() 1197e4ce719238e910043325567e941e4ea9a953264Ian Romanick { 1207e4ce719238e910043325567e941e4ea9a953264Ian Romanick return prev; 1217e4ce719238e910043325567e941e4ea9a953264Ian Romanick } 1227e4ce719238e910043325567e941e4ea9a953264Ian Romanick 1237e4ce719238e910043325567e941e4ea9a953264Ian Romanick void remove() 1247e4ce719238e910043325567e941e4ea9a953264Ian Romanick { 1257e4ce719238e910043325567e941e4ea9a953264Ian Romanick next->prev = prev; 1267e4ce719238e910043325567e941e4ea9a953264Ian Romanick prev->next = next; 1277e4ce719238e910043325567e941e4ea9a953264Ian Romanick next = NULL; 1287e4ce719238e910043325567e941e4ea9a953264Ian Romanick prev = NULL; 1297e4ce719238e910043325567e941e4ea9a953264Ian Romanick } 1307e4ce719238e910043325567e941e4ea9a953264Ian Romanick 1317e4ce719238e910043325567e941e4ea9a953264Ian Romanick /** 1327e4ce719238e910043325567e941e4ea9a953264Ian Romanick * Link a node with itself 1337e4ce719238e910043325567e941e4ea9a953264Ian Romanick * 1347e4ce719238e910043325567e941e4ea9a953264Ian Romanick * This creates a sort of degenerate list that is occasionally useful. 1357e4ce719238e910043325567e941e4ea9a953264Ian Romanick */ 1367e4ce719238e910043325567e941e4ea9a953264Ian Romanick void self_link() 1377e4ce719238e910043325567e941e4ea9a953264Ian Romanick { 1387e4ce719238e910043325567e941e4ea9a953264Ian Romanick next = this; 1397e4ce719238e910043325567e941e4ea9a953264Ian Romanick prev = this; 1407e4ce719238e910043325567e941e4ea9a953264Ian Romanick } 1417e4ce719238e910043325567e941e4ea9a953264Ian Romanick 1427e4ce719238e910043325567e941e4ea9a953264Ian Romanick /** 1437e4ce719238e910043325567e941e4ea9a953264Ian Romanick * Insert a node in the list after the current node 1447e4ce719238e910043325567e941e4ea9a953264Ian Romanick */ 1457e4ce719238e910043325567e941e4ea9a953264Ian Romanick void insert_after(exec_node *after) 1467e4ce719238e910043325567e941e4ea9a953264Ian Romanick { 1477e4ce719238e910043325567e941e4ea9a953264Ian Romanick after->next = this->next; 1487e4ce719238e910043325567e941e4ea9a953264Ian Romanick after->prev = this; 1497e4ce719238e910043325567e941e4ea9a953264Ian Romanick 1507e4ce719238e910043325567e941e4ea9a953264Ian Romanick this->next->prev = after; 1517e4ce719238e910043325567e941e4ea9a953264Ian Romanick this->next = after; 1527e4ce719238e910043325567e941e4ea9a953264Ian Romanick } 153cad9766118d269725ef33b4e9588d674d5225010Eric Anholt /** 154cad9766118d269725ef33b4e9588d674d5225010Eric Anholt * Insert a node in the list before the current node 155cad9766118d269725ef33b4e9588d674d5225010Eric Anholt */ 156cad9766118d269725ef33b4e9588d674d5225010Eric Anholt void insert_before(exec_node *before) 157cad9766118d269725ef33b4e9588d674d5225010Eric Anholt { 158cad9766118d269725ef33b4e9588d674d5225010Eric Anholt before->next = this; 159cad9766118d269725ef33b4e9588d674d5225010Eric Anholt before->prev = this->prev; 160cad9766118d269725ef33b4e9588d674d5225010Eric Anholt 161cad9766118d269725ef33b4e9588d674d5225010Eric Anholt this->prev->next = before; 162cad9766118d269725ef33b4e9588d674d5225010Eric Anholt this->prev = before; 163cad9766118d269725ef33b4e9588d674d5225010Eric Anholt } 16479082b8aca130ecdcaa1167a9961c16fc620f423Ian Romanick 16579082b8aca130ecdcaa1167a9961c16fc620f423Ian Romanick /** 16679082b8aca130ecdcaa1167a9961c16fc620f423Ian Romanick * Insert another list in the list before the current node 16779082b8aca130ecdcaa1167a9961c16fc620f423Ian Romanick */ 168a5fd0396726d0142af364e3ea8ade470ff6c0559Brian Paul void insert_before(struct exec_list *before); 16979082b8aca130ecdcaa1167a9961c16fc620f423Ian Romanick 1701fdcdb2dca97cdf4b8f4790aa66587ff3e89e526Kenneth Graunke /** 1711fdcdb2dca97cdf4b8f4790aa66587ff3e89e526Kenneth Graunke * Replace the current node with the given node. 1721fdcdb2dca97cdf4b8f4790aa66587ff3e89e526Kenneth Graunke */ 1731fdcdb2dca97cdf4b8f4790aa66587ff3e89e526Kenneth Graunke void replace_with(exec_node *replacement) 1741fdcdb2dca97cdf4b8f4790aa66587ff3e89e526Kenneth Graunke { 1751fdcdb2dca97cdf4b8f4790aa66587ff3e89e526Kenneth Graunke replacement->prev = this->prev; 1761fdcdb2dca97cdf4b8f4790aa66587ff3e89e526Kenneth Graunke replacement->next = this->next; 1771fdcdb2dca97cdf4b8f4790aa66587ff3e89e526Kenneth Graunke 1781fdcdb2dca97cdf4b8f4790aa66587ff3e89e526Kenneth Graunke this->prev->next = replacement; 1791fdcdb2dca97cdf4b8f4790aa66587ff3e89e526Kenneth Graunke this->next->prev = replacement; 1801fdcdb2dca97cdf4b8f4790aa66587ff3e89e526Kenneth Graunke } 1817c40a3205439e406d54feca6cd0a09fda091522cIan Romanick 1827c40a3205439e406d54feca6cd0a09fda091522cIan Romanick /** 18362c4763b707e2227409f81b09dd5cf6e4410ea6aEric Anholt * Is this the sentinel at the tail of the list? 1847c40a3205439e406d54feca6cd0a09fda091522cIan Romanick */ 18562c4763b707e2227409f81b09dd5cf6e4410ea6aEric Anholt bool is_tail_sentinel() const 1867c40a3205439e406d54feca6cd0a09fda091522cIan Romanick { 1877c40a3205439e406d54feca6cd0a09fda091522cIan Romanick return this->next == NULL; 1887c40a3205439e406d54feca6cd0a09fda091522cIan Romanick } 1897c40a3205439e406d54feca6cd0a09fda091522cIan Romanick 1907c40a3205439e406d54feca6cd0a09fda091522cIan Romanick /** 19162c4763b707e2227409f81b09dd5cf6e4410ea6aEric Anholt * Is this the sentinel at the head of the list? 1927c40a3205439e406d54feca6cd0a09fda091522cIan Romanick */ 19362c4763b707e2227409f81b09dd5cf6e4410ea6aEric Anholt bool is_head_sentinel() const 1947c40a3205439e406d54feca6cd0a09fda091522cIan Romanick { 1957c40a3205439e406d54feca6cd0a09fda091522cIan Romanick return this->prev == NULL; 1967c40a3205439e406d54feca6cd0a09fda091522cIan Romanick } 1977e4ce719238e910043325567e941e4ea9a953264Ian Romanick#endif 1987e4ce719238e910043325567e941e4ea9a953264Ian Romanick}; 1997e4ce719238e910043325567e941e4ea9a953264Ian Romanick 20043bfc2b6b5477b24d831f49a6ab2123ce95ba747Ian Romanick 20143bfc2b6b5477b24d831f49a6ab2123ce95ba747Ian Romanick#ifdef __cplusplus 20243bfc2b6b5477b24d831f49a6ab2123ce95ba747Ian Romanick/* This macro will not work correctly if `t' uses virtual inheritance. If you 20343bfc2b6b5477b24d831f49a6ab2123ce95ba747Ian Romanick * are using virtual inheritance, you deserve a slow and painful death. Enjoy! 20443bfc2b6b5477b24d831f49a6ab2123ce95ba747Ian Romanick */ 20543bfc2b6b5477b24d831f49a6ab2123ce95ba747Ian Romanick#define exec_list_offsetof(t, f, p) \ 20643bfc2b6b5477b24d831f49a6ab2123ce95ba747Ian Romanick (((char *) &((t *) p)->f) - ((char *) p)) 20743bfc2b6b5477b24d831f49a6ab2123ce95ba747Ian Romanick#else 20843bfc2b6b5477b24d831f49a6ab2123ce95ba747Ian Romanick#define exec_list_offsetof(t, f, p) offsetof(t, f) 20943bfc2b6b5477b24d831f49a6ab2123ce95ba747Ian Romanick#endif 21043bfc2b6b5477b24d831f49a6ab2123ce95ba747Ian Romanick 21143bfc2b6b5477b24d831f49a6ab2123ce95ba747Ian Romanick/** 21243bfc2b6b5477b24d831f49a6ab2123ce95ba747Ian Romanick * Get a pointer to the structure containing an exec_node 21343bfc2b6b5477b24d831f49a6ab2123ce95ba747Ian Romanick * 21443bfc2b6b5477b24d831f49a6ab2123ce95ba747Ian Romanick * Given a pointer to an \c exec_node embedded in a structure, get a pointer to 21543bfc2b6b5477b24d831f49a6ab2123ce95ba747Ian Romanick * the containing structure. 21643bfc2b6b5477b24d831f49a6ab2123ce95ba747Ian Romanick * 21743bfc2b6b5477b24d831f49a6ab2123ce95ba747Ian Romanick * \param type Base type of the structure containing the node 21843bfc2b6b5477b24d831f49a6ab2123ce95ba747Ian Romanick * \param node Pointer to the \c exec_node 21943bfc2b6b5477b24d831f49a6ab2123ce95ba747Ian Romanick * \param field Name of the field in \c type that is the embedded \c exec_node 22043bfc2b6b5477b24d831f49a6ab2123ce95ba747Ian Romanick */ 22143bfc2b6b5477b24d831f49a6ab2123ce95ba747Ian Romanick#define exec_node_data(type, node, field) \ 22243bfc2b6b5477b24d831f49a6ab2123ce95ba747Ian Romanick ((type *) (((char *) node) - exec_list_offsetof(type, field, node))) 22343bfc2b6b5477b24d831f49a6ab2123ce95ba747Ian Romanick 2247e4ce719238e910043325567e941e4ea9a953264Ian Romanick#ifdef __cplusplus 2257e4ce719238e910043325567e941e4ea9a953264Ian Romanickstruct exec_node; 2267e4ce719238e910043325567e941e4ea9a953264Ian Romanick 2277e4ce719238e910043325567e941e4ea9a953264Ian Romanickclass iterator { 2287e4ce719238e910043325567e941e4ea9a953264Ian Romanickpublic: 2297e4ce719238e910043325567e941e4ea9a953264Ian Romanick void next() 2307e4ce719238e910043325567e941e4ea9a953264Ian Romanick { 2317e4ce719238e910043325567e941e4ea9a953264Ian Romanick } 2327e4ce719238e910043325567e941e4ea9a953264Ian Romanick 2337e4ce719238e910043325567e941e4ea9a953264Ian Romanick void *get() 2347e4ce719238e910043325567e941e4ea9a953264Ian Romanick { 2357e4ce719238e910043325567e941e4ea9a953264Ian Romanick return NULL; 2367e4ce719238e910043325567e941e4ea9a953264Ian Romanick } 2377e4ce719238e910043325567e941e4ea9a953264Ian Romanick 2387e4ce719238e910043325567e941e4ea9a953264Ian Romanick bool has_next() const 2397e4ce719238e910043325567e941e4ea9a953264Ian Romanick { 2407e4ce719238e910043325567e941e4ea9a953264Ian Romanick return false; 2417e4ce719238e910043325567e941e4ea9a953264Ian Romanick } 2427e4ce719238e910043325567e941e4ea9a953264Ian Romanick}; 2437e4ce719238e910043325567e941e4ea9a953264Ian Romanick 2447e4ce719238e910043325567e941e4ea9a953264Ian Romanickclass exec_list_iterator : public iterator { 2457e4ce719238e910043325567e941e4ea9a953264Ian Romanickpublic: 2467e4ce719238e910043325567e941e4ea9a953264Ian Romanick exec_list_iterator(exec_node *n) : node(n), _next(n->next) 2477e4ce719238e910043325567e941e4ea9a953264Ian Romanick { 2487e4ce719238e910043325567e941e4ea9a953264Ian Romanick /* empty */ 2497e4ce719238e910043325567e941e4ea9a953264Ian Romanick } 2507e4ce719238e910043325567e941e4ea9a953264Ian Romanick 2517e4ce719238e910043325567e941e4ea9a953264Ian Romanick void next() 2527e4ce719238e910043325567e941e4ea9a953264Ian Romanick { 2537e4ce719238e910043325567e941e4ea9a953264Ian Romanick node = _next; 2547e4ce719238e910043325567e941e4ea9a953264Ian Romanick _next = node->next; 2557e4ce719238e910043325567e941e4ea9a953264Ian Romanick } 2567e4ce719238e910043325567e941e4ea9a953264Ian Romanick 2577e4ce719238e910043325567e941e4ea9a953264Ian Romanick void remove() 2587e4ce719238e910043325567e941e4ea9a953264Ian Romanick { 2597e4ce719238e910043325567e941e4ea9a953264Ian Romanick node->remove(); 2607e4ce719238e910043325567e941e4ea9a953264Ian Romanick } 2617e4ce719238e910043325567e941e4ea9a953264Ian Romanick 2627e4ce719238e910043325567e941e4ea9a953264Ian Romanick exec_node *get() 2637e4ce719238e910043325567e941e4ea9a953264Ian Romanick { 2647e4ce719238e910043325567e941e4ea9a953264Ian Romanick return node; 2657e4ce719238e910043325567e941e4ea9a953264Ian Romanick } 2667e4ce719238e910043325567e941e4ea9a953264Ian Romanick 2677e4ce719238e910043325567e941e4ea9a953264Ian Romanick bool has_next() const 2687e4ce719238e910043325567e941e4ea9a953264Ian Romanick { 2697e4ce719238e910043325567e941e4ea9a953264Ian Romanick return _next != NULL; 2707e4ce719238e910043325567e941e4ea9a953264Ian Romanick } 2717e4ce719238e910043325567e941e4ea9a953264Ian Romanick 2727e4ce719238e910043325567e941e4ea9a953264Ian Romanickprivate: 2737e4ce719238e910043325567e941e4ea9a953264Ian Romanick exec_node *node; 2747e4ce719238e910043325567e941e4ea9a953264Ian Romanick exec_node *_next; 2757e4ce719238e910043325567e941e4ea9a953264Ian Romanick}; 2767e4ce719238e910043325567e941e4ea9a953264Ian Romanick 2777e4ce719238e910043325567e941e4ea9a953264Ian Romanick#define foreach_iter(iter_type, iter, container) \ 278605ff69b0dbcf3206e4c9af50732083be0c908deIan Romanick for (iter_type iter = (container) . iterator(); iter.has_next(); iter.next()) 2797e4ce719238e910043325567e941e4ea9a953264Ian Romanick#endif 2807e4ce719238e910043325567e941e4ea9a953264Ian Romanick 2817e4ce719238e910043325567e941e4ea9a953264Ian Romanick 2827e4ce719238e910043325567e941e4ea9a953264Ian Romanickstruct exec_list { 2837e4ce719238e910043325567e941e4ea9a953264Ian Romanick struct exec_node *head; 2847e4ce719238e910043325567e941e4ea9a953264Ian Romanick struct exec_node *tail; 2857e4ce719238e910043325567e941e4ea9a953264Ian Romanick struct exec_node *tail_pred; 2867e4ce719238e910043325567e941e4ea9a953264Ian Romanick 2877e4ce719238e910043325567e941e4ea9a953264Ian Romanick#ifdef __cplusplus 288d3073f58c17d8675a2ecdd5dfa83e5520c78e1a8Kenneth Graunke /* Callers of this ralloc-based new need not call delete. It's 289d3073f58c17d8675a2ecdd5dfa83e5520c78e1a8Kenneth Graunke * easier to just ralloc_free 'ctx' (or any of its ancestors). */ 29016b68b1952d0da14b9ce8306efa64988ce46b4b7Eric Anholt static void* operator new(size_t size, void *ctx) 29116b68b1952d0da14b9ce8306efa64988ce46b4b7Eric Anholt { 29216b68b1952d0da14b9ce8306efa64988ce46b4b7Eric Anholt void *node; 29316b68b1952d0da14b9ce8306efa64988ce46b4b7Eric Anholt 294d3073f58c17d8675a2ecdd5dfa83e5520c78e1a8Kenneth Graunke node = ralloc_size(ctx, size); 29516b68b1952d0da14b9ce8306efa64988ce46b4b7Eric Anholt assert(node != NULL); 29616b68b1952d0da14b9ce8306efa64988ce46b4b7Eric Anholt 29716b68b1952d0da14b9ce8306efa64988ce46b4b7Eric Anholt return node; 29816b68b1952d0da14b9ce8306efa64988ce46b4b7Eric Anholt } 29916b68b1952d0da14b9ce8306efa64988ce46b4b7Eric Anholt 30016b68b1952d0da14b9ce8306efa64988ce46b4b7Eric Anholt /* If the user *does* call delete, that's OK, we will just 301d3073f58c17d8675a2ecdd5dfa83e5520c78e1a8Kenneth Graunke * ralloc_free in that case. */ 30216b68b1952d0da14b9ce8306efa64988ce46b4b7Eric Anholt static void operator delete(void *node) 30316b68b1952d0da14b9ce8306efa64988ce46b4b7Eric Anholt { 304d3073f58c17d8675a2ecdd5dfa83e5520c78e1a8Kenneth Graunke ralloc_free(node); 30516b68b1952d0da14b9ce8306efa64988ce46b4b7Eric Anholt } 30616b68b1952d0da14b9ce8306efa64988ce46b4b7Eric Anholt 3077e4ce719238e910043325567e941e4ea9a953264Ian Romanick exec_list() 3087e4ce719238e910043325567e941e4ea9a953264Ian Romanick { 3097e4ce719238e910043325567e941e4ea9a953264Ian Romanick make_empty(); 3107e4ce719238e910043325567e941e4ea9a953264Ian Romanick } 3117e4ce719238e910043325567e941e4ea9a953264Ian Romanick 3127e4ce719238e910043325567e941e4ea9a953264Ian Romanick void make_empty() 3137e4ce719238e910043325567e941e4ea9a953264Ian Romanick { 3147e4ce719238e910043325567e941e4ea9a953264Ian Romanick head = (exec_node *) & tail; 3157e4ce719238e910043325567e941e4ea9a953264Ian Romanick tail = NULL; 3167e4ce719238e910043325567e941e4ea9a953264Ian Romanick tail_pred = (exec_node *) & head; 3177e4ce719238e910043325567e941e4ea9a953264Ian Romanick } 3187e4ce719238e910043325567e941e4ea9a953264Ian Romanick 3197e4ce719238e910043325567e941e4ea9a953264Ian Romanick bool is_empty() const 3207e4ce719238e910043325567e941e4ea9a953264Ian Romanick { 3217e4ce719238e910043325567e941e4ea9a953264Ian Romanick /* There are three ways to test whether a list is empty or not. 3227e4ce719238e910043325567e941e4ea9a953264Ian Romanick * 3237e4ce719238e910043325567e941e4ea9a953264Ian Romanick * - Check to see if the \c head points to the \c tail. 3247e4ce719238e910043325567e941e4ea9a953264Ian Romanick * - Check to see if the \c tail_pred points to the \c head. 32562c4763b707e2227409f81b09dd5cf6e4410ea6aEric Anholt * - Check to see if the \c head is the sentinel node by test whether its 3267e4ce719238e910043325567e941e4ea9a953264Ian Romanick * \c next pointer is \c NULL. 3277e4ce719238e910043325567e941e4ea9a953264Ian Romanick * 3287e4ce719238e910043325567e941e4ea9a953264Ian Romanick * The first two methods tend to generate better code on modern systems 3297e4ce719238e910043325567e941e4ea9a953264Ian Romanick * because they save a pointer dereference. 3307e4ce719238e910043325567e941e4ea9a953264Ian Romanick */ 3317e4ce719238e910043325567e941e4ea9a953264Ian Romanick return head == (exec_node *) &tail; 3327e4ce719238e910043325567e941e4ea9a953264Ian Romanick } 3337e4ce719238e910043325567e941e4ea9a953264Ian Romanick 3347e4ce719238e910043325567e941e4ea9a953264Ian Romanick const exec_node *get_head() const 3357e4ce719238e910043325567e941e4ea9a953264Ian Romanick { 3367e4ce719238e910043325567e941e4ea9a953264Ian Romanick return !is_empty() ? head : NULL; 3377e4ce719238e910043325567e941e4ea9a953264Ian Romanick } 3387e4ce719238e910043325567e941e4ea9a953264Ian Romanick 3397e4ce719238e910043325567e941e4ea9a953264Ian Romanick exec_node *get_head() 3407e4ce719238e910043325567e941e4ea9a953264Ian Romanick { 3417e4ce719238e910043325567e941e4ea9a953264Ian Romanick return !is_empty() ? head : NULL; 3427e4ce719238e910043325567e941e4ea9a953264Ian Romanick } 3437e4ce719238e910043325567e941e4ea9a953264Ian Romanick 3447e4ce719238e910043325567e941e4ea9a953264Ian Romanick const exec_node *get_tail() const 3457e4ce719238e910043325567e941e4ea9a953264Ian Romanick { 3467e4ce719238e910043325567e941e4ea9a953264Ian Romanick return !is_empty() ? tail_pred : NULL; 3477e4ce719238e910043325567e941e4ea9a953264Ian Romanick } 3487e4ce719238e910043325567e941e4ea9a953264Ian Romanick 3497e4ce719238e910043325567e941e4ea9a953264Ian Romanick exec_node *get_tail() 3507e4ce719238e910043325567e941e4ea9a953264Ian Romanick { 3517e4ce719238e910043325567e941e4ea9a953264Ian Romanick return !is_empty() ? tail_pred : NULL; 3527e4ce719238e910043325567e941e4ea9a953264Ian Romanick } 3537e4ce719238e910043325567e941e4ea9a953264Ian Romanick 3547e4ce719238e910043325567e941e4ea9a953264Ian Romanick void push_head(exec_node *n) 3557e4ce719238e910043325567e941e4ea9a953264Ian Romanick { 3567e4ce719238e910043325567e941e4ea9a953264Ian Romanick n->next = head; 3577e4ce719238e910043325567e941e4ea9a953264Ian Romanick n->prev = (exec_node *) &head; 3587e4ce719238e910043325567e941e4ea9a953264Ian Romanick 3597e4ce719238e910043325567e941e4ea9a953264Ian Romanick n->next->prev = n; 3607e4ce719238e910043325567e941e4ea9a953264Ian Romanick head = n; 3617e4ce719238e910043325567e941e4ea9a953264Ian Romanick } 3627e4ce719238e910043325567e941e4ea9a953264Ian Romanick 3637e4ce719238e910043325567e941e4ea9a953264Ian Romanick void push_tail(exec_node *n) 3647e4ce719238e910043325567e941e4ea9a953264Ian Romanick { 3657e4ce719238e910043325567e941e4ea9a953264Ian Romanick n->next = (exec_node *) &tail; 3667e4ce719238e910043325567e941e4ea9a953264Ian Romanick n->prev = tail_pred; 3677e4ce719238e910043325567e941e4ea9a953264Ian Romanick 3687e4ce719238e910043325567e941e4ea9a953264Ian Romanick n->prev->next = n; 3697e4ce719238e910043325567e941e4ea9a953264Ian Romanick tail_pred = n; 3707e4ce719238e910043325567e941e4ea9a953264Ian Romanick } 3717e4ce719238e910043325567e941e4ea9a953264Ian Romanick 3727e4ce719238e910043325567e941e4ea9a953264Ian Romanick void push_degenerate_list_at_head(exec_node *n) 3737e4ce719238e910043325567e941e4ea9a953264Ian Romanick { 3747e4ce719238e910043325567e941e4ea9a953264Ian Romanick assert(n->prev->next == n); 3757e4ce719238e910043325567e941e4ea9a953264Ian Romanick 3767e4ce719238e910043325567e941e4ea9a953264Ian Romanick n->prev->next = head; 3777e4ce719238e910043325567e941e4ea9a953264Ian Romanick head->prev = n->prev; 3787e4ce719238e910043325567e941e4ea9a953264Ian Romanick n->prev = (exec_node *) &head; 3797e4ce719238e910043325567e941e4ea9a953264Ian Romanick head = n; 3807e4ce719238e910043325567e941e4ea9a953264Ian Romanick } 3817e4ce719238e910043325567e941e4ea9a953264Ian Romanick 3827e4ce719238e910043325567e941e4ea9a953264Ian Romanick /** 38329eebe9a9a0486f12e33e2818c192ef683fdfedeIan Romanick * Remove the first node from a list and return it 38429eebe9a9a0486f12e33e2818c192ef683fdfedeIan Romanick * 38529eebe9a9a0486f12e33e2818c192ef683fdfedeIan Romanick * \return 38629eebe9a9a0486f12e33e2818c192ef683fdfedeIan Romanick * The first node in the list or \c NULL if the list is empty. 38729eebe9a9a0486f12e33e2818c192ef683fdfedeIan Romanick * 38829eebe9a9a0486f12e33e2818c192ef683fdfedeIan Romanick * \sa exec_list::get_head 38929eebe9a9a0486f12e33e2818c192ef683fdfedeIan Romanick */ 39029eebe9a9a0486f12e33e2818c192ef683fdfedeIan Romanick exec_node *pop_head() 39129eebe9a9a0486f12e33e2818c192ef683fdfedeIan Romanick { 39229eebe9a9a0486f12e33e2818c192ef683fdfedeIan Romanick exec_node *const n = this->get_head(); 39329eebe9a9a0486f12e33e2818c192ef683fdfedeIan Romanick if (n != NULL) 39429eebe9a9a0486f12e33e2818c192ef683fdfedeIan Romanick n->remove(); 39529eebe9a9a0486f12e33e2818c192ef683fdfedeIan Romanick 39629eebe9a9a0486f12e33e2818c192ef683fdfedeIan Romanick return n; 39729eebe9a9a0486f12e33e2818c192ef683fdfedeIan Romanick } 39829eebe9a9a0486f12e33e2818c192ef683fdfedeIan Romanick 39929eebe9a9a0486f12e33e2818c192ef683fdfedeIan Romanick /** 4007e4ce719238e910043325567e941e4ea9a953264Ian Romanick * Move all of the nodes from this list to the target list 4017e4ce719238e910043325567e941e4ea9a953264Ian Romanick */ 4027e4ce719238e910043325567e941e4ea9a953264Ian Romanick void move_nodes_to(exec_list *target) 4037e4ce719238e910043325567e941e4ea9a953264Ian Romanick { 404acce380a3f6df56d44460c0b066b4791cc0f9732Ian Romanick if (is_empty()) { 405acce380a3f6df56d44460c0b066b4791cc0f9732Ian Romanick target->make_empty(); 406acce380a3f6df56d44460c0b066b4791cc0f9732Ian Romanick } else { 407acce380a3f6df56d44460c0b066b4791cc0f9732Ian Romanick target->head = head; 408acce380a3f6df56d44460c0b066b4791cc0f9732Ian Romanick target->tail = NULL; 409acce380a3f6df56d44460c0b066b4791cc0f9732Ian Romanick target->tail_pred = tail_pred; 410acce380a3f6df56d44460c0b066b4791cc0f9732Ian Romanick 411acce380a3f6df56d44460c0b066b4791cc0f9732Ian Romanick target->head->prev = (exec_node *) &target->head; 412acce380a3f6df56d44460c0b066b4791cc0f9732Ian Romanick target->tail_pred->next = (exec_node *) &target->tail; 413acce380a3f6df56d44460c0b066b4791cc0f9732Ian Romanick 414acce380a3f6df56d44460c0b066b4791cc0f9732Ian Romanick make_empty(); 415acce380a3f6df56d44460c0b066b4791cc0f9732Ian Romanick } 4167e4ce719238e910043325567e941e4ea9a953264Ian Romanick } 4177e4ce719238e910043325567e941e4ea9a953264Ian Romanick 418c44556317abf77ca6e344c79d119c91bebe25c8cIan Romanick /** 419c44556317abf77ca6e344c79d119c91bebe25c8cIan Romanick * Append all nodes from the source list to the target list 420c44556317abf77ca6e344c79d119c91bebe25c8cIan Romanick */ 421c44556317abf77ca6e344c79d119c91bebe25c8cIan Romanick void 422c44556317abf77ca6e344c79d119c91bebe25c8cIan Romanick append_list(exec_list *source) 423c44556317abf77ca6e344c79d119c91bebe25c8cIan Romanick { 424c44556317abf77ca6e344c79d119c91bebe25c8cIan Romanick if (source->is_empty()) 425c44556317abf77ca6e344c79d119c91bebe25c8cIan Romanick return; 426c44556317abf77ca6e344c79d119c91bebe25c8cIan Romanick 427c44556317abf77ca6e344c79d119c91bebe25c8cIan Romanick /* Link the first node of the source with the last node of the target list. 428c44556317abf77ca6e344c79d119c91bebe25c8cIan Romanick */ 429c44556317abf77ca6e344c79d119c91bebe25c8cIan Romanick this->tail_pred->next = source->head; 430c44556317abf77ca6e344c79d119c91bebe25c8cIan Romanick source->head->prev = this->tail_pred; 431c44556317abf77ca6e344c79d119c91bebe25c8cIan Romanick 432c44556317abf77ca6e344c79d119c91bebe25c8cIan Romanick /* Make the tail of the source list be the tail of the target list. 433c44556317abf77ca6e344c79d119c91bebe25c8cIan Romanick */ 434c44556317abf77ca6e344c79d119c91bebe25c8cIan Romanick this->tail_pred = source->tail_pred; 435c44556317abf77ca6e344c79d119c91bebe25c8cIan Romanick this->tail_pred->next = (exec_node *) &this->tail; 436c44556317abf77ca6e344c79d119c91bebe25c8cIan Romanick 437c44556317abf77ca6e344c79d119c91bebe25c8cIan Romanick /* Make the source list empty for good measure. 438c44556317abf77ca6e344c79d119c91bebe25c8cIan Romanick */ 439c44556317abf77ca6e344c79d119c91bebe25c8cIan Romanick source->make_empty(); 440c44556317abf77ca6e344c79d119c91bebe25c8cIan Romanick } 441c44556317abf77ca6e344c79d119c91bebe25c8cIan Romanick 4427e4ce719238e910043325567e941e4ea9a953264Ian Romanick exec_list_iterator iterator() 4437e4ce719238e910043325567e941e4ea9a953264Ian Romanick { 4447e4ce719238e910043325567e941e4ea9a953264Ian Romanick return exec_list_iterator(head); 4457e4ce719238e910043325567e941e4ea9a953264Ian Romanick } 4467e4ce719238e910043325567e941e4ea9a953264Ian Romanick 4477e4ce719238e910043325567e941e4ea9a953264Ian Romanick exec_list_iterator iterator() const 4487e4ce719238e910043325567e941e4ea9a953264Ian Romanick { 4497e4ce719238e910043325567e941e4ea9a953264Ian Romanick return exec_list_iterator((exec_node *) head); 4507e4ce719238e910043325567e941e4ea9a953264Ian Romanick } 4517e4ce719238e910043325567e941e4ea9a953264Ian Romanick#endif 4527e4ce719238e910043325567e941e4ea9a953264Ian Romanick}; 4537e4ce719238e910043325567e941e4ea9a953264Ian Romanick 45479082b8aca130ecdcaa1167a9961c16fc620f423Ian Romanick 45579082b8aca130ecdcaa1167a9961c16fc620f423Ian Romanick#ifdef __cplusplus 45679082b8aca130ecdcaa1167a9961c16fc620f423Ian Romanickinline void exec_node::insert_before(exec_list *before) 45779082b8aca130ecdcaa1167a9961c16fc620f423Ian Romanick{ 45879082b8aca130ecdcaa1167a9961c16fc620f423Ian Romanick if (before->is_empty()) 45979082b8aca130ecdcaa1167a9961c16fc620f423Ian Romanick return; 46079082b8aca130ecdcaa1167a9961c16fc620f423Ian Romanick 46179082b8aca130ecdcaa1167a9961c16fc620f423Ian Romanick before->tail_pred->next = this; 46279082b8aca130ecdcaa1167a9961c16fc620f423Ian Romanick before->head->prev = this->prev; 46379082b8aca130ecdcaa1167a9961c16fc620f423Ian Romanick 46479082b8aca130ecdcaa1167a9961c16fc620f423Ian Romanick this->prev->next = before->head; 46579082b8aca130ecdcaa1167a9961c16fc620f423Ian Romanick this->prev = before->tail_pred; 46679082b8aca130ecdcaa1167a9961c16fc620f423Ian Romanick 46779082b8aca130ecdcaa1167a9961c16fc620f423Ian Romanick before->make_empty(); 46879082b8aca130ecdcaa1167a9961c16fc620f423Ian Romanick} 46979082b8aca130ecdcaa1167a9961c16fc620f423Ian Romanick#endif 47079082b8aca130ecdcaa1167a9961c16fc620f423Ian Romanick 471f3290e950cd78a423d380b7e0a7aa18eb7718e27Kenneth Graunke/** 47261a44ccaef63a8ad36ebd934e6944ede5587e4d5Kenneth Graunke * This version is safe even if the current node is removed. 473f3290e950cd78a423d380b7e0a7aa18eb7718e27Kenneth Graunke */ 47461a44ccaef63a8ad36ebd934e6944ede5587e4d5Kenneth Graunke#define foreach_list_safe(__node, __list) \ 47561a44ccaef63a8ad36ebd934e6944ede5587e4d5Kenneth Graunke for (exec_node * __node = (__list)->head, * __next = __node->next \ 47661a44ccaef63a8ad36ebd934e6944ede5587e4d5Kenneth Graunke ; __next != NULL \ 47761a44ccaef63a8ad36ebd934e6944ede5587e4d5Kenneth Graunke ; __node = __next, __next = __next->next) 478f3290e950cd78a423d380b7e0a7aa18eb7718e27Kenneth Graunke 479752c905b8ca694df1e863d500653b386653c35e7Ian Romanick#define foreach_list(__node, __list) \ 480752c905b8ca694df1e863d500653b386653c35e7Ian Romanick for (exec_node * __node = (__list)->head \ 481752c905b8ca694df1e863d500653b386653c35e7Ian Romanick ; (__node)->next != NULL \ 482752c905b8ca694df1e863d500653b386653c35e7Ian Romanick ; (__node) = (__node)->next) 483752c905b8ca694df1e863d500653b386653c35e7Ian Romanick 484752c905b8ca694df1e863d500653b386653c35e7Ian Romanick#define foreach_list_const(__node, __list) \ 485752c905b8ca694df1e863d500653b386653c35e7Ian Romanick for (const exec_node * __node = (__list)->head \ 486752c905b8ca694df1e863d500653b386653c35e7Ian Romanick ; (__node)->next != NULL \ 487752c905b8ca694df1e863d500653b386653c35e7Ian Romanick ; (__node) = (__node)->next) 488752c905b8ca694df1e863d500653b386653c35e7Ian Romanick 4894cfbad9e4df4acb011676bde761af557ae58e96aIan Romanick#define foreach_list_typed(__type, __node, __field, __list) \ 4904cfbad9e4df4acb011676bde761af557ae58e96aIan Romanick for (__type * __node = \ 4914cfbad9e4df4acb011676bde761af557ae58e96aIan Romanick exec_node_data(__type, (__list)->head, __field); \ 4924cfbad9e4df4acb011676bde761af557ae58e96aIan Romanick (__node)->__field.next != NULL; \ 4934cfbad9e4df4acb011676bde761af557ae58e96aIan Romanick (__node) = exec_node_data(__type, (__node)->__field.next, __field)) 4944cfbad9e4df4acb011676bde761af557ae58e96aIan Romanick 4954cfbad9e4df4acb011676bde761af557ae58e96aIan Romanick#define foreach_list_typed_const(__type, __node, __field, __list) \ 4964cfbad9e4df4acb011676bde761af557ae58e96aIan Romanick for (const __type * __node = \ 4974cfbad9e4df4acb011676bde761af557ae58e96aIan Romanick exec_node_data(__type, (__list)->head, __field); \ 4984cfbad9e4df4acb011676bde761af557ae58e96aIan Romanick (__node)->__field.next != NULL; \ 4994cfbad9e4df4acb011676bde761af557ae58e96aIan Romanick (__node) = exec_node_data(__type, (__node)->__field.next, __field)) 5004cfbad9e4df4acb011676bde761af557ae58e96aIan Romanick 5017e4ce719238e910043325567e941e4ea9a953264Ian Romanick#endif /* LIST_CONTAINER_H */ 502