Warning: session_start(): open(/var/lib/php/sessions/sess_k2mbdqv3qs8j0t2dr9ahth11vv, 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
/*
* #!
* loosely based on code from the 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.
* !#
*/
// Note: Long.MIN_VALUE and Long.MIN_VALUE+1 are not allowed as keys
sclass LongIntHashMap_IntMemory extends AbstractMap {
final static int INITIAL_SIZE = 3;
final static double LOAD_FACTOR = 0.6;
/**
* 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 long noKey = Long.MIN_VALUE; // null in original code
final static long deletedKey = Long.MIN_VALUE+1;
IIntMemory mem;
// memory layout:
// tableSize at 0
// elements at 1
// freecells at 2
// table starts at 3 (long key, int value, ...)
int tableSize;
int elements;
int freecells;
int modCount;
// load existing map
*(IIntMemory *mem) {
tableSize = mem.get(0);
elements = mem.get(1);
freecells = mem.get(2);
}
// make new map
*(IIntMemory *mem, int capacity) {
setTableSize(iceil(capacity/LOAD_FACTOR));
setElements(0);
setFreecells(0);
for i to tableSize:
setKey(i, noKey);
}
void setTableSize(int tableSize) {
mem.set(0, this.tableSize = tableSize);
}
void setElements(int elements) {
mem.set(1, this.elements = elements);
}
void setFreecells(int freecells) {
mem.set(2, this.freecells = freecells);
}
// ===== MAP IMPLEMENTATION =============================================
public synchronized int size() { ret elements; }
public synchronized boolean isEmpty() { ret elements == 0; }
public synchronized void clear() {
setElements(0);
for ix to tableSize: {
setKey(ix, noKey);
setValue(ix, 0); // just for beauty
}
setFreecells(tableSize);
modCount++;
}
int ptr(int i) { ret 3+i*3; }
void setKey(int i, long key) {
mem.setLong(ptr(i), key);
}
void setValue(int i, int val) {
mem.set(ptr(i)+2, val);
}
long getKey(int i) {
ret mem.getLong(ptr(i));
}
int getValue(int i) {
ret mem.get(ptr(i)+2);
}
public synchronized bool containsKey(Object k) {
return getKey(findKeyIndex((Long) k)) != noKey;
}
public synchronized Set> entrySet() {
throw new UnsupportedOperationException();
}
public synchronized Int remove(Object k) {
int index = findKeyIndex((Long) k);
// we found the right position, now do the removal
if (getKey(index) != noKey) {
// we found the object
// same problem here as with put
int v = getValue(index);
setKey(index, deletedKey);
setValue(index, 0);
modCount++;
setElements(elements-1);
ret v;
}
// we did not find the key
null;
}
public synchronized Int put(Long k, Int v) {
int hash = k.hashCode();
int index = (hash & 0x7FFFFFFF) % tableSize;
int offset = 1;
int deletedix = -1;
// search for the key (continue while !null and !this key)
while (getKey(index) != noKey && getKey(index) != k) {
// if there's a deleted mapping here we can put this mapping here,
// provided it's not in here somewhere else already
if (getKey(index) == deletedKey)
deletedix = index;
index = ((index + offset) & 0x7FFFFFFF) % tableSize;
offset = offset*2 + 1;
if (offset == -1)
offset = 2;
}
if (getKey(index) == noKey) { // wasn't present already
if (deletedix != -1) // reusing a deleted cell
index = deletedix;
else
setFreecells(freecells-1);
modCount++;
setElements(elements+1);
setKey(index, k);
setValue(index, v);
// rehash with increased capacity
if (1 - (freecells / (double) tableSize) > LOAD_FACTOR)
rehash(tableSize*2 + 1);
null;
} else { // was there already
modCount++;
int oldv = getValue(index);
setValue(index, v);
ret oldv;
}
}
/**
* INTERNAL: Rehashes the hashmap to a bigger size.
*/
void rehash(int newCapacity) {
fail("rehash not implemented");
}
public synchronized Int get(Object k) {
int i = findKeyIndex((Long) k);
ret getKey(i) == noKey ? null : getValue(i);
}
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(long k) {
int hash = hashCode(k);
int index = (hash & 0x7FFFFFFF) % tableSize;
int offset = 1;
// search for the key (continue while !null and !this key)
while (getKey(index) != noKey && getKey(index) != k) {
index = ((index + offset) & 0x7FFFFFFF) % tableSize;
offset = offset*2 + 1;
if (offset == -1)
offset = 2;
}
ret index;
}
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 < tableSize; ix++)
if (getKey(ix) != noKey && getKey(ix) != deletedKey)
break;
}
public synchronized boolean hasNext() {
return ix < tableSize;
}
public synchronized void remove() {
throw new UnsupportedOperationException("Collection is read-only");
}
public synchronized Long next() {
if (ix >= tableSize)
throw new NoSuchElementException();
long key = getKey(ix++);
// walk up to next value
for (; ix < tableSize; ix++)
if (getKey(ix) != noKey && getKey(ix) != deletedKey)
break;
// ix now either points to next key, or outside array (if no next)
ret 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 < tableSize; ix++)
if (getKey(ix) != noKey && getKey(ix) != deletedKey)
break;
}
public synchronized boolean hasNext() {
return ix < tableSize;
}
public synchronized void remove() {
throw new UnsupportedOperationException("Collection is read-only");
}
public synchronized Int next() {
if (ix >= tableSize)
throw new NoSuchElementException();
int value = getValue(ix++);
// walk up to next value
for (; ix < tableSize; ix++)
if (getKey(ix) != noKey && getKey(ix) != deletedKey)
break;
// ix now either points to next value, or outside array (if no next)
return value;
}
}
}