hashcontainer.hh

Click is a modular router toolkit. To use it you ll need to know how to compile and install the sof

	if (_element && _hc->_rep.hashnext(_element)) {
	    _pprev = &_hc->_rep.hashnext(_element);
	    _element = *_pprev;
	} else if (_bucket != _hc->_rep.nbuckets) {
	    for (++_bucket; _bucket != _hc->_rep.nbuckets; ++_bucket)
		if (*(_pprev = &_hc->_rep.buckets[_bucket])) {
		    _element = *_pprev;
		    return;
		}
	    _element = 0;
	}
    }

    /** @brief Advance this iterator to the next element. */
    void operator++(int) {
	++*this;
    }

  private:

    T *_element;
    T **_pprev;
    size_type _bucket;
    const HashContainer<T, A> *_hc;

    inline HashContainer_const_iterator(const HashContainer<T, A> *hc)
	: _hc(hc) {
	_bucket = hc->_rep.first_bucket;
	_pprev = &hc->_rep.buckets[_bucket];
	if (unlikely(_bucket == hc->_rep.nbuckets))
	    _element = 0;
	else if (!(_element = *_pprev)) {
	    (*this)++;
	    hc->_rep.first_bucket = _bucket;
	}
    }

    inline HashContainer_const_iterator(const HashContainer<T, A> *hc, size_type b, T **pprev, T *element)
	: _element(element), _pprev(pprev), _bucket(b), _hc(hc) {
	click_hash_assert((!_pprev && !_element) || *_pprev == _element);
    }

    friend class HashContainer<T, A>;
    friend class HashContainer_iterator<T, A>;

};

/** @class HashContainer_iterator
  @brief The iterator type for HashContainer. */
template <typename T, typename A>
class HashContainer_iterator : public HashContainer_const_iterator<T, A> { public:

    typedef HashContainer_const_iterator<T, A> inherited;

    /** @brief Construct an uninitialized iterator. */
    HashContainer_iterator() {
    }

    /** @brief Return true iff elements can be inserted here.
     *
     * Specifically, returns true iff this iterator is valid to pass to
     * HashContainer::insert_at() or HashContainer::set().  All live()
     * iterators can_insert(), but some !live() iterators can_insert() as
     * well. */
    bool can_insert() const {
	return this->_bucket < this->_hc->bucket_count();
    }

    /** @brief Return the corresponding HashContainer. */
    HashContainer<T, A> *hashcontainer() const {
	return const_cast<HashContainer<T, A> *>(this->_hc);
    }

  private:

    inline HashContainer_iterator(HashContainer<T, A> *hc)
	: inherited(hc) {
    }

    inline HashContainer_iterator(HashContainer<T, A> *hc, typename inherited::size_type b, T **pprev, T *element)
	: inherited(hc, b, pprev, element) {
    }

    friend class HashContainer<T, A>;

};

template <typename T, typename A>
HashContainer<T, A>::HashContainer()
{
    _rep.size = 0;
    _rep.nbuckets = initial_bucket_count;
    _rep.buckets = (T **) CLICK_LALLOC(sizeof(T *) * _rep.nbuckets);
    _rep.first_bucket = _rep.nbuckets;
    for (size_type b = 0; b < _rep.nbuckets; ++b)
	_rep.buckets[b] = 0;
}

template <typename T, typename A>
HashContainer<T, A>::HashContainer(size_type nb)
{
    size_type b = 1;
    while (b < nb && b < max_bucket_count)
	b = ((b + 1) << 1) - 1;
    _rep.size = 0;
    _rep.nbuckets = b;
    _rep.buckets = (T **) CLICK_LALLOC(sizeof(T *) * _rep.nbuckets);
    _rep.first_bucket = _rep.nbuckets;
    for (b = 0; b < _rep.nbuckets; ++b)
	_rep.buckets[b] = 0;
}

template <typename T, typename A>
HashContainer<T, A>::~HashContainer()
{
    CLICK_LFREE(_rep.buckets, sizeof(T *) * _rep.nbuckets);
}

template <typename T, typename A>
inline typename HashContainer<T, A>::size_type
HashContainer<T, A>::bucket(const key_type &key) const
{
    return ((size_type) hashcode(key)) % _rep.nbuckets;
}

template <typename T, typename A>
inline typename HashContainer<T, A>::const_iterator
HashContainer<T, A>::begin() const
{
    return const_iterator(this);
}

template <typename T, typename A>
inline typename HashContainer<T, A>::iterator
HashContainer<T, A>::begin()
{
    return iterator(this);
}

template <typename T, typename A>
inline typename HashContainer<T, A>::const_iterator
HashContainer<T, A>::end() const
{
    return const_iterator(this, -1, 0, 0);
}

template <typename T, typename A>
inline typename HashContainer<T, A>::iterator
HashContainer<T, A>::end()
{
    return iterator(this, -1, 0, 0);
}

template <typename T, typename A>
inline typename HashContainer<T, A>::iterator
HashContainer<T, A>::begin(size_type b)
{
    click_hash_assert(b < _rep.nbuckets);
    return iterator(this, b, &_rep.buckets[b], _rep.buckets[b]);
}

template <typename T, typename A>
inline typename HashContainer<T, A>::iterator
HashContainer<T, A>::find(const key_type &key)
{
    size_type b = bucket(key);
    T **pprev;
    for (pprev = &_rep.buckets[b]; *pprev; pprev = &_rep.hashnext(*pprev))
	if (_rep.hashkeyeq(_rep.hashkey(*pprev), key))
	    return iterator(this, b, pprev, *pprev);
    return iterator(this, b, &_rep.buckets[b], 0);
}

