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 File: LocalComputationGraph.java
019
020 */
021
022 package galois.objects.graph;
023
024 import galois.objects.GObject;
025 import galois.objects.MethodFlag;
026 import galois.runtime.Callback;
027 import galois.runtime.GaloisRuntime;
028 import galois.runtime.Iteration;
029 import galois.runtime.IterationAbortException;
030 import galois.runtime.MapInternalContext;
031 import gnu.trove.list.array.TIntArrayList;
032 import gnu.trove.map.hash.TObjectIntHashMap;
033
034 import java.util.ArrayList;
035 import java.util.List;
036 import java.util.concurrent.atomic.AtomicInteger;
037
038 import util.fn.Lambda2Void;
039 import util.fn.Lambda3Void;
040 import util.fn.LambdaVoid;
041
042 /**
043 * Implementation of an {@link ObjectGraph} that is optimized for <i>local computation</i> operators: operators
044 * that do not add/remove nodes and edges to/from the graph. An attempt to modify the structure of the graph
045 * will result on an {@link UnsupportedOperationException}. The most typical scenario involves creating
046 * a local computation graph out of a {@link MorphGraph}:
047 * <pre>
048 * // create a morph graph
049 * ObjectGraph<Object, Object> mg = MorphGraph.ObjectGraphBuilder().create();
050 * // build the graph
051 * mg.add(...);
052 * mg.addEdge(...);
053 * // create a local computation graph out of the morph graph
054 * ObjectGraph<Object, Object> lcg = new LocalComputationGraph.ObjectGraphBuilder().from(mg).create();
055 * </pre>
056 *
057 * @param <N> the type of the object stored in each node
058 * @param <E> the type of the object stored in each edge
059 */
060 public final class LocalComputationGraph<N extends GObject, E> implements ObjectGraph<N, E> {
061 private static final int chunkSize = 2 * GaloisRuntime.getRuntime().getMaxThreads();
062 private final AtomicInteger mapCur;
063
064 private Node[] nodes;
065 private E[] edgeData;
066 private int[] inIdx;
067 private int[] ins;
068 private int[] outIdx;
069 private int[] outs;
070
071 LocalComputationGraph(ObjectGraph<N, E> in) {
072 createGraph(in);
073 mapCur = new AtomicInteger();
074 }
075
076 /**
077 * A {@link galois.objects.graph.LocalComputationGraph} builder, providing combinations of several features.
078 */
079 @SuppressWarnings("unchecked")
080 public static class ObjectGraphBuilder {
081 private boolean serial = false;
082 private ObjectGraph in;
083
084 /**
085 * Constructs a new builder instance assuming that the graph about to be created is parallel.
086 */
087 public ObjectGraphBuilder() {
088 }
089
090 /**
091 * Indicates whether the implementation of the graph about to be created is serial (there is no concurrency or
092 * transactional support) or parallel (can be safely used within Galois iterators). For example, a graph that is
093 * purely thread local can benefit from using a serial implementation, which is expected to add no overheads
094 * due to concurrency or the runtime system.
095 *
096 * @param serial boolean value that indicates whether the graph is serial or not.
097 */
098 public ObjectGraphBuilder serial(boolean serial) {
099 this.serial = serial;
100 return this;
101 }
102
103 /**
104 * Indicate the graph used as the initial value for the local computation instance about to be created.
105 *
106 * @param in initial value for the graph
107 */
108 public ObjectGraphBuilder from(ObjectGraph in) {
109 this.in = in;
110 return this;
111 }
112
113 /**
114 * Builds the final graph. This method does not alter the state of this
115 * builder instance, so it can be invoked again to create
116 * multiple independent graphs.
117 *
118 * @param <N> the type of the object stored in each node
119 * @param <E> the type of the object stored in each edge
120 * @return an object graph with the requested features
121 */
122 public <N extends GObject, E> ObjectGraph<N, E> create() {
123 ObjectGraph<N, E> retval;
124 if (serial || GaloisRuntime.getRuntime().useSerial()) {
125 retval = new SerialLocalComputationObjectGraph<N, E>(in);
126 } else {
127 retval = new LocalComputationGraph<N, E>(in);
128 }
129
130 if (GaloisRuntime.getRuntime().ignoreUserFlags()) {
131 retval = new ObjectGraphToAllObjectGraphAdapter<N, E>(retval);
132 }
133
134 return retval;
135 }
136 }
137
138 /**
139 * A {@link galois.objects.graph.LocalComputationGraph} builder, providing combinations of several features.
140 */
141 @SuppressWarnings("unchecked")
142 public static class IntGraphBuilder {
143 private boolean serial = false;
144 private ObjectGraph in;
145
146 /**
147 * Constructs a new builder instance assuming that the graph about to be created is parallel.
148 */
149 public IntGraphBuilder() {
150 }
151
152 /**
153 * Indicates whether the implementation of the graph about to be created is serial (there is no concurrency or
154 * transactional support) or parallel (can be safely used within Galois iterators). For example, a graph that is
155 * purely thread local can benefit from using a serial implementation, which is expected to add no overheads
156 * due to concurrency or the runtime system.
157 *
158 * @param serial boolean value that indicates whether the graph is serial or not.
159 */
160 public IntGraphBuilder serial(boolean serial) {
161 this.serial = serial;
162 return this;
163 }
164
165 /**
166 * Indicate the graph used as the initial value for the local computation instance about to be created.
167 *
168 * @param in initial value for the graph
169 */
170 public <N extends GObject> IntGraphBuilder from(IntGraph<N> in) {
171 this.in = new IntGraphToObjectGraphAdapter<N>(in);
172 return this;
173 }
174
175 /**
176 * Builds the final graph. This method does not alter the state of this
177 * builder instance, so it can be invoked again to create
178 * multiple independent graphs.
179 *
180 * @param <N> the type of the object stored in each node
181 * @return an integer graph with the requested features
182 */
183 public <N extends GObject> IntGraph<N> create() {
184 return new ObjectGraphToIntGraphAdapter(new ObjectGraphBuilder().serial(serial).from(in).create());
185 }
186 }
187
188 /**
189 * A {@link galois.objects.graph.LocalComputationGraph} builder, providing combinations of several features.
190 */
191 @SuppressWarnings("unchecked")
192 public static class LongGraphBuilder {
193 private boolean serial = false;
194 private ObjectGraph in;
195
196 /**
197 * Constructs a new builder instance assuming that the graph about to be created is parallel.
198 */
199 public LongGraphBuilder() {
200 }
201
202 /**
203 * Indicates whether the implementation of the graph about to be created is serial (there is no concurrency or
204 * transactional support) or parallel (can be safely used within Galois iterators). For example, a graph that is
205 * purely thread local can benefit from using a serial implementation, which is expected to add no overheads
206 * due to concurrency or the runtime system.
207 *
208 * @param serial boolean value that indicates whether the graph is serial or not.
209 */
210 public LongGraphBuilder serial(boolean serial) {
211 this.serial = serial;
212 return this;
213 }
214
215 /**
216 * Indicate the graph used as the initial value for the local computation instance about to be created.
217 *
218 * @param in initial value for the graph
219 */
220 public <N extends GObject> LongGraphBuilder from(LongGraph<N> in) {
221 this.in = new LongGraphToObjectGraphAdapter<N>(in);
222 return this;
223 }
224
225 /**
226 * Builds the final graph. This method does not alter the state of this
227 * builder instance, so it can be invoked again to create
228 * multiple independent graphs.
229 *
230 * @param <N> the type of the object stored in each node
231 * @return a long graph with the requested features
232 */
233 public <N extends GObject> LongGraph<N> create() {
234 return new ObjectGraphToLongGraphAdapter(new ObjectGraphBuilder().serial(serial).from(in).create());
235 }
236 }
237
238 /**
239 * A {@link galois.objects.graph.LocalComputationGraph} builder, providing combinations of several features.
240 */
241 @SuppressWarnings("unchecked")
242 public static class FloatGraphBuilder {
243 private boolean serial = false;
244 private ObjectGraph in;
245
246 /**
247 * Constructs a new builder instance assuming that the graph about to be created is parallel.
248 */
249 public FloatGraphBuilder() {
250 }
251
252 /**
253 * Indicates whether the implementation of the graph about to be created is serial (there is no concurrency or
254 * transactional support) or parallel (can be safely used within Galois iterators). For example, a graph that is
255 * purely thread local can benefit from using a serial implementation, which is expected to add no overheads
256 * due to concurrency or the runtime system.
257 *
258 * @param serial boolean value that indicates whether the graph is serial or not.
259 */
260 public FloatGraphBuilder serial(boolean serial) {
261 this.serial = serial;
262 return this;
263 }
264
265 /**
266 * Indicate the graph used as the initial value for the local computation instance about to be created.
267 *
268 * @param in initial value for the graph
269 */
270 public <N extends GObject> FloatGraphBuilder from(FloatGraph<N> in) {
271 this.in = new FloatGraphToObjectGraphAdapter<N>(in);
272 return this;
273 }
274
275 /**
276 * Builds the final graph. This method does not alter the state of this
277 * builder instance, so it can be invoked again to create
278 * multiple independent graphs.
279 *
280 * @param <N> the type of the object stored in each node
281 * @return a float graph with the requested features
282 */
283 public <N extends GObject> FloatGraph<N> create() {
284 return new ObjectGraphToFloatGraphAdapter(new ObjectGraphBuilder().serial(serial).from(in).create());
285 }
286 }
287
288 /**
289 * A {@link galois.objects.graph.LocalComputationGraph} builder, providing combinations of several features.
290 */
291 @SuppressWarnings("unchecked")
292 public static class DoubleGraphBuilder {
293 private boolean serial = false;
294 private ObjectGraph in;
295
296 /**
297 * Constructs a new builder instance assuming that the graph about to be created is parallel.
298 */
299 public DoubleGraphBuilder() {
300 }
301
302 /**
303 * Indicates whether the implementation of the graph about to be created is serial (there is no concurrency or
304 * transactional support) or parallel (can be safely used within Galois iterators). For example, a graph that is
305 * purely thread local can benefit from using a serial implementation, which is expected to add no overheads
306 * due to concurrency or the runtime system.
307 *
308 * @param serial boolean value that indicates whether the graph is serial or not.
309 */
310 public DoubleGraphBuilder serial(boolean serial) {
311 this.serial = serial;
312 return this;
313 }
314
315 /**
316 * Indicate the graph used as the initial value for the local computation instance about to be created.
317 *
318 * @param in initial value for the graph
319 */
320 public <N extends GObject> DoubleGraphBuilder from(DoubleGraph<N> in) {
321 this.in = new DoubleGraphToObjectGraphAdapter<N>(in);
322 return this;
323 }
324
325 /**
326 * Builds the final graph. This method does not alter the state of this
327 * builder instance, so it can be invoked again to create
328 * multiple independent graphs.
329 *
330 * @param <N> the type of the object stored in each node
331 * @return a double graph with the requested features
332 */
333 public <N extends GObject> DoubleGraph<N> create() {
334 return new ObjectGraphToDoubleGraphAdapter(new ObjectGraphBuilder().serial(serial).from(in).create());
335 }
336 }
337
338 /**
339 * A {@link galois.objects.graph.LocalComputationGraph} builder, providing combinations of several features.
340 */
341 @SuppressWarnings("unchecked")
342 public static class VoidGraphBuilder {
343 private boolean serial = false;
344 private Graph in;
345
346 /**
347 * Constructs a new builder instance assuming that the graph about to be created is parallel.
348 */
349 public VoidGraphBuilder() {
350 }
351
352 /**
353 * Indicates whether the implementation of the graph about to be created is serial (there is no concurrency or
354 * transactional support) or parallel (can be safely used within Galois iterators). For example, a graph that is
355 * purely thread local can benefit from using a serial implementation, which is expected to add no overheads
356 * due to concurrency or the runtime system.
357 *
358 * @param serial boolean value that indicates whether the graph is serial or not.
359 */
360 public VoidGraphBuilder serial(boolean serial) {
361 this.serial = serial;
362 return this;
363 }
364
365 /**
366 * Indicate the graph used as the initial value for the local computation instance about to be created.
367 *
368 * @param in initial value for the graph
369 */
370 public VoidGraphBuilder from(Graph in) {
371 this.in = in;
372 return this;
373 }
374
375 /**
376 * Builds the final graph. This method does not alter the state of this
377 * builder instance, so it can be invoked again to create
378 * multiple independent graphs.
379 *
380 * @param <N> the type of the object stored in each node
381 * @return a graph with the requested features
382 */
383 public <N extends GObject> Graph<N> create() {
384 return new ObjectGraphToVoidGraphAdapter(new ObjectGraphBuilder().serial(serial).from(
385 new VoidGraphToObjectGraphAdapter<N, Object>(in)).create());
386 }
387 }
388
389 @SuppressWarnings("unchecked")
390 private void createGraph(final ObjectGraph<N, E> g) {
391 int numNodes = g.size();
392 this.nodes = new LocalComputationGraph.Node[numNodes];
393 final GNode[] rnodes = new GNode[numNodes];
394 final TObjectIntHashMap<GNode<N>> nodeMap = new TObjectIntHashMap<GNode<N>>();
395
396 g.map(new LambdaVoid<GNode<N>>() {
397 @Override
398 public void call(GNode<N> node) {
399 int idx = nodeMap.size();
400 nodeMap.put(node, idx);
401 nodes[idx] = new Node(idx, node.getData());
402 rnodes[idx] = node;
403 }
404 });
405
406 TIntArrayList inIdx = new TIntArrayList();
407 final TIntArrayList ins = new TIntArrayList();
408 TIntArrayList outIdx = new TIntArrayList();
409 final TIntArrayList outs = new TIntArrayList();
410 final List<E> edgeData = new ArrayList<E>();
411
412 inIdx.add(0);
413 outIdx.add(0);
414 for (int i = 0; i < numNodes; i++) {
415 final GNode<N> src = rnodes[i];
416 g.mapInNeighbors(src, new LambdaVoid<GNode<N>>() {
417 @Override
418 public void call(GNode<N> dst) {
419 ins.add(nodeMap.get(dst));
420 }
421 });
422 inIdx.add(ins.size());
423
424 src.map(new LambdaVoid<GNode<N>>() {
425 @Override
426 public void call(GNode<N> dst) {
427 outs.add(nodeMap.get(dst));
428 edgeData.add(g.getEdgeData(src, dst));
429 }
430 });
431 outIdx.add(outs.size());
432 }
433
434 this.inIdx = inIdx.toArray();
435 this.ins = ins.toArray();
436 this.outIdx = outIdx.toArray();
437 this.outs = outs.toArray();
438 this.edgeData = (E[]) edgeData.toArray();
439 }
440
441 @SuppressWarnings("unchecked")
442 private int getId(GNode n) {
443 return ((Node) n).id;
444 }
445
446 @SuppressWarnings("unchecked")
447 static void acquire(GNode node, byte flags) {
448 Iteration.acquire(node, flags);
449 }
450
451 private static void acquireAll(byte flags) {
452 if (GaloisRuntime.needMethodFlag(flags, MethodFlag.CHECK_CONFLICT)) {
453 throw new UnsupportedOperationException();
454 }
455 }
456
457 @Override
458 public GNode<N> createNode(N n) {
459 throw new UnsupportedOperationException();
460 }
461
462 @Override
463 public GNode<N> createNode(N n, byte flags) {
464 throw new UnsupportedOperationException();
465 }
466
467 @Override
468 public boolean add(GNode<N> src) {
469 return add(src, MethodFlag.ALL);
470 }
471
472 @Override
473 public boolean add(GNode<N> src, byte flags) {
474 throw new UnsupportedOperationException();
475 }
476
477 @Override
478 public boolean remove(GNode<N> src) {
479 return remove(src, MethodFlag.ALL);
480 }
481
482 @Override
483 public boolean remove(GNode<N> src, byte flags) {
484 throw new UnsupportedOperationException();
485 }
486
487 @Override
488 public boolean contains(GNode<N> src) {
489 return contains(src, MethodFlag.ALL);
490 }
491
492 @Override
493 public boolean contains(GNode<N> src, byte flags) {
494 acquire(src, flags);
495 int idx = getId(src);
496 return 0 <= idx && idx < nodes.length;
497 }
498
499 @Override
500 public int size() {
501 return size(MethodFlag.ALL);
502 }
503
504 @Override
505 public int size(byte flags) {
506 acquireAll(flags);
507 return nodes.length;
508 }
509
510 @Override
511 public boolean addNeighbor(GNode<N> src, GNode<N> dst) {
512 throw new UnsupportedOperationException();
513 }
514
515 @Override
516 public boolean addNeighbor(GNode<N> src, GNode<N> dst, byte flags) {
517 throw new UnsupportedOperationException();
518 }
519
520 @Override
521 public boolean removeNeighbor(GNode<N> src, GNode<N> dst) {
522 return removeNeighbor(src, dst, MethodFlag.ALL);
523 }
524
525 @Override
526 public boolean removeNeighbor(GNode<N> src, GNode<N> dst, byte flags) {
527 throw new UnsupportedOperationException();
528 }
529
530 @Override
531 public boolean hasNeighbor(GNode<N> src, GNode<N> dst) {
532 return hasNeighbor(src, dst, MethodFlag.ALL);
533 }
534
535 private boolean hasNeighbor(GNode<N> src, GNode<N> dst, int[] adjIdx, int[] adj) {
536 int idx = getId(src);
537 int target = getId(dst);
538 int start = adjIdx[idx];
539 int end = adjIdx[idx + 1];
540
541 for (int i = start; i < end; i++) {
542 if (adj[i] == target) {
543 return true;
544 }
545 }
546 return false;
547 }
548
549 @Override
550 public boolean hasNeighbor(GNode<N> src, GNode<N> dst, byte flags) {
551 acquire(src, flags);
552 acquire(dst, flags);
553
554 return hasNeighbor(src, dst, inIdx, ins) || hasNeighbor(src, dst, outIdx, outs);
555 }
556
557 // NB(ddn): See visiblity comment above
558
559 void acquireNeighbors(GNode<N> src, int[] adjIdx, int[] adj, byte flags) {
560 Iteration it = Iteration.acquire(src, flags);
561 if (it != null) {
562 int idx = getId(src);
563 int start = adjIdx[idx];
564 int end = adjIdx[idx + 1];
565
566 for (int i = start; i < end; i++) {
567 GNode<N> other = nodes[adj[i]];
568 it.acquire(other);
569 }
570 }
571 }
572
573 // NB(ddn): See visiblity comment above
574
575 void mapNeighbor(int[] adjIdx, int[] adj, GNode<N> src, LambdaVoid<GNode<N>> body) {
576 int idx = getId(src);
577 int start = adjIdx[idx];
578 int end = adjIdx[idx + 1];
579
580 for (int i = start; i < end; i++) {
581 GNode<N> other = nodes[adj[i]];
582 body.call(other);
583 }
584 }
585
586 @Override
587 public void mapInNeighbors(GNode<N> src, LambdaVoid<GNode<N>> body) {
588 mapInNeighbors(src, body, MethodFlag.ALL);
589 }
590
591 /**
592 * Does not fail if the set of in neighbors of src is modified within the closure.
593 */
594 @Override
595 public void mapInNeighbors(GNode<N> src, LambdaVoid<GNode<N>> body, byte flags) {
596 acquireNeighbors(src, inIdx, ins, flags);
597
598 mapNeighbor(inIdx, ins, src, body);
599 }
600
601 private int neighborsSize(GNode<N> src, int[] adjIdx, int[] adj) {
602 int idx = getId(src);
603 int start = adjIdx[idx];
604 int end = adjIdx[idx + 1];
605
606 return end - start;
607 }
608
609 @Override
610 public int inNeighborsSize(GNode<N> src) {
611 return inNeighborsSize(src, MethodFlag.ALL);
612 }
613
614 @Override
615 public int inNeighborsSize(GNode<N> src, byte flags) {
616 acquireNeighbors(src, inIdx, ins, flags);
617
618 return neighborsSize(src, inIdx, ins);
619 }
620
621 @Override
622 public int outNeighborsSize(GNode<N> src) {
623 return outNeighborsSize(src, MethodFlag.ALL);
624 }
625
626 @Override
627 public int outNeighborsSize(GNode<N> src, byte flags) {
628 acquireNeighbors(src, outIdx, outs, flags);
629
630 return neighborsSize(src, outIdx, outs);
631 }
632
633 @Override
634 public boolean addEdge(GNode<N> src, GNode<N> dst, E data) {
635 return addEdge(src, dst, data, MethodFlag.ALL);
636 }
637
638 @Override
639 public boolean addEdge(GNode<N> src, GNode<N> dst, E data, byte flags) {
640 throw new UnsupportedOperationException();
641 }
642
643 private int getEdgeIdx(GNode<N> src, GNode<N> dst) {
644 int idx = getId(src);
645 int target = getId(dst);
646 int start = outIdx[idx];
647 int end = outIdx[idx + 1];
648
649 for (int i = start; i < end; i++) {
650 if (outs[i] == target) {
651 return i;
652 }
653 }
654 throw new Error("No such edge");
655 }
656
657 @Override
658 public E getEdgeData(GNode<N> src, GNode<N> dst) {
659 return getEdgeData(src, dst, MethodFlag.ALL);
660 }
661
662 @Override
663 public E getEdgeData(GNode<N> src, GNode<N> dst, byte flags) {
664 return getEdgeData(src, dst, flags, flags);
665 }
666
667 @Override
668 public E getEdgeData(GNode<N> src, GNode<N> dst, byte edgeFlags, byte dataFlags) {
669 acquire(src, edgeFlags);
670 acquire(dst, edgeFlags);
671
672 // TODO(ddn): Revive EdgeClosure so that we can implement map with getEdgeData
673 // better than this
674 E retval = edgeData[getEdgeIdx(src, dst)];
675
676 // Lift check up to here because it's slightly faster
677 if (GaloisRuntime.needMethodFlag(dataFlags, (byte) (MethodFlag.SAVE_UNDO | MethodFlag.CHECK_CONFLICT))) {
678 ((GObject) retval).access(dataFlags);
679 }
680 return retval;
681 }
682
683 @Override
684 public E setEdgeData(GNode<N> src, GNode<N> dst, E d) {
685 return setEdgeData(src, dst, d, MethodFlag.ALL);
686 }
687
688 @Override
689 public E setEdgeData(final GNode<N> src, final GNode<N> dst, E data, byte flags) {
690 acquire(src, flags);
691 acquire(dst, flags);
692
693 int idx = getEdgeIdx(src, dst);
694 final E oldData = edgeData[idx];
695
696 if (oldData != data) {
697 edgeData[idx] = data;
698 if (GaloisRuntime.needMethodFlag(flags, MethodFlag.SAVE_UNDO)) {
699 GaloisRuntime.getRuntime().onUndo(Iteration.getCurrentIteration(), new Callback() {
700 @Override
701 public void call() {
702 setEdgeData(src, dst, oldData, MethodFlag.NONE);
703 }
704 });
705 }
706 }
707
708 return oldData;
709 }
710
711 @Override
712 public boolean isDirected() {
713 return true;
714 }
715
716 @Override
717 public void mapInternal(LambdaVoid<GNode<N>> body, MapInternalContext ctx) {
718 int size = nodes.length;
719 for (int i = mapCur.getAndAdd(chunkSize); i < size; i = mapCur.getAndAdd(chunkSize)) {
720 for (int j = 0; j < chunkSize; j++) {
721 int index = i + j;
722 if (index >= size) {
723 break;
724 }
725
726 while (true) {
727 try {
728 Node item = nodes[index];
729 ctx.begin();
730 body.call(item);
731 ctx.commit(item);
732 break;
733 } catch (IterationAbortException _) {
734 ctx.abort();
735 }
736 }
737 }
738 }
739 }
740
741 @Override
742 public <A1> void mapInternal(Lambda2Void<GNode<N>, A1> body, MapInternalContext ctx, A1 arg1) {
743 int size = nodes.length;
744 for (int i = mapCur.getAndAdd(chunkSize); i < size; i = mapCur.getAndAdd(chunkSize)) {
745 for (int j = 0; j < chunkSize; j++) {
746 int index = i + j;
747 if (index >= size) {
748 break;
749 }
750
751 while (true) {
752 try {
753 Node item = nodes[index];
754 ctx.begin();
755 body.call(item, arg1);
756 ctx.commit(item);
757 break;
758 } catch (IterationAbortException _) {
759 ctx.abort();
760 }
761 }
762 }
763 }
764 }
765
766 @Override
767 public <A1, A2> void mapInternal(Lambda3Void<GNode<N>, A1, A2> body, MapInternalContext ctx, A1 arg1, A2 arg2) {
768 int size = nodes.length;
769 for (int i = mapCur.getAndAdd(chunkSize); i < size; i = mapCur.getAndAdd(chunkSize)) {
770 for (int j = 0; j < chunkSize; j++) {
771 int index = i + j;
772 if (index >= size) {
773 break;
774 }
775
776 while (true) {
777 try {
778 Node item = nodes[index];
779 ctx.begin();
780 body.call(item, arg1, arg2);
781 ctx.commit(item);
782 break;
783 } catch (IterationAbortException _) {
784 ctx.abort();
785 }
786 }
787 }
788 }
789 }
790
791 @Override
792 public void mapInternalDone() {
793 mapCur.set(0);
794 }
795
796 @Override
797 public void map(LambdaVoid<GNode<N>> body) {
798 map(body, MethodFlag.ALL);
799 }
800
801 @Override
802 public void map(LambdaVoid<GNode<N>> body, byte flags) {
803 acquireAll(flags);
804 for (int i = 0; i < nodes.length; i++) {
805 body.call(nodes[i]);
806 }
807 }
808
809 @Override
810 public <A1> void map(Lambda2Void<GNode<N>, A1> body, A1 arg1) {
811 map(body, arg1, MethodFlag.ALL);
812 }
813
814 @Override
815 public <A1> void map(Lambda2Void<GNode<N>, A1> body, A1 arg1, byte flags) {
816 acquireAll(flags);
817 for (int i = 0; i < nodes.length; i++) {
818 body.call(nodes[i], arg1);
819 }
820 }
821
822 @Override
823 public <A1, A2> void map(Lambda3Void<GNode<N>, A1, A2> body, A1 arg1, A2 arg2) {
824 map(body, arg1, arg2, MethodFlag.ALL);
825 }
826
827 @Override
828 public <A1, A2> void map(Lambda3Void<GNode<N>, A1, A2> body, A1 arg1, A2 arg2, byte flags) {
829 acquireAll(flags);
830 for (int i = 0; i < nodes.length; i++) {
831 body.call(nodes[i], arg1, arg2);
832 }
833 }
834
835 private final class Node extends ConcurrentGNode<N> {
836 private final int id;
837 private N data;
838
839 private Node(int id, N data) {
840 this.id = id;
841 this.data = data;
842 }
843
844 @Override
845 public N getData() {
846 return getData(MethodFlag.ALL);
847 }
848
849 @Override
850 public N getData(byte flags) {
851 return getData(flags, flags);
852 }
853
854 @Override
855 public N getData(byte nodeFlags, byte dataFlags) {
856 acquire(this, nodeFlags);
857 // Lift check up to here because it's slightly faster
858 if (GaloisRuntime.needMethodFlag(dataFlags, (byte) (MethodFlag.SAVE_UNDO | MethodFlag.CHECK_CONFLICT))) {
859 data.access(dataFlags);
860 }
861 return data;
862 }
863
864 @Override
865 public N setData(N data) {
866 return setData(data, MethodFlag.ALL);
867 }
868
869 @Override
870 public N setData(N data, byte flags) {
871 acquire(this, flags);
872
873 final N oldData = this.data;
874
875 if (oldData != data) {
876 this.data = data;
877
878 if (GaloisRuntime.needMethodFlag(flags, MethodFlag.SAVE_UNDO)) {
879 GaloisRuntime.getRuntime().onUndo(Iteration.getCurrentIteration(), new Callback() {
880 @Override
881 public void call() {
882 setData(oldData, MethodFlag.NONE);
883 }
884 });
885 }
886 }
887
888 return oldData;
889 }
890
891 @Override
892 public void mapInternal(LambdaVoid<GNode<N>> body, MapInternalContext ctx) {
893 int idx = getId(this);
894 int startIdx = outIdx[idx];
895 int endIdx = outIdx[idx + 1];
896
897 int size = endIdx - startIdx;
898 for (int i = mapCur.getAndAdd(chunkSize); i < size; i = mapCur.getAndAdd(chunkSize)) {
899 for (int j = 0; j < chunkSize; j++) {
900 int index = i + j;
901 if (index >= size) {
902 break;
903 }
904
905 while (true) {
906 try {
907 Node item = nodes[outs[startIdx + index]];
908 ctx.begin();
909 body.call(item);
910 ctx.commit(item);
911 break;
912 } catch (IterationAbortException _) {
913 ctx.abort();
914 }
915 }
916 }
917 }
918 }
919
920 @Override
921 public <A1> void mapInternal(Lambda2Void<GNode<N>, A1> body, MapInternalContext ctx, A1 arg1) {
922 int idx = getId(this);
923 int startIdx = outIdx[idx];
924 int endIdx = outIdx[idx + 1];
925
926 int size = endIdx - startIdx;
927 for (int i = mapCur.getAndAdd(chunkSize); i < size; i = mapCur.getAndAdd(chunkSize)) {
928 for (int j = 0; j < chunkSize; j++) {
929 int index = i + j;
930 if (index >= size) {
931 break;
932 }
933
934 while (true) {
935 try {
936 Node item = nodes[outs[startIdx + index]];
937 ctx.begin();
938 body.call(item, arg1);
939 ctx.commit(item);
940 break;
941 } catch (IterationAbortException _) {
942 ctx.abort();
943 }
944 }
945 }
946 }
947 }
948
949 @Override
950 public <A1, A2> void mapInternal(Lambda3Void<GNode<N>, A1, A2> body, MapInternalContext ctx, A1 arg1, A2 arg2) {
951 int idx = getId(this);
952 int startIdx = outIdx[idx];
953 int endIdx = outIdx[idx + 1];
954
955 int size = endIdx - startIdx;
956 for (int i = mapCur.getAndAdd(chunkSize); i < size; i = mapCur.getAndAdd(chunkSize)) {
957 for (int j = 0; j < chunkSize; j++) {
958 int index = i + j;
959 if (index >= size) {
960 break;
961 }
962
963 while (true) {
964 try {
965 Node item = nodes[outs[startIdx + index]];
966 ctx.begin();
967 body.call(item, arg1, arg2);
968 ctx.commit(item);
969 break;
970 } catch (IterationAbortException _) {
971 ctx.abort();
972 }
973 }
974 }
975 }
976 }
977
978 @Override
979 public void mapInternalDone() {
980 mapCur.set(0);
981 }
982
983 @Override
984 public void map(LambdaVoid<GNode<N>> body) {
985 map(body, MethodFlag.ALL);
986 }
987
988 @Override
989 public void map(LambdaVoid<GNode<N>> body, byte flags) {
990 acquireNeighbors(this, outIdx, outs, flags);
991 LocalComputationGraph.this.mapNeighbor(outIdx, outs, this, body);
992 }
993
994 @Override
995 public <A1> void map(Lambda2Void<GNode<N>, A1> body, A1 arg1) {
996 map(body, arg1, MethodFlag.ALL);
997 }
998
999 @Override
1000 public <A1> void map(Lambda2Void<GNode<N>, A1> body, A1 arg1, byte flags) {
1001 acquireNeighbors(this, outIdx, outs, flags);
1002 int idx = getId(this);
1003 int start = outIdx[idx];
1004 int end = outIdx[idx + 1];
1005
1006 for (int i = start; i < end; i++) {
1007 GNode<N> other = nodes[outs[i]];
1008 body.call(other, arg1);
1009 }
1010 }
1011
1012 @Override
1013 public <A1, A2> void map(Lambda3Void<GNode<N>, A1, A2> body, A1 arg1, A2 arg2) {
1014 map(body, arg1, arg2, MethodFlag.ALL);
1015 }
1016
1017 @Override
1018 public <A1, A2> void map(Lambda3Void<GNode<N>, A1, A2> body, A1 arg1, A2 arg2, byte flags) {
1019 acquireNeighbors(this, outIdx, outs, flags);
1020 int idx = getId(this);
1021 int start = outIdx[idx];
1022 int end = outIdx[idx + 1];
1023
1024 for (int i = start; i < end; i++) {
1025 GNode<N> other = nodes[outs[i]];
1026 body.call(other, arg1, arg2);
1027 }
1028 }
1029 }
1030
1031 @Override
1032 public void access(byte flags) {
1033 }
1034 }