addr_range.hh revision 531
112839Sgabeblack@google.com/* 212839Sgabeblack@google.com * Copyright (c) 2003 The Regents of The University of Michigan 312839Sgabeblack@google.com * All rights reserved. 412839Sgabeblack@google.com * 512839Sgabeblack@google.com * Redistribution and use in source and binary forms, with or without 612839Sgabeblack@google.com * modification, are permitted provided that the following conditions are 712839Sgabeblack@google.com * met: redistributions of source code must retain the above copyright 812839Sgabeblack@google.com * notice, this list of conditions and the following disclaimer; 912839Sgabeblack@google.com * redistributions in binary form must reproduce the above copyright 1012839Sgabeblack@google.com * notice, this list of conditions and the following disclaimer in the 1112839Sgabeblack@google.com * documentation and/or other materials provided with the distribution; 1212839Sgabeblack@google.com * neither the name of the copyright holders nor the names of its 1312839Sgabeblack@google.com * contributors may be used to endorse or promote products derived from 1412839Sgabeblack@google.com * this software without specific prior written permission. 1512839Sgabeblack@google.com * 1612839Sgabeblack@google.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1712839Sgabeblack@google.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1812839Sgabeblack@google.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1912839Sgabeblack@google.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2012839Sgabeblack@google.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2112839Sgabeblack@google.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2212839Sgabeblack@google.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2312839Sgabeblack@google.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2412839Sgabeblack@google.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2512839Sgabeblack@google.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2612839Sgabeblack@google.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2712839Sgabeblack@google.com */ 2812839Sgabeblack@google.com 2912839Sgabeblack@google.com#ifndef __RANGE_HH__ 3012839Sgabeblack@google.com#define __RANGE_HH__ 3112993Sgabeblack@google.com 3212993Sgabeblack@google.com#include <cassert> 3312993Sgabeblack@google.com#include <string> 3413129Sgabeblack@google.com 3512993Sgabeblack@google.comtemplate <class T> 3612839Sgabeblack@google.combool __parse_range(const std::string &s, T &start, T &end); 3712839Sgabeblack@google.com 3812993Sgabeblack@google.comtemplate <class T> 3912993Sgabeblack@google.comstruct Range 4012993Sgabeblack@google.com{ 4112993Sgabeblack@google.com private: 4212993Sgabeblack@google.com /** 4312993Sgabeblack@google.com * @param s range string 4412993Sgabeblack@google.com * Ranges are in the following format: 4512993Sgabeblack@google.com * <range> := {<start_val>}:{<end>} 4612993Sgabeblack@google.com * <end> := <end_val> | +<delta> 4712993Sgabeblack@google.com */ 4812993Sgabeblack@google.com void 4912993Sgabeblack@google.com parse(const std::string &s) 5012993Sgabeblack@google.com { 5112993Sgabeblack@google.com if (!__parse_range(s, start, end)) 5212993Sgabeblack@google.com invalidate(); 5312993Sgabeblack@google.com } 5412993Sgabeblack@google.com 5512993Sgabeblack@google.com public: 5612993Sgabeblack@google.com T start; 5712993Sgabeblack@google.com T end; 5812993Sgabeblack@google.com 5912993Sgabeblack@google.com public: 6012993Sgabeblack@google.com Range() 6112993Sgabeblack@google.com { 6212993Sgabeblack@google.com invalidate(); 6312993Sgabeblack@google.com } 6412993Sgabeblack@google.com 6513131Sgabeblack@google.com template <class U> 6612993Sgabeblack@google.com Range(const Range<U> &r) 6713131Sgabeblack@google.com : start(r.start), end(r.end) 6812993Sgabeblack@google.com {} 6912993Sgabeblack@google.com 7012993Sgabeblack@google.com template <class U> 7112993Sgabeblack@google.com Range(const std::pair<U, U> &r) 7212993Sgabeblack@google.com : start(r.first), end(r.second) 7312993Sgabeblack@google.com {} 7412993Sgabeblack@google.com 7512993Sgabeblack@google.com Range(const std::string &s) 7612993Sgabeblack@google.com { 7712993Sgabeblack@google.com parse(s); 7812993Sgabeblack@google.com } 7912993Sgabeblack@google.com 8012993Sgabeblack@google.com template <class U> 8112993Sgabeblack@google.com const Range<T> &operator=(const Range<U> &r) 8212993Sgabeblack@google.com { 8312993Sgabeblack@google.com start = r.start; 8412993Sgabeblack@google.com end = r.end; 8512993Sgabeblack@google.com return *this; 8612993Sgabeblack@google.com } 8712993Sgabeblack@google.com 8812993Sgabeblack@google.com template <class U> 8912993Sgabeblack@google.com const Range<T> &operator=(const std::pair<U, U> &r) 9012993Sgabeblack@google.com { 9112993Sgabeblack@google.com start = r.first; 9212993Sgabeblack@google.com end = r.second; 9312993Sgabeblack@google.com return *this; 9412993Sgabeblack@google.com } 9512993Sgabeblack@google.com 9612839Sgabeblack@google.com const Range &operator=(const std::string &s) 9712839Sgabeblack@google.com { 9812839Sgabeblack@google.com parse(s); 9912993Sgabeblack@google.com return *this; 10012993Sgabeblack@google.com } 10112993Sgabeblack@google.com 10212839Sgabeblack@google.com void invalidate() { start = 0; end = 0; } 10312839Sgabeblack@google.com bool size() const { return end - start; } 10412839Sgabeblack@google.com bool valid() const { return start < end; } 10512839Sgabeblack@google.com}; 10612839Sgabeblack@google.com 10712993Sgabeblack@google.comtemplate<class T> 10812839Sgabeblack@google.cominline std::ostream & 10912839Sgabeblack@google.comoperator<<(std::ostream &o, const Range<T> &r) 11012839Sgabeblack@google.com{ 11112839Sgabeblack@google.com // don't currently support output of invalid ranges 11212839Sgabeblack@google.com assert(r.valid()); 11312993Sgabeblack@google.com o << r.start << ":" << r.end; 11412839Sgabeblack@google.com return o; 11512839Sgabeblack@google.com} 11612839Sgabeblack@google.com 11712993Sgabeblack@google.com//////////////////////////////////////////////////////////////////////// 11812839Sgabeblack@google.com// 11912993Sgabeblack@google.com// Range to Range Comparisons 12012839Sgabeblack@google.com// 12112839Sgabeblack@google.com 12212839Sgabeblack@google.com/** 12312839Sgabeblack@google.com * @param range1 is a range. 12412993Sgabeblack@google.com * @param range2 is a range. 12512839Sgabeblack@google.com * @return if range1 and range2 are identical. 12612993Sgabeblack@google.com */ 12712839Sgabeblack@google.comtemplate<class T, class U> 12812839Sgabeblack@google.cominline bool 12912839Sgabeblack@google.comoperator==(const Range<T> &range1, const Range<U> &range2) 13012993Sgabeblack@google.com{ 13112839Sgabeblack@google.com assert(range1.valid() && range2.valid()); 13212993Sgabeblack@google.com return range1.start == range2.start && range1.end == range2.end; 13312839Sgabeblack@google.com} 13412839Sgabeblack@google.com 13512839Sgabeblack@google.com/** 13612993Sgabeblack@google.com * @param range1 is a range. 13712839Sgabeblack@google.com * @param range2 is a range. 13812993Sgabeblack@google.com * @return if range1 and range2 are not identical. 13912839Sgabeblack@google.com */ 14012839Sgabeblack@google.comtemplate<class T, class U> 14112839Sgabeblack@google.cominline bool 14212993Sgabeblack@google.comoperator!=(const Range<T> &range1, const Range<U> &range2) 14312839Sgabeblack@google.com{ 14412993Sgabeblack@google.com assert(range1.valid() && range2.valid()); 14512839Sgabeblack@google.com return range1.start != range2.start || range1.end != range2.end; 14612839Sgabeblack@google.com} 14712839Sgabeblack@google.com 14812993Sgabeblack@google.com/** 14912839Sgabeblack@google.com * @param range1 is a range. 15012993Sgabeblack@google.com * @param range2 is a range. 15112839Sgabeblack@google.com * @return if range1 is less than range2 and does not overlap range1. 15212839Sgabeblack@google.com */ 15312839Sgabeblack@google.comtemplate<class T, class U> 15412839Sgabeblack@google.cominline bool 15512839Sgabeblack@google.comoperator<(const Range<T> &range1, const Range<U> &range2) 15612839Sgabeblack@google.com{ 15712839Sgabeblack@google.com assert(range1.valid() && range2.valid()); 15812839Sgabeblack@google.com return range1.end <= range2.start; 15912839Sgabeblack@google.com} 16012839Sgabeblack@google.com 16112839Sgabeblack@google.com/** 16212839Sgabeblack@google.com * @param range1 is a range. 16312839Sgabeblack@google.com * @param range2 is a range. 16412839Sgabeblack@google.com * @return if range1 is less than range2. range1 may overlap range2, 16512839Sgabeblack@google.com * but not extend beyond the end of range2. 16612839Sgabeblack@google.com */ 16712839Sgabeblack@google.comtemplate<class T, class U> 16812839Sgabeblack@google.cominline bool 16912839Sgabeblack@google.comoperator<=(const Range<T> &range1, const Range<U> &range2) 17012839Sgabeblack@google.com{ 17112839Sgabeblack@google.com assert(range1.valid() && range2.valid()); 17212839Sgabeblack@google.com return range1.start <= range2.start && range1.end <= range2.end; 17312839Sgabeblack@google.com} 17412839Sgabeblack@google.com 17512839Sgabeblack@google.com/** 17612839Sgabeblack@google.com * @param range1 is a range. 17712839Sgabeblack@google.com * @param range2 is a range. 17812839Sgabeblack@google.com * @return if range1 is greater than range2 and does not overlap range2. 17912839Sgabeblack@google.com */ 18012839Sgabeblack@google.comtemplate<class T, class U> 18112839Sgabeblack@google.cominline bool 18212839Sgabeblack@google.comoperator>(const Range<T> &range1, const Range<U> &range2) 18312839Sgabeblack@google.com{ 18412839Sgabeblack@google.com assert(range1.valid() && range2.valid()); 18512839Sgabeblack@google.com return range1.start >= range2.end; 18612839Sgabeblack@google.com} 18712839Sgabeblack@google.com 18812839Sgabeblack@google.com/** 18912839Sgabeblack@google.com * @param range1 is a range. 19012839Sgabeblack@google.com * @param range2 is a range. 19112839Sgabeblack@google.com * @return if range1 is greater than range2. range1 may overlap range2, 19212839Sgabeblack@google.com * but not extend beyond the beginning of range2. 19312839Sgabeblack@google.com */ 19412839Sgabeblack@google.comtemplate<class T, class U> 19512839Sgabeblack@google.cominline bool 19612839Sgabeblack@google.comoperator>=(const Range<T> &range1, const Range<U> &range2) 19712839Sgabeblack@google.com{ 19812839Sgabeblack@google.com assert(range1.valid() && range2.valid()); 19912839Sgabeblack@google.com return range1.start >= range2.start && range1.end >= range2.end; 20012839Sgabeblack@google.com} 20112839Sgabeblack@google.com 20212839Sgabeblack@google.com//////////////////////////////////////////////////////////////////////// 20312839Sgabeblack@google.com// 20412839Sgabeblack@google.com// Position to Range Comparisons 20512839Sgabeblack@google.com// 20612839Sgabeblack@google.com 20712839Sgabeblack@google.com/** 20812839Sgabeblack@google.com * @param pos position compared to the range. 20912839Sgabeblack@google.com * @param range range compared against. 21012839Sgabeblack@google.com * @return indicates that position pos is within the range. 21112839Sgabeblack@google.com */ 21212839Sgabeblack@google.comtemplate<class T, class U> 21312839Sgabeblack@google.cominline bool 21412839Sgabeblack@google.comoperator==(const T &pos, const Range<U> &range) 21512839Sgabeblack@google.com{ 21612839Sgabeblack@google.com assert(range.valid()); 21712839Sgabeblack@google.com return pos >= range.start && pos < range.end; 21812839Sgabeblack@google.com} 21912839Sgabeblack@google.com 22012839Sgabeblack@google.com/** 22112839Sgabeblack@google.com * @param pos position compared to the range. 22212839Sgabeblack@google.com * @param range range compared against. 22312839Sgabeblack@google.com * @return indicates that position pos is not within the range. 22412839Sgabeblack@google.com */ 22512839Sgabeblack@google.comtemplate<class T, class U> 226inline bool 227operator!=(const T &pos, const Range<U> &range) 228{ 229 assert(range.valid()); 230 return pos < range.start || pos >= range.end; 231} 232 233/** 234 * @param pos position compared to the range. 235 * @param range range compared against. 236 * @return indicates that position pos is below the range. 237 */ 238template<class T, class U> 239inline bool 240operator<(const T &pos, const Range<U> &range) 241{ 242 assert(range.valid()); 243 return pos < range.start; 244} 245 246/** 247 * @param pos position compared to the range. 248 * @param range range compared against. 249 * @return indicates that position pos is below or in the range. 250 */ 251template<class T, class U> 252inline bool 253operator<=(const T &pos, const Range<U> &range) 254{ 255 assert(range.valid()); 256 return pos < range.end; 257} 258 259/** 260 * @param pos position compared to the range. 261 * @param range range compared against. 262 * @return indicates that position pos is above the range. 263 */ 264template<class T, class U> 265inline bool 266operator>(const T &pos, const Range<U> &range) 267{ 268 assert(range.valid()); 269 return pos >= range.end; 270} 271 272/** 273 * @param pos position compared to the range. 274 * @param range range compared against. 275 * @return indicates that position pos is above or in the range. 276 */ 277template<class T, class U> 278inline bool 279operator>=(const T &pos, const Range<U> &range) 280{ 281 assert(range.valid()); 282 return pos >= range.start; 283} 284 285//////////////////////////////////////////////////////////////////////// 286// 287// Range to Position Comparisons (for symmetry) 288// 289 290/** 291 * @param range range compared against. 292 * @param pos position compared to the range. 293 * @return indicates that position pos is within the range. 294 */ 295template<class T, class U> 296inline bool 297operator==(const Range<T> &range, const U &pos) 298{ 299 assert(range.valid()); 300 return pos >= range.start && pos < range.end; 301} 302 303/** 304 * @param range range compared against. 305 * @param pos position compared to the range. 306 * @return indicates that position pos is not within the range. 307 */ 308template<class T, class U> 309inline bool 310operator!=(const Range<T> &range, const U &pos) 311{ 312 assert(range.valid()); 313 return pos < range.start || pos >= range.end; 314} 315 316/** 317 * @param range range compared against. 318 * @param pos position compared to the range. 319 * @return indicates that position pos is above the range. 320 */ 321template<class T, class U> 322inline bool 323operator<(const Range<T> &range, const U &pos) 324{ 325 assert(range.valid()); 326 return range.end <= pos; 327} 328 329/** 330 * @param range range compared against. 331 * @param pos position compared to the range. 332 * @return indicates that position pos is above or in the range. 333 */ 334template<class T, class U> 335inline bool 336operator<=(const Range<T> &range, const U &pos) 337{ 338 assert(range.valid()); 339 return range.start <= pos; 340} 341 342/** 343 * @param range range compared against. 344 * @param pos position compared to the range. 345 * 'range > pos' indicates that position pos is below the range. 346 */ 347template<class T, class U> 348inline bool 349operator>(const Range<T> &range, const U &pos) 350{ 351 assert(range.valid()); 352 return range.start > pos; 353} 354 355/** 356 * @param range range compared against. 357 * @param pos position compared to the range. 358 * 'range >= pos' indicates that position pos is below or in the range. 359 */ 360template<class T, class U> 361inline bool 362operator>=(const Range<T> &range, const U &pos) 363{ 364 assert(range.valid()); 365 return range.end > pos; 366} 367 368#endif // __RANGE_HH__ 369