Revision: 4527
http://sourceforge.net/p/vexi/code/4527
Author: mkpg2
Date: 2013-05-26 10:16:43 +0000 (Sun, 26 May 2013)
Log Message:
-----------
Resurrect ibex map as org.ibex.js.util.Hash
- Fixed. There was a logic bug in rehash. That meant it would lose track of its
size.
- Fixed/Changed probing algorithm
- It was not using primes of size 4n+3 as the size of the elements list. It
started with 4n+3 number (pseudo prime) and then just multiplied that by the
number of slots (for some reason) i.e. 2/3 when resizing.
- New probing algorithm requires basket size 2^n instead, so avoids this
issue.
- Removed multiple slots (a better way to achieve this is to use keys of a
different type in a single map).
- Made as small as possible by hardcoding load factor ... etc. It is no longer
tunable at runtime, so for this reason it is essentially JS specific.
Added Paths:
-----------
branches/vexi4/org.vexi-library.js/src/main/java/org/ibex/js/util/
branches/vexi4/org.vexi-library.js/src/main/java/org/ibex/js/util/Hash.java
Added:
branches/vexi4/org.vexi-library.js/src/main/java/org/ibex/js/util/Hash.java
===================================================================
--- branches/vexi4/org.vexi-library.js/src/main/java/org/ibex/js/util/Hash.java
(rev 0)
+++ branches/vexi4/org.vexi-library.js/src/main/java/org/ibex/js/util/Hash.java
2013-05-26 10:16:43 UTC (rev 4527)
@@ -0,0 +1,200 @@
+
+package org.ibex.js.util;
+
+import org.ibex.util.Basket;
+import org.ibex.util.Basket.Map;
+
+/**
+ *
+ * <P>Copyright 2013 the Contributors, as shown in the revision logs.
+ * Licensed under the Apache Public Source License 2.0 ("the License").
+ * You may not use this file except in compliance with the License.</p>
+ *
+ * <p>Based on the original implementation by [email protected], [email protected].
+ * Originally Hash used the standard form of Radke's quadratic residue linear
probing.</p>
+ *
+ * <p>
+ * Now hash uses a variant probing strategy by F R A Hopgood and J. Davenport,
which supports
+ * full table scans when the table size is a power of 2.
+ * </p>
+ *
+ * <p>Not thread safe</p>
+ *
+ * @author [email protected]
+ */
+public class Hash implements Basket, Map {
+ /** When <tt>loadFactor * usedslots > num_slots</tt>, call
+ * <tt>rehash()</tt>. */
+ static final float LOAD_FACTOR = 0.75f;
+ static final Object PLACE_HOLDER = new Object();
+ static final int SLOTS = 2; // 2 slots, one for the key, one for the
value
+
+ private int size = 0; // bookkeeping - the nmuber of active
entries
+ private int placeholders = 0; // bookkeeping - the number of
placeholders (used when removing entries - until next rehash)
+ private Object[] entries = null;
+
+ public Hash() { this(4); }
+ public Hash(int sizePowerOf2) {
+ if(sizePowerOf2>=1){
+ int size = 1<<sizePowerOf2;
+ // 2 entries, key + value
+ this.entries = new Object[size*SLOTS];
+ }
+ }
+
+ // Returns the array position of the key, if it exists.
+ //
+ // If the key is not found, this function returns
+ // (-1 * indexPosition) - 1, where indexPosition
+ // is the array position where the mapping should be stored.
+ private int _indexOf(Object k) {
+ if(entries==null) return Integer.MIN_VALUE;
+
+ final int capacity = _capacity();
+ final int orig = Math.abs(k.hashCode()) % capacity;
+ int dest = orig * SLOTS;
+ int increment = 1;
+ while (entries[dest] != null) {
+ if (equals(k, entries[dest])) return dest;
+
+ dest = Math.abs((dest + increment) % capacity) * SLOTS;
+
+ if(increment>capacity) return Integer.MIN_VALUE;
+ increment = increment +1;
+ }
+ return _convertKey(dest);
+ }
+
+ // encode/decodes index as a negative value
+ private int _convertKey(int dest){
+ return -1 * dest - 1;
+ }
+
+ private int _capacity(){ return entries==null?0:entries.length/SLOTS; }
+ private boolean _notKey(Object k){ return k==null || k==PLACE_HOLDER; }
+
+ public int size() { return size; }
+ public void clear() {
+ if(entries==null) return;
+ for (int i = 0; i<entries.length; i++) entries[i] = null;
+ size = 0; placeholders=0;
+ }
+
+ private boolean areEqual(Object a, Object b){
+ if(a==null && b==null) return true;
+ if(a!=null && b!=null) return a.equals(b);
+ return false;
+ }
+
+ public boolean containsKey(Object k) { return _indexOf(k) >= 0; }
+ public boolean containsValue(Object value) {
+ for(int i=0; i<entries.length; i+=SLOTS){
+ Object k = entries[i];
+ if(_notKey(k)) continue;
+ Object v = entries[i+1];
+ if(areEqual(value, v)) return true;
+ }
+ return false;
+ }
+
+ public Object[] listKeys() {
+ Object[] arr = new Object[size];
+ listKeys(arr);
+ return arr;
+ }
+ public void listKeys(Object[] arr) {
+ int pos = 0;
+ if(entries!=null) for(int i=0; i<entries.length; i+=SLOTS){
+ Object k = entries[i];
+ if(_notKey(k)) continue;
+ arr[pos++] = entries[i];
+ }
+ }
+
+ public Object remove(Object k) { return remove(_indexOf(k)); }
+ public Object remove(int dest) {
+ if (dest < 0) return null;
+ // instead of removing, insert a placeholder
+ Object r = entries[dest+1];
+ entries[dest] = PLACE_HOLDER;
+ entries[dest + 1] = null;
+ size--;
+ placeholders++;
+ return r;
+ }
+
+ public Object get(Object key) {
+ int i = _indexOf(key);
+ return i >= 0 ? entries[i + 1] : null;
+ }
+
+ public Object put(Object key, Object value) {
+ if (size + placeholders >= (float)(_capacity() * LOAD_FACTOR))
rehash();
+ int dest = _indexOf(key);
+ Object old = null;
+ if (dest < 0) {
+ dest = _convertKey(dest);
+ if (entries[dest] != PLACE_HOLDER) size++;
+ entries[dest] = key;
+ entries[dest+1] = null;
+ } else {
+ old = entries[dest + 1];
+ }
+ entries[dest + 1] = value;
+ return old;
+ }
+
+ /*
+ public boolean containsKey(Object k) { return super.containsValue(k); }
+ public boolean containsValue(Object v) {
+ for (int i=0; i < entries.length/indexmultiple; i++)
+ if ((i == 0 || entries[i * indexmultiple] != null) && // exception
for null key
+ !equals(placeholder, entries[i * indexmultiple]) &&
+ v == null ? entries[i + 1] == null : v.equals(entries[i + 1]))
+ return true;
+ return false;
+ }
+ */
+
+ /** Compares two keys for equality. <tt>userKey</tt> is the key
+ * passed to the map, <tt>storedKey</tt> is from the map.
+ *
+ * <p>Default implementation provides standard Java equality
+ * testing, <tt>k1 == null ? k2 == null : k1.equals(k2)</tt>.</p>
+ */
+ protected boolean equals(Object userKey, Object storedKey) {
+ return userKey == null ? storedKey == null : userKey.equals(storedKey);
+ }
+
+ /** Doubles the available entry space, first by packing the data
+ * set (removes <tt>placeholder</tt> references) and if necessary
+ * by increasing the size of the <tt>entries</tt> array.
+ */
+ private void rehash() {
+ // we may rehash if we have too many
+ boolean expand = size > (float)(_capacity() * LOAD_FACTOR);
+ rehash(expand);
+ }
+ private void rehash(boolean expand) {
+ Object[] oldentries = entries;
+ if(oldentries==null){
+ entries = new Object[4];
+ return;
+ }
+
+ entries = new Object[oldentries.length * (expand?2:1)];
+
+ for (int pos=0; pos < oldentries.length; pos+=2) {
+ Object k = oldentries[pos];
+ if (_notKey(k)) continue;
+
+ // dont adjust any of the support entries
+ int dest = _indexOf(k);
+ // dest is negative (new entry) so we
+ dest = _convertKey(dest);
+ entries[dest] = oldentries[pos];
+ entries[dest + 1] = oldentries[pos + 1];
+ }
+ placeholders = 0;
+ }
+}
\ No newline at end of file
Property changes on:
branches/vexi4/org.vexi-library.js/src/main/java/org/ibex/js/util/Hash.java
___________________________________________________________________
Added: svn:mime-type
## -0,0 +1 ##
+text/plain
\ No newline at end of property
This was sent by the SourceForge.net collaborative development platform, the
world's largest Open Source development site.
------------------------------------------------------------------------------
Try New Relic Now & We'll Send You this Cool Shirt
New Relic is the only SaaS-based application performance monitoring service
that delivers powerful full stack analytics. Optimize and monitor your
browser, app, & servers with just a few lines of code. Try New Relic
and get this awesome Nerd Life shirt! http://p.sf.net/sfu/newrelic_d2d_may
_______________________________________________
Vexi-svn mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/vexi-svn
