Publish

1 files changed, 226 insertions, 0 deletions

diff --git a/vespajlib/src/main/java/com/yahoo/collections/Hashlet.java b/vespajlib/src/main/java/com/yahoo/collections/Hashlet.java
new file mode 100644
index 00000000000..86e82bb3241
--- /dev/null
+++ b/vespajlib/src/main/java/com/yahoo/collections/Hashlet.java
@@ -0,0 +1,226 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.collections;
+
+
+/**
+ * Lightweight hash map from key to value with limited
+ * functionality. This class lets you build a map from key to
+ * value. The value for a key may be overwritten and the put and get
+ * methods have the same semantics as for normal Java Maps, but there
+ * is no remove operation. Also, there is no iterator support, but
+ * keys and values can be accessed directly by index. The access order
+ * of keys and values are defined by the insert order of the keys. The
+ * goal of this class is to reduce the amount of object that are
+ * allocated by packing everything into two internal arrays. The keys
+ * and values are packed in an Object array and the hash table and
+ * entries are packed in an int array. The internal arrays are not
+ * created until space is needed. The default initial capacity is 16
+ * entries. If you know you need much more space than this, you can
+ * explicitly reserve more space before starting to insert values. The
+ * maximum load factor is 0.7 and drops slightly with increasing
+ * capacity.
+ *
+ * @author <a href="mailto:havardpe@yahoo-inc.com">Havard Pettersen</a>
+ **/
+public final class Hashlet<K, V> {
+
+    private static final int[] emptyHash = new int[1];
+    private int capacity = 0;
+    private int hashSize() { return (capacity + (capacity / 2) - 1); }
+    private int used = 0;
+    private Object[] store;
+    private int[] hash = emptyHash;
+
+    /**
+     * Create an empty Hashlet.
+     **/
+    public Hashlet() {}
+
+    /**
+     * Create a Hashlet that is a shallow copy of another Hashlet.
+     *
+     * @param hashlet the Hashlet to copy.
+     **/
+    public Hashlet(Hashlet<K, V> hashlet) {
+        if (hashlet.used > 0) {
+            capacity = hashlet.capacity;
+            used = hashlet.used;
+            store = new Object[hashlet.store.length];
+            hash = new int[hashlet.hash.length];
+            System.arraycopy(hashlet.store, 0, store, 0, store.length);
+            System.arraycopy(hashlet.hash, 0, hash, 0, hash.length);
+        }
+    }
+
+    /**
+     * Reserve space for more key value pairs. This method is used by
+     * the put method to perform rehashing when needed. It can be
+     * invoked directly by the application to reduce the number of
+     * rehashes needed to insert a large number of entries.
+     *
+     * @param n the number of additional entries to reserve space for
+     **/
+    public void reserve(int n) {
+        if (used + n > capacity) {
+            final int c = capacity;
+            if (capacity == 0) {
+                capacity = 16;
+            }
+            while (used + n > capacity) {
+                capacity *= 2;
+            }
+            final Object[] s = store;
+            store = new Object[capacity * 2];
+            hash = new int[hashSize() + (capacity * 2)];
+            if (c > 0) {
+                System.arraycopy(s, 0, store, 0, used);
+                System.arraycopy(s, c, store, capacity, used);
+                for (int i = 0; i < used; i++) {
+                    int prev = Math.abs(s[i].hashCode() % hashSize());
+                    int entry = hash[prev];
+                    while (entry != 0) {
+                        prev = entry + 1;
+                        entry = hash[prev];
+                    }
+                    final int insertIdx = (hashSize() + (i * 2));
+                    hash[prev] = insertIdx;
+                    hash[insertIdx] = i;
+                }
+            }
+        }
+    }
+
+    /**
+     * The current size. This is the number of key value pairs
+     * currently stored in this object.
+     *
+     * @return current size
+     **/
+    public int size() {
+        return used;
+    }
+
+    /**
+     * Obtain a key. Keys are accessed in the order they were first
+     * inserted.
+     *
+     * @return the requested key
+     * @param i the index of the key, must be in the range [0, size() - 1]
+     **/
+    @SuppressWarnings("unchecked")
+    public K key(int i) {
+        return (K) store[i];
+    }
+
+    /**
+     * Obtain a value. Values are accessed in the order in which
+     * theirs keys were first inserted.
+     *
+     * @return the requested value
+     * @param i the index of the value, must be in the range [0, size() - 1]
+     **/
+    @SuppressWarnings("unchecked")
+    public V value(int i) {
+        return (V) store[capacity + i];
+    }
+
+    /**
+     * This will replace the value at the index give.
+     *
+     * @param i the index of the value, must be in the range [0, size() - 1]
+     * @param value The new value you want to set for this index.
+     * @return previous value
+     */
+    public V setValue(int i, V value) {
+        V prev = value(i);
+        store[capacity + i] = value;
+        return prev;
+    }
+
+    /**
+     * Associate a value with a specific key.
+     *
+     * @return the old value for the key, if it was already present
+     * @param key the key
+     * @param value the value
+     **/
+    public V put(K key, V value) {
+        reserve(1);
+        int prev = Math.abs(key.hashCode() % hashSize());
+        int entry = hash[prev];
+        while (entry != 0) {
+            final int idx = hash[entry];
+            if (store[idx].equals(key)) { // found entry
+                @SuppressWarnings("unchecked")
+                final V ret = (V) store[capacity + idx];
+                store[capacity + idx] = value;
+                return ret;
+            }
+            prev = entry + 1;
+            entry = hash[prev];
+        }
+        final int insertIdx = (hashSize() + (used * 2));
+        hash[prev] = insertIdx;
+        hash[insertIdx] = used;
+        store[used] = key;
+        store[capacity + (used++)] = value;
+        return null;
+    }
+
+    /**
+     * Obtain the value for a specific key.
+     *
+     * @return the value for a key, or null if not found
+     * @param key the key
+     **/
+    public V get(Object key) {
+        int index = getIndexOfKey(key);
+        return (index != -1) ? value(index) : null;
+    }
+
+    /**
+     * Finds the index where the key,value pair is stored.
+     * @param key to look for
+     * @return the index where the key is found or -1 if it is not found
+     */
+    public int getIndexOfKey(Object key) {
+        int entry = hash[Math.abs(key.hashCode() % hashSize())];
+        while (entry != 0) {
+            final int idx = hash[entry];
+            if (store[idx].equals(key)) { // found entry
+                return idx;
+            }
+            entry = hash[entry + 1];
+        }
+        return -1;
+    }
+
+    @Override
+    public int hashCode() {
+        int h = 0;
+        for (int i = 0; i < used; i++) {
+            h += key(i).hashCode();
+            V v = value(i);
+            if (v != null) {
+                h += v.hashCode();
+            }
+        }
+        return h;
+    }
+
+    @Override
+    public boolean equals(Object o) {
+        if (! (o instanceof Hashlet) ) return false;
+        Hashlet<?, ?> rhs = (Hashlet<?, ?>) o;
+        if (used != rhs.used) return false;
+        for (int i = 0; i < used; i++) {
+            int bi = rhs.getIndexOfKey(key(i));
+            if (bi == -1) return false;
+            Object a = value(i);
+            Object b = rhs.value(bi);
+            boolean equal = (a == null) ? b == null : a.equals(b);
+            if ( !equal ) return false;
+        }
+        return true;
+    }
+}