src/main/gov/nasa/jpf/util/LinkedObjectQueue.java

   1 /*
   2  * Copyright (C) 2014, United States Government, as represented by the
   3  * Administrator of the National Aeronautics and Space Administration.
   4  * All rights reserved.
   5  *
   6  * The Java Pathfinder core (jpf-core) platform is licensed under the
   7  * Apache License, Version 2.0 (the "License"); you may not use this file except
   8  * in compliance with the License. You may obtain a copy of the License at
   9  *
  10  *        http://www.apache.org/licenses/LICENSE-2.0.
  11  *
  12  * Unless required by applicable law or agreed to in writing, software
  13  * distributed under the License is distributed on an "AS IS" BASIS,
  14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15  * See the License for the specific language governing permissions and
  16  * limitations under the License.
  17  */
  18
  19 package gov.nasa.jpf.util;
  20
  21 import java.util.Iterator;
  22 import java.util.NoSuchElementException;
  23
  24 /**
  25  * object queue that uses cached link entries
  26  */
  27 public class LinkedObjectQueue<E> implements ObjectQueue<E> {
  28
  29   static class Entry {
  30     Entry next; // single linked list
  31     Object obj;  // referenced object
  32   }
  33
  34   protected Entry last;
  35   protected Entry first;
  36
  37   protected int size;
  38
  39   protected int maxCache;
  40   protected int nFree;
  41   protected Entry free;
  42
  43   class FIFOIterator implements Iterator<E> {
  44     Entry e = first;
  45
  46     @Override
  47         public boolean hasNext() {
  48       return e != null;
  49     }
  50
  51     @Override
  52         public E next() {
  53       if (e == null){
  54         throw new NoSuchElementException();
  55       } else {
  56         E obj = (E)e.obj;
  57         e = e.next;
  58         return obj;
  59       }
  60     }
  61
  62     @Override
  63         public void remove() {
  64       throw new UnsupportedOperationException("arbitrary remove from queue not supported");
  65     }
  66   }
  67
  68   public LinkedObjectQueue (){
  69     maxCache = 256;
  70   }
  71
  72   public LinkedObjectQueue (int maxCache){
  73     this.maxCache = maxCache;
  74   }
  75
  76   @Override
  77   public int size() {
  78     return size;
  79   }
  80
  81   @Override
  82   public boolean add(E obj) {
  83     Entry e;
  84
  85     if (nFree > 0){ // reuse a cached Entry object
  86       e = free;
  87       free = e.next;
  88       nFree--;
  89
  90     } else {
  91       e = new Entry();
  92     }
  93
  94     e.obj = obj;
  95     e.next = null;
  96
  97     if (last != null) {
  98       last.next = e;
  99     } else {
 100       first = e;
 101     }
 102
 103     last = e;
 104
 105     size++;
 106     return true;
 107   }
 108
 109   @Override
 110   public boolean offer( E obj){
 111     return add(obj);
 112   }
 113
 114   @Override
 115   public boolean isEmpty(){
 116     return size > 0;
 117   }
 118
 119   @Override
 120   public E peek (){
 121     if (size == 0){
 122       return null;
 123     } else {
 124       return (E)first.obj;
 125     }
 126   }
 127
 128   @Override
 129   public E poll(){
 130     if (size == 0){
 131       return null;
 132
 133     } else {
 134       Entry e = first;
 135       first = first.next;
 136       size--;
 137
 138       E obj = (E)e.obj;
 139
 140       if (nFree < maxCache){
 141         Entry next = e.next;
 142         e.next = (nFree++ > 0) ? free : null;
 143         e.obj = null;
 144         free = e;
 145       }
 146
 147       return obj;
 148     }
 149   }
 150
 151   @Override
 152   public E remove() throws NoSuchElementException {
 153     if (size == 0){
 154       throw new NoSuchElementException();
 155     } else {
 156       return poll();
 157     }
 158   }
 159
 160   @Override
 161   public Iterator<E> iterator(){
 162     return new FIFOIterator();
 163   }
 164
 165   @Override
 166   public void process( Processor<E> proc) {
 167     for (Entry e = first; e != null; ) {
 168       proc.process( (E)e.obj);
 169
 170       e.obj = null; // avoid memory leaks
 171
 172       if (nFree < maxCache){
 173         // recycle to save some allocation and a lot of shortliving garbage
 174         Entry next = e.next;
 175         e.next = (nFree++ > 0) ? free : null;
 176         free = e;
 177         e = next;
 178
 179       } else {
 180         e = e.next;
 181       }
 182     }
 183     clear();
 184   }
 185
 186   @Override
 187   public void clear () {
 188     first = null;
 189     last = null;
 190     size = 0;
 191
 192     // don't reset nFree and free since we limit the memory size of our cache
 193     // and the Entry object do not reference anything
 194   }
 195 }