#include <SphynxCollexion.hpp>

Public Member Functions
void	Begin (CollexionIterator< T > &iter)
	Collexion ()
bool	Insert (T *conn)
CAT_INLINE bool	IsEmpty ()
void	Next (CollexionIterator< T > &iter, bool refill=true)
bool	Remove (T *conn)
	~Collexion ()
Protected Member Functions
bool	DoubleTable ()
void	Fill (CollexionIterator< T > &iter, u32 first)
u32	Find (T *conn)
void	Unlink (u32 key)
Static Protected Member Functions
static CAT_INLINE u32	HashPtr (T *ptr)
Private Attributes
u32	_allocated
u32	_first
Mutex	_lock
CollexionElement< T > *	_table
CollexionElement2 *	_table2
u32	_used
Static Private Attributes
static const u32	COLLIDE_MASK = 0x80000000
static const u32	KILL_MASK = 0x40000000
static const u32	MIN_ALLOCATED = 32
static const u32	NEXT_MASK = 0x3fffffff

Detailed Description

template<class T>
class cat::sphynx::Collexion< T >

Definition at line 94 of file SphynxCollexion.hpp.

Constructor & Destructor Documentation

template<class T>

cat::sphynx::Collexion< T >::Collexion ( ) [inline]

Definition at line 159 of file SphynxCollexion.hpp.

References cat::sphynx::Collexion< T >::_allocated, cat::sphynx::Collexion< T >::_first, cat::sphynx::Collexion< T >::_table, cat::sphynx::Collexion< T >::_table2, and cat::sphynx::Collexion< T >::_used.

    {
        _first = 0;
        _used = 0;
        _allocated = 0;
        _table = 0;
        _table2 = 0;
    }

template<class T >

cat::sphynx::Collexion< T >::~Collexion ( )

Definition at line 323 of file SphynxCollexion.hpp.

References cat::Singleton< RegionAllocator >::ii, cat::RegionAllocator::Release(), and T.

{
    if (_table2)
    {
        RegionAllocator::ii->Release(_table2);
    }

    // If table doesn't exist, return
    if (!_table) return;

    // For each allocated table entry,
    for (u32 ii = 0; ii < _allocated; ++ii)
    {
        // Get Connexion object
        T *conn = _table[ii].conn;

        // If object is valid, release it
        if (conn) conn->ReleaseRef();
    }

    // Release table memory
    RegionAllocator::ii->Release(_table);
}

Member Function Documentation

template<class T >

void cat::sphynx::Collexion< T >::Begin ( CollexionIterator< T > & iter )

Definition at line 565 of file SphynxCollexion.hpp.

References cat::sphynx::CollexionIterator< T >::_parent.

Referenced by cat::sphynx::CollexionIterator< T >::CollexionIterator().

{
    iter._parent = this;

    AutoMutex lock(_lock);

    Fill(iter, _first);
}

template<class T >

bool cat::sphynx::Collexion< T >::DoubleTable ( ) [protected]

Definition at line 239 of file SphynxCollexion.hpp.

References cat::RegionAllocator::Acquire(), CAT_CLR, cat::sphynx::COLLISION_INCREMENTER, cat::sphynx::COLLISION_MULTIPLIER, cat::sphynx::CollexionElement< T >::conn, cat::sphynx::CollexionElement2::hash, cat::Singleton< RegionAllocator >::ii, cat::sphynx::CollexionElement2::last, cat::sphynx::CollexionElement< T >::next, and cat::RegionAllocator::Release().

