addr_range_map.hh revision 8229
13101Sstever@eecs.umich.edu/* 27534Ssteve.reinhardt@amd.com * Copyright (c) 2006 The Regents of The University of Michigan 33101Sstever@eecs.umich.edu * All rights reserved. 43101Sstever@eecs.umich.edu * 53101Sstever@eecs.umich.edu * Redistribution and use in source and binary forms, with or without 63101Sstever@eecs.umich.edu * modification, are permitted provided that the following conditions are 73101Sstever@eecs.umich.edu * met: redistributions of source code must retain the above copyright 83101Sstever@eecs.umich.edu * notice, this list of conditions and the following disclaimer; 93101Sstever@eecs.umich.edu * redistributions in binary form must reproduce the above copyright 103101Sstever@eecs.umich.edu * notice, this list of conditions and the following disclaimer in the 113101Sstever@eecs.umich.edu * documentation and/or other materials provided with the distribution; 123101Sstever@eecs.umich.edu * neither the name of the copyright holders nor the names of its 133101Sstever@eecs.umich.edu * contributors may be used to endorse or promote products derived from 143101Sstever@eecs.umich.edu * this software without specific prior written permission. 153101Sstever@eecs.umich.edu * 163101Sstever@eecs.umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 173101Sstever@eecs.umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 183101Sstever@eecs.umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 193101Sstever@eecs.umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 203101Sstever@eecs.umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 213101Sstever@eecs.umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 223101Sstever@eecs.umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 233101Sstever@eecs.umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 243101Sstever@eecs.umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 253101Sstever@eecs.umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 263101Sstever@eecs.umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 273101Sstever@eecs.umich.edu * 283101Sstever@eecs.umich.edu * Authors: Ali Saidi 293101Sstever@eecs.umich.edu */ 303101Sstever@eecs.umich.edu 313101Sstever@eecs.umich.edu#ifndef __BASE_RANGE_MAP_HH__ 323101Sstever@eecs.umich.edu#define __BASE_RANGE_MAP_HH__ 333101Sstever@eecs.umich.edu 343101Sstever@eecs.umich.edu#include <map> 353101Sstever@eecs.umich.edu 363101Sstever@eecs.umich.edu#include "base/range.hh" 373101Sstever@eecs.umich.edu 383101Sstever@eecs.umich.edutemplate <class T,class V> 393101Sstever@eecs.umich.educlass range_map 403101Sstever@eecs.umich.edu{ 413101Sstever@eecs.umich.edu private: 423101Sstever@eecs.umich.edu typedef std::map<Range<T>,V> RangeMap; 433101Sstever@eecs.umich.edu RangeMap tree; 443101Sstever@eecs.umich.edu 453101Sstever@eecs.umich.edu public: 463101Sstever@eecs.umich.edu typedef typename RangeMap::iterator iterator; 473101Sstever@eecs.umich.edu 483885Sbinkertn@umich.edu template <class U> 493885Sbinkertn@umich.edu const iterator 504762Snate@binkert.org find(const Range<U> &r) 513885Sbinkertn@umich.edu { 523885Sbinkertn@umich.edu iterator i; 537528Ssteve.reinhardt@amd.com 543885Sbinkertn@umich.edu i = tree.upper_bound(r); 554380Sbinkertn@umich.edu 564167Sbinkertn@umich.edu if (i == tree.begin()) { 573102Sstever@eecs.umich.edu if (i->first.start <= r.end && i->first.end >= r.start) 583101Sstever@eecs.umich.edu return i; 594762Snate@binkert.org else 604762Snate@binkert.org // Nothing could match, so return end() 614762Snate@binkert.org return tree.end(); 624762Snate@binkert.org } 634762Snate@binkert.org 644762Snate@binkert.org i--; 654762Snate@binkert.org 664762Snate@binkert.org if (i->first.start <= r.end && i->first.end >= r.start) 674762Snate@binkert.org return i; 685033Smilesck@eecs.umich.edu 695033Smilesck@eecs.umich.edu return tree.end(); 705033Smilesck@eecs.umich.edu } 715033Smilesck@eecs.umich.edu 725033Smilesck@eecs.umich.edu template <class U> 735033Smilesck@eecs.umich.edu const iterator 745033Smilesck@eecs.umich.edu find(const U &r) 755033Smilesck@eecs.umich.edu { 765033Smilesck@eecs.umich.edu return find(RangeSize(r, 1)); 775033Smilesck@eecs.umich.edu } 783101Sstever@eecs.umich.edu 793101Sstever@eecs.umich.edu template <class U> 803101Sstever@eecs.umich.edu bool 815033Smilesck@eecs.umich.edu intersect(const Range<U> &r) 823101Sstever@eecs.umich.edu { 837673Snate@binkert.org iterator i; 847673Snate@binkert.org i = find(r); 857673Snate@binkert.org if (i != tree.end()) 867673Snate@binkert.org return true; 877673Snate@binkert.org return false; 887673Snate@binkert.org } 897673Snate@binkert.org 903101Sstever@eecs.umich.edu 913101Sstever@eecs.umich.edu template <class U,class W> 923101Sstever@eecs.umich.edu iterator 933101Sstever@eecs.umich.edu insert(const Range<U> &r, const W d) 943101Sstever@eecs.umich.edu { 953101Sstever@eecs.umich.edu if (intersect(r)) 963101Sstever@eecs.umich.edu return tree.end(); 973101Sstever@eecs.umich.edu 983101Sstever@eecs.umich.edu return tree.insert(std::make_pair<Range<T>,V>(r, d)).first; 993101Sstever@eecs.umich.edu } 1003101Sstever@eecs.umich.edu 1013101Sstever@eecs.umich.edu size_t 1023101Sstever@eecs.umich.edu erase(T k) 1036656Snate@binkert.org { 1046656Snate@binkert.org return tree.erase(k); 1053101Sstever@eecs.umich.edu } 1063101Sstever@eecs.umich.edu 1073101Sstever@eecs.umich.edu void 1083101Sstever@eecs.umich.edu erase(iterator p) 1093101Sstever@eecs.umich.edu { 1103101Sstever@eecs.umich.edu tree.erase(p); 1113101Sstever@eecs.umich.edu } 1123101Sstever@eecs.umich.edu 1133101Sstever@eecs.umich.edu void 1143101Sstever@eecs.umich.edu erase(iterator p, iterator q) 1153101Sstever@eecs.umich.edu { 1163101Sstever@eecs.umich.edu tree.erase(p,q); 1173101Sstever@eecs.umich.edu } 1183101Sstever@eecs.umich.edu 1193101Sstever@eecs.umich.edu void 1203101Sstever@eecs.umich.edu clear() 1213101Sstever@eecs.umich.edu { 1223101Sstever@eecs.umich.edu tree.erase(tree.begin(), tree.end()); 1233101Sstever@eecs.umich.edu } 1243101Sstever@eecs.umich.edu 1253101Sstever@eecs.umich.edu iterator 1263101Sstever@eecs.umich.edu begin() 1273101Sstever@eecs.umich.edu { 1283101Sstever@eecs.umich.edu return tree.begin(); 1293101Sstever@eecs.umich.edu } 1303101Sstever@eecs.umich.edu 1313101Sstever@eecs.umich.edu iterator 1323101Sstever@eecs.umich.edu end() 1333101Sstever@eecs.umich.edu { 1343101Sstever@eecs.umich.edu return tree.end(); 1353101Sstever@eecs.umich.edu } 1363101Sstever@eecs.umich.edu 1373101Sstever@eecs.umich.edu size_t 1385033Smilesck@eecs.umich.edu size() 1396656Snate@binkert.org { 1405033Smilesck@eecs.umich.edu return tree.size(); 1415033Smilesck@eecs.umich.edu } 1425033Smilesck@eecs.umich.edu 1433101Sstever@eecs.umich.edu bool 1443101Sstever@eecs.umich.edu empty() 1453101Sstever@eecs.umich.edu { 1463101Sstever@eecs.umich.edu return tree.empty(); 1473101Sstever@eecs.umich.edu } 1483101Sstever@eecs.umich.edu}; 1493101Sstever@eecs.umich.edu 1503101Sstever@eecs.umich.edu 1513101Sstever@eecs.umich.edutemplate <class T,class V> 1523101Sstever@eecs.umich.educlass range_multimap 1533101Sstever@eecs.umich.edu{ 1543101Sstever@eecs.umich.edu private: 1553101Sstever@eecs.umich.edu typedef std::multimap<Range<T>,V> RangeMap; 1563102Sstever@eecs.umich.edu RangeMap tree; 1573101Sstever@eecs.umich.edu 1583101Sstever@eecs.umich.edu public: 1593101Sstever@eecs.umich.edu typedef typename RangeMap::iterator iterator; 1607673Snate@binkert.org 1617673Snate@binkert.org template <class U> 1623101Sstever@eecs.umich.edu std::pair<iterator,iterator> find(const Range<U> &r) 1637673Snate@binkert.org { 1647673Snate@binkert.org iterator i; 1653101Sstever@eecs.umich.edu iterator j; 1667673Snate@binkert.org 1677673Snate@binkert.org i = tree.lower_bound(r); 1683101Sstever@eecs.umich.edu 1693101Sstever@eecs.umich.edu if (i == tree.begin()) { 1703101Sstever@eecs.umich.edu if (i->first.start <= r.end && i->first.end >= r.start) 1713101Sstever@eecs.umich.edu return std::make_pair<iterator, iterator>(i,i); 1723101Sstever@eecs.umich.edu else 1733101Sstever@eecs.umich.edu // Nothing could match, so return end() 1745033Smilesck@eecs.umich.edu return std::make_pair<iterator, iterator>(tree.end(), tree.end()); 1755475Snate@binkert.org } 1765475Snate@binkert.org i--; 1775475Snate@binkert.org 1785475Snate@binkert.org if (i->first.start <= r.end && i->first.end >= r.start) { 1793101Sstever@eecs.umich.edu // we have at least one match 1803101Sstever@eecs.umich.edu j = i; 1813101Sstever@eecs.umich.edu 1824762Snate@binkert.org i--; 1834762Snate@binkert.org while (i->first.start <= r.end && i->first.end >= 1844762Snate@binkert.org r.start) { 1853101Sstever@eecs.umich.edu if (i == tree.begin()) 1863101Sstever@eecs.umich.edu break; 1873101Sstever@eecs.umich.edu i--; 1887528Ssteve.reinhardt@amd.com } 1897528Ssteve.reinhardt@amd.com if (i == tree.begin() && i->first.start <= r.end && i->first.end >= 1907528Ssteve.reinhardt@amd.com r.start) 1917528Ssteve.reinhardt@amd.com return std::make_pair<iterator, iterator>(i,j); 1927528Ssteve.reinhardt@amd.com i++; 1937528Ssteve.reinhardt@amd.com return std::make_pair<iterator, iterator>(i,j); 1943101Sstever@eecs.umich.edu 1957528Ssteve.reinhardt@amd.com } 1967528Ssteve.reinhardt@amd.com 1977528Ssteve.reinhardt@amd.com return std::make_pair<iterator, iterator>(tree.end(), tree.end()); 1987528Ssteve.reinhardt@amd.com } 1997528Ssteve.reinhardt@amd.com 2007528Ssteve.reinhardt@amd.com template <class U> 2017528Ssteve.reinhardt@amd.com bool 2027528Ssteve.reinhardt@amd.com intersect(const Range<U> &r) 2037528Ssteve.reinhardt@amd.com { 2047528Ssteve.reinhardt@amd.com std::pair<iterator,iterator> p; 2057528Ssteve.reinhardt@amd.com p = find(r); 2067528Ssteve.reinhardt@amd.com if (p.first != tree.end()) 2077528Ssteve.reinhardt@amd.com return true; 2087528Ssteve.reinhardt@amd.com return false; 2097528Ssteve.reinhardt@amd.com } 2107528Ssteve.reinhardt@amd.com 2117528Ssteve.reinhardt@amd.com 2127528Ssteve.reinhardt@amd.com template <class U,class W> 2137528Ssteve.reinhardt@amd.com iterator 2147528Ssteve.reinhardt@amd.com insert(const Range<U> &r, const W d) 2157528Ssteve.reinhardt@amd.com { 2167528Ssteve.reinhardt@amd.com std::pair<iterator,iterator> p; 2177528Ssteve.reinhardt@amd.com p = find(r); 2187528Ssteve.reinhardt@amd.com if (p.first->first.start == r.start && p.first->first.end == r.end || 2197528Ssteve.reinhardt@amd.com p.first == tree.end()) 2207528Ssteve.reinhardt@amd.com return tree.insert(std::make_pair<Range<T>,V>(r, d)); 2217528Ssteve.reinhardt@amd.com else 2227528Ssteve.reinhardt@amd.com return tree.end(); 2237528Ssteve.reinhardt@amd.com } 2243101Sstever@eecs.umich.edu 2253101Sstever@eecs.umich.edu size_t 2266656Snate@binkert.org erase(T k) 2276656Snate@binkert.org { 2283101Sstever@eecs.umich.edu return tree.erase(k); 2293101Sstever@eecs.umich.edu } 2303101Sstever@eecs.umich.edu 2313101Sstever@eecs.umich.edu void 2323101Sstever@eecs.umich.edu erase(iterator p) 2333101Sstever@eecs.umich.edu { 2343101Sstever@eecs.umich.edu tree.erase(p); 2354762Snate@binkert.org } 2364762Snate@binkert.org 2374762Snate@binkert.org void 2384762Snate@binkert.org erase(iterator p, iterator q) 2397528Ssteve.reinhardt@amd.com { 2404762Snate@binkert.org tree.erase(p,q); 2414762Snate@binkert.org } 2424762Snate@binkert.org 2437673Snate@binkert.org void 2447673Snate@binkert.org clear() 2454762Snate@binkert.org { 2467673Snate@binkert.org tree.erase(tree.begin(), tree.end()); 2474762Snate@binkert.org } 2487673Snate@binkert.org 2497673Snate@binkert.org iterator 2507673Snate@binkert.org begin() 2517673Snate@binkert.org { 2527673Snate@binkert.org return tree.begin(); 2537673Snate@binkert.org } 2547673Snate@binkert.org 2553101Sstever@eecs.umich.edu iterator 2567673Snate@binkert.org end() 2577673Snate@binkert.org { 2587673Snate@binkert.org return tree.end(); 2593101Sstever@eecs.umich.edu } 2607673Snate@binkert.org 2617673Snate@binkert.org size_t 2623101Sstever@eecs.umich.edu size() 2633101Sstever@eecs.umich.edu { 2643101Sstever@eecs.umich.edu return tree.size(); 2653101Sstever@eecs.umich.edu } 2663101Sstever@eecs.umich.edu 2673101Sstever@eecs.umich.edu bool 2683101Sstever@eecs.umich.edu empty() 2693101Sstever@eecs.umich.edu { 2703101Sstever@eecs.umich.edu return tree.empty(); 2713101Sstever@eecs.umich.edu } 2723101Sstever@eecs.umich.edu}; 2733101Sstever@eecs.umich.edu 2743101Sstever@eecs.umich.edu#endif //__BASE_RANGE_MAP_HH__ 2753101Sstever@eecs.umich.edu