FM / common

/usr/include/stxxl/bits/common

Name	Size	Mode	Actions
addressable_queues.h	6036	0644	edit dl rm
aligned_alloc.h	5387	0644	edit dl rm
binary_buffer.h	20063	0644	edit dl rm
cmdline.h	23482	0644	edit dl rm
condition_variable.h	2141	0644	edit dl rm
counting_ptr.h	16404	0644	edit dl rm
error_handling.h	7702	0644	edit dl rm
exceptions.h	2000	0644	edit dl rm
exithandler.h	1400	0644	edit dl rm
external_shared_ptr.h	3760	0644	edit dl rm
is_sorted.h	1818	0644	edit dl rm
log.h	1265	0644	edit dl rm
mutex.h	3332	0644	edit dl rm
new_alloc.h	3901	0644	edit dl rm
onoff_switch.h	2146	0644	edit dl rm
rand.h	8191	0644	edit dl rm
seed.h	863	0644	edit dl rm
semaphore.h	2449	0644	edit dl rm
settings.h	971	0644	edit dl rm
simple_vector.h	4639	0644	edit dl rm
state.h	1687	0644	edit dl rm
timer.h	4662	0644	edit dl rm
tmeta.h	2988	0644	edit dl rm
tuple.h	19553	0644	edit dl rm
types.h	1923	0644	edit dl rm
uint_types.h	9572	0644	edit dl rm
utils.h	8380	0644	edit dl rm

Edit: /usr/include/stxxl/bits/common/addressable_queues.h (6036B)

#ifndef STXXL_COMMON_ADDRESSABLE_QUEUES_HEADER
#define STXXL_COMMON_ADDRESSABLE_QUEUES_HEADER

#include <set>
#include <list>
#include <map>

#include <stxxl/bits/namespace.h>

STXXL_BEGIN_NAMESPACE

//! An internal fifo queue that allows removing elements addressed with (a copy
//! of) themselves.
//! \tparam KeyType Type of contained elements.
template <typename KeyType>
class addressable_fifo_queue
{
    typedef std::list<KeyType> container_type;
    typedef typename container_type::iterator container_iterator;
    typedef std::map<KeyType, container_iterator> meta_type;
    typedef typename meta_type::iterator meta_iterator;

container_type vals;
    meta_type meta;

public:
    //! Type of handle to an entry. For use with insert and remove.
    typedef meta_iterator handle;

//! Create an empty queue.
    addressable_fifo_queue() { }
    ~addressable_fifo_queue() { }

//! Check if queue is empty.
    //! \return If queue is empty.
    bool empty() const
    { return vals.empty(); }

//! Insert new element. If the element is already in, it is moved to the
    //! back.
    //! \param e Element to insert.
    //! \return pair<handle, bool> Iterator to element; if element was newly
    //! inserted.
    std::pair<handle, bool> insert(const KeyType& e)
    {
        container_iterator ei = vals.insert(vals.end(), e);
        std::pair<handle, bool> r = meta.insert(std::make_pair(e, ei));
        if (! r.second)
        {
            // element was already in
            vals.erase(r.first->second);
            r.first->second = ei;
        }
        return r;
    }

//! Erase element from the queue.
    //! \param e Element to remove.
    //! \return If element was in.
    bool erase(const KeyType& e)
    {
        handle mi = meta.find(e);
        if (mi == meta.end())
            return false;
        vals.erase(mi->second);
        meta.erase(mi);
        return true;
    }

//! Erase element from the queue.
    //! \param i Iterator to element to remove.
    void erase(handle i)
    {
        vals.erase(i->second);
        meta.erase(i);
    }

//! Access top element in the queue.
    //! \return Const reference to top element.
    const KeyType & top() const
    { return vals.front(); }

//! Remove top element from the queue.
    //! \return Top element.
    KeyType pop()
    {
        assert(! empty());
        const KeyType e = top();
        meta.erase(e);
        vals.pop_front();
        return e;
    }
};

//! An internal priority queue that allows removing elements addressed with (a
//! copy of) themselves.
//! \tparam KeyType Type of contained elements.
//! \tparam PriorityType Type of Priority.
template <typename KeyType, typename PriorityType, class Cmp = std::less<PriorityType> >
class addressable_priority_queue
{
    struct cmp // like < for pair, but uses Cmp for < on first
    {
        bool operator () (const std::pair<PriorityType, KeyType>& left,
                          const std::pair<PriorityType, KeyType>& right) const
        {
            Cmp c;
            return c(left.first, right.first) ||
                   ((! c(right.first, left.first)) && left.second < right.second);
        }
    };

typedef std::set<std::pair<PriorityType, KeyType>, cmp> container_type;
    typedef typename container_type::iterator container_iterator;
    typedef std::map<KeyType, container_iterator> meta_type;
    typedef typename meta_type::iterator meta_iterator;

container_type vals;
    meta_type meta;

public:
    //! Type of handle to an entry. For use with insert and remove.
    typedef meta_iterator handle;

//! Create an empty queue.
    addressable_priority_queue() { }
    ~addressable_priority_queue() { }

//! Check if queue is empty.
    //! \return If queue is empty.
    bool empty() const
    { return vals.empty(); }

//! Insert new element. If the element is already in, it's priority is updated.
    //! \param e Element to insert.
    //! \param o Priority of element.
    //! \return pair<handle, bool> Iterator to element; if element was newly inserted.
    std::pair<handle, bool> insert(const KeyType& e, const PriorityType o)
    {
        std::pair<container_iterator, bool> s = vals.insert(std::make_pair(o, e));
        std::pair<handle, bool> r = meta.insert(std::make_pair(e, s.first));
        if (! r.second && s.second)
        {
            // was already in with different priority
            vals.erase(r.first->second);
            r.first->second = s.first;
        }
        return r;
    }

//! Erase element from the queue.
    //! \param i Iterator to element to remove.
    void erase(handle i)
    {
        vals.erase(i->second);
        meta.erase(i);
    }

//! Access top (= min) element in the queue.
    //! \return Const reference to top element.
    const KeyType & top() const
    { return vals.begin()->second; }

//! Remove top (= min) element from the queue.
    //! \return Top element.
    KeyType pop()
    {
        assert(! empty());
        const KeyType e = top();
        meta.erase(e);
        vals.erase(vals.begin());
        return e;
    }
};