{
    u32 new_allocated = _allocated << 1;
    if (new_allocated < MIN_ALLOCATED) new_allocated = MIN_ALLOCATED;

    // Allocate secondary table
    u32 new_bytes2 = sizeof(CollexionElement2) * new_allocated;
    CollexionElement2 *new_table2 = reinterpret_cast<CollexionElement2*>(
        RegionAllocator::ii->Acquire(new_bytes2) );

    if (!new_table2) return false;

    // Allocate primary table
    u32 new_bytes = sizeof(CollexionElement<T>) * new_allocated;
    CollexionElement<T> *new_table = reinterpret_cast<CollexionElement<T> *>(
        RegionAllocator::ii->Acquire(new_bytes) );

    if (!new_table)
    {
        RegionAllocator::ii->Release(new_table2);
        return false;
    }

    CAT_CLR(new_table, new_bytes);

    u32 new_first = 0;

    if (_table && _table2)
    {
        // For each entry in the old table,
        u32 ii = _first, mask = _allocated - 1;

        while (ii)
        {
            --ii;
            CollexionElement<T> *oe = &_table[ii];
            u32 hash = _table2[ii].hash;
            u32 key = hash & mask;

            // While collisions occur,
            while (new_table[key].conn)
            {
                // Mark collision
                new_table[key].next |= COLLIDE_MASK;

                // Walk collision list
                key = (key * COLLISION_MULTIPLIER + COLLISION_INCREMENTER) & mask;
            }

            // Fill new table element
            new_table[key].conn = oe->conn;
            new_table2[key].hash = hash;
            // new_table[key].refcnt is already zero

            // Link new element to new list
            if (new_first)
            {
                new_table[key].next |= new_first;
                new_table2[new_first - 1].last = key;
            }
            // new_table[key].next is already zero so no need to zero it here
            new_first = key + 1;

            // Get next old table entry
            ii = oe->next & NEXT_MASK;
        }

        // Zero head->last
        new_table2[new_first - 1].last = 0;
    }

    // Resulting linked list starting with _first-1 will extend until e->next == 0

    if (_table2) RegionAllocator::ii->Release(_table2);
    if (_table) RegionAllocator::ii->Release(_table);

    _table = new_table;
    _table2 = new_table2;
    _allocated = new_allocated;
    _first = new_first;
    return true;
}

template<class T >

void cat::sphynx::Collexion< T >::Fill	(	CollexionIterator< T > &	iter,
		u32	first
	)		`[protected]`

Definition at line 501 of file SphynxCollexion.hpp.

References cat::sphynx::CollexionIterator< T >::_cache, cat::sphynx::CollexionIterator< T >::_first, cat::sphynx::CollexionIterator< T >::_last, cat::sphynx::CollexionIterator< T >::_offset, cat::sphynx::CollexionIterator< T >::_prev_allocated, and cat::sphynx::CollexionIterator< T >::_total.

{
    u32 key = first;

    // Find first list element that does not want to die
    while (key && (_table[key-1].next & KILL_MASK))
    {
        // Go to next
        key = _table[key-1].next & NEXT_MASK;
    }

    iter._offset = 0;

    // If no elements in table,
    if (!key)
    {
        // Return empty set
        iter._cache[0] = 0;
        iter._total = 0;
        iter._first = 0;
        iter._last = 0;
        return;
    }

    // Remember size of hash table in case it grows before iterator is done
    iter._prev_allocated = _allocated;

    // Remember first key for next iteration
    iter._first = key;

    // For each of the first MAX_CACHE elements in the table, copy the data pointer to cache
    u32 ii = 0, final = 0;

    do
    {
        // If element does not want to die,
        if (!(_table[key-1].next & KILL_MASK))
        {
            // Copy data pointer
            iter._cache[ii] = _table[key-1].conn;

            // Increment reference count for element
            _table[key-1].refcnt++;

            // Remember key as the next iteration starting point
            final = key;

            // Check if copy is complete
            if (++ii >= CollexionIterator<T>::MAX_CACHE) break;
        }

        // Go to next key
        key = _table[key-1].next & NEXT_MASK;

    } while (key);

    // Record number of elements written
    iter._total = ii;

    // Remember next key for next iteration
    iter._last = final;
}

template<class T >

u32 cat::sphynx::Collexion< T >::Find ( T * conn ) [protected]

