graphhopper · karussell · Jul 7, 2022 · Jul 5, 2022 · Jul 5, 2022 · Jul 5, 2022
diff --git a/core/src/main/java/com/graphhopper/reader/osm/OSMReader.java b/core/src/main/java/com/graphhopper/reader/osm/OSMReader.java
@@ -35,6 +35,7 @@
 import com.graphhopper.routing.util.countryrules.CountryRule;
 import com.graphhopper.routing.util.countryrules.CountryRuleFactory;
 import com.graphhopper.routing.util.parsers.TurnCostParser;
+import com.graphhopper.search.EdgeKVStorage;
 import com.graphhopper.storage.BaseGraph;
 import com.graphhopper.storage.IntsRef;
 import com.graphhopper.storage.NodeAccess;
@@ -332,14 +333,14 @@ protected void addEdge(int fromIndex, int toIndex, PointList pointList, ReaderWa
         if (edgeFlags.isEmpty())
             return;
 
-        Map<String, Object> map = new HashMap<>(2);
+        List<EdgeKVStorage.KeyValue> list = new ArrayList<>(2);
         // the storage does not accept too long strings -> Helper.cutStringForKV
         if (way.hasTag("way_name")) // do not store empty string if missing tag
-            map.put("name", Helper.cutStringForKV(way.getTag("way_name", "")));
+            list.add(new EdgeKVStorage.KeyValue("name", Helper.cutStringForKV(way.getTag("way_name", ""))));
         if (way.hasTag("way_ref"))
-            map.put("ref", Helper.cutStringForKV(way.getTag("way_ref", "")));
+            list.add(new EdgeKVStorage.KeyValue("ref", Helper.cutStringForKV(way.getTag("way_ref", ""))));
         EdgeIteratorState edge = baseGraph.edge(fromIndex, toIndex).setDistance(distance).setFlags(edgeFlags).
-                setKeyValues(map);
+                setKeyValues(list);
 
         // If the entire way is just the first and last point, do not waste space storing an empty way geometry
         if (pointList.size() > 2) {

diff --git a/core/src/main/java/com/graphhopper/routing/querygraph/QueryOverlayBuilder.java b/core/src/main/java/com/graphhopper/routing/querygraph/QueryOverlayBuilder.java
@@ -20,6 +20,7 @@
 
 import com.carrotsearch.hppc.predicates.IntObjectPredicate;
 import com.graphhopper.coll.GHIntObjectHashMap;
+import com.graphhopper.search.EdgeKVStorage;
 import com.graphhopper.storage.Graph;
 import com.graphhopper.storage.IntsRef;
 import com.graphhopper.storage.index.Snap;
@@ -222,7 +223,7 @@ private void createEdges(int origEdgeKey, int origRevEdgeKey,
 
         boolean reverse = closestEdge.get(EdgeIteratorState.REVERSE_STATE);
         // edges between base and snapped point
-        Map<String, Object> keyValues = closestEdge.getKeyValues();
+        List<EdgeKVStorage.KeyValue> keyValues = closestEdge.getKeyValues();
         VirtualEdgeIteratorState baseEdge = new VirtualEdgeIteratorState(origEdgeKey, GHUtility.createEdgeKey(virtEdgeId, prevNodeId == nodeId, false),
                 prevNodeId, nodeId, baseDistance, closestEdge.getFlags(), keyValues, basePoints, reverse);
         VirtualEdgeIteratorState baseReverseEdge = new VirtualEdgeIteratorState(origRevEdgeKey, GHUtility.createEdgeKey(virtEdgeId, prevNodeId == nodeId, true),

diff --git a/core/src/main/java/com/graphhopper/routing/querygraph/VirtualEdgeIterator.java b/core/src/main/java/com/graphhopper/routing/querygraph/VirtualEdgeIterator.java
@@ -19,14 +19,14 @@
 
 import com.graphhopper.routing.ev.*;
 import com.graphhopper.routing.util.EdgeFilter;
+import com.graphhopper.search.EdgeKVStorage;
 import com.graphhopper.storage.IntsRef;
 import com.graphhopper.util.EdgeIterator;
 import com.graphhopper.util.EdgeIteratorState;
 import com.graphhopper.util.FetchMode;
 import com.graphhopper.util.PointList;
 
 import java.util.List;
-import java.util.Map;
 
 /**
  * @author Peter Karich
@@ -262,13 +262,13 @@ public String getName() {
     }
 
     @Override
-    public Map<String, Object> getKeyValues() {
+    public List<EdgeKVStorage.KeyValue> getKeyValues() {
         return getCurrentEdge().getKeyValues();
     }
 
     @Override
-    public EdgeIteratorState setKeyValues(Map<String, Object> map) {
-        return getCurrentEdge().setKeyValues(map);
+    public EdgeIteratorState setKeyValues(List<EdgeKVStorage.KeyValue> list) {
+        return getCurrentEdge().setKeyValues(list);
     }
 
     @Override

diff --git a/core/src/main/java/com/graphhopper/routing/querygraph/VirtualEdgeIteratorState.java b/core/src/main/java/com/graphhopper/routing/querygraph/VirtualEdgeIteratorState.java
@@ -18,13 +18,14 @@
 package com.graphhopper.routing.querygraph;
 
 import com.graphhopper.routing.ev.*;
+import com.graphhopper.search.EdgeKVStorage;
 import com.graphhopper.storage.IntsRef;
 import com.graphhopper.util.EdgeIteratorState;
 import com.graphhopper.util.FetchMode;
 import com.graphhopper.util.GHUtility;
 import com.graphhopper.util.PointList;
 
-import java.util.Map;
+import java.util.List;
 
 /**
  * Creates an edge state decoupled from a graph where nodes, pointList, etc are kept in memory.
@@ -40,14 +41,14 @@ public class VirtualEdgeIteratorState implements EdgeIteratorState {
     private final int originalEdgeKey;
     private double distance;
     private IntsRef edgeFlags;
-    private Map<String, Object> keyValues;
+    private List<EdgeKVStorage.KeyValue> keyValues;
     // true if edge should be avoided as start/stop
     private boolean unfavored;
     private EdgeIteratorState reverseEdge;
     private final boolean reverse;
 
     public VirtualEdgeIteratorState(int originalEdgeKey, int edgeKey, int baseNode, int adjNode, double distance,
-                                    IntsRef edgeFlags, Map<String, Object> keyValues, PointList pointList, boolean reverse) {
+                                    IntsRef edgeFlags, List<EdgeKVStorage.KeyValue> keyValues, PointList pointList, boolean reverse) {
         this.originalEdgeKey = originalEdgeKey;
         this.edgeKey = edgeKey;
         this.baseNode = baseNode;
@@ -309,25 +310,28 @@ public EdgeIteratorState set(StringEncodedValue property, String fwd, String bwd
 
     @Override
     public String getName() {
-        String name = (String) keyValues.get("name");
+        String name = (String) getValue("name");
         // preserve backward compatibility (returns empty string if name tag missing)
         return name == null ? "" : name;
     }
 
     @Override
-    public EdgeIteratorState setKeyValues(Map<String, Object> map) {
-        this.keyValues = map;
+    public EdgeIteratorState setKeyValues(List<EdgeKVStorage.KeyValue> list) {
+        this.keyValues = list;
         return this;
     }
 
     @Override
-    public Map<String, Object> getKeyValues() {
+    public List<EdgeKVStorage.KeyValue> getKeyValues() {
         return keyValues;
     }
 
     @Override
     public Object getValue(String key) {
-        return keyValues.get(key);
+        for (EdgeKVStorage.KeyValue keyValue : keyValues) {
+            if (keyValue.key.equals(key)) return keyValue.value;
+        }
+        return null;
     }
 
     /**

diff --git a/core/src/main/java/com/graphhopper/search/EdgeKVStorage.java b/core/src/main/java/com/graphhopper/search/EdgeKVStorage.java
@@ -35,8 +35,8 @@
 public class EdgeKVStorage {
 
     private static final long EMPTY_POINTER = 0, START_POINTER = 1;
-    // Store the key index in 2 bytes (for now ignore the highest bit)
-    static final int MAX_UNIQUE_KEYS = (1 << 15);
+    // Store the key index in 2 bytes. Use first 2 bits for marking fwd+bwd existence.
+    static final int MAX_UNIQUE_KEYS = (1 << 14);
     // Store string value as byte array and store the length into 1 byte
     private static final int MAX_LENGTH = (1 << 8) - 1;
 
@@ -72,14 +72,15 @@ public class EdgeKVStorage {
     // 1. The key strings are limited MAX_UNIQUE_KEYS. A dynamic value has a maximum byte length of 255.
     // 2. Every key can store values only of the same type
     // 3. We need to loop through X entries to get the start val_x.
+    // 4. The key index (14 bits) is stored along with the availability (2 bits), i.e. whether they KeyValue is available in forward and/or backward directions
     private final DataAccess vals;
     private final Map<String, Integer> keyToIndex = new HashMap<>();
     private final List<Class<?>> indexToClass = new ArrayList<>();
     private final List<String> indexToKey = new ArrayList<>();
     private final BitUtil bitUtil = BitUtil.LITTLE;
     private long bytePointer = START_POINTER;
     private long lastEntryPointer = -1;
-    private Map<String, Object> lastEntryMap;
+    private List<KeyValue> lastEntries;
 
     public EdgeKVStorage(Directory dir) {
         this(dir, 1000);
@@ -148,33 +149,33 @@ Collection<String> getKeys() {
      *
      * @return entryPointer with which you can later fetch the entryMap via the get or getAll method
      */
-    public long add(final Map<String, Object> entryMap) {
-        if (entryMap == null) throw new IllegalArgumentException("specified Map must not be null");
-        if (entryMap.isEmpty()) return EMPTY_POINTER;
-        else if (entryMap.size() > 200)
+    public long add(final List<KeyValue> entries) {
+        if (entries == null) throw new IllegalArgumentException("specified List must not be null");
+        if (entries.isEmpty()) return EMPTY_POINTER;
+        else if (entries.size() > 200)
             throw new IllegalArgumentException("Cannot store more than 200 entries per entry");
 
         // This is a very important "compression" mechanism because one OSM way is split into multiple edges and so we
         // can often re-use the serialized key-value pairs of the previous edge.
-        if (isEquals(entryMap, lastEntryMap)) return lastEntryPointer;
+        if (isEquals(entries, lastEntries)) return lastEntryPointer;
 
         // If the Class of a value is unknown it should already fail here, before we modify internal data. (see #2597#discussion_r896469840)
-        for (Map.Entry<String, Object> entry : entryMap.entrySet())
-            if (keyToIndex.get(entry.getKey()) != null)
-                getBytesForValue(indexToClass.get(keyToIndex.get(entry.getKey())), entry.getValue());
+        for (KeyValue kv : entries)
+            if (keyToIndex.get(kv.key) != null)
+                getBytesForValue(indexToClass.get(keyToIndex.get(kv.key)), kv.value);
 
-        lastEntryMap = entryMap;
+        lastEntries = entries;
         lastEntryPointer = bytePointer;
         // while adding there could be exceptions and we need to avoid that the bytePointer is modified
         long currentPointer = bytePointer;
 
         vals.ensureCapacity(currentPointer + 1);
-        vals.setByte(currentPointer, (byte) entryMap.size());
+        vals.setByte(currentPointer, (byte) entries.size());
         currentPointer += 1;
-        for (Map.Entry<String, Object> entry : entryMap.entrySet()) {
-            String key = entry.getKey();
+        for (KeyValue entry : entries) {
+            String key = entry.key;
             if (key == null) throw new IllegalArgumentException("key cannot be null");
-            Object value = entry.getValue();
+            Object value = entry.value;
             if (value == null) throw new IllegalArgumentException("value for key " + key + " cannot be null");
             Integer keyIndex = keyToIndex.get(key);
             Class<?> clazz;
@@ -207,7 +208,7 @@ else if (entryMap.size() > 200)
 
             final byte[] valueBytes = getBytesForValue(clazz, value);
             vals.ensureCapacity(currentPointer + 2 + 1 + valueBytes.length);
-            vals.setShort(currentPointer, keyIndex.shortValue());
+            vals.setShort(currentPointer, (short) (keyIndex << 2 | (entry.fwd ? 2 : 0) | (entry.bwd ? 1 : 0)));
             currentPointer += 2;
             if (hasDynLength) {
                 vals.setByte(currentPointer, (byte) valueBytes.length);
@@ -222,45 +223,46 @@ else if (entryMap.size() > 200)
         return lastEntryPointer;
     }
 
-    private boolean isEquals(Map<String, Object> entryMap, Map<String, Object> lastEntryMap) {
-        if (lastEntryMap != null && entryMap.size() == lastEntryMap.size()) {
-            for (Map.Entry<String, Object> entry : entryMap.entrySet()) {
-                Object val = entry.getValue();
-                if (val == null)
-                    throw new IllegalArgumentException("value for key " + entry.getKey() + " cannot be null");
-                Object lastVal = lastEntryMap.get(entry.getKey());
-                if (val instanceof byte[] && lastVal instanceof byte[] && Arrays.equals((byte[]) lastVal, (byte[]) val)
-                        || val.equals(lastVal)) continue;
-                return false;
+    // compared to entries.equals(lastEntries) this method avoids a NPE if a value is null and throws an IAE instead
+    private boolean isEquals(List<KeyValue> entries, List<KeyValue> lastEntries) {
+        if (lastEntries != null && entries.size() == lastEntries.size()) {
+            for (int i = 0; i < entries.size(); i++) {
+                KeyValue kv = entries.get(i);
+                if (kv.value == null)
+                    throw new IllegalArgumentException("value for key " + kv.key + " cannot be null");
+                if (!kv.equals(lastEntries.get(i))) return false;
             }
             return true;
         }
         return false;
     }
 
-    public Map<String, Object> getAll(final long entryPointer) {
+    public List<EdgeKVStorage.KeyValue> getAll(final long entryPointer) {
         if (entryPointer < 0)
             throw new IllegalStateException("Pointer to access EdgeKVStorage cannot be negative:" + entryPointer);
 
-        if (entryPointer == EMPTY_POINTER) return Collections.emptyMap();
+        if (entryPointer == EMPTY_POINTER) return Collections.emptyList();
 
         int keyCount = vals.getByte(entryPointer) & 0xFF;
-        if (keyCount == 0) return Collections.emptyMap();
+        if (keyCount == 0) return Collections.emptyList();
 
-        Map<String, Object> map = new HashMap<>(keyCount);
+        List<EdgeKVStorage.KeyValue> list = new ArrayList<>(keyCount);
         long tmpPointer = entryPointer + 1;
         AtomicInteger sizeOfObject = new AtomicInteger();
         for (int i = 0; i < keyCount; i++) {
-            int currentKeyIndex = vals.getShort(tmpPointer);
+            int currentKeyIndexRaw = vals.getShort(tmpPointer);
+            boolean bwd = (currentKeyIndexRaw & 1) == 1;
+            boolean fwd = (currentKeyIndexRaw & 2) == 2;
+            int currentKeyIndex = currentKeyIndexRaw >>> 2;
             tmpPointer += 2;
 
             Object object = deserializeObj(sizeOfObject, tmpPointer, indexToClass.get(currentKeyIndex));
             tmpPointer += sizeOfObject.get();
             String key = indexToKey.get(currentKeyIndex);
-            map.put(key, object);
+            list.add(new KeyValue(key, object, fwd, bwd));
         }
 
-        return map;
+        return list;
     }
 
     private boolean hasDynLength(Class<?> clazz) {
@@ -366,14 +368,17 @@ public Object get(final long entryPointer, String key, boolean reverse) {
         long tmpPointer = entryPointer + 1;
         for (int i = 0; i < keyCount; i++) {
             int currentKeyIndexRaw = vals.getShort(tmpPointer);
-            int keyIndexPositive = Math.abs(currentKeyIndexRaw);
-            assert keyIndexPositive < indexToKey.size() : "invalid key index " + keyIndexPositive + ">=" + indexToKey.size() + ", entryPointer=" + entryPointer + ", max=" + bytePointer;
+            boolean bwd = (currentKeyIndexRaw & 1) == 1;
+            boolean fwd = (currentKeyIndexRaw & 2) == 2;
+            int currentKeyIndex = currentKeyIndexRaw >>> 2;
+
+            assert currentKeyIndex < indexToKey.size() : "invalid key index " + currentKeyIndex + ">=" + indexToKey.size() + ", entryPointer=" + entryPointer + ", max=" + bytePointer;
             tmpPointer += 2;
-            if (keyIndexPositive == keyIndex)
+            if ((!reverse && fwd || reverse && bwd) && currentKeyIndex == keyIndex)
                 return deserializeObj(null, tmpPointer, indexToClass.get(keyIndex));
 
             // skip to next entry of same edge via skipping the real value
-            Class<?> clazz = indexToClass.get(keyIndexPositive);
+            Class<?> clazz = indexToClass.get(currentKeyIndex);
             int valueLength = hasDynLength(clazz) ? 1 + vals.getByte(tmpPointer) & 0xFF : getFixLength(clazz);
             tmpPointer += valueLength;
         }
@@ -425,4 +430,50 @@ public boolean isClosed() {
     public long getCapacity() {
         return vals.getCapacity() + keys.getCapacity();
     }
+
+    public static class KeyValue {
+        public String key;
+        public Object value;
+        public boolean fwd, bwd;
+
+        public KeyValue(String key, Object value) {
+            this.key = key;
+            this.value = value;
+            this.fwd = true;
+            this.bwd = true;
+        }
+
+        public KeyValue(String key, Object value, boolean fwd, boolean bwd) {
+            this.key = key;
+            this.value = value;
+            this.fwd = fwd;
+            this.bwd = bwd;
+        }
+
+        public static List<KeyValue> createKV(String key, Object value) {
+            return Collections.singletonList(new KeyValue(key, value));
+        }
+
+        @Override
+        public boolean equals(Object o) {
+            if (this == o) return true;
+            if (o == null || getClass() != o.getClass()) return false;
+            KeyValue keyValue = (KeyValue) o;
+            return key.equals(keyValue.key)
+                    && fwd == keyValue.fwd
+                    && bwd == keyValue.bwd
+                    && (value instanceof byte[] && keyValue.value instanceof byte[] &&
+                    Arrays.equals((byte[]) value, (byte[]) keyValue.value) || value.equals(keyValue.value));
+        }
+
+        @Override
+        public int hashCode() {
+            return Objects.hash(key, value, fwd, bwd);
+        }
+
+        @Override
+        public String toString() {
+            return key + '=' + value + " (" + fwd + "|" + bwd + ")";
+        }
+    }
 }
diff --git a/core/src/main/java/com/graphhopper/storage/BaseGraph.java b/core/src/main/java/com/graphhopper/storage/BaseGraph.java
@@ -27,6 +27,7 @@
 import com.graphhopper.util.shapes.BBox;
 
 import java.io.Closeable;
+import java.util.List;
 import java.util.Map;
 
 import static com.graphhopper.util.Helper.nf;
@@ -946,16 +947,16 @@ public int getReverseEdgeKey() {
         }
 
         @Override
-        public EdgeIteratorState setKeyValues(Map<String, Object> map) {
-            long pointer = baseGraph.edgeKVStorage.add(map);
+        public EdgeIteratorState setKeyValues(List<EdgeKVStorage.KeyValue> entries) {
+            long pointer = baseGraph.edgeKVStorage.add(entries);
             if (pointer > Integer.MAX_VALUE)
                 throw new IllegalStateException("Too many key value pairs are stored, currently limited to " + Integer.MAX_VALUE + " was " + pointer);
             store.setKeyValuesRef(edgePointer, (int) pointer);
             return this;
         }
 
         @Override
-        public Map<String, Object> getKeyValues() {
+        public List<EdgeKVStorage.KeyValue> getKeyValues() {
             int kvEntryRef = store.getKeyValuesRef(edgePointer);
             return baseGraph.edgeKVStorage.getAll(kvEntryRef);
         }