1 /*
   2  * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 package org.graalvm.compiler.lir.alloc.lsra;
  24 
  25 /**
  26  * Represents a range of integers from a start (inclusive) to an end (exclusive.
  27  */
  28 public final class Range {
  29 
  30     public static final Range EndMarker = new Range(Integer.MAX_VALUE, Integer.MAX_VALUE, null);
  31 
  32     /**
  33      * The start of the range, inclusive.
  34      */
  35     public int from;
  36 
  37     /**
  38      * The end of the range, exclusive.
  39      */
  40     public int to;
  41 
  42     /**
  43      * A link to allow the range to be put into a singly linked list.
  44      */
  45     public Range next;
  46 
  47     boolean intersects(Range r) {
  48         return intersectsAt(r) != -1;
  49     }
  50 
  51     /**
  52      * Creates a new range.
  53      *
  54      * @param from the start of the range, inclusive
  55      * @param to the end of the range, exclusive
  56      * @param next link to the next range in a linked list
  57      */
  58     Range(int from, int to, Range next) {
  59         this.from = from;
  60         this.to = to;
  61         this.next = next;
  62     }
  63 
  64     int intersectsAt(Range other) {
  65         Range r1 = this;
  66         Range r2 = other;
  67 
  68         assert r2 != null : "null ranges not allowed";
  69         assert r1 != EndMarker && r2 != EndMarker : "empty ranges not allowed";
  70 
  71         do {
  72             if (r1.from < r2.from) {
  73                 if (r1.to <= r2.from) {
  74                     r1 = r1.next;
  75                     if (r1 == EndMarker) {
  76                         return -1;
  77                     }
  78                 } else {
  79                     return r2.from;
  80                 }
  81             } else {
  82                 if (r2.from < r1.from) {
  83                     if (r2.to <= r1.from) {
  84                         r2 = r2.next;
  85                         if (r2 == EndMarker) {
  86                             return -1;
  87                         }
  88                     } else {
  89                         return r1.from;
  90                     }
  91                 } else { // r1.from() == r2.from()
  92                     if (r1.from == r1.to) {
  93                         r1 = r1.next;
  94                         if (r1 == EndMarker) {
  95                             return -1;
  96                         }
  97                     } else {
  98                         if (r2.from == r2.to) {
  99                             r2 = r2.next;
 100                             if (r2 == EndMarker) {
 101                                 return -1;
 102                             }
 103                         } else {
 104                             return r1.from;
 105                         }
 106                     }
 107                 }
 108             }
 109         } while (true);
 110     }
 111 
 112     @Override
 113     public String toString() {
 114         return "[" + from + ", " + to + "]";
 115     }
 116 }