concurrent_priority_queue.h

/*
    Copyright 2005-2011 Intel Corporation.  All Rights Reserved.

    The source code contained or described herein and all documents related
    to the source code ("Material") are owned by Intel Corporation or its
    suppliers or licensors.  Title to the Material remains with Intel
    Corporation or its suppliers and licensors.  The Material is protected
    by worldwide copyright laws and treaty provisions.  No part of the
    Material may be used, copied, reproduced, modified, published, uploaded,
    posted, transmitted, distributed, or disclosed in any way without
    Intel's prior express written permission.

    No license under any patent, copyright, trade secret or other
    intellectual property right is granted to or conferred upon you by
    disclosure or delivery of the Materials, either expressly, by
    implication, inducement, estoppel or otherwise.  Any license under such
    intellectual property rights must be express and approved by Intel in
    writing.
*/

#ifndef __TBB_concurrent_priority_queue_H
#define __TBB_concurrent_priority_queue_H

#include "atomic.h"
#include "cache_aligned_allocator.h"
#include "tbb_exception.h"
#include "tbb_stddef.h"
#include "tbb_profiling.h"
#include "internal/_aggregator_impl.h"
#include <vector>
#include <iterator>
#include <functional>

namespace tbb {
namespace interface5 {

using namespace tbb::internal;

template <typename T, typename Compare=std::less<T>, typename A=cache_aligned_allocator<T> >
class concurrent_priority_queue {
 public:
    typedef T value_type;

    typedef T& reference;

    typedef const T& const_reference;

    typedef size_t size_type;

    typedef ptrdiff_t difference_type;

    typedef A allocator_type;

    explicit concurrent_priority_queue(const allocator_type& a = allocator_type()) : mark(0), my_size(0), data(a)
    {
        my_aggregator.initialize_handler(my_functor_t(this));
    }

    explicit concurrent_priority_queue(size_type init_capacity, const allocator_type& a = allocator_type()) :
        mark(0), my_size(0), data(a)
    {
        data.reserve(init_capacity);
        my_aggregator.initialize_handler(my_functor_t(this));
    }

    template<typename InputIterator>
    concurrent_priority_queue(InputIterator begin, InputIterator end, const allocator_type& a = allocator_type()) :
        data(begin, end, a)
    {
        mark = 0;
        my_aggregator.initialize_handler(my_functor_t(this));
        heapify();
        my_size = data.size();
    }


    explicit concurrent_priority_queue(const concurrent_priority_queue& src) : mark(src.mark),
        my_size(src.my_size), data(src.data.begin(), src.data.end(), src.data.get_allocator())
    {
        my_aggregator.initialize_handler(my_functor_t(this));
        heapify();
    }


    concurrent_priority_queue(const concurrent_priority_queue& src, const allocator_type& a) : mark(src.mark),
        my_size(src.my_size), data(src.data.begin(), src.data.end(), a)
    {
        my_aggregator.initialize_handler(my_functor_t(this));
        heapify();
    }


    concurrent_priority_queue& operator=(const concurrent_priority_queue& src) {
        if (this != &src) {
            std::vector<value_type, allocator_type>(src.data.begin(), src.data.end(), src.data.get_allocator()).swap(data);
            mark = src.mark;
            my_size = src.my_size;
        }
        return *this;
    }


    bool empty() const { return size()==0; }


    size_type size() const { return __TBB_load_with_acquire(my_size); }


    void push(const_reference elem) {
        cpq_operation op_data(elem, PUSH_OP);
        my_aggregator.execute(&op_data);
        if (op_data.status == FAILED) // exception thrown
            throw_exception(eid_bad_alloc);
    }


    bool try_pop(reference elem) {
        cpq_operation op_data(POP_OP);
        op_data.elem = &elem;
        my_aggregator.execute(&op_data);
        return op_data.status==SUCCEEDED;
    }


    void clear() {
        data.clear();
        mark = 0;
        my_size = 0;
    }


    void swap(concurrent_priority_queue& q) {
        data.swap(q.data);
        std::swap(mark, q.mark);
        std::swap(my_size, q.my_size);
    }

    allocator_type get_allocator() const { return data.get_allocator(); }

 private:
    enum operation_type {INVALID_OP, PUSH_OP, POP_OP};
    enum operation_status { WAIT=0, SUCCEEDED, FAILED };

    class cpq_operation : public aggregated_operation<cpq_operation> {
     public:
        operation_type type;
        union {
            value_type *elem;
            size_type sz;
        };
        cpq_operation(const_reference e, operation_type t) :
            type(t), elem(const_cast<value_type*>(&e)) {}
        cpq_operation(operation_type t) : type(t) {}
    };

    class my_functor_t {
        concurrent_priority_queue<T, Compare, A> *cpq;
     public:
        my_functor_t() {}
        my_functor_t(concurrent_priority_queue<T, Compare, A> *cpq_) : cpq(cpq_) {}
        void operator()(cpq_operation* op_list) {
            cpq->handle_operations(op_list);
        }
    };

