001    /*
002    Galois, a framework to exploit amorphous data-parallelism in irregular
003    programs.
004    
005    Copyright (C) 2010, The University of Texas at Austin. All rights reserved.
006    UNIVERSITY EXPRESSLY DISCLAIMS ANY AND ALL WARRANTIES CONCERNING THIS SOFTWARE
007    AND DOCUMENTATION, INCLUDING ANY WARRANTIES OF MERCHANTABILITY, FITNESS FOR ANY
008    PARTICULAR PURPOSE, NON-INFRINGEMENT AND WARRANTIES OF PERFORMANCE, AND ANY
009    WARRANTY THAT MIGHT OTHERWISE ARISE FROM COURSE OF DEALING OR USAGE OF TRADE.
010    NO WARRANTY IS EITHER EXPRESS OR IMPLIED WITH RESPECT TO THE USE OF THE
011    SOFTWARE OR DOCUMENTATION. Under no circumstances shall University be liable
012    for incidental, special, indirect, direct or consequential damages or loss of
013    profits, interruption of business, or related expenses which may arise from use
014    of Software or Documentation, including but not limited to those resulting from
015    defects in Software and/or Documentation, or loss or inaccuracy of data of any
016    kind.
017    
018    
019    */
020    
021    
022    
023    
024    
025    package galois.runtime.wl;
026    
027    import galois.runtime.ForeachContext;
028    
029    /**
030     * Order elements in chunks of size <i>N</i>, full chunks are ordered in LIFO order. Elements are unordered
031     * within a chunk and are eligible to be ordered by subsequent rules.
032     * 
033     *
034     * @param <T>  the type of elements of the worklist
035     * @see ChunkedLIFO
036     * @see FIFO
037     */
038    @NestedAreSerial
039    @MatchingConcurrentVersion(ConcurrentChunkedLIFO.class)
040    @MatchingLeafVersion(ChunkedLIFOLeaf.class)
041    public class ChunkedLIFO<T> implements Worklist<T> {
042      public static final int DEFAULT_CHUNK_SIZE = 32;
043    
044      private final int chunkSize;
045      private Worklist<T> current;
046      private Node<T> head;
047      private int size;
048    
049      /**
050       * Creates a chunked LIFO order with the default chunk size ({@value #DEFAULT_CHUNK_SIZE})
051       */
052      public ChunkedLIFO(Maker<T> maker, boolean needSize) {
053        this(DEFAULT_CHUNK_SIZE, maker, needSize);
054      }
055    
056      /**
057       * Creates a chunked LIFO order with the given chunk size
058       * 
059       * @param chunkSize        chunk size to use
060       */
061      public ChunkedLIFO(int chunkSize, Maker<T> maker, boolean needSize) {
062        this(chunkSize, maker.make(), needSize);
063      }
064    
065      private ChunkedLIFO(int chunkSize, Worklist<T> current, boolean needSize) {
066        this.chunkSize = chunkSize;
067        this.current = current;
068        this.head = null;
069      }
070    
071      @Override
072      public Worklist<T> newInstance() {
073        return new ChunkedLIFO<T>(chunkSize, current.newInstance(), false);
074      }
075    
076      @Override
077      public void add(T item, ForeachContext<T> ctx) {
078        size++;
079    
080        current.add(item, ctx);
081    
082        if (current.size() >= chunkSize) {
083          addInternal(current);
084          current = current.newInstance();
085        }
086      }
087    
088      @Override
089      public void addInitial(T item, ForeachContext<T> ctx) {
090        add(item, ctx);
091      }
092    
093      @Override
094      public T poll(final ForeachContext<T> ctx) {
095        if (current == null)
096          current = pollInternal();
097    
098        T retval = null;
099        while (current != null) {
100          retval = current.poll(ctx);
101    
102          if (retval == null) {
103            current = pollInternal();
104          } else {
105            break;
106          }
107        }
108    
109        if (retval != null)
110          size++;
111    
112        return retval;
113      }
114    
115      private void addInternal(Worklist<T> wl) {
116        Node<T> next = new Node<T>(wl);
117        next.next = head;
118        head = next;
119      }
120    
121      private Worklist<T> pollInternal() {
122        Node<T> cur = head;
123    
124        if (cur == null)
125          return null;
126        Node<T> next = cur.next;
127        head = next;
128    
129        return cur.wl;
130      }
131    
132      @Override
133      public boolean isEmpty() {
134        return head == null;
135      }
136    
137      @Override
138      public int size() {
139        return size;
140      }
141    
142      @Override
143      public void finishAddInitial() {
144    
145      }
146    
147      private static class Node<T> {
148        private Node<T> next;
149        private Worklist<T> wl;
150    
151        public Node(Worklist<T> wl) {
152          this.wl = wl;
153        }
154      }
155    }