Definition at line 576 of file SphynxCollexion.hpp.

References cat::sphynx::COLLISION_INCREMENTER, and cat::sphynx::COLLISION_MULTIPLIER.

{
    u32 mask = _allocated - 1;
    u32 key = HashPtr(conn) & mask;

    // Find the object in the collision list starting at the expected location
    while (_table[key].conn != conn)
    {
        // If at the end of the collision list,
        if (!(_table[key].next & COLLIDE_MASK))
            break; // Should never happen

        // Walk collision list
        key = (key * COLLISION_MULTIPLIER + COLLISION_INCREMENTER) & mask;
    }

    return key;
}

template<class T>

static CAT_INLINE u32 cat::sphynx::Collexion< T >::HashPtr ( T * ptr ) [inline, static, protected]

Definition at line 126 of file SphynxCollexion.hpp.

    {
        u64 key = 0xBADdecafDEADbeef;

#if defined(CAT_WORD_64)
        key ^= *(u64*)&ptr;
#else
        key ^= *(u32*)&ptr;
#endif

        key = (~key) + (key << 18);
        key = key ^ (key >> 31);
        key = key * 21;
        key = key ^ (key >> 11);
        key = key + (key << 6);
        key = key ^ (key >> 22);
        return (u32)key;
    }

template<class T >

bool cat::sphynx::Collexion< T >::Insert ( T * conn )

Definition at line 348 of file SphynxCollexion.hpp.

References cat::sphynx::COLLISION_INCREMENTER, cat::sphynx::COLLISION_MULTIPLIER, and cat::AutoMutex::Release().

{
    u32 hash = HashPtr(conn);
    conn->AddRef();

    AutoMutex lock(_lock);

    // If more than half of the table will be used,
    if (_used >= (_allocated >> 1))
    {
        // Double the size of the table (O(1) allocation pattern)
        // Growing pains are softened by careful design
        if (!DoubleTable())
        {
            // On growth failure, return false
            lock.Release();

            conn->ReleaseRef();

            return false;
        }
    }

    // Mask off high bits to make table key from hash
    u32 mask = _allocated - 1;
    u32 key = hash & mask;

    // While empty table entry not found,
    while (_table[key].conn)
    {
        // If Connexion object is already in the table,
        if (_table[key].conn == conn)
        {
            // Return false on duplicate
            lock.Release();

            conn->ReleaseRef();

            return false;
        }

        // Mark as a collision
        _table[key].next |= COLLIDE_MASK;

        // Walk collision list
        key = (key * COLLISION_MULTIPLIER + COLLISION_INCREMENTER) & mask;
    }

    // Fill new element
    _table[key].conn = conn;
    _table[key].refcnt = 0;
    _table2[key].hash = hash;
    _table2[key].last = 0;

    // Link new element to front of list
    if (_first) _table2[_first - 1].last = key + 1;
    _table[key].next = (_table[key].next & COLLIDE_MASK) | _first;
    _first = key + 1;

    ++_used;
    return true;
}

template<class T>

CAT_INLINE bool cat::sphynx::Collexion< T >::IsEmpty ( ) [inline]

Definition at line 172 of file SphynxCollexion.hpp.

References cat::sphynx::Collexion< T >::_used.

{ return _used == 0; }

template<class T >

void cat::sphynx::Collexion< T >::Next	(	CollexionIterator< T > &	iter,
		bool	refill = `true`
	)

Definition at line 596 of file SphynxCollexion.hpp.

References cat::sphynx::CollexionIterator< T >::_cache, cat::sphynx::CollexionIterator< T >::_first, cat::sphynx::CollexionIterator< T >::_last, cat::sphynx::CollexionIterator< T >::_offset, cat::sphynx::CollexionIterator< T >::_prev_allocated, cat::sphynx::CollexionIterator< T >::_total, cat::AutoMutex::Release(), and T.

{
    T *release_list[CollexionIterator<T>::MAX_CACHE];
    u32 release_ii = 0;

    u32 key = iter._first;
    u32 last = iter._last;

    // If iteration is done,
    if (!key) return;

    AutoMutex lock(_lock);

    // If hash table changed size (rare),
    if (iter._prev_allocated != _allocated)
    {
        // iter._first and iter._last are invalid
        // ...but we can find them again based on the cached pointers!
        key = Find(iter._cache[0]) + 1;
        last = Find(iter._cache[iter._total - 1]) + 1;
    }

    last = _table[last-1].next & NEXT_MASK;

    // Release any table elements that want to die now
    do 
    {
        u32 flags = _table[key-1].next;

        // If reference count is now zero for this element,
        if (0 == --_table[key-1].refcnt)
        {
            // If element wants to die,
            if (flags & KILL_MASK)
            {
                // Prepare to release data after lock is released
                release_list[release_ii++] = _table[key-1].conn;

                Unlink(key-1);
            }
        }

        key = flags & NEXT_MASK;

    } while (key != last);

    // Fill iterator starting with next key
    if (refill) Fill(iter, key);

    lock.Release();

    if (!refill)
    {
        // Return empty set
        iter._cache[0] = 0;
        iter._total = 0;
        iter._offset = 0;
        iter._first = 0;
        iter._last = 0;
    }

    // Release data awaiting destruction
    for (u32 ii = 0; ii < release_ii; ++ii)
    {
        release_list[ii]->ReleaseRef();
    }
}

template<class T >

bool cat::sphynx::Collexion< T >::Remove ( T * conn )

Definition at line 450 of file SphynxCollexion.hpp.

References cat::sphynx::COLLISION_INCREMENTER, cat::sphynx::COLLISION_MULTIPLIER, and cat::AutoMutex::Release().

{
    u32 hash = HashPtr(conn);

    AutoMutex lock(_lock);

    // If table doesn't exist,
    if (!_allocated) return false;

    // Mask off high bits to make table key from hash
    u32 mask = _allocated - 1;
    u32 key = hash & mask;

    // While target table entry not found,
    for (;;)
    {
        // If target was found,
        if (_table[key].conn == conn)
        {
            if (_table[key].refcnt)
            {
                // Mark it killed so iterator can clean it up when it's finished
                _table[key].next |= KILL_MASK;
            }
            else
            {
                Unlink(key);

                lock.Release();

                conn->ReleaseRef();
            }

            // Return success
            return true;
        }

        if (!(_table[key].next & COLLIDE_MASK))
        {
            break; // End of collision list
        }

        // Walk collision list
        key = (key * COLLISION_MULTIPLIER + COLLISION_INCREMENTER) & mask;
    }

    // Return failure: not found
    return false;
}

template<class T >

void cat::sphynx::Collexion< T >::Unlink ( u32 key ) [protected]

Definition at line 412 of file SphynxCollexion.hpp.

References cat::sphynx::COLLISION_INCRINVERSE, and cat::sphynx::COLLISION_MULTINVERSE.

{
    // Clear reference
    _table[key].conn = 0;

    // Unlink from active list
    u32 next = _table[key].next & NEXT_MASK;
    u32 last = _table2[key].last;

    if (last) _table[last-1].next = (_table[last-1].next & ~NEXT_MASK) | next;
    else _first = next;
    if (next) _table2[next-1].last = last;

    // If this key was a leaf on a collision wind,
    if (!(_table[key].next & COLLIDE_MASK))
    {
        u32 mask = _allocated - 1;

        do
        {
            // Go backwards through the collision list one step
            key = ((key + COLLISION_INCRINVERSE) * COLLISION_MULTINVERSE) & mask;

            // Stop where collision list stops
            if (!(_table[key].next & COLLIDE_MASK))
                break;

            // Turn off collision key for previous entry
            _table[key].next &= ~COLLIDE_MASK;

        } while (!_table[key].conn);
    }

    // Update number of used elements
    --_used;
}