1f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/* 2f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Copyright 2011 Christoph Bumiller 3f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 4f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Permission is hereby granted, free of charge, to any person obtaining a 5f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * copy of this software and associated documentation files (the "Software"), 6f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * to deal in the Software without restriction, including without limitation 7f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * the rights to use, copy, modify, merge, publish, distribute, sublicense, 8f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * and/or sell copies of the Software, and to permit persons to whom the 9f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Software is furnished to do so, subject to the following conditions: 10f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 11f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * The above copyright notice and this permission notice shall be included in 12f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * all copies or substantial portions of the Software. 13f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 14f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 15f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 16f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 17f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, 18f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF 19f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 20f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * SOFTWARE. 21f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 22f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 23f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#ifndef __NV50_IR_UTIL_H__ 24f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define __NV50_IR_UTIL_H__ 25f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 26f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include <new> 27f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include <assert.h> 28f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include <stdio.h> 29f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include <memory> 30f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include <map> 31f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 32f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#ifndef NDEBUG 33f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org# include <typeinfo> 34f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#endif 35f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 36f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "util/u_inlines.h" 37f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "util/u_memory.h" 38f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 39f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define ERROR(args...) debug_printf("ERROR: " args) 40f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define WARN(args...) debug_printf("WARNING: " args) 41f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define INFO(args...) debug_printf(args) 42f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 43f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define INFO_DBG(m, f, args...) \ 44f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org do { \ 45f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (m & NV50_IR_DEBUG_##f) \ 46f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org debug_printf(args); \ 47f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } while(0) 48f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 49f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define FATAL(args...) \ 50f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org do { \ 51f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org fprintf(stderr, args); \ 52f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org abort(); \ 53f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } while(0) 54f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 55f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 56f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define NV50_IR_FUNC_ALLOC_OBJ_DEF(obj, f, args...) \ 57f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org new ((f)->getProgram()->mem_##obj.allocate()) obj(f, args) 58f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 59f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define new_Instruction(f, args...) \ 60f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org NV50_IR_FUNC_ALLOC_OBJ_DEF(Instruction, f, args) 61f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define new_CmpInstruction(f, args...) \ 62f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org NV50_IR_FUNC_ALLOC_OBJ_DEF(CmpInstruction, f, args) 63f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define new_TexInstruction(f, args...) \ 64f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org NV50_IR_FUNC_ALLOC_OBJ_DEF(TexInstruction, f, args) 65f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define new_FlowInstruction(f, args...) \ 66f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org NV50_IR_FUNC_ALLOC_OBJ_DEF(FlowInstruction, f, args) 67f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 68f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define new_LValue(f, args...) \ 69f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org NV50_IR_FUNC_ALLOC_OBJ_DEF(LValue, f, args) 70f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 71f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 72f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define NV50_IR_PROG_ALLOC_OBJ_DEF(obj, p, args...) \ 73f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org new ((p)->mem_##obj.allocate()) obj(p, args) 74f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 75f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define new_Symbol(p, args...) \ 76f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org NV50_IR_PROG_ALLOC_OBJ_DEF(Symbol, p, args) 77f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define new_ImmediateValue(p, args...) \ 78f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org NV50_IR_PROG_ALLOC_OBJ_DEF(ImmediateValue, p, args) 79f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 80f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 81f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define delete_Instruction(p, insn) (p)->releaseInstruction(insn) 82f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define delete_Value(p, val) (p)->releaseValue(val) 83f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 84f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 85f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgnamespace nv50_ir { 86f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 87f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgclass Iterator 88f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 89f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgpublic: 90f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual ~Iterator() { }; 91f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual void next() = 0; 92f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual void *get() const = 0; 93f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual bool end() const = 0; // if true, get will return 0 94f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual void reset() { assert(0); } // only for graph iterators 95f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org}; 96f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 97f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgtypedef std::auto_ptr<Iterator> IteratorRef; 98f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 99f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgclass ManipIterator : public Iterator 100f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 101f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgpublic: 102f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual bool insert(void *) = 0; // insert after current position 103f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual void erase() = 0; 104f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org}; 105f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 106f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org// WARNING: do not use a->prev/next for __item or __list 107f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 108f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define DLLIST_DEL(__item) \ 109f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org do { \ 110f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (__item)->prev->next = (__item)->next; \ 111f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (__item)->next->prev = (__item)->prev; \ 112f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (__item)->next = (__item); \ 113f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (__item)->prev = (__item); \ 114f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } while(0) 115f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 116f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define DLLIST_ADDTAIL(__list, __item) \ 117f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org do { \ 118f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (__item)->next = (__list); \ 119f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (__item)->prev = (__list)->prev; \ 120f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (__list)->prev->next = (__item); \ 121f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (__list)->prev = (__item); \ 122f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } while(0) 123f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 124f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define DLLIST_ADDHEAD(__list, __item) \ 125f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org do { \ 126f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (__item)->prev = (__list); \ 127f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (__item)->next = (__list)->next; \ 128f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (__list)->next->prev = (__item); \ 129f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (__list)->next = (__item); \ 130f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } while(0) 131f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 132f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define DLLIST_MERGE(__listA, __listB, ty) \ 133f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org do { \ 134f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ty prevB = (__listB)->prev; \ 135f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (__listA)->prev->next = (__listB); \ 136f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (__listB)->prev->next = (__listA); \ 137f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (__listB)->prev = (__listA)->prev; \ 138f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (__listA)->prev = prevB; \ 139f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } while(0) 140f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 141f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define DLLIST_EMPTY(__list) ((__list)->next == (__list)) 142f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 143f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define DLLIST_FOR_EACH(list, it) \ 144f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (DLList::Iterator (it) = (list)->iterator(); !(it).end(); (it).next()) 145f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 146f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgclass DLList 147f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 148f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgpublic: 149f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org class Item 150f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 151f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public: 152f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Item(void *priv) : next(this), prev(this), data(priv) { } 153f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 154f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public: 155f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Item *next; 156f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Item *prev; 157f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void *data; 158f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org }; 159f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 160f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org DLList() : head(0) { } 161f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ~DLList() { clear(); } 162f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 163f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline void insertHead(void *data) 164f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 165f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Item *item = new Item(data); 166f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 167f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(data); 168f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 169f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org item->prev = &head; 170f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org item->next = head.next; 171f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org head.next->prev = item; 172f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org head.next = item; 173f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 174f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 175f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline void insertTail(void *data) 176f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 177f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Item *item = new Item(data); 178f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 179f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(data); 180f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 181f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org DLLIST_ADDTAIL(&head, item); 182f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 183f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 184f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline void insert(void *data) { insertTail(data); } 185f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 186f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void clear(); 187f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 188f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org class Iterator : public ManipIterator 189f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 190f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public: 191f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Iterator(Item *head, bool r) : rev(r), pos(r ? head->prev : head->next), 192f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org term(head) { } 193f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 194f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual void next() { if (!end()) pos = rev ? pos->prev : pos->next; } 195f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual void *get() const { return pos->data; } 196f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual bool end() const { return pos == term; } 197f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 198f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // caution: if you're at end-2 and erase it, then do next, you're at end 199f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual void erase(); 200f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual bool insert(void *data); 201f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 202f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // move item to a another list, no consistency with its iterators though 203f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void moveToList(DLList&); 204f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 205f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org private: 206f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const bool rev; 207f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Item *pos; 208f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Item *term; 209f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 210f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org friend class DLList; 211f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org }; 212f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 213f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline void erase(Iterator& pos) 214f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 215f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org pos.erase(); 216f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 217f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 218f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Iterator iterator() 219f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 220f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return Iterator(&head, false); 221f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 222f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 223f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Iterator revIterator() 224f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 225f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return Iterator(&head, true); 226f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 227f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 228f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgprivate: 229f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Item head; 230f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org}; 231f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 232f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgclass Stack 233f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 234f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgpublic: 235f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org class Item { 236f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public: 237f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org union { 238f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void *p; 239f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int i; 240f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org unsigned int u; 241f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org float f; 242f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org double d; 243f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } u; 244f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 245f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Item() { memset(&u, 0, sizeof(u)); } 246f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org }; 247f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 248f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Stack() : size(0), limit(0), array(0) { } 249f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ~Stack() { if (array) FREE(array); } 250f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 251f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline void push(int i) { Item data; data.u.i = i; push(data); } 252f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline void push(unsigned int u) { Item data; data.u.u = u; push(data); } 253f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline void push(void *p) { Item data; data.u.p = p; push(data); } 254f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline void push(float f) { Item data; data.u.f = f; push(data); } 255f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 256f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline void push(Item data) 257f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 258f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (size == limit) 259f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org resize(); 260f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org array[size++] = data; 261f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 262f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 263f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline Item pop() 264f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 265f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!size) { 266f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Item data; 267f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(0); 268f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return data; 269f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 270f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return array[--size]; 271f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 272f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 273f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline unsigned int getSize() { return size; } 274f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 275f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline Item& peek() { assert(size); return array[size - 1]; } 276f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 277f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void clear(bool releaseStorage = false) 278f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 279f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (releaseStorage && array) 280f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org FREE(array); 281f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org size = limit = 0; 282f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 283f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 284f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void moveTo(Stack&); // move all items to target (not like push(pop())) 285f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 286f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgprivate: 287f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void resize() 288f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 289f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org unsigned int sizeOld, sizeNew; 290f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 291f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org sizeOld = limit * sizeof(Item); 292f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org limit = MAX2(4, limit + limit); 293f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org sizeNew = limit * sizeof(Item); 294f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 295f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org array = (Item *)REALLOC(array, sizeOld, sizeNew); 296f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 297f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 298f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org unsigned int size; 299f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org unsigned int limit; 300f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Item *array; 301f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org}; 302f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 303f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgclass DynArray 304f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 305f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgpublic: 306f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org class Item 307f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 308f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public: 309f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org union { 310f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org uint32_t u32; 311f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void *p; 312f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org }; 313f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org }; 314f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 315f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org DynArray() : data(NULL), size(0) { } 316f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 317f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ~DynArray() { if (data) FREE(data); } 318f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 319f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline Item& operator[](unsigned int i) 320f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 321f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (i >= size) 322f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org resize(i); 323f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return data[i]; 324f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 325f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 326f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline const Item operator[](unsigned int i) const 327f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 328f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return data[i]; 329f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 330f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 331f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void resize(unsigned int index) 332f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 333f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const unsigned int oldSize = size * sizeof(Item); 334f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 335f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!size) 336f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org size = 8; 337f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org while (size <= index) 338f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org size <<= 1; 339f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 340f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org data = (Item *)REALLOC(data, oldSize, size * sizeof(Item)); 341f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 342f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 343f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void clear() 344f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 345f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org FREE(data); 346f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org data = NULL; 347f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org size = 0; 348f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 349f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 350f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgprivate: 351f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Item *data; 352f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org unsigned int size; 353f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org}; 354f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 355f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgclass ArrayList 356f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 357f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgpublic: 358f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ArrayList() : size(0) { } 359f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 360f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void insert(void *item, int& id) 361f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 362f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org id = ids.getSize() ? ids.pop().u.i : size++; 363f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org data[id].p = item; 364f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 365f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 366f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void remove(int& id) 367f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 368f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const unsigned int uid = id; 369f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(uid < size && data[id].p); 370f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ids.push(uid); 371f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org data[uid].p = NULL; 372f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org id = -1; 373f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 374f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 375f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline int getSize() const { return size; } 376f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 377f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline void *get(unsigned int id) { assert(id < size); return data[id].p; } 378f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 379f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org class Iterator : public nv50_ir::Iterator 380f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 381f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public: 382f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Iterator(const ArrayList *array) : pos(0), data(array->data) 383f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 384f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org size = array->getSize(); 385f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (size) 386f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org nextValid(); 387f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 388f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 389f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void nextValid() { while ((pos < size) && !data[pos].p) ++pos; } 390f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 391f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void next() { if (pos < size) { ++pos; nextValid(); } } 392f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void *get() const { assert(pos < size); return data[pos].p; } 393f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bool end() const { return pos >= size; } 394f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 395f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org private: 396f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org unsigned int pos; 397f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org unsigned int size; 398f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const DynArray& data; 399f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 400f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org friend class ArrayList; 401f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org }; 402f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 403f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Iterator iterator() const { return Iterator(this); } 404f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 405f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void clear() 406f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 407f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org data.clear(); 408f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ids.clear(true); 409f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org size = 0; 410f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 411f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 412f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgprivate: 413f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org DynArray data; 414f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Stack ids; 415f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org unsigned int size; 416f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org}; 417f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 418f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgclass Interval 419f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 420f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgpublic: 421f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Interval() : head(0), tail(0) { } 422f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Interval(const Interval&); 423f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ~Interval(); 424f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 425f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bool extend(int, int); 426f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void insert(const Interval&); 427f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void unify(Interval&); // clears source interval 428f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void clear(); 429f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 430f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline int begin() const { return head ? head->bgn : -1; } 431f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline int end() const { checkTail(); return tail ? tail->end : -1; } 432f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline bool isEmpty() const { return !head; } 433f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bool overlaps(const Interval&) const; 434f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bool contains(int pos) const; 435f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 436f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline int extent() const { return end() - begin(); } 437f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int length() const; 438f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 439f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void print() const; 440f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 441f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline void checkTail() const; 442f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 443f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgprivate: 444f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org class Range 445f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 446f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public: 447f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Range(int a, int b) : next(0), bgn(a), end(b) { } 448f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 449f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Range *next; 450f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int bgn; 451f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int end; 452f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 453f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void coalesce(Range **ptail) 454f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 455f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Range *rnn; 456f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 457f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org while (next && end >= next->bgn) { 458f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(bgn <= next->bgn); 459f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org rnn = next->next; 460f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org end = MAX2(end, next->end); 461f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org delete next; 462f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org next = rnn; 463f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 464f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!next) 465f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org *ptail = this; 466f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 467f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org }; 468f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 469f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Range *head; 470f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Range *tail; 471f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org}; 472f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 473f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgclass BitSet 474f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 475f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgpublic: 476f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org BitSet() : marker(false), data(0), size(0) { } 477f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org BitSet(unsigned int nBits, bool zero) : marker(false), data(0), size(0) 478f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 479f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org allocate(nBits, zero); 480f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 481f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ~BitSet() 482f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 483f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (data) 484f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org FREE(data); 485f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 486f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 487f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bool allocate(unsigned int nBits, bool zero); 488f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bool resize(unsigned int nBits); // keep old data, zero additional bits 489f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 490f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline unsigned int getSize() const { return size; } 491f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 492f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void fill(uint32_t val); 493f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 494f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void setOr(BitSet *, BitSet *); // second BitSet may be NULL 495f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 496f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline void set(unsigned int i) 497f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 498f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(i < size); 499f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org data[i / 32] |= 1 << (i % 32); 500f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 501f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // NOTE: range may not cross 32 bit boundary (implies n <= 32) 502f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline void setRange(unsigned int i, unsigned int n) 503f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 504f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert((i + n) <= size && (((i % 32) + n) <= 32)); 505f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org data[i / 32] |= ((1 << n) - 1) << (i % 32); 506f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 507f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline void setMask(unsigned int i, uint32_t m) 508f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 509f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(i < size); 510f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org data[i / 32] |= m; 511f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 512f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 513f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline void clr(unsigned int i) 514f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 515f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(i < size); 516f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org data[i / 32] &= ~(1 << (i % 32)); 517f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 518f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // NOTE: range may not cross 32 bit boundary (implies n <= 32) 519f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline void clrRange(unsigned int i, unsigned int n) 520f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 521f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert((i + n) <= size && (((i % 32) + n) <= 32)); 522f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org data[i / 32] &= ~(((1 << n) - 1) << (i % 32)); 523f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 524f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 525f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline bool test(unsigned int i) const 526f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 527f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(i < size); 528f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return data[i / 32] & (1 << (i % 32)); 529f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 530f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // NOTE: range may not cross 32 bit boundary (implies n <= 32) 531f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline bool testRange(unsigned int i, unsigned int n) 532f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 533f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert((i + n) <= size && (((i % 32) + n) <= 32)); 534f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return data[i / 32] & (((1 << n) - 1) << (i % 32)); 535f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 536f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 537f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // Find a range of size (<= 32) clear bits aligned to roundup_pow2(size). 538f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int findFreeRange(unsigned int size) const; 539f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 540f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org BitSet& operator|=(const BitSet&); 541f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 542f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org BitSet& operator=(const BitSet& set) 543f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 544f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(data && set.data); 545f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(size == set.size); 546f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org memcpy(data, set.data, (set.size + 7) / 8); 547f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return *this; 548f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 549f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 550f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void andNot(const BitSet&); 551f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 552f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // bits = (bits | setMask) & ~clrMask 553f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline void periodicMask32(uint32_t setMask, uint32_t clrMask) 554f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 555f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (unsigned int i = 0; i < (size + 31) / 32; ++i) 556f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org data[i] = (data[i] | setMask) & ~clrMask; 557f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 558f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 559f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org unsigned int popCount() const; 560f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 561f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void print() const; 562f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 563f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgpublic: 564f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bool marker; // for user 565f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 566f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgprivate: 567f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org uint32_t *data; 568f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org unsigned int size; 569f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org}; 570f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 571f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid Interval::checkTail() const 572f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 573f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#if NV50_DEBUG & NV50_DEBUG_PROG_RA 574f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Range *r = head; 575f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org while (r->next) 576f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org r = r->next; 577f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(tail == r); 578f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#endif 579f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 580f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 581f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgclass MemoryPool 582f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 583f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgprivate: 584f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline bool enlargeAllocationsArray(const unsigned int id, unsigned int nr) 585f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 586f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const unsigned int size = sizeof(uint8_t *) * id; 587f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const unsigned int incr = sizeof(uint8_t *) * nr; 588f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 589f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org uint8_t **alloc = (uint8_t **)REALLOC(allocArray, size, size + incr); 590f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!alloc) 591f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return false; 592f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org allocArray = alloc; 593f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return true; 594f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 595f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 596f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inline bool enlargeCapacity() 597f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 598f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const unsigned int id = count >> objStepLog2; 599f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 600f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org uint8_t *const mem = (uint8_t *)MALLOC(objSize << objStepLog2); 601f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!mem) 602f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return false; 603f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 604f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!(id % 32)) { 605f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!enlargeAllocationsArray(id, 32)) { 606f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org FREE(mem); 607f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return false; 608f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 609f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 610f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org allocArray[id] = mem; 611f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return true; 612f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 613f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 614f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgpublic: 615f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org MemoryPool(unsigned int size, unsigned int incr) : objSize(size), 616f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org objStepLog2(incr) 617f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 618f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org allocArray = NULL; 619f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org released = NULL; 620f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org count = 0; 621f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 622f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 623f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ~MemoryPool() 624f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 625f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org unsigned int allocCount = (count + (1 << objStepLog2) - 1) >> objStepLog2; 626f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (unsigned int i = 0; i < allocCount && allocArray[i]; ++i) 627f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org FREE(allocArray[i]); 628f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (allocArray) 629f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org FREE(allocArray); 630f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 631f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 632f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void *allocate() 633f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 634f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void *ret; 635f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const unsigned int mask = (1 << objStepLog2) - 1; 636f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 637f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (released) { 638f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ret = released; 639f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org released = *(void **)released; 640f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return ret; 641f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 642f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 643f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!(count & mask)) 644f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!enlargeCapacity()) 645f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return NULL; 646f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 647f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ret = allocArray[count >> objStepLog2] + (count & mask) * objSize; 648f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ++count; 649f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return ret; 650f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 651f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 652f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void release(void *ptr) 653f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 654f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org *(void **)ptr = released; 655f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org released = ptr; 656f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 657f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 658f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgprivate: 659f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org uint8_t **allocArray; // array (list) of MALLOC allocations 660f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 661f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void *released; // list of released objects 662f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 663f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org unsigned int count; // highest allocated object 664f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 665f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const unsigned int objSize; 666f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const unsigned int objStepLog2; 667f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org}; 668f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 669f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 670f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Composite object cloning policy. 671f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 672f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Encapsulates how sub-objects are to be handled (if at all) when a 673f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * composite object is being cloned. 674f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 675f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgtemplate<typename C> 676f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgclass ClonePolicy 677f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 678f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgprotected: 679f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org C *c; 680f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 681f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgpublic: 682f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ClonePolicy(C *c) : c(c) {} 683f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 684f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org C *context() { return c; } 685f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 686f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org template<typename T> T *get(T *obj) 687f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 688f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void *clone = lookup(obj); 689f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!clone) 690f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org clone = obj->clone(*this); 691f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return reinterpret_cast<T *>(clone); 692f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 693f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 694f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org template<typename T> void set(const T *obj, T *clone) 695f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 696f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org insert(obj, clone); 697f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 698f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 699f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgprotected: 700f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual void *lookup(void *obj) = 0; 701f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual void insert(const void *obj, void *clone) = 0; 702f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org}; 703f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 704f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 705f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Shallow non-recursive cloning policy. 706f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 707f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Objects cloned with the "shallow" policy don't clone their 708f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * children recursively, instead, the new copy shares its children 709f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * with the original object. 710f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 711f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgtemplate<typename C> 712f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgclass ShallowClonePolicy : public ClonePolicy<C> 713f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 714f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgpublic: 715f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ShallowClonePolicy(C *c) : ClonePolicy<C>(c) {} 716f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 717f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgprotected: 718f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual void *lookup(void *obj) 719f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 720f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return obj; 721f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 722f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 723f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual void insert(const void *obj, void *clone) 724f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 725f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 726f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org}; 727f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 728f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgtemplate<typename C, typename T> 729f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orginline T *cloneShallow(C *c, T *obj) 730f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 731f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ShallowClonePolicy<C> pol(c); 732f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return obj->clone(pol); 733f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 734f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 735f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 736f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Recursive cloning policy. 737f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 738f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Objects cloned with the "deep" policy clone their children 739f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * recursively, keeping track of what has already been cloned to 740f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * avoid making several new copies of the same object. 741f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 742f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgtemplate<typename C> 743f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgclass DeepClonePolicy : public ClonePolicy<C> 744f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 745f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgpublic: 746f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org DeepClonePolicy(C *c) : ClonePolicy<C>(c) {} 747f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 748f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgprivate: 749f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org std::map<const void *, void *> map; 750f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 751f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgprotected: 752f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual void *lookup(void *obj) 753f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 754f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return map[obj]; 755f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 756f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 757f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual void insert(const void *obj, void *clone) 758f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 759f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org map[obj] = clone; 760f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 761f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org}; 762f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 763f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgtemplate<typename S, typename T> 764f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgstruct bimap 765f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 766f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org std::map<S, T> forth; 767f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org std::map<T, S> back; 768f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 769f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgpublic: 770f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bimap() : l(back), r(forth) { } 771f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bimap(const bimap<S, T> &m) 772f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org : forth(m.forth), back(m.back), l(back), r(forth) { } 773f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 774f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void insert(const S &s, const T &t) 775f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 776f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org forth.insert(std::make_pair(s, t)); 777f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org back.insert(std::make_pair(t, s)); 778f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 779f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 780f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org typedef typename std::map<T, S>::const_iterator l_iterator; 781f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const std::map<T, S> &l; 782f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org typedef typename std::map<S, T>::const_iterator r_iterator; 783f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const std::map<S, T> &r; 784f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org}; 785f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 786f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} // namespace nv50_ir 787f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 788f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#endif // __NV50_IR_UTIL_H__ 789