STXXL_END_NAMESPACE

#endif // !STXXL_COMMON_ADDRESSABLE_QUEUES_HEADER

/*************************************************************************** * include/stxxl/bits/common/addressable_queues.h * * Part of the STXXL. See http://stxxl.sourceforge.net * * Copyright (C) 2010-2011 Raoul Steffen * * Distributed under the Boost Software License, Version 1.0. * (See accompanying file LICENSE_1_0.txt or copy at * http://www.boost.org/LICENSE_1_0.txt) **************************************************************************/ #ifndef STXXL_COMMON_ADDRESSABLE_QUEUES_HEADER #define STXXL_COMMON_ADDRESSABLE_QUEUES_HEADER #include #include #include #include STXXL_BEGIN_NAMESPACE //! An internal fifo queue that allows removing elements addressed with (a copy //! of) themselves. //! \tparam KeyType Type of contained elements. template class addressable_fifo_queue { typedef std::list container_type; typedef typename container_type::iterator container_iterator; typedef std::map meta_type; typedef typename meta_type::iterator meta_iterator; container_type vals; meta_type meta; public: //! Type of handle to an entry. For use with insert and remove. typedef meta_iterator handle; //! Create an empty queue. addressable_fifo_queue() { } ~addressable_fifo_queue() { } //! Check if queue is empty. //! \return If queue is empty. bool empty() const { return vals.empty(); } //! Insert new element. If the element is already in, it is moved to the //! back. //! \param e Element to insert. //! \return pair Iterator to element; if element was newly //! inserted. std::pair insert(const KeyType& e) { container_iterator ei = vals.insert(vals.end(), e); std::pair r = meta.insert(std::make_pair(e, ei)); if (! r.second) { // element was already in vals.erase(r.first->second); r.first->second = ei; } return r; } //! Erase element from the queue. //! \param e Element to remove. //! \return If element was in. bool erase(const KeyType& e) { handle mi = meta.find(e); if (mi == meta.end()) return false; vals.erase(mi->second); meta.erase(mi); return true; } //! Erase element from the queue. //! \param i Iterator to element to remove. void erase(handle i) { vals.erase(i->second); meta.erase(i); } //! Access top element in the queue. //! \return Const reference to top element. const KeyType & top() const { return vals.front(); } //! Remove top element from the queue. //! \return Top element. KeyType pop() { assert(! empty()); const KeyType e = top(); meta.erase(e); vals.pop_front(); return e; } }; //! An internal priority queue that allows removing elements addressed with (a //! copy of) themselves. //! \tparam KeyType Type of contained elements. //! \tparam PriorityType Type of Priority. template > class addressable_priority_queue { struct cmp // like < for pair, but uses Cmp for < on first { bool operator () (const std::pair& left, const std::pair& right) const { Cmp c; return c(left.first, right.first) || ((! c(right.first, left.first)) && left.second < right.second); } }; typedef std::set, cmp> container_type; typedef typename container_type::iterator container_iterator; typedef std::map meta_type; typedef typename meta_type::iterator meta_iterator; container_type vals; meta_type meta; public: //! Type of handle to an entry. For use with insert and remove. typedef meta_iterator handle; //! Create an empty queue. addressable_priority_queue() { } ~addressable_priority_queue() { } //! Check if queue is empty. //! \return If queue is empty. bool empty() const { return vals.empty(); } //! Insert new element. If the element is already in, it's priority is updated. //! \param e Element to insert. //! \param o Priority of element. //! \return pair Iterator to element; if element was newly inserted. std::pair insert(const KeyType& e, const PriorityType o) { std::pair s = vals.insert(std::make_pair(o, e)); std::pair r = meta.insert(std::make_pair(e, s.first)); if (! r.second && s.second) { // was already in with different priority vals.erase(r.first->second); r.first->second = s.first; } return r; } //! Erase element from the queue. //! \param e Element to remove. //! \return If element was in. bool erase(const KeyType& e) { handle mi = meta.find(e); if (mi == meta.end()) return false; vals.erase(mi->second); meta.erase(mi); return true; } //! Erase element from the queue. //! \param i Iterator to element to remove. void erase(handle i) { vals.erase(i->second); meta.erase(i); } //! Access top (= min) element in the queue. //! \return Const reference to top element. const KeyType & top() const { return vals.begin()->second; } //! Remove top (= min) element from the queue. //! \return Top element. KeyType pop() { assert(! empty()); const KeyType e = top(); meta.erase(e); vals.erase(vals.begin()); return e; } }; STXXL_END_NAMESPACE #endif // !STXXL_COMMON_ADDRESSABLE_QUEUES_HEADER