template <typename T, typename A>
inline typename HashContainer<T, A>::const_iterator
HashContainer<T, A>::find(const key_type &key) const
{
    return const_cast<HashContainer<T, A> *>(this)->find(key);
}

template <typename T, typename A>
inline typename HashContainer<T, A>::iterator
HashContainer<T, A>::find_prefer(const key_type &key)
{
    size_type b = bucket(key);
    T **pprev;
    for (pprev = &_rep.buckets[b]; *pprev; pprev = &_rep.hashnext(*pprev))
	if (_rep.hashkeyeq(_rep.hashkey(*pprev), key)) {
	    T *element = *pprev;
	    *pprev = _rep.hashnext(element);
	    _rep.hashnext(element) = _rep.buckets[b];
	    _rep.buckets[b] = element;
	    return iterator(this, b, &_rep.buckets[b], element);
	}
    return iterator(this, b, &_rep.buckets[b], 0);
}

template <typename T, typename A>
inline T *HashContainer<T, A>::get(const key_type &key) const
{
    return find(key).get();
}

template <typename T, typename A>
T *HashContainer<T, A>::set(iterator &it, T *element, bool balance)
{
    click_hash_assert(it._hc == this && it._bucket < _rep.nbuckets);
    click_hash_assert(bucket(_rep.hashkey(element)) == it._bucket);
    click_hash_assert(!it._element || _rep.hashkeyeq(_rep.hashkey(element), _rep.hashkey(it._element)));
    T *old = it.get();
    if (unlikely(old == element))
	return old;
    if (!element) {
	--_rep.size;
	if (!(*it._pprev = it._element = _rep.hashnext(old)))
	    ++it;
	return old;
    }
    if (old)
	_rep.hashnext(element) = _rep.hashnext(old);
    else {
	++_rep.size;
	if (unlikely(unbalanced()) && balance) {
	    rehash(bucket_count() + 1);
	    it._bucket = bucket(_rep.hashkey(element));
	    it._pprev = &_rep.buckets[it._bucket];
	}
	if (!(_rep.hashnext(element) = *it._pprev))
	    _rep.first_bucket = 0;
    }
    *it._pprev = it._element = element;
    return old;
}

template <typename T, typename A>
inline void HashContainer<T, A>::insert_at(iterator &it, T *element)
{
    click_hash_assert(it._hc == this && it._bucket < _rep.nbuckets);
    click_hash_assert(bucket(_rep.hashkey(element)) == it._bucket);
    ++_rep.size;
    if (!(_rep.hashnext(element) = it._element))
	_rep.first_bucket = 0;
    *it._pprev = element;
    it._pprev = &_rep.hashnext(element);
}

template <typename T, typename A>
inline T *HashContainer<T, A>::set(T *element)
{
    iterator it = find(_rep.hashkey(element));
    return set(it, element);
}

template <typename T, typename A>
inline T *HashContainer<T, A>::erase(iterator &it)
{
    click_hash_assert(it._hc == this);
    return set(it, 0);
}

template <typename T, typename A>
inline T *HashContainer<T, A>::erase(const key_type &key)
{
    iterator it = find(key);
    return set(it, 0);
}

template <typename T, typename A>
inline void HashContainer<T, A>::clear()
{
    for (size_type b = 0; b < _rep.nbuckets; ++b)
	_rep.buckets[b] = 0;
    _rep.size = 0;
}

template <typename T, typename A>
inline void HashContainer<T, A>::swap(HashContainer<T, A> &o)
{
    HashContainer_rep<T, A> rep(_rep);
    _rep = o._rep;
    o._rep = rep;
}

template <typename T, typename A>
void HashContainer<T, A>::rehash(size_type n)
{
    size_type new_nbuckets = 1;
    while (new_nbuckets < n && new_nbuckets < max_bucket_count)
	new_nbuckets = ((new_nbuckets + 1) << 1) - 1;
    click_hash_assert(new_nbuckets > 0 && new_nbuckets <= max_bucket_count);
    if (_rep.nbuckets == new_nbuckets)
	return;

    T **new_buckets = (T **) CLICK_LALLOC(sizeof(T *) * new_nbuckets);
    for (size_type b = 0; b < new_nbuckets; ++b)
	new_buckets[b] = 0;

    size_type old_nbuckets = _rep.nbuckets;
    T **old_buckets = _rep.buckets;
    _rep.nbuckets = new_nbuckets;
    _rep.buckets = new_buckets;
    _rep.first_bucket = 0;

    for (size_t b = 0; b < old_nbuckets; b++)
	for (T *element = old_buckets[b]; element; ) {
	    T *next = _rep.hashnext(element);
	    size_type new_b = bucket(_rep.hashkey(element));
	    _rep.hashnext(element) = new_buckets[new_b];
	    new_buckets[new_b] = element;
	    element = next;
	}

    CLICK_LFREE(old_buckets, sizeof(T *) * old_nbuckets);
}

template <typename T, typename A>
inline bool
operator==(const HashContainer_const_iterator<T, A> &a, const HashContainer_const_iterator<T, A> &b)
{
    click_hash_assert(a.hashcontainer() == b.hashcontainer());
    return a.get() == b.get();
}

template <typename T, typename A>
inline bool
operator!=(const HashContainer_const_iterator<T, A> &a, const HashContainer_const_iterator<T, A> &b)
{
    click_hash_assert(a.hashcontainer() == b.hashcontainer());
    return a.get() != b.get();
}

CLICK_ENDDECLS
#endif