    aggregator< my_functor_t, cpq_operation> my_aggregator;
    char padding1[NFS_MaxLineSize - sizeof(aggregator< my_functor_t, cpq_operation >)];
    size_type mark;
    __TBB_atomic size_type my_size;
    Compare compare;
    char padding2[NFS_MaxLineSize - (2*sizeof(size_type)) - sizeof(Compare)];

    std::vector<value_type, allocator_type> data;

    void handle_operations(cpq_operation *op_list) {
        cpq_operation *tmp, *pop_list=NULL;

        __TBB_ASSERT(mark == data.size(), NULL);

        // first pass processes all constant time operations: pushes,
        // tops, some pops. Also reserve.
        while (op_list) {
            // ITT note: &(op_list->status) tag is used to cover accesses to op_list
            // node. This thread is going to handle the operation, and so will acquire it
            // and perform the associated operation w/o triggering a race condition; the
            // thread that created the operation is waiting on the status field, so when
            // this thread is done with the operation, it will perform a
            // store_with_release to give control back to the waiting thread in
            // aggregator::insert_operation.
            call_itt_notify(acquired, &(op_list->status));
            __TBB_ASSERT(op_list->type != INVALID_OP, NULL);
            tmp = op_list;
            op_list = itt_hide_load_word(op_list->next);
            if (tmp->type == PUSH_OP) {
                __TBB_TRY {
                    data.push_back(*(tmp->elem));
                    __TBB_store_with_release(my_size, my_size+1);
                    itt_store_word_with_release(tmp->status, uintptr_t(SUCCEEDED));
                } __TBB_CATCH(...) {
                    itt_store_word_with_release(tmp->status, uintptr_t(FAILED));
                }
            }
            else { // tmp->type == POP_OP
                __TBB_ASSERT(tmp->type == POP_OP, NULL);
                if (mark < data.size() &&
                    compare(data[0], data[data.size()-1])) {
                    // there are newly pushed elems and the last one
                    // is higher than top
                    *(tmp->elem) = data[data.size()-1]; // copy the data
                    __TBB_store_with_release(my_size, my_size-1);
                    itt_store_word_with_release(tmp->status, uintptr_t(SUCCEEDED));
                    data.pop_back();
                    __TBB_ASSERT(mark<=data.size(), NULL);
                }
                else { // no convenient item to pop; postpone
                    itt_hide_store_word(tmp->next, pop_list);
                    pop_list = tmp;
                }
            }
        }

        // second pass processes pop operations
        while (pop_list) {
            tmp = pop_list;
            pop_list = itt_hide_load_word(pop_list->next);
            __TBB_ASSERT(tmp->type == POP_OP, NULL);
            if (data.empty()) {
                itt_store_word_with_release(tmp->status, uintptr_t(FAILED));
            }
            else {
                __TBB_ASSERT(mark<=data.size(), NULL);
                if (mark < data.size() &&
                    compare(data[0], data[data.size()-1])) {
                    // there are newly pushed elems and the last one is
                    // higher than top
                    *(tmp->elem) = data[data.size()-1]; // copy the data
                    __TBB_store_with_release(my_size, my_size-1);
                    itt_store_word_with_release(tmp->status, uintptr_t(SUCCEEDED));
                    data.pop_back();
                }
                else { // extract top and push last element down heap
                    *(tmp->elem) = data[0]; // copy the data
                    __TBB_store_with_release(my_size, my_size-1);
                    itt_store_word_with_release(tmp->status, uintptr_t(SUCCEEDED));
                    reheap();
                }
            }
        }

        // heapify any leftover pushed elements before doing the next
        // batch of operations
        if (mark<data.size()) heapify();
        __TBB_ASSERT(mark == data.size(), NULL);
    }

    void heapify() {
        if (!mark && data.size()>0) mark = 1;
        for (; mark<data.size(); ++mark) {
            // for each unheapified element under size
            size_type cur_pos = mark;
            value_type to_place = data[mark];
            do { // push to_place up the heap
                size_type parent = (cur_pos-1)>>1;
                if (!compare(data[parent], to_place)) break;
                data[cur_pos] = data[parent];
                cur_pos = parent;
            } while( cur_pos );
            data[cur_pos] = to_place;
        }
    }


    void reheap() {
        size_type cur_pos=0, child=1;

        while (child < mark) {
            size_type target = child;
            if (child+1 < mark && compare(data[child], data[child+1]))
                ++target;
            // target now has the higher priority child
            if (compare(data[target], data[data.size()-1])) break;
            data[cur_pos] = data[target];
            cur_pos = target;
            child = (cur_pos<<1)+1;
        }
        data[cur_pos] = data[data.size()-1];
        data.pop_back();
        if (mark > data.size()) mark = data.size();
    }
};

} // namespace interface5

using interface5::concurrent_priority_queue;

} // namespace tbb

#endif /* __TBB_concurrent_priority_queue_H */

---

Copyright © 2005-2011 Intel Corporation. All Rights Reserved.

Intel, Pentium, Intel Xeon, Itanium, Intel XScale and VTune are registered trademarks or trademarks of Intel Corporation or its subsidiaries in the United States and other countries.

* Other names and brands may be claimed as the property of others.