Warning: session_start(): open(/var/lib/php/sessions/sess_n31mseaqp979c45cmq078p3ot4, O_RDWR) failed: No space left on device (28) in /var/www/tb-usercake/models/config.php on line 51
Warning: session_start(): Failed to read session data: files (path: /var/lib/php/sessions) in /var/www/tb-usercake/models/config.php on line 51
/*
* #!
* Ontopia Engine
* #-
* Copyright (C) 2001 - 2013 The Ontopia Project
* #-
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
* !#
*/
sclass CompactHashMap extends AbstractMap {
final static int INITIAL_SIZE = 3;
final static double LOAD_FACTOR = 0.6;
// This object is used to represent null, should clients use that as
final static Object nullObject = new Object();
/**
* When a key is deleted this object is put into the hashtable in
* its place, so that other entries with the same key (collisions)
* further down the hashtable are not lost after we delete an object
* in the collision chain.
*/
final static Object deletedObject = new Object();
int elements;
int freecells;
O[] table; // key, value, key, value, ...
int modCount;
*() {
this(INITIAL_SIZE);
}
*(int size) {
table = new Object[(size==0 ? 1 : size)*2];
elements = 0;
freecells = keys.length;
modCount = 0;
}
// ===== MAP IMPLEMENTATION =============================================
/**
* Returns the number of key/value mappings in this map.
*/
public synchronized int size() {
return elements;
}
/**
* Returns true if this map contains no mappings.
*/
public synchronized boolean isEmpty() {
return elements == 0;
}
/**
* Removes all key/value mappings in the map.
*/
public synchronized void clear() {
elements = 0;
for (int ix = 0; ix < keys.length; ix++) {
key(ix, null);
value(ix, null);
}
freecells = values.length;
modCount++;
}
/**
* Returns true if this map contains the specified key.
*/
public synchronized boolean containsKey(Object k) {
return key(findKeyIndex(k)) != null;
}
/**
* Returns true if this map contains the specified value.
*/
public synchronized boolean containsValue(Object v) {
if (v == null)
v = (V)nullObject;
for (int ix = 0; ix < values.length; ix++)
if (value(ix) != null && value(ix).equals(v))
return true;
return false;
}
/**
* Returns a read-only set view of the map's keys.
*/
public synchronized Set> entrySet() {
throw new UnsupportedOperationException();
}
/**
* Removes the mapping with key k, if there is one, and returns its
* value, if there is one, and null if there is none.
*/
public synchronized V remove(Object k) {
int index = findKeyIndex(k);
// we found the right position, now do the removal
if (key(index) != null) {
// we found the object
// same problem here as with put
V v = value(index);
key(index, deletedObject);
value(index, deletedObject);
modCount++;
elements--;
return v;
} else
// we did not find the key
return null;
}
/**
* Adds the specified mapping to this map, returning the old value for
* the mapping, if there was one.
*/
public synchronized V put(K k, V v) {
if (k == null)
k = (K)nullObject;
int hash = k.hashCode();
int index = (hash & 0x7FFFFFFF) % keys.length;
int offset = 1;
int deletedix = -1;
// search for the key (continue while !null and !this key)
while(key(index) != null &&
!(key(index).hashCode() == hash &&
key(index).equals(k))) {
// if there's a deleted mapping here we can put this mapping here,
// provided it's not in here somewhere else already
if (key(index) == deletedObject)
deletedix = index;
index = ((index + offset) & 0x7FFFFFFF) % keys.length;
offset = offset*2 + 1;
if (offset == -1)
offset = 2;
}
if (key(index) == null) { // wasn't present already
if (deletedix != -1) // reusing a deleted cell
index = deletedix;
else
freecells--;
modCount++;
elements++;
key(index, k);
value(index, v);
// rehash with increased capacity
if (1 - (freecells / (double) keys.length) > LOAD_FACTOR)
rehash(keys.length*2 + 1);
return null;
} else { // was there already
modCount++;
V oldv = value(index);
value(index, v);
return oldv;
}
}
/**
* INTERNAL: Rehashes the hashmap to a bigger size.
*/
void rehash(int newCapacity) {
int oldCapacity = keys.length;
O[] newTable = new Object[newCapacity*2];
for (int ix = 0; ix < oldCapacity; ix++) {
Object k = key(ix);
if (k == null || k == deletedObject)
continue;
int hash = k.hashCode();
int index = (hash & 0x7FFFFFFF) % newCapacity;
int offset = 1;
// search for the key
while(newTable[index*2] != null) { // no need to test for duplicates
index = ((index + offset) & 0x7FFFFFFF) % newCapacity;
offset = offset*2 + 1;
if (offset == -1)
offset = 2;
}
newTable[index*2] = k;
newTable[index*2+1] = value(ix);
}
table = newTable;
freecells = keys.length - elements;
}
/**
* Returns the value for the key k, if there is one, and null if
* there is none.
*/
public synchronized V get(Object k) {
return value(findKeyIndex(k)];
}
/**
* Returns a virtual read-only collection containing all the values
* in the map.
*/
public synchronized Collection values() {
return new ValueCollection();
}
/**
* Returns a virtual read-only set of all the keys in the map.
*/
public synchronized Set keySet() {
return new KeySet();
}
// --- Internal utilities
final int findKeyIndex(Object k) {
if (k == null)
k = nullObject;
int hash = k.hashCode();
int index = (hash & 0x7FFFFFFF) % keys.length;
int offset = 1;
// search for the key (continue while !null and !this key)
while(key(index] != null &&
!(key(index].hashCode() == hash &&
key(index].equals(k))) {
index = ((index + offset) & 0x7FFFFFFF) % keys.length;
offset = offset*2 + 1;
if (offset == -1)
offset = 2;
}
return index;
}
// --- Key set
class KeySet extends AbstractSet {
public synchronized int size() {
return elements;
}
public synchronized boolean contains(Object k) {
return containsKey(k);
}
public synchronized Iterator iterator() {
return new KeyIterator();
}
}
class KeyIterator implements Iterator {
private int ix;
private KeyIterator() {
// walk up to first value, so that hasNext() and next() return
// correct results
for (; ix < keys.length; ix++)
if (value(ix) != null && key(ix) != deletedObject)
break;
}
public synchronized boolean hasNext() {
return ix < keys.length;
}
public synchronized void remove() {
throw new UnsupportedOperationException("Collection is read-only");
}
public synchronized K next() {
if (ix >= keys.length)
throw new NoSuchElementException();
K key = (K) key(ix++);
// walk up to next value
for (; ix < keys.length; ix++)
if (key(ix) != null && key(ix) != deletedObject)
break;
// ix now either points to next key, or outside array (if no next)
return key;
}
}
// --- Value collection
class ValueCollection extends AbstractCollection {
public synchronized int size() {
return elements;
}
public synchronized Iterator iterator() {
return new ValueIterator();
}
public synchronized boolean contains(Object v) {
return containsValue(v);
}
}
class ValueIterator implements Iterator {
private int ix;
private ValueIterator() {
// walk up to first value, so that hasNext() and next() return
// correct results
for (; ix < table.length/2; ix++)
if (value(ix) != null && value(ix) != deletedObject)
break;
}
public synchronized boolean hasNext() {
return ix < values.length;
}
public synchronized void remove() {
throw new UnsupportedOperationException("Collection is read-only");
}
public synchronized V next() {
if (ix >= values.length)
throw new NoSuchElementException();
V value = (V) value(ix++];
// walk up to next value
for (; ix < values.length; ix++)
if (value(ix] != null && value(ix] != deletedObject)
break;
// ix now either points to next value, or outside array (if no next)
return value;
}
}
K key(int i) { ret (K) table[i*2]; }
void key(int i, O key) { ret table[i*2] = key; }
V value(int i) { ret (V) table[i*2+1]; }
void value(int i, O value) { table[i*2+1] = value; }
}