This project has retired. For details please refer to its Attic page.
LongByteHashMapEdges xref
View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * 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 org.apache.giraph.edge;
20  
21  import it.unimi.dsi.fastutil.longs.Long2ByteMap;
22  import it.unimi.dsi.fastutil.longs.Long2ByteOpenHashMap;
23  import it.unimi.dsi.fastutil.objects.ObjectIterator;
24  
25  import java.io.DataInput;
26  import java.io.DataOutput;
27  import java.io.IOException;
28  import java.util.Iterator;
29  
30  import org.apache.giraph.utils.EdgeIterables;
31  import org.apache.giraph.utils.Trimmable;
32  import org.apache.hadoop.io.ByteWritable;
33  import org.apache.hadoop.io.LongWritable;
34  
35  import com.google.common.collect.UnmodifiableIterator;
36  
37  /**
38   * {@link OutEdges} implementation with long ids and byte edge values,
39   * backed by a {@link Long2ByteOpenHashMap}.
40   * Parallel edges are not allowed.
41   * Note: this implementation is optimized for fast random access and mutations,
42   * and uses less space than a generic {@link HashMapEdges}.
43   */
44  public class LongByteHashMapEdges
45      implements StrictRandomAccessOutEdges<LongWritable, ByteWritable>,
46      ReuseObjectsOutEdges<LongWritable, ByteWritable>,
47      MutableOutEdges<LongWritable, ByteWritable>, Trimmable {
48    /** Hash map from target vertex id to edge value. */
49    private Long2ByteOpenHashMap edgeMap;
50    /** Representative edge value object, used by getEdgeValue(). */
51    private ByteWritable representativeEdgeValue;
52  
53    @Override
54    public void initialize(Iterable<Edge<LongWritable, ByteWritable>> edges) {
55      EdgeIterables.initialize(this, edges);
56    }
57  
58    @Override
59    public void initialize(int capacity) {
60      edgeMap = new Long2ByteOpenHashMap(capacity);
61    }
62  
63    @Override
64    public void initialize() {
65      edgeMap = new Long2ByteOpenHashMap();
66    }
67  
68    @Override
69    public void add(Edge<LongWritable, ByteWritable> edge) {
70      edgeMap.put(edge.getTargetVertexId().get(), edge.getValue().get());
71    }
72  
73    @Override
74    public void remove(LongWritable targetVertexId) {
75      edgeMap.remove(targetVertexId.get());
76    }
77  
78    @Override
79    public ByteWritable getEdgeValue(LongWritable targetVertexId) {
80      if (!edgeMap.containsKey(targetVertexId.get())) {
81        return null;
82      }
83      if (representativeEdgeValue == null) {
84        representativeEdgeValue = new ByteWritable();
85      }
86      representativeEdgeValue.set(edgeMap.get(targetVertexId.get()));
87      return representativeEdgeValue;
88    }
89  
90    @Override
91    public void setEdgeValue(LongWritable targetVertexId,
92                             ByteWritable edgeValue) {
93      if (edgeMap.containsKey(targetVertexId.get())) {
94        edgeMap.put(targetVertexId.get(), edgeValue.get());
95      }
96    }
97  
98    @Override
99    public int size() {
100     return edgeMap.size();
101   }
102 
103   @Override
104   public Iterator<Edge<LongWritable, ByteWritable>> iterator() {
105     // Returns an iterator that reuses objects.
106     return new UnmodifiableIterator<Edge<LongWritable, ByteWritable>>() {
107       /** Wrapped map iterator. */
108       private final ObjectIterator<Long2ByteMap.Entry> mapIterator =
109           edgeMap.long2ByteEntrySet().fastIterator();
110       /** Representative edge object. */
111       private final ReusableEdge<LongWritable, ByteWritable>
112       representativeEdge =
113           EdgeFactory.createReusable(new LongWritable(), new ByteWritable());
114 
115       @Override
116       public boolean hasNext() {
117         return mapIterator.hasNext();
118       }
119 
120       @Override
121       public Edge<LongWritable, ByteWritable> next() {
122         Long2ByteMap.Entry nextEntry = mapIterator.next();
123         representativeEdge.getTargetVertexId().set(nextEntry.getLongKey());
124         representativeEdge.getValue().set(nextEntry.getByteValue());
125         return representativeEdge;
126       }
127     };
128   }
129 
130   @Override
131   public void trim() {
132     edgeMap.trim();
133   }
134 
135   /** Helper class for a mutable edge that modifies the backing map entry. */
136   private static class LongByteHashMapMutableEdge
137       extends DefaultEdge<LongWritable, ByteWritable> {
138     /** Backing entry for the edge in the map. */
139     private Long2ByteMap.Entry entry;
140 
141     /** Constructor. */
142     public LongByteHashMapMutableEdge() {
143       super(new LongWritable(), new ByteWritable());
144     }
145 
146     /**
147      * Make the edge point to the given entry in the backing map.
148      *
149      * @param entry Backing entry
150      */
151     public void setEntry(Long2ByteMap.Entry entry) {
152       // Update the id and value objects from the superclass.
153       getTargetVertexId().set(entry.getLongKey());
154       getValue().set(entry.getByteValue());
155       // Update the entry.
156       this.entry = entry;
157     }
158 
159     @Override
160     public void setValue(ByteWritable value) {
161       // Update the value object from the superclass.
162       getValue().set(value.get());
163       // Update the value stored in the backing map.
164       entry.setValue(value.get());
165     }
166   }
167 
168   @Override
169   public Iterator<MutableEdge<LongWritable, ByteWritable>> mutableIterator() {
170     return new Iterator<MutableEdge<LongWritable, ByteWritable>>() {
171       /**
172        * Wrapped map iterator.
173        * Note: we cannot use the fast iterator in this case,
174        * because we need to call setValue() on an entry.
175        */
176       private final ObjectIterator<Long2ByteMap.Entry> mapIterator =
177           edgeMap.long2ByteEntrySet().iterator();
178       /** Representative edge object. */
179       private final LongByteHashMapMutableEdge representativeEdge =
180           new LongByteHashMapMutableEdge();
181 
182       @Override
183       public boolean hasNext() {
184         return mapIterator.hasNext();
185       }
186 
187       @Override
188       public MutableEdge<LongWritable, ByteWritable> next() {
189         representativeEdge.setEntry(mapIterator.next());
190         return representativeEdge;
191       }
192 
193       @Override
194       public void remove() {
195         mapIterator.remove();
196       }
197     };
198   }
199 
200   @Override
201   public void write(DataOutput out) throws IOException {
202     out.writeInt(edgeMap.size());
203     for (Long2ByteMap.Entry entry : edgeMap.long2ByteEntrySet()) {
204       out.writeLong(entry.getLongKey());
205       out.writeByte(entry.getByteValue());
206     }
207   }
208 
209   @Override
210   public void readFields(DataInput in) throws IOException {
211     int numEdges = in.readInt();
212     initialize(numEdges);
213     for (int i = 0; i < numEdges; ++i) {
214       edgeMap.put(in.readLong(), in.readByte());
215     }
216   }
217 }