1 /*
   2  * Copyright (c) 2015, 2015, 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.trace.lsra;
  24 
  25 /**
  26  * Represents a range of integers from a start (inclusive) to an end (exclusive).
  27  */
  28 final class FixedRange {
  29 
  30     public static final FixedRange EndMarker = new FixedRange(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 FixedRange next;
  46 
  47     boolean intersects(TraceInterval i) {
  48         return intersectsAt(i) != -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     FixedRange(int from, int to, FixedRange next) {
  59         this.from = from;
  60         this.to = to;
  61         this.next = next;
  62     }
  63 
  64     int intersectsAt(TraceInterval other) {
  65         FixedRange range = this;
  66         assert other != null : "null ranges not allowed";
  67         assert range != EndMarker && other != TraceInterval.EndMarker : "empty ranges not allowed";
  68         int intervalFrom = other.from();
  69         int intervalTo = other.to();
  70 
  71         do {
  72             if (range.from < intervalFrom) {
  73                 if (range.to <= intervalFrom) {
  74                     range = range.next;
  75                     if (range == EndMarker) {
  76                         return -1;
  77                     }
  78                 } else {
  79                     return intervalFrom;
  80                 }
  81             } else {
  82                 if (intervalFrom < range.from) {
  83                     if (intervalTo <= range.from) {
  84                         return -1;
  85                     }
  86                     return range.from;
  87                 } else {
  88                     assert range.from == intervalFrom;
  89                     if (range.from == range.to) {
  90                         range = range.next;
  91                         if (range == EndMarker) {
  92                             return -1;
  93                         }
  94                     } else {
  95                         if (intervalFrom == intervalTo) {
  96                             return -1;
  97                         }
  98                         return range.from;
  99                     }
 100                 }
 101             }
 102         } while (true);
 103     }
 104 
 105     @Override
 106     public String toString() {
 107         return "[" + from + ", " + to + "]";
 108     }
 109 }