1 /*
   2  * Copyright (c) 2014, 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.dfa;
  24 
  25 import java.util.ArrayDeque;
  26 import java.util.BitSet;
  27 import java.util.Collection;
  28 
  29 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
  30 
  31 /**
  32  * Ensures that an element is only in the worklist once.
  33  *
  34  */
  35 class UniqueWorkList extends ArrayDeque<AbstractBlockBase<?>> {
  36     private static final long serialVersionUID = 8009554570990975712L;
  37     BitSet valid;
  38 
  39     UniqueWorkList(int size) {
  40         this.valid = new BitSet(size);
  41     }
  42 
  43     @Override
  44     public AbstractBlockBase<?> poll() {
  45         AbstractBlockBase<?> result = super.poll();
  46         if (result != null) {
  47             valid.set(result.getId(), false);
  48         }
  49         return result;
  50     }
  51 
  52     @Override
  53     public boolean add(AbstractBlockBase<?> pred) {
  54         if (!valid.get(pred.getId())) {
  55             valid.set(pred.getId(), true);
  56             return super.add(pred);
  57         }
  58         return false;
  59     }
  60 
  61     @Override
  62     public boolean addAll(Collection<? extends AbstractBlockBase<?>> collection) {
  63         boolean changed = false;
  64         for (AbstractBlockBase<?> element : collection) {
  65             if (!valid.get(element.getId())) {
  66                 valid.set(element.getId(), true);
  67                 super.add(element);
  68                 changed = true;
  69             }
  70         }
  71         return changed;
  72     }
  73 }