16 #ifndef STXXL_PRIORITY_QUEUE_HEADER
17 #define STXXL_PRIORITY_QUEUE_HEADER
23 #include <stxxl/bits/mng/mng.h>
24 #include <stxxl/bits/mng/prefetch_pool.h>
25 #include <stxxl/bits/mng/write_pool.h>
26 #include <stxxl/bits/common/tmeta.h>
29 __STXXL_BEGIN_NAMESPACE
37 namespace priority_queue_local
45 template <
typename _Tp,
typename _Sequence = std::vector<_Tp>,
46 typename _Compare = std::less<
typename _Sequence::value_type> >
50 typedef typename _Sequence::value_type _Sequence_value_type;
53 typedef typename _Sequence::value_type value_type;
54 typedef typename _Sequence::reference reference;
55 typedef typename _Sequence::const_reference const_reference;
56 typedef typename _Sequence::size_type size_type;
57 typedef _Sequence container_type;
109 std::push_heap(c.begin(), c.begin() + N, comp);
126 std::pop_heap(c.begin(), c.begin() + N, comp);
135 std::sort(c.begin(), c.begin() + N, comp);
136 std::reverse_copy(c.begin(), c.begin() + N, target);
158 template <
class InputIterator,
class OutputIterator,
class Cmp_>
160 InputIterator & from0,
161 InputIterator & from1,
162 OutputIterator to, unsigned_type sz, Cmp_ cmp)
164 OutputIterator done = to + sz;
168 if (cmp(*from0, *from1))
188 template <
class InputIterator,
class OutputIterator,
class Cmp_>
189 void merge3_iterator(
190 InputIterator & from0,
191 InputIterator & from1,
192 InputIterator & from2,
193 OutputIterator to, unsigned_type sz, Cmp_ cmp)
195 OutputIterator done = to + sz;
197 if (cmp(*from1, *from0)) {
198 if (cmp(*from2, *from1)) {
202 if (cmp(*from0, *from2)) {
210 if (cmp(*from2, *from1)) {
211 if (cmp(*from2, *from0)) {
222 #define Merge3Case(a, b, c) \
229 if (cmp(*from ## b, *from ## a)) \
230 goto s ## a ## b ## c;\
231 if (cmp(*from ## c, *from ## a)) \
232 goto s ## b ## a ## c;\
233 goto s ## b ## c ## a;
254 template <
class InputIterator,
class OutputIterator,
class Cmp_>
255 void merge4_iterator(
256 InputIterator & from0,
257 InputIterator & from1,
258 InputIterator & from2,
259 InputIterator & from3,
260 OutputIterator to, unsigned_type sz, Cmp_ cmp)
262 OutputIterator done = to + sz;
264 #define StartMerge4(a, b, c, d) \
265 if ((!cmp(*from ## a, *from ## b)) && (!cmp(*from ## b, *from ## c)) && (!cmp(*from ## c, *from ## d))) \
266 goto s ## a ## b ## c ## d;
273 StartMerge4(0, 1, 2, 3);
274 StartMerge4(1, 2, 3, 0);
275 StartMerge4(2, 3, 0, 1);
276 StartMerge4(3, 0, 1, 2);
278 StartMerge4(0, 3, 1, 2);
279 StartMerge4(3, 1, 2, 0);
280 StartMerge4(1, 2, 0, 3);
281 StartMerge4(2, 0, 3, 1);
283 StartMerge4(0, 2, 3, 1);
284 StartMerge4(2, 3, 1, 0);
285 StartMerge4(3, 1, 0, 2);
286 StartMerge4(1, 0, 2, 3);
288 StartMerge4(2, 0, 1, 3);
289 StartMerge4(0, 1, 3, 2);
290 StartMerge4(1, 3, 2, 0);
291 StartMerge4(3, 2, 0, 1);
293 StartMerge4(3, 0, 2, 1);
294 StartMerge4(0, 2, 1, 3);
295 StartMerge4(2, 1, 3, 0);
296 StartMerge4(1, 3, 0, 2);
298 StartMerge4(1, 0, 3, 2);
299 StartMerge4(0, 3, 2, 1);
300 StartMerge4(3, 2, 1, 0);
301 StartMerge4(2, 1, 0, 3);
303 #define Merge4Case(a, b, c, d) \
304 s ## a ## b ## c ## d : \
310 if (cmp(*from ## c, *from ## a)) \
312 if (cmp(*from ## b, *from ## a)) \
313 goto s ## a ## b ## c ## d;\
315 goto s ## b ## a ## c ## d;\
319 if (cmp(*from ## d, *from ## a)) \
320 goto s ## b ## c ## a ## d;\
322 goto s ## b ## c ## d ## a;\
325 Merge4Case(0, 1, 2, 3);
326 Merge4Case(1, 2, 3, 0);
327 Merge4Case(2, 3, 0, 1);
328 Merge4Case(3, 0, 1, 2);
330 Merge4Case(0, 3, 1, 2);
331 Merge4Case(3, 1, 2, 0);
332 Merge4Case(1, 2, 0, 3);
333 Merge4Case(2, 0, 3, 1);
335 Merge4Case(0, 2, 3, 1);
336 Merge4Case(2, 3, 1, 0);
337 Merge4Case(3, 1, 0, 2);
338 Merge4Case(1, 0, 2, 3);
340 Merge4Case(2, 0, 1, 3);
341 Merge4Case(0, 1, 3, 2);
342 Merge4Case(1, 3, 2, 0);
343 Merge4Case(3, 2, 0, 1);
345 Merge4Case(3, 0, 2, 1);
346 Merge4Case(0, 2, 1, 3);
347 Merge4Case(2, 1, 3, 0);
348 Merge4Case(1, 3, 0, 2);
350 Merge4Case(1, 0, 3, 2);
351 Merge4Case(0, 3, 2, 1);
352 Merge4Case(3, 2, 1, 0);
353 Merge4Case(2, 1, 0, 3);
365 template <
typename Tp_,
unsigned_type max_size_>
368 typedef Tp_ value_type;
369 typedef unsigned_type size_type;
370 enum { max_size = max_size_ };
373 value_type array[max_size];
378 void push(
const value_type & x)
380 assert(size_ < max_size);
384 const value_type & top()
const
387 return array[size_ - 1];
401 size_type size()
const
417 template <
class BlockType_,
420 class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>
424 typedef stxxl::uint64 size_type;
425 typedef BlockType_ block_type;
426 typedef typename block_type::bid_type bid_type;
427 typedef typename block_type::value_type value_type;
428 typedef Cmp_ comparator_type;
429 typedef AllocStr_ alloc_strategy;
430 typedef value_type Element;
434 enum { arity = Arity_, KNKMAX = 1UL << (LOG2<Arity_>::ceil) };
438 return reinterpret_cast<block_type *
>(arg);
444 bool is_sentinel(
const Element & a)
const
446 return !(cmp(cmp.min_value(), a));
449 bool not_sentinel(
const Element & a)
const
451 return cmp(cmp.min_value(), a);
454 struct sequence_state :
private noncopyable
456 unsigned_type current;
458 std::list<bid_type> * bids;
464 const value_type & operator * ()
const
466 return (*block)[current];
469 sequence_state() : bids(NULL), allocated(
false)
474 STXXL_VERBOSE2(
"ext_merger sequence_state::~sequence_state()");
486 (*block)[0] = cmp.min_value();
489 bool is_sentinel(
const Element & a)
const
491 return !(cmp(cmp.min_value(), a));
494 bool not_sentinel(
const Element & a)
const
496 return cmp(cmp.min_value(), a);
499 void swap(sequence_state & obj)
503 std::swap(current, obj.current);
504 std::swap(block, obj.block);
505 std::swap(bids, obj.bids);
506 assert(merger == obj.merger);
507 std::swap(allocated, obj.allocated);
511 sequence_state & operator ++ ()
513 assert(not_sentinel((*block)[current]));
514 assert(current < block->size);
518 if (current == block->size)
520 STXXL_VERBOSE2(
"ext_merger sequence_state operator++ crossing block border ");
522 assert(bids != NULL);
525 STXXL_VERBOSE2(
"ext_merger sequence_state operator++ it was the last block in the sequence ");
532 STXXL_VERBOSE2(
"ext_merger sequence_state operator++ there is another block ");
533 bid_type bid = bids->front();
535 if (!(bids->empty()))
537 STXXL_VERBOSE2(
"ext_merger sequence_state operator++ one more block exists in a sequence: " <<
538 "flushing this block in write cache (if not written yet) and giving hint to prefetcher");
539 bid_type next_bid = bids->front();
542 merger->p_pool->hint(next_bid, *(merger->w_pool));
544 merger->p_pool->read(block, bid)->wait();
545 STXXL_VERBOSE2(
"first element of read block " << bid <<
" " << *(block->begin()) <<
" cached in " << block);
546 block_manager::get_instance()->delete_block(bid);
579 sequence_state states[KNKMAX];
588 size_(0), logK(0), k(1), p_pool(0), w_pool(0)
595 size_(0), logK(0), k(1),
604 STXXL_VERBOSE1(
"ext_merger::~ext_merger()");
605 for (unsigned_type i = 0; i < arity; ++i)
607 delete states[i].block;
621 STXXL_VERBOSE2(
"ext_merger::init()");
622 assert(!cmp(cmp.min_value(), cmp.min_value()));
624 sentinel_block[0] = cmp.min_value();
626 for (unsigned_type i = 0; i < KNKMAX; ++i)
628 states[i].merger =
this;
630 states[i].block =
new block_type;
632 states[i].block = convert_block_pointer(&(sentinel_block));
634 states[i].make_inf();
638 free_segments.push(0);
641 assert(is_sentinel(*states[entry[0].index]));
645 void rebuildLoserTree()
647 unsigned_type winner = initWinner(1);
648 entry[0].index = winner;
649 entry[0].key = *(states[winner]);
658 unsigned_type initWinner(unsigned_type root)
663 unsigned_type left = initWinner(2 * root);
664 unsigned_type right = initWinner(2 * root + 1);
665 Element lk = *(states[left]);
666 Element rk = *(states[right]);
667 if (!(cmp(lk, rk))) {
668 entry[root].index = right;
669 entry[root].key = rk;
672 entry[root].index = left;
673 entry[root].key = lk;
684 void update_on_insert(
686 const Element & newKey,
687 unsigned_type newIndex,
689 unsigned_type * winnerIndex,
690 unsigned_type * mask)
693 *mask = 1 << (logK - 1);
694 *winnerKey = entry[0].key;
695 *winnerIndex = entry[0].index;
696 if (cmp(entry[node].key, newKey))
698 entry[node].key = newKey;
699 entry[node].index = newIndex;
702 update_on_insert(node >> 1, newKey, newIndex, winnerKey, winnerIndex, mask);
703 Element loserKey = entry[node].key;
704 unsigned_type loserIndex = entry[node].index;
705 if ((*winnerIndex & *mask) != (newIndex & *mask)) {
706 if (cmp(loserKey, newKey)) {
707 if (cmp(*winnerKey, newKey)) {
708 entry[node].key = *winnerKey;
709 entry[node].index = *winnerIndex;
711 entry[node].key = newKey;
712 entry[node].index = newIndex;
715 *winnerKey = loserKey;
716 *winnerIndex = loserIndex;
732 STXXL_VERBOSE1(
"ext_merger::doubleK (before) k=" << k <<
" logK=" << logK <<
" KNKMAX=" << KNKMAX <<
" arity=" << arity <<
" #free=" << free_segments.size());
735 assert(free_segments.empty());
739 for (unsigned_type i = 2 * k - 1; i >= k; i--)
741 states[i].make_inf();
743 free_segments.push(i);
750 STXXL_VERBOSE1(
"ext_merger::doubleK (after) k=" << k <<
" logK=" << logK <<
" KNKMAX=" << KNKMAX <<
" arity=" << arity <<
" #free=" << free_segments.size());
751 assert(!free_segments.empty());
761 STXXL_VERBOSE1(
"ext_merger::compactTree (before) k=" << k <<
" logK=" << logK <<
" #free=" << free_segments.size());
766 unsigned_type to = 0;
767 for (unsigned_type from = 0; from < k; from++)
769 if (!is_segment_empty(from))
771 assert(is_segment_allocated(from));
773 assert(!is_segment_allocated(to));
774 states[to].swap(states[from]);
781 while (k > 1 && to <= (k / 2)) {
787 free_segments.clear();
788 for ( ; to < k; to++) {
789 assert(!is_segment_allocated(to));
790 states[to].make_inf();
792 free_segments.push(to);
795 STXXL_VERBOSE1(
"ext_merger::compactTree (after) k=" << k <<
" logK=" << logK <<
" #free=" << free_segments.size());
806 std::swap(cmp, obj.cmp);
807 std::swap(free_segments, obj.free_segments);
808 std::swap(size_, obj.size_);
809 std::swap(logK, obj.logK);
811 swap_1D_arrays(entry, obj.entry, KNKMAX);
812 swap_1D_arrays(states, obj.states, KNKMAX);
820 unsigned_type mem_cons()
const
822 return (arity * block_type::raw_size);
830 template <
class OutputIterator>
831 void multi_merge(OutputIterator begin, OutputIterator end)
833 size_type length = end - begin;
835 STXXL_VERBOSE1(
"ext_merger::multi_merge from " << k <<
" sequence(s), length = " << length);
841 assert(length <= size_);
845 for (unsigned_type i = 0; i < k; ++i)
847 if (states[i].bids != NULL && !states[i].bids->empty())
848 p_pool->
hint(states[i].bids->front(), *w_pool);
854 assert(entry[0].index == 0);
855 assert(free_segments.empty());
858 for (size_type i = 0; i < length; ++i, ++(states[0]), ++begin)
859 *begin = *(states[0]);
861 entry[0].key = **states;
862 if (is_segment_empty(0))
863 deallocate_segment(0);
868 merge_iterator(states[0], states[1], begin, length, cmp);
870 if (is_segment_empty(0) && is_segment_allocated(0))
871 deallocate_segment(0);
873 if (is_segment_empty(1) && is_segment_allocated(1))
874 deallocate_segment(1);
879 if (is_segment_empty(3))
880 merge3_iterator(states[0], states[1], states[2], begin, length, cmp);
882 merge4_iterator(states[0], states[1], states[2], states[3], begin, length, cmp);
884 if (is_segment_empty(0) && is_segment_allocated(0))
885 deallocate_segment(0);
887 if (is_segment_empty(1) && is_segment_allocated(1))
888 deallocate_segment(1);
890 if (is_segment_empty(2) && is_segment_allocated(2))
891 deallocate_segment(2);
893 if (is_segment_empty(3) && is_segment_allocated(3))
894 deallocate_segment(3);
897 case 3: multi_merge_f<OutputIterator, 3>(begin, end);
899 case 4: multi_merge_f<OutputIterator, 4>(begin, end);
901 case 5: multi_merge_f<OutputIterator, 5>(begin, end);
903 case 6: multi_merge_f<OutputIterator, 6>(begin, end);
905 case 7: multi_merge_f<OutputIterator, 7>(begin, end);
907 case 8: multi_merge_f<OutputIterator, 8>(begin, end);
909 case 9: multi_merge_f<OutputIterator, 9>(begin, end);
911 case 10: multi_merge_f<OutputIterator, 10>(begin, end);
913 default: multi_merge_k(begin, end);
922 const unsigned_type num_segments_used = std::min<unsigned_type>(arity, k) - free_segments.size();
923 const unsigned_type num_segments_trigger = k - (3 * k / 5);
929 STXXL_VERBOSE3(
"ext_merger compact? k=" << k <<
" #used=" << num_segments_used
930 <<
" <= #trigger=" << num_segments_trigger <<
" ==> "
931 << ((k > 1 && num_segments_used <= num_segments_trigger) ?
"yes" :
"no ")
933 << ((k == 4 && !free_segments.empty() && !is_segment_empty(3)) ?
"yes" :
"no ")
934 <<
" #free=" << free_segments.size());
935 if (k > 1 && ((num_segments_used <= num_segments_trigger) ||
936 (k == 4 && !free_segments.empty() && !is_segment_empty(3))))
945 template <
class OutputIterator>
946 void multi_merge_k(OutputIterator begin, OutputIterator end)
950 unsigned_type currentIndex;
951 unsigned_type kReg = k;
952 OutputIterator done = end;
953 OutputIterator to = begin;
954 unsigned_type winnerIndex = entry[0].index;
955 Element winnerKey = entry[0].key;
960 *to = *(states[winnerIndex]);
963 ++(states[winnerIndex]);
965 winnerKey = *(states[winnerIndex]);
968 if (is_sentinel(winnerKey))
969 deallocate_segment(winnerIndex);
973 for (unsigned_type i = (winnerIndex + kReg) >> 1; i > 0; i >>= 1) {
974 currentPos = entry + i;
975 currentKey = currentPos->key;
976 if (cmp(winnerKey, currentKey)) {
977 currentIndex = currentPos->index;
978 currentPos->key = winnerKey;
979 currentPos->index = winnerIndex;
980 winnerKey = currentKey;
981 winnerIndex = currentIndex;
987 entry[0].index = winnerIndex;
988 entry[0].key = winnerKey;
991 template <
class OutputIterator,
unsigned LogK>
992 void multi_merge_f(OutputIterator begin, OutputIterator end)
994 OutputIterator done = end;
995 OutputIterator to = begin;
996 unsigned_type winnerIndex = entry[0].index;
997 Entry * regEntry = entry;
998 sequence_state * regStates = states;
999 Element winnerKey = entry[0].key;
1001 assert(logK >= LogK);
1005 *to = *(regStates[winnerIndex]);
1008 ++(regStates[winnerIndex]);
1010 winnerKey = *(regStates[winnerIndex]);
1014 if (is_sentinel(winnerKey))
1015 deallocate_segment(winnerIndex);
1021 #define TreeStep(L) \
1022 if (1 << LogK >= 1 << L) { \
1023 Entry * pos ## L = regEntry + ((winnerIndex + (1 << LogK)) >> (((int(LogK - L) + 1) >= 0) ? ((LogK - L) + 1) : 0)); \
1024 Element key ## L = pos ## L->key; \
1025 if (cmp(winnerKey, key ## L)) { \
1026 unsigned_type index ## L = pos ## L->index; \
1027 pos ## L->key = winnerKey; \
1028 pos ## L->index = winnerIndex; \
1029 winnerKey = key ## L; \
1030 winnerIndex = index ## L; \
1045 regEntry[0].index = winnerIndex;
1046 regEntry[0].key = winnerKey;
1050 bool spaceIsAvailable()
const
1052 return k < arity || !free_segments.empty();
1058 template <
class Merger>
1059 void insert_segment(Merger & another_merger, size_type segment_size)
1061 STXXL_VERBOSE1(
"ext_merger::insert_segment(merger,...)" <<
this);
1063 if (segment_size > 0)
1066 if (free_segments.empty()) {
1069 assert(!free_segments.empty());
1070 unsigned_type free_slot = free_segments.top();
1071 free_segments.pop();
1075 assert(segment_size);
1076 unsigned_type nblocks = segment_size / block_type::size;
1078 STXXL_VERBOSE1(
"ext_merger::insert_segment nblocks=" << nblocks);
1081 STXXL_VERBOSE1(
"ext_merger::insert_segment(merger,...) WARNING: inserting a segment with " <<
1082 nblocks <<
" blocks");
1083 STXXL_VERBOSE1(
"THIS IS INEFFICIENT: TRY TO CHANGE PRIORITY QUEUE PARAMETERS");
1085 unsigned_type first_size = segment_size % block_type::size;
1086 if (first_size == 0)
1088 first_size = block_type::size;
1092 std::list<bid_type> * bids =
new std::list<bid_type>(nblocks);
1093 bm->
new_blocks(alloc_strategy(), bids->begin(), bids->end());
1094 block_type * first_block =
new block_type;
1096 another_merger.multi_merge(
1097 first_block->begin() + (block_type::size - first_size),
1098 first_block->end());
1100 STXXL_VERBOSE1(
"last element of first block " << *(first_block->end() - 1));
1101 assert(!cmp(*(first_block->begin() + (block_type::size - first_size)), *(first_block->end() - 1)));
1103 assert(w_pool->
size() > 0);
1105 for (
typename std::list<bid_type>::iterator curbid = bids->begin(); curbid != bids->end(); ++curbid)
1107 block_type * b = w_pool->
steal();
1108 another_merger.multi_merge(b->begin(), b->end());
1109 STXXL_VERBOSE1(
"first element of following block " << *curbid <<
" " << *(b->begin()));
1110 STXXL_VERBOSE1(
"last element of following block " << *curbid <<
" " << *(b->end() - 1));
1111 assert(!cmp(*(b->begin()), *(b->end() - 1)));
1112 w_pool->
write(b, *curbid);
1113 STXXL_VERBOSE1(
"written to block " << *curbid <<
" cached in " << b);
1116 insert_segment(bids, first_block, first_size, free_slot);
1118 size_ += segment_size;
1122 unsigned_type dummyIndex;
1123 unsigned_type dummyMask;
1124 update_on_insert((free_slot + k) >> 1, *(states[free_slot]), free_slot,
1125 &dummyKey, &dummyIndex, &dummyMask);
1128 STXXL_VERBOSE1(
"Merged segment with zero size.");
1132 size_type size()
const {
return size_; }
1137 void insert_segment(std::list<bid_type> * bidlist, block_type * first_block,
1138 unsigned_type first_size, unsigned_type slot)
1140 STXXL_VERBOSE1(
"ext_merger::insert_segment(bidlist,...) " <<
this <<
" " << bidlist->size() <<
" " << slot);
1141 assert(!is_segment_allocated(slot));
1142 assert(first_size > 0);
1144 sequence_state & new_sequence = states[slot];
1145 new_sequence.current = block_type::size - first_size;
1146 std::swap(new_sequence.block, first_block);
1148 std::swap(new_sequence.bids, bidlist);
1151 assert(bidlist->empty());
1154 new_sequence.allocated =
true;
1155 assert(is_segment_allocated(slot));
1159 void deallocate_segment(unsigned_type slot)
1161 STXXL_VERBOSE1(
"ext_merger::deallocate_segment() deleting segment " << slot <<
" allocated=" <<
int(is_segment_allocated(slot)));
1162 assert(is_segment_allocated(slot));
1163 states[slot].allocated =
false;
1164 states[slot].make_inf();
1167 free_segments.push(slot);
1171 bool is_segment_empty(unsigned_type slot)
const
1173 return is_sentinel(*(states[slot]));
1178 bool is_segment_allocated(unsigned_type slot)
const
1180 return states[slot].allocated;
1191 template <
class ValTp_,
class Cmp_,
unsigned KNKMAX>
1195 typedef ValTp_ value_type;
1196 typedef Cmp_ comparator_type;
1197 typedef value_type Element;
1203 unsigned_type index;
1206 comparator_type cmp;
1210 unsigned_type size_;
1218 Entry entry[KNKMAX];
1223 Element * current[KNKMAX];
1224 Element * segment[KNKMAX];
1225 unsigned_type segment_size[KNKMAX];
1227 unsigned_type mem_cons_;
1230 unsigned_type initWinner(unsigned_type root);
1231 void update_on_insert(unsigned_type node,
const Element & newKey, unsigned_type newIndex,
1232 Element * winnerKey, unsigned_type * winnerIndex, unsigned_type * mask);
1233 void deallocate_segment(unsigned_type slot);
1236 void rebuildLoserTree();
1237 bool is_segment_empty(unsigned_type slot);
1238 void multi_merge_k(Element * to, unsigned_type length);
1240 template <
unsigned LogK>
1241 void multi_merge_f(Element * to, unsigned_type length)
1246 Element * done = to + length;
1247 Entry * regEntry = entry;
1248 Element ** regStates = current;
1249 unsigned_type winnerIndex = regEntry[0].index;
1250 Element winnerKey = regEntry[0].key;
1251 Element * winnerPos;
1254 assert(logK >= LogK);
1257 winnerPos = regStates[winnerIndex];
1264 regStates[winnerIndex] = winnerPos;
1265 winnerKey = *winnerPos;
1268 if (is_sentinel(winnerKey))
1270 deallocate_segment(winnerIndex);
1275 #define TreeStep(L) \
1276 if (1 << LogK >= 1 << L) { \
1277 Entry * pos ## L = regEntry + ((winnerIndex + (1 << LogK)) >> (((int(LogK - L) + 1) >= 0) ? ((LogK - L) + 1) : 0)); \
1278 Element key ## L = pos ## L->key; \
1279 if (cmp(winnerKey, key ## L)) { \
1280 unsigned_type index ## L = pos ## L->index; \
1281 pos ## L->key = winnerKey; \
1282 pos ## L->index = winnerIndex; \
1283 winnerKey = key ## L; \
1284 winnerIndex = index ## L; \
1299 regEntry[0].index = winnerIndex;
1300 regEntry[0].key = winnerKey;
1304 bool is_sentinel(
const Element & a)
1306 return !(cmp(cmp.min_value(), a));
1308 bool not_sentinel(
const Element & a)
1310 return cmp(cmp.min_value(), a);
1320 std::swap(cmp, obj.cmp);
1321 std::swap(free_segments, obj.free_segments);
1322 std::swap(size_, obj.size_);
1323 std::swap(logK, obj.logK);
1324 std::swap(k, obj.k);
1325 std::swap(sentinel, obj.sentinel);
1326 swap_1D_arrays(entry, obj.entry, KNKMAX);
1327 swap_1D_arrays(current, obj.current, KNKMAX);
1328 swap_1D_arrays(segment, obj.segment, KNKMAX);
1329 swap_1D_arrays(segment_size, obj.segment_size, KNKMAX);
1330 std::swap(mem_cons_, obj.mem_cons_);
1333 void multi_merge(Element * begin, Element * end)
1335 multi_merge(begin, end - begin);
1337 void multi_merge(Element *, unsigned_type length);
1339 unsigned_type mem_cons()
const {
return mem_cons_; }
1341 bool spaceIsAvailable()
const
1343 return k < KNKMAX || !free_segments.empty();
1346 void insert_segment(Element * to, unsigned_type sz);
1347 unsigned_type size() {
return size_; }
1351 template <
class ValTp_,
class Cmp_,
unsigned KNKMAX>
1354 free_segments.push(0);
1356 current[0] = &sentinel;
1362 template <
class ValTp_,
class Cmp_,
unsigned KNKMAX>
1363 void loser_tree<ValTp_, Cmp_, KNKMAX>::init()
1365 assert(!cmp(cmp.min_value(), cmp.min_value()));
1366 sentinel = cmp.min_value();
1368 assert(current[entry[0].index] == &sentinel);
1373 template <
class ValTp_,
class Cmp_,
unsigned KNKMAX>
1374 void loser_tree<ValTp_, Cmp_, KNKMAX>::rebuildLoserTree()
1376 assert(LOG2<KNKMAX>::floor == LOG2<KNKMAX>::ceil);
1377 unsigned_type winner = initWinner(1);
1378 entry[0].index = winner;
1379 entry[0].key = *(current[winner]);
1388 template <
class ValTp_,
class Cmp_,
unsigned KNKMAX>
1389 unsigned_type loser_tree<ValTp_, Cmp_, KNKMAX>::initWinner(unsigned_type root)
1394 unsigned_type left = initWinner(2 * root);
1395 unsigned_type right = initWinner(2 * root + 1);
1396 Element lk = *(current[left]);
1397 Element rk = *(current[right]);
1398 if (!(cmp(lk, rk))) {
1399 entry[root].index = right;
1400 entry[root].key = rk;
1403 entry[root].index = left;
1404 entry[root].key = lk;
1416 template <
class ValTp_,
class Cmp_,
unsigned KNKMAX>
1417 void loser_tree<ValTp_, Cmp_, KNKMAX>::update_on_insert(
1419 const Element & newKey,
1420 unsigned_type newIndex,
1421 Element * winnerKey,
1422 unsigned_type * winnerIndex,
1423 unsigned_type * mask)
1426 *mask = 1 << (logK - 1);
1427 *winnerKey = entry[0].key;
1428 *winnerIndex = entry[0].index;
1429 if (cmp(entry[node].key, newKey))
1431 entry[node].key = newKey;
1432 entry[node].index = newIndex;
1435 update_on_insert(node >> 1, newKey, newIndex, winnerKey, winnerIndex, mask);
1436 Element loserKey = entry[node].key;
1437 unsigned_type loserIndex = entry[node].index;
1438 if ((*winnerIndex & *mask) != (newIndex & *mask)) {
1439 if (cmp(loserKey, newKey)) {
1440 if (cmp(*winnerKey, newKey)) {
1441 entry[node].key = *winnerKey;
1442 entry[node].index = *winnerIndex;
1444 entry[node].key = newKey;
1445 entry[node].index = newIndex;
1448 *winnerKey = loserKey;
1449 *winnerIndex = loserIndex;
1464 template <
class ValTp_,
class Cmp_,
unsigned KNKMAX>
1465 void loser_tree<ValTp_, Cmp_, KNKMAX>::doubleK()
1467 STXXL_VERBOSE3(
"loser_tree::doubleK (before) k=" << k <<
" logK=" << logK <<
" KNKMAX=" << KNKMAX <<
" #free=" << free_segments.size());
1470 assert(free_segments.empty());
1474 for (unsigned_type i = 2 * k - 1; i >= k; i--)
1476 current[i] = &sentinel;
1478 free_segments.push(i);
1485 STXXL_VERBOSE3(
"loser_tree::doubleK (after) k=" << k <<
" logK=" << logK <<
" KNKMAX=" << KNKMAX <<
" #free=" << free_segments.size());
1486 assert(!free_segments.empty());
1494 template <
class ValTp_,
class Cmp_,
unsigned KNKMAX>
1495 void loser_tree<ValTp_, Cmp_, KNKMAX>::compactTree()
1497 STXXL_VERBOSE3(
"loser_tree::compactTree (before) k=" << k <<
" logK=" << logK <<
" #free=" << free_segments.size());
1501 unsigned_type from = 0;
1502 unsigned_type to = 0;
1503 for ( ; from < k; from++)
1505 if (not_sentinel(*(current[from])))
1507 segment_size[to] = segment_size[from];
1508 current[to] = current[from];
1509 segment[to] = segment[from];
1526 while (k > 1 && to <= (k / 2)) {
1532 free_segments.clear();
1533 for ( ; to < k; to++) {
1534 current[to] = &sentinel;
1535 free_segments.push(to);
1538 STXXL_VERBOSE3(
"loser_tree::compactTree (after) k=" << k <<
" logK=" << logK <<
" #free=" << free_segments.size());
1547 template <
class ValTp_,
class Cmp_,
unsigned KNKMAX>
1548 void loser_tree<ValTp_, Cmp_, KNKMAX>::insert_segment(Element * to, unsigned_type sz)
1550 STXXL_VERBOSE2(
"loser_tree::insert_segment(" << to <<
"," << sz <<
")");
1555 assert(not_sentinel(to[0]));
1556 assert(not_sentinel(to[sz - 1]));
1557 assert(is_sentinel(to[sz]));
1560 if (free_segments.empty()) {
1563 assert(!free_segments.empty());
1564 unsigned_type index = free_segments.top();
1565 free_segments.pop();
1569 current[index] = segment[index] = to;
1570 segment_size[index] = (sz + 1) *
sizeof(value_type);
1571 mem_cons_ += (sz + 1) *
sizeof(value_type);
1576 unsigned_type dummyIndex;
1577 unsigned_type dummyMask;
1578 update_on_insert((index + k) >> 1, *to, index,
1579 &dummyKey, &dummyIndex, &dummyMask);
1590 template <
class ValTp_,
class Cmp_,
unsigned KNKMAX>
1591 loser_tree<ValTp_, Cmp_, KNKMAX>::~loser_tree()
1593 STXXL_VERBOSE1(
"loser_tree::~loser_tree()");
1594 for (unsigned_type i = 0; i < k; ++i)
1598 STXXL_VERBOSE2(
"loser_tree::~loser_tree() deleting segment " << i);
1599 delete[] segment[i];
1600 mem_cons_ -= segment_size[i];
1604 assert(mem_cons_ == 0);
1608 template <
class ValTp_,
class Cmp_,
unsigned KNKMAX>
1609 void loser_tree<ValTp_, Cmp_, KNKMAX>::deallocate_segment(unsigned_type slot)
1613 STXXL_VERBOSE2(
"loser_tree::deallocate_segment() deleting segment " <<
1614 slot <<
" address: " << segment[slot] <<
" size: " << segment_size[slot]);
1615 current[slot] = &sentinel;
1618 delete[] segment[slot];
1619 segment[slot] = NULL;
1620 mem_cons_ -= segment_size[slot];
1623 free_segments.push(slot);
1632 template <
class ValTp_,
class Cmp_,
unsigned KNKMAX>
1633 void loser_tree<ValTp_, Cmp_, KNKMAX>::multi_merge(Element * to, unsigned_type length)
1635 STXXL_VERBOSE3(
"loser_tree::multi_merge(to=" << to <<
", len=" << length <<
") k=" << k);
1641 assert(length <= size_);
1648 assert(entry[0].index == 0);
1649 assert(free_segments.empty());
1651 std::copy(current[0], current[0] + length, to);
1652 current[0] += length;
1653 entry[0].key = **current;
1654 if (is_segment_empty(0))
1655 deallocate_segment(0);
1660 merge_iterator(current[0], current[1], to, length, cmp);
1662 if (is_segment_empty(0))
1663 deallocate_segment(0);
1665 if (is_segment_empty(1))
1666 deallocate_segment(1);
1671 if (is_segment_empty(3))
1672 merge3_iterator(current[0], current[1], current[2], to, length, cmp);
1674 merge4_iterator(current[0], current[1], current[2], current[3], to, length, cmp);
1677 if (is_segment_empty(0))
1678 deallocate_segment(0);
1680 if (is_segment_empty(1))
1681 deallocate_segment(1);
1683 if (is_segment_empty(2))
1684 deallocate_segment(2);
1686 if (is_segment_empty(3))
1687 deallocate_segment(3);
1690 case 3: multi_merge_f<3>(to, length);
1692 case 4: multi_merge_f<4>(to, length);
1694 case 5: multi_merge_f<5>(to, length);
1696 case 6: multi_merge_f<6>(to, length);
1698 case 7: multi_merge_f<7>(to, length);
1700 case 8: multi_merge_f<8>(to, length);
1702 case 9: multi_merge_f<9>(to, length);
1704 case 10: multi_merge_f<10>(to, length);
1706 default: multi_merge_k(to, length);
1715 const unsigned_type num_segments_used = k - free_segments.size();
1716 const unsigned_type num_segments_trigger = k - (3 * k / 5);
1722 STXXL_VERBOSE3(
"loser_tree compact? k=" << k <<
" #used=" << num_segments_used
1723 <<
" <= #trigger=" << num_segments_trigger <<
" ==> "
1724 << ((k > 1 && num_segments_used <= num_segments_trigger) ?
"yes" :
"no ")
1726 << ((k == 4 && !free_segments.empty() && !is_segment_empty(3)) ?
"yes" :
"no ")
1727 <<
" #free=" << free_segments.size());
1728 if (k > 1 && ((num_segments_used <= num_segments_trigger) ||
1729 (k == 4 && !free_segments.empty() && !is_segment_empty(3))))
1739 template <
class ValTp_,
class Cmp_,
unsigned KNKMAX>
1740 inline bool loser_tree<ValTp_, Cmp_, KNKMAX>::is_segment_empty(unsigned_type slot)
1742 return (is_sentinel(*(current[slot])) && (current[slot] != &sentinel));
1746 template <
class ValTp_,
class Cmp_,
unsigned KNKMAX>
1747 void loser_tree<ValTp_, Cmp_, KNKMAX>::
1748 multi_merge_k(Element * to, unsigned_type length)
1752 unsigned_type currentIndex;
1753 unsigned_type kReg = k;
1754 Element * done = to + length;
1755 unsigned_type winnerIndex = entry[0].index;
1756 Element winnerKey = entry[0].key;
1757 Element * winnerPos;
1761 winnerPos = current[winnerIndex];
1768 current[winnerIndex] = winnerPos;
1769 winnerKey = *winnerPos;
1772 if (is_sentinel(winnerKey))
1773 deallocate_segment(winnerIndex);
1777 for (unsigned_type i = (winnerIndex + kReg) >> 1; i > 0; i >>= 1) {
1778 currentPos = entry + i;
1779 currentKey = currentPos->key;
1780 if (cmp(winnerKey, currentKey)) {
1781 currentIndex = currentPos->index;
1782 currentPos->key = winnerKey;
1783 currentPos->index = winnerIndex;
1784 winnerKey = currentKey;
1785 winnerIndex = currentIndex;
1791 entry[0].index = winnerIndex;
1792 entry[0].key = winnerKey;
1810 unsigned BufferSize1_ = 32,
1812 unsigned IntKMAX_ = 64,
1813 unsigned IntLevels_ = 4,
1814 unsigned BlockSize_ = (2 * 1024 * 1024),
1815 unsigned ExtKMAX_ = 64,
1816 unsigned ExtLevels_ = 2,
1817 class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY
1819 struct priority_queue_config
1821 typedef Tp_ value_type;
1822 typedef Cmp_ comparator_type;
1823 typedef AllocStr_ alloc_strategy_type;
1826 BufferSize1 = BufferSize1_,
1829 IntLevels = IntLevels_,
1830 ExtLevels = ExtLevels_,
1831 BlockSize = BlockSize_,
1837 __STXXL_END_NAMESPACE
1841 template <
class BlockType_,
1845 void swap(stxxl::priority_queue_local::ext_merger<BlockType_, Cmp_, Arity_, AllocStr_> & a,
1846 stxxl::priority_queue_local::ext_merger<BlockType_, Cmp_, Arity_, AllocStr_> & b)
1850 template <
class ValTp_,
class Cmp_,
unsigned KNKMAX>
1851 void swap(stxxl::priority_queue_local::loser_tree<ValTp_, Cmp_, KNKMAX> & a,
1852 stxxl::priority_queue_local::loser_tree<ValTp_, Cmp_, KNKMAX> & b)
1858 __STXXL_BEGIN_NAMESPACE
1861 template <
class Config_>
1865 typedef Config_ Config;
1868 BufferSize1 = Config::BufferSize1,
1870 IntKMAX = Config::IntKMAX,
1871 IntLevels = Config::IntLevels,
1872 ExtLevels = Config::ExtLevels,
1873 Levels = Config::IntLevels + Config::ExtLevels,
1874 BlockSize = Config::BlockSize,
1875 ExtKMAX = Config::ExtKMAX
1882 typedef typename Config::alloc_strategy_type alloc_strategy_type;
1909 value_type buffer2[Levels][N + 1];
1910 value_type * minBuffer2[Levels];
1913 value_type buffer1[BufferSize1 + 1];
1914 value_type * minBuffer1;
1916 comparator_type cmp;
1922 unsigned_type activeLevels;
1926 bool deallocate_pools;
1929 void refillBuffer1();
1930 unsigned_type refillBuffer2(unsigned_type k);
1932 unsigned_type makeSpaceAvailable(unsigned_type level);
1933 void emptyInsertHeap();
1935 value_type getSupremum()
const {
return cmp.min_value(); }
1936 unsigned_type getSize1()
const {
return (buffer1 + BufferSize1) - minBuffer1; }
1937 unsigned_type getSize2(unsigned_type i)
const {
return &(buffer2[i][N]) - minBuffer2[i]; }
1960 priority_queue(unsigned_type p_pool_mem, unsigned_type w_pool_mem);
1965 for (unsigned_type i = 0; i < IntLevels; ++i)
1966 std::swap(itree[i], obj.itree[i]);
1970 std::swap(etree, obj.etree);
1971 for (unsigned_type i1 = 0; i1 < Levels; ++i1)
1972 for (unsigned_type i2 = 0; i2 < (N + 1); ++i2)
1973 std::swap(buffer2[i1][i2], obj.buffer2[i1][i2]);
1975 swap_1D_arrays(minBuffer2, obj.minBuffer2, Levels);
1976 swap_1D_arrays(buffer1, obj.buffer1, BufferSize1 + 1);
1977 std::swap(minBuffer1, obj.minBuffer1);
1978 std::swap(cmp, obj.cmp);
1979 std::swap(insertHeap, obj.insertHeap);
1980 std::swap(activeLevels, obj.activeLevels);
1981 std::swap(size_, obj.size_);
2006 const value_type &
top()
const;
2020 void push(
const value_type & obj);
2028 unsigned_type dynam_alloc_mem(0), i(0);
2031 for ( ; i < IntLevels; ++i)
2032 dynam_alloc_mem += itree[i].
mem_cons();
2034 for (i = 0; i < ExtLevels; ++i)
2035 dynam_alloc_mem += etree[i].
mem_cons();
2038 return (
sizeof(*
this) +
2045 template <
class Config_>
2049 insertHeap.size() - 1 +
2050 ((buffer1 + BufferSize1) - minBuffer1);
2054 template <
class Config_>
2057 assert(!insertHeap.empty());
2060 if ( cmp(*minBuffer1, t))
2067 template <
class Config_>
2071 assert(!insertHeap.empty());
2073 if ( cmp(*minBuffer1, insertHeap.top()))
2079 assert(minBuffer1 < buffer1 + BufferSize1);
2081 if (minBuffer1 == buffer1 + BufferSize1)
2086 template <
class Config_>
2090 assert(itree->not_sentinel(obj));
2091 if (insertHeap.size() == N + 1)
2095 assert(!insertHeap.empty());
2097 insertHeap.push(obj);
2103 template <
class Config_>
2105 p_pool(p_pool_), w_pool(w_pool_),
2107 activeLevels(0), size_(0),
2108 deallocate_pools(false)
2110 STXXL_VERBOSE2(
"priority_queue::priority_queue()");
2111 assert(!cmp(cmp.min_value(), cmp.min_value()));
2114 for (unsigned_type j = 0; j < ExtLevels; ++j)
2115 etree[j].set_pools(&p_pool, &w_pool);
2117 value_type sentinel = cmp.min_value();
2118 buffer1[BufferSize1] = sentinel;
2119 insertHeap.
push(sentinel);
2120 minBuffer1 = buffer1 + BufferSize1;
2121 for (unsigned_type i = 0; i < Levels; i++)
2123 buffer2[i][N] = sentinel;
2124 minBuffer2[i] = &(buffer2[i][N]);
2128 template <
class Config_>
2133 activeLevels(0), size_(0),
2134 deallocate_pools(true)
2136 STXXL_VERBOSE2(
"priority_queue::priority_queue()");
2137 assert(!cmp(cmp.min_value(), cmp.min_value()));
2139 for (unsigned_type j = 0; j < ExtLevels; ++j)
2140 etree[j].set_pools(&p_pool, &w_pool);
2142 value_type sentinel = cmp.min_value();
2143 buffer1[BufferSize1] = sentinel;
2144 insertHeap.
push(sentinel);
2145 minBuffer1 = buffer1 + BufferSize1;
2146 for (unsigned_type i = 0; i < Levels; i++)
2148 buffer2[i][N] = sentinel;
2149 minBuffer2[i] = &(buffer2[i][N]);
2153 template <
class Config_>
2156 STXXL_VERBOSE2(
"priority_queue::~priority_queue()");
2157 if (deallocate_pools)
2169 template <
class Config_>
2172 STXXL_VERBOSE2(
"priority_queue::refillBuffer2(" << j <<
")");
2174 value_type * oldTarget;
2175 unsigned_type deleteSize;
2176 size_type treeSize = (j < IntLevels) ? itree[j].size() : etree[j - IntLevels].size();
2177 unsigned_type bufferSize = buffer2[j] + N - minBuffer2[j];
2178 if (treeSize + bufferSize >= size_type(N))
2180 oldTarget = buffer2[j];
2181 deleteSize = N - bufferSize;
2185 oldTarget = buffer2[j] + N - treeSize - bufferSize;
2186 deleteSize = treeSize;
2194 memmove(oldTarget, minBuffer2[j], bufferSize *
sizeof(value_type));
2195 minBuffer2[j] = oldTarget;
2199 itree[j].multi_merge(oldTarget + bufferSize, deleteSize);
2204 etree[j - IntLevels].multi_merge(oldTarget + bufferSize,
2205 oldTarget + bufferSize + deleteSize);
2213 return deleteSize + bufferSize;
2219 template <
class Config_>
2222 STXXL_VERBOSE2(
"priority_queue::refillBuffer1()");
2224 size_type totalSize = 0;
2227 for (int_type i = activeLevels - 1; i >= 0; i--)
2229 if ((buffer2[i] + N) - minBuffer2[i] < BufferSize1)
2231 sz = refillBuffer2(i);
2233 if (sz == 0 && unsigned_type(i) == activeLevels - 1)
2241 totalSize += BufferSize1;
2245 if (totalSize >= BufferSize1)
2247 minBuffer1 = buffer1;
2249 size_ -= size_type(BufferSize1);
2253 minBuffer1 = buffer1 + BufferSize1 - totalSize;
2255 assert(size_ == size_type(sz));
2262 minBuffer1 = buffer1 + BufferSize1 - sz;
2263 STXXL_VERBOSE2(
"Active levels = " << activeLevels);
2264 switch (activeLevels)
2268 std::copy(minBuffer2[0], minBuffer2[0] + sz, minBuffer1);
2269 minBuffer2[0] += sz;
2272 priority_queue_local::merge_iterator(
2274 minBuffer2[1], minBuffer1, sz, cmp);
2277 priority_queue_local::merge3_iterator(
2280 minBuffer2[2], minBuffer1, sz, cmp);
2283 priority_queue_local::merge4_iterator(
2287 minBuffer2[3], minBuffer1, sz, cmp);
2290 STXXL_THROW(std::runtime_error,
"priority_queue<...>::refillBuffer1()",
2291 "Overflow! The number of buffers on 2nd level in stxxl::priority_queue is currently limited to 4");
2302 template <
class Config_>
2305 STXXL_VERBOSE2(
"priority_queue::makeSpaceAvailable(" << level <<
")");
2306 unsigned_type finalLevel;
2307 assert(level < Levels);
2308 assert(level <= activeLevels);
2310 if (level == activeLevels)
2314 const bool spaceIsAvailable_ =
2315 (level < IntLevels) ? itree[level].spaceIsAvailable()
2316 : ((level == Levels - 1) ?
true : (etree[level - IntLevels].spaceIsAvailable()));
2318 if (spaceIsAvailable_)
2324 finalLevel = makeSpaceAvailable(level + 1);
2326 if (level < IntLevels - 1)
2328 unsigned_type segmentSize = itree[level].size();
2329 value_type * newSegment =
new value_type[segmentSize + 1];
2330 itree[level].multi_merge(newSegment, segmentSize);
2332 newSegment[segmentSize] = buffer1[BufferSize1];
2336 itree[level + 1].insert_segment(newSegment, segmentSize);
2340 if (level == IntLevels - 1)
2342 const unsigned_type segmentSize = itree[IntLevels - 1].size();
2343 STXXL_VERBOSE1(
"Inserting segment into first level external: " << level <<
" " << segmentSize);
2344 etree[0].insert_segment(itree[IntLevels - 1], segmentSize);
2348 const size_type segmentSize = etree[level - IntLevels].size();
2349 STXXL_VERBOSE1(
"Inserting segment into second level external: " << level <<
" " << segmentSize);
2350 etree[level - IntLevels + 1].insert_segment(etree[level - IntLevels], segmentSize);
2359 template <
class Config_>
2362 STXXL_VERBOSE2(
"priority_queue::emptyInsertHeap()");
2363 assert(insertHeap.size() == (N + 1));
2365 const value_type sup = getSupremum();
2368 value_type * newSegment =
new value_type[N + 1];
2369 value_type * newPos = newSegment;
2373 value_type * SortTo = newSegment;
2375 insertHeap.sort_to(SortTo);
2377 SortTo = newSegment + N;
2379 insertHeap.push(*SortTo);
2381 assert(insertHeap.size() == 1);
2383 newSegment[N] = sup;
2387 const unsigned_type tempSize = N + BufferSize1;
2388 value_type temp[tempSize + 1];
2389 unsigned_type sz1 = getSize1();
2390 unsigned_type sz2 = getSize2(0);
2391 value_type * pos = temp + tempSize - sz1 - sz2;
2392 std::copy(minBuffer1, minBuffer1 + sz1, pos);
2393 std::copy(minBuffer2[0], minBuffer2[0] + sz2, pos + sz1);
2394 temp[tempSize] = sup;
2399 priority_queue_local::merge_iterator(pos, newPos, minBuffer1, sz1, cmp);
2404 priority_queue_local::merge_iterator(pos, newPos, minBuffer2[0], sz2, cmp);
2409 priority_queue_local::merge_iterator(pos, newPos, newSegment, N, cmp);
2412 unsigned_type freeLevel = makeSpaceAvailable(0);
2413 assert(freeLevel == 0 || itree[0].size() == 0);
2414 itree[0].insert_segment(newSegment, N);
2420 for (int_type i = freeLevel; i >= 0; i--)
2424 newSegment =
new value_type[getSize2(i) + 1];
2425 std::copy(minBuffer2[i], minBuffer2[i] + getSize2(i) + 1, newSegment);
2426 itree[0].insert_segment(newSegment, getSize2(i));
2427 minBuffer2[i] = buffer2[i] + N;
2432 size_ += size_type(N);
2435 if (minBuffer1 == buffer1 + BufferSize1)
2439 namespace priority_queue_local
2441 struct Parameters_for_priority_queue_not_found_Increase_IntM
2443 enum { fits =
false };
2444 typedef Parameters_for_priority_queue_not_found_Increase_IntM result;
2449 enum { fits =
false };
2450 typedef dummy result;
2453 template <
unsigned_type E_,
unsigned_type IntM_,
unsigned_type MaxS_,
unsigned_type B_,
unsigned_type m_,
bool stop = false>
2456 typedef find_B_m<E_, IntM_, MaxS_, B_, m_, stop> Self;
2466 fits = c > 10 && ((k - m) * (m) * (m * B / (E * 4 * 1024))) >= MaxS_ && (MaxS_ < ((k - m) * m / (2 * E)) * 1024 || m >= 128),
2470 typedef typename find_B_m<E, IntM, MaxS_, B, m + step, fits || (m >= k - step)>::result candidate1;
2471 typedef typename find_B_m<E, IntM, MaxS_, B / 2, 1, fits || candidate1::fits>::result candidate2;
2476 template <
unsigned_type E_,
unsigned_type IntM_,
unsigned_type MaxS_,
bool stop>
2477 struct find_B_m<E_, IntM_, MaxS_, 2048, 1, stop>
2479 enum { fits =
false };
2480 typedef Parameters_for_priority_queue_not_found_Increase_IntM result;
2484 template <
unsigned_type E_,
unsigned_type IntM_,
unsigned_type MaxS_,
unsigned_type B_,
unsigned_type m_>
2485 struct find_B_m<E_, IntM_, MaxS_, B_, m_, true>
2487 enum { fits =
false };
2488 typedef dummy result;
2492 template <
unsigned_type E_,
unsigned_type IntM_,
unsigned_type MaxS_>
2493 struct find_settings
2496 typedef typename find_B_m<E_, IntM_, MaxS_, (8 * 1024 * 1024), 1>::result result;
2499 struct Parameters_not_found_Try_to_change_the_Tune_parameter
2501 typedef Parameters_not_found_Try_to_change_the_Tune_parameter result;
2505 template <
unsigned_type AI_,
unsigned_type X_,
unsigned_type CriticalSize_>
2508 typedef compute_N<AI_, X_, CriticalSize_> Self;
2515 typedef typename IF<(N >= CriticalSize_), Self,
typename compute_N<AI / 2, X, CriticalSize_>::result>::result result;
2518 template <
unsigned_type X_,
unsigned_type CriticalSize_>
2519 struct compute_N<1, X_, CriticalSize_>
2521 typedef Parameters_not_found_Try_to_change_the_Tune_parameter result;
2595 template <
class Tp_,
class Cmp_,
unsigned_type IntM_,
unsigned MaxS_,
unsigned Tune_ = 6>
2600 typedef typename priority_queue_local::find_settings<sizeof(Tp_), IntM_, MaxS_>::result settings;
2604 X = B * (settings::k - m) / settings::E,
2608 typedef typename priority_queue_local::compute_N<(1 << Tune_), X, 4 * Buffer1Size>::result ComputeN;
2613 AE = (m / 2 < 2) ? 2 : (m / 2)
2617 EConsumption = X * settings::E + settings::B * AE + ((MaxS_ / X) / AE) * settings::B * 1024
2633 __STXXL_END_NAMESPACE
2638 template <
class Config_>
2639 void swap(stxxl::priority_queue<Config_> & a,
2640 stxxl::priority_queue<Config_> & b)
2646 #endif // !STXXL_PRIORITY_QUEUE_HEADER