lsst::ap::detail::HashedSet< EntryT, NumEntries > Class Template Reference

A set of up to NumEntries elements of type EntryT, hashed by an integer identifier. More...

#include <ChunkManagerImpl.h>

Inheritance diagram for lsst::ap::detail::HashedSet< EntryT, NumEntries >:

Public Member Functions
	HashedSet ()
EntryT *	find (int const id)
	Returns a pointer to the entry with the given identifier, or null if there is no such entry. More...
EntryT const *	find (int const id) const
	Returns a pointer to the entry with the given identifier, or null if there is no such entry. More...
EntryT *	insert (int const id)
std::pair< EntryT *, bool >	findOrInsert (int const id)
bool	erase (int const id)
int	size () const
int	space () const
EntryT *	begin ()
EntryT const *	begin () const
EntryT *	end ()
EntryT const *	end () const

Private Member Functions
	BOOST_STATIC_ASSERT (NumEntries > 0 &&(NumEntries &(NumEntries-1))==0)
	BOOST_STATIC_ASSERT (NumEntries< INT_MAX)
EntryT const *	doFind (int const id) const

Private Attributes
int	_hashTable [2 *NumEntries]
int	_free
int	_size
EntryT	_entries [NumEntries]

Detailed Description

template<typename EntryT, int NumEntries>
class lsst::ap::detail::HashedSet< EntryT, NumEntries >

A set of up to NumEntries elements of type EntryT, hashed by an integer identifier.

The hash table implementation is chained and intrusive – requirements follow:

• NumEntries must be a positive power of 2
• EntryT must have

  int64_t getId() 

  and

  void setId(int64_t) 

  methods which get/set an int64_t member field and never throw. An id value of -1 is reserved for invalid entries.
• EntryT must have

  int getNextInChain() 

  and

  void setNextInChain(int) 

  methods which get/set an int member field and never throw
• EntryT must have a trivial destructor, and a default constructor that doesn't throw

Definition at line 72 of file ChunkManagerImpl.h.

Constructor & Destructor Documentation

template<typename EntryT , int NumEntries>

lsst::ap::detail::HashedSet< EntryT, NumEntries >::HashedSet

(

)

Definition at line 71 of file ChunkManagerImpl.cc.

                                         :
    _free(0), _size(0)
{
    for (int i = 0; i < 2*NumEntries; ++i) {
        _hashTable[i] = -1;
    }
    // initialize linked list of free entries (embedded in the entries themselves)
    for (int i = 0; i < NumEntries - 1; ++i) {
        _entries[i].setId(-1);
        _entries[i].setNextInChain(i + 1);
    }
    _entries[NumEntries - 1].setNextInChain(-1);
}

Member Function Documentation

template<typename EntryT, int NumEntries>

EntryT* lsst::ap::detail::HashedSet< EntryT, NumEntries >::begin ( )

inline

Returns a pointer to the beginning of the underlying array of entries. Not all array entries will correspond to HashedSet entries : invalid entries - those that do not correspond to an entry that has been added to the set via insert() or findOrInsert() - are marked with an id value of -1.

Definition at line 112 of file ChunkManagerImpl.h.

                     {
        return _entries;
    }

template<typename EntryT, int NumEntries>

EntryT const* lsst::ap::detail::HashedSet< EntryT, NumEntries >::begin ( ) const

inline

Definition at line 115 of file ChunkManagerImpl.h.

                                 {
        return _entries;
    }

template<typename EntryT, int NumEntries>

lsst::ap::detail::HashedSet< EntryT, NumEntries >::BOOST_STATIC_ASSERT ( NumEntries  , 0 &&  NumEntries &(NumEntries-1) = =0  )

private

template<typename EntryT, int NumEntries>

lsst::ap::detail::HashedSet< EntryT, NumEntries >::BOOST_STATIC_ASSERT ( )

private

template<typename EntryT , int NumEntries>

EntryT const * lsst::ap::detail::HashedSet< EntryT, NumEntries >::doFind ( int const  id ) const

private

Returns a pointer to the entry with the given identifier, or null if there is no such entry.

Parameters

[in]

id

The identifier of the entry to find.

Returns

A pointer to the entry with the given identifier, or null if no such entry was found.

Definition at line 93 of file ChunkManagerImpl.cc.

                                                                       {
    int i = _hashTable[hash(id) & (2*NumEntries - 1)];
    while (i >= 0) {
        if (id == _entries[i].getId()) {
            return &_entries[i];
        }
        i = _entries[i].getNextInChain();
    }
    return 0;
}

template<typename EntryT, int NumEntries>

EntryT* lsst::ap::detail::HashedSet< EntryT, NumEntries >::end ( )

inline

Returns a pointer to the end of the underlying array of entries.

Definition at line 120 of file ChunkManagerImpl.h.

                   {
        return _entries + NumEntries;
    }

template<typename EntryT, int NumEntries>

EntryT const* lsst::ap::detail::HashedSet< EntryT, NumEntries >::end ( ) const

inline

Definition at line 123 of file ChunkManagerImpl.h.

                               {
        return _entries + NumEntries;
    }

template<typename EntryT , int NumEntries>

bool lsst::ap::detail::HashedSet< EntryT, NumEntries >::erase

(

int const

id

)

Erases the entry with the given id, returning true if an entry with the given id was found.

Parameters

[in]

id

The id of the entry to erase.

Returns

true if an entry with the given id was found (and erased).

Definition at line 211 of file ChunkManagerImpl.cc.

                                                      {

    int const bucket = hash(id) & (2*NumEntries - 1);

    int i    = _hashTable[bucket];
    int last = -1;

    while (i >= 0) {
        if (id == _entries[i].getId()) {
            // found entry to erase, unlink it from the chain for its bucket
            if (last < 0) {
                _hashTable[bucket] = _entries[i].getNextInChain();
            } else {
                _entries[last].setNextInChain(_entries[i].getNextInChain());
            }
            // append the entry to the free list
            _entries[i].setId(-1);
            _entries[i].setNextInChain(_free);
            _free = i;
            --_size;
            return true;
        }
        last = i;
        i    = _entries[i].getNextInChain();
    }
    return false;
}

template<typename EntryT, int NumEntries>

EntryT* lsst::ap::detail::HashedSet< EntryT, NumEntries >::find ( int const  id )

inline

Returns a pointer to the entry with the given identifier, or null if there is no such entry.

Definition at line 82 of file ChunkManagerImpl.h.

                                {
        return const_cast<EntryT *>(doFind(id));
    }

template<typename EntryT, int NumEntries>

EntryT const* lsst::ap::detail::HashedSet< EntryT, NumEntries >::find ( int const  id ) const

inline

Returns a pointer to the entry with the given identifier, or null if there is no such entry.

Definition at line 87 of file ChunkManagerImpl.h.

                                            {
        return doFind(id);
    }

template<typename EntryT , int NumEntries>

std::pair< EntryT *, bool > lsst::ap::detail::HashedSet< EntryT, NumEntries >::findOrInsert

(

int const

id

)

Returns a pointer to a preexisting or freshly default-constructed entry with the given identifier, along with a boolean indicating whether the entry was inserted (true) or found (false). The pointer returned is null if and only if a fresh entry was required but there were no free entries available.

Parameters

[in]

id

The identifier (unique within this set) of the entry to find or insert.

Returns

A pointer to the entry with the given id along with a boolean indicating whether the entry was inserted (true) or found (false).

Definition at line 166 of file ChunkManagerImpl.cc.

                                                                                {

    int const bucket = hash(id) & (2*NumEntries - 1);

    int i    = _hashTable[bucket];
    int last = -1;

    while (i >= 0) {
        if (id == _entries[i].getId()) {
            return std::pair<EntryT *, bool>(&_entries[i], false); // found an entry with the given id
        }
        last = i;
        i    = _entries[i].getNextInChain();
    }

    // check that there is a free chunk, if so use it
    int const c = _free;
    if (c < 0) {
        return std::pair<EntryT *, bool>(0, true);
    }
    _free = _entries[c].getNextInChain();

    if (last < 0) {
        _hashTable[bucket] = c;
    } else {
        // hash collision - chain to the end of the bucket
        _entries[last].setNextInChain(c);
    }

    // basic chunk initialization, then return
    new (&_entries[c]) EntryT();
    _entries[c].setId(id);
    _entries[c].setNextInChain(-1);
    ++_size;
    return std::pair<EntryT *, bool>(&_entries[c], true);
}

template<typename EntryT , int NumEntries>

EntryT * lsst::ap::detail::HashedSet< EntryT, NumEntries >::insert

(

int const

id

)

Returns a pointer to a freshly initialized entry with the given identifier, or null if an entry with the given identifier already exists.

Parameters

[in]

id

The identifier (unique within this set) of the entry to insert.

Returns

A pointer to a freshly default-constructed entry with identifier set to id, or null if either a preexisting entry with the given identifier was found or no space for new entries remains.

Definition at line 115 of file ChunkManagerImpl.cc.

                                                           {

    // check that there is space for another entry
    if (_free < 0) {
        return 0;
    }

    int const bucket = hash(id) & (2*NumEntries - 1);

    int i    = _hashTable[bucket];
    int last = -1;

    while (i >= 0) {
        if (id == _entries[i].getId()) {
            return 0; // already have an entry with the given id
        }
        last = i;
        i    = _entries[i].getNextInChain();
    }

    // take an entry off the free list
    int const c = _free;
    _free = _entries[c].getNextInChain();

    if (last < 0) {
        _hashTable[bucket] = c;
    } else {
        // hash collision - chain to the end of the bucket
        _entries[last].setNextInChain(c);
    }

    // basic entry initialization, then return
    new (&_entries[c]) EntryT();
    _entries[c].setId(id);
    _entries[c].setNextInChain(-1);
    ++_size;
    return &_entries[c];
}

template<typename EntryT, int NumEntries>

int lsst::ap::detail::HashedSet< EntryT, NumEntries >::size ( ) const

inline

Returns the number of entries in the set

Definition at line 98 of file ChunkManagerImpl.h.

                     {
        return _size;
    }

template<typename EntryT, int NumEntries>

int lsst::ap::detail::HashedSet< EntryT, NumEntries >::space ( ) const

inline

Returns the number of additional entries there is space for in the set

Definition at line 103 of file ChunkManagerImpl.h.

                      {
        return NumEntries - _size;
    }

Member Data Documentation

template<typename EntryT, int NumEntries>

EntryT lsst::ap::detail::HashedSet< EntryT, NumEntries >::_entries[NumEntries]

private

Definition at line 131 of file ChunkManagerImpl.h.

template<typename EntryT, int NumEntries>

int lsst::ap::detail::HashedSet< EntryT, NumEntries >::_free

private

Definition at line 129 of file ChunkManagerImpl.h.

template<typename EntryT, int NumEntries>

int lsst::ap::detail::HashedSet< EntryT, NumEntries >::_hashTable[2 *NumEntries]

private

Definition at line 128 of file ChunkManagerImpl.h.

template<typename EntryT, int NumEntries>

int lsst::ap::detail::HashedSet< EntryT, NumEntries >::_size

private

Definition at line 130 of file ChunkManagerImpl.h.

---

The documentation for this class was generated from the following files:

• /lsst/home/lsstsw/stack/Linux64/ap/master-g60f1e072bb+1/include/lsst/ap/ChunkManagerImpl.h
• /lsst/home/lsstsw/stack/Linux64/ap/master-g60f1e072bb+1/include/lsst/ap/ChunkManagerImpl.cc