Warning: session_start(): open(/var/lib/php/sessions/sess_gs7cvqd88bsahmmmtsuag0a6s7, 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
sclass IntIntMap implements IIntIntMap {
private static final int FREE_KEY = 0;
public static final int NO_VALUE = 0;
/** Keys and values */
private int[] m_data;
/** Do we have 'free' key in the map? */
private boolean m_hasFreeKey;
/** Value of 'free' key */
private int m_freeValue;
/** Fill factor, must be between (0 and 1) */
private final float m_fillFactor;
/** We will resize a map once it reaches this size */
private int m_threshold;
/** Current map size */
private int m_size;
/** Mask to calculate the original position */
private int m_mask;
private int m_mask2;
*( final int size, final float fillFactor )
{
if ( fillFactor <= 0 || fillFactor >= 1 )
throw new IllegalArgumentException( "FillFactor must be in (0, 1)" );
if ( size <= 0 )
throw new IllegalArgumentException( "Size must be positive!" );
final int capacity = arraySize(size, fillFactor);
m_mask = capacity - 1;
m_mask2 = capacity*2 - 1;
m_fillFactor = fillFactor;
m_data = new int[capacity * 2];
m_threshold = (int) (capacity * fillFactor);
}
public int get( final int key )
{
int ptr = ( phiMix( key ) & m_mask) << 1;
if ( key == FREE_KEY )
return m_hasFreeKey ? m_freeValue : NO_VALUE;
int k = m_data[ ptr ];
if ( k == FREE_KEY )
return NO_VALUE; //end of chain already
if ( k == key ) //we check FREE prior to this call
return m_data[ ptr + 1 ];
while ( true )
{
ptr = (ptr + 2) & m_mask2; //that's next index
k = m_data[ ptr ];
if ( k == FREE_KEY )
return NO_VALUE;
if ( k == key )
return m_data[ ptr + 1 ];
}
}
public int put( final int key, final int value )
{
if ( key == FREE_KEY )
{
final int ret = m_freeValue;
if ( !m_hasFreeKey )
++m_size;
m_hasFreeKey = true;
m_freeValue = value;
return ret;
}
int ptr = ( phiMix( key ) & m_mask) << 1;
int k = m_data[ptr];
if ( k == FREE_KEY ) //end of chain already
{
m_data[ ptr ] = key;
m_data[ ptr + 1 ] = value;
if ( m_size >= m_threshold )
rehash( m_data.length * 2 ); //size is set inside
else
++m_size;
return NO_VALUE;
}
else if ( k == key ) //we check FREE prior to this call
{
final int _ret = m_data[ ptr + 1 ];
m_data[ ptr + 1 ] = value;
return _ret;
}
while ( true )
{
ptr = ( ptr + 2 ) & m_mask2; //that's next index calculation
k = m_data[ ptr ];
if ( k == FREE_KEY )
{
m_data[ ptr ] = key;
m_data[ ptr + 1 ] = value;
if ( m_size >= m_threshold )
rehash( m_data.length * 2 ); //size is set inside
else
++m_size;
return NO_VALUE;
}
else if ( k == key )
{
final int _ret = m_data[ ptr + 1 ];
m_data[ ptr + 1 ] = value;
return _ret;
}
}
}
public int remove( final int key )
{
if ( key == FREE_KEY )
{
if ( !m_hasFreeKey )
return NO_VALUE;
m_hasFreeKey = false;
--m_size;
return m_freeValue; //value is not cleaned
}
int ptr = ( phiMix( key ) & m_mask) << 1;
int k = m_data[ ptr ];
if ( k == key ) //we check FREE prior to this call
{
final int res = m_data[ ptr + 1 ];
shiftKeys( ptr );
--m_size;
return res;
}
else if ( k == FREE_KEY )
return NO_VALUE; //end of chain already
while ( true )
{
ptr = ( ptr + 2 ) & m_mask2; //that's next index calculation
k = m_data[ ptr ];
if ( k == key )
{
final int res = m_data[ ptr + 1 ];
shiftKeys( ptr );
--m_size;
return res;
}
else if ( k == FREE_KEY )
return NO_VALUE;
}
}
private int shiftKeys(int pos)
{
// Shift entries with the same hash.
int last, slot;
int k;
final int[] data = this.m_data;
while ( true )
{
pos = ((last = pos) + 2) & m_mask2;
while ( true )
{
if ((k = data[pos]) == FREE_KEY)
{
data[last] = FREE_KEY;
return last;
}
slot = ( phiMix( k ) & m_mask) << 1; //calculate the starting slot for the current key
if (last <= pos ? last >= slot || slot > pos : last >= slot && slot > pos) break;
pos = (pos + 2) & m_mask2; //go to the next entry
}
data[last] = k;
data[last + 1] = data[pos + 1];
}
}
public int size()
{
return m_size;
}
private void rehash( final int newCapacity )
{
m_threshold = (int) (newCapacity/2 * m_fillFactor);
m_mask = newCapacity/2 - 1;
m_mask2 = newCapacity - 1;
final int oldCapacity = m_data.length;
final int[] oldData = m_data;
m_data = new int[ newCapacity ];
m_size = m_hasFreeKey ? 1 : 0;
for ( int i = 0; i < oldCapacity; i += 2 ) {
final int oldKey = oldData[ i ];
if( oldKey != FREE_KEY )
put( oldKey, oldData[ i + 1 ]);
}
}
static int arraySize( final int expected, final float f ) {
final long s = Math.max( 2, nextPowerOfTwo( (long)Math.ceil( expected / f ) ) );
if ( s > (1 << 30) ) throw new IllegalArgumentException( "Too large (" + expected + " expected elements with load factor " + f + ")" );
return (int)s;
}
static final int INT_PHI = 0x9E3779B9;
static int phiMix( final int x ) {
final int h = x * INT_PHI;
return h ^ (h >> 16);
}
}