16 #ifndef STXXL_PQ_EXT_MERGER_HEADER
17 #define STXXL_PQ_EXT_MERGER_HEADER
19 #include <stxxl/bits/mng/mng.h>
21 __STXXL_BEGIN_NAMESPACE
29 namespace priority_queue_local
31 template <
typename Iterator>
32 class short_sequence :
public std::pair<Iterator, Iterator>
34 typedef std::pair<Iterator, Iterator> pair;
37 typedef Iterator iterator;
38 typedef const iterator const_iterator;
39 typedef typename std::iterator_traits<iterator>::value_type value_type;
40 typedef typename std::iterator_traits<iterator>::difference_type size_type;
41 typedef value_type & reference;
42 typedef const value_type & const_reference;
43 typedef unsigned_type origin_type;
49 short_sequence(Iterator first, Iterator last, origin_type origin) :
50 pair(first, last), m_origin(origin)
58 const_iterator begin()
const
63 const_iterator cbegin()
const
73 const_iterator end()
const
78 const_iterator cend()
const
88 const_reference front()
const
98 const_reference back()
const
103 size_type size()
const
105 return end() - begin();
113 origin_type origin()
const
123 template <
class BlockType_,
126 class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>
130 typedef stxxl::uint64 size_type;
131 typedef BlockType_ block_type;
132 typedef typename block_type::bid_type bid_type;
133 typedef typename block_type::value_type value_type;
134 typedef Cmp_ comparator_type;
135 typedef AllocStr_ alloc_strategy;
139 enum { arity = Arity_, arity_bound = 1UL << (LOG2<Arity_>::ceil) };
144 bool is_sentinel(
const value_type & a)
const
146 return !(cmp(cmp.min_value(), a));
149 bool not_sentinel(
const value_type & a)
const
151 return cmp(cmp.min_value(), a);
154 struct sequence_state :
private noncopyable
157 unsigned_type current;
158 std::list<bid_type> * bids;
164 const value_type & operator * ()
const
166 return (*block)[current];
169 sequence_state() : bids(NULL), allocated(
false)
174 STXXL_VERBOSE2(
"ext_merger sequence_state::~sequence_state()");
186 (*block)[0] = cmp.min_value();
189 bool is_sentinel(
const value_type & a)
const
191 return !(cmp(cmp.min_value(), a));
194 bool not_sentinel(
const value_type & a)
const
196 return cmp(cmp.min_value(), a);
199 void swap(sequence_state & obj)
203 std::swap(current, obj.current);
204 std::swap(block, obj.block);
205 std::swap(bids, obj.bids);
206 assert(merger == obj.merger);
207 std::swap(allocated, obj.allocated);
211 sequence_state & operator ++ ()
213 assert(not_sentinel((*block)[current]));
214 assert(current < block->size);
218 if (current == block->size)
220 STXXL_VERBOSE2(
"ext_merger sequence_state operator++ crossing block border ");
222 assert(bids != NULL);
225 STXXL_VERBOSE2(
"ext_merger sequence_state operator++ it was the last block in the sequence ");
232 STXXL_VERBOSE2(
"ext_merger sequence_state operator++ there is another block ");
233 bid_type bid = bids->front();
235 merger->pool->hint(bid);
236 if (!(bids->empty()))
238 STXXL_VERBOSE2(
"ext_merger sequence_state operator++ more blocks exist in a sequence, hinting the next");
239 merger->pool->hint(bids->front());
241 merger->pool->read(block, bid)->wait();
242 STXXL_VERBOSE2(
"first element of read block " << bid <<
" " << *(block->begin()) <<
" cached in " << block);
243 if (!(bids->empty()))
244 merger->pool->hint(bids->front());
245 block_manager::get_instance()->delete_block(bid);
254 #if STXXL_PQ_EXTERNAL_LOSER_TREE
260 #endif //STXXL_PQ_EXTERNAL_LOSER_TREE
272 #if STXXL_PQ_EXTERNAL_LOSER_TREE
275 Entry entry[arity_bound];
276 #endif //STXXL_PQ_EXTERNAL_LOSER_TREE
281 sequence_state states[arity_bound];
285 block_type * sentinel_block;
289 size_(0), log_k(0), k(1), pool(0)
295 size_(0), log_k(0), k(1),
303 STXXL_VERBOSE1(
"ext_merger::~ext_merger()");
304 for (unsigned_type i = 0; i < arity; ++i)
306 delete states[i].block;
308 delete sentinel_block;
319 STXXL_VERBOSE2(
"ext_merger::init()");
320 assert(!cmp(cmp.min_value(), cmp.min_value()));
322 sentinel_block = NULL;
323 if (arity < arity_bound)
325 sentinel_block =
new block_type;
326 for (unsigned_type i = 0; i < block_type::size; ++i)
327 (*sentinel_block)[i] = cmp.min_value();
328 if (arity + 1 == arity_bound) {
330 STXXL_ERRMSG(
"inefficient PQ parameters for ext_merger: arity + 1 == arity_bound");
334 for (unsigned_type i = 0; i < arity_bound; ++i)
336 states[i].merger =
this;
338 states[i].block =
new block_type;
340 states[i].block = sentinel_block;
342 states[i].make_inf();
346 free_segments.push(0);
348 rebuild_loser_tree();
349 #if STXXL_PQ_EXTERNAL_LOSER_TREE
350 assert(is_sentinel(*states[entry[0].index]));
351 #endif //STXXL_PQ_EXTERNAL_LOSER_TREE
355 void rebuild_loser_tree()
357 #if STXXL_PQ_EXTERNAL_LOSER_TREE
358 unsigned_type winner = init_winner(1);
359 entry[0].index = winner;
360 entry[0].key = *(states[winner]);
361 #endif //STXXL_PQ_EXTERNAL_LOSER_TREE
365 #if STXXL_PQ_EXTERNAL_LOSER_TREE
371 unsigned_type init_winner(unsigned_type root)
379 unsigned_type left = init_winner(2 * root);
380 unsigned_type right = init_winner(2 * root + 1);
381 value_type lk = *(states[left]);
382 value_type rk = *(states[right]);
385 entry[root].index = right;
386 entry[root].key = rk;
391 entry[root].index = left;
392 entry[root].key = lk;
403 void update_on_insert(
405 const value_type & new_key,
406 unsigned_type new_index,
407 value_type * winner_key,
408 unsigned_type * winner_index,
409 unsigned_type * mask)
413 *mask = 1 << (log_k - 1);
414 *winner_key = entry[0].key;
415 *winner_index = entry[0].index;
416 if (cmp(entry[node].key, new_key))
418 entry[node].key = new_key;
419 entry[node].index = new_index;
424 update_on_insert(node >> 1, new_key, new_index, winner_key, winner_index, mask);
425 value_type loserKey = entry[node].key;
426 unsigned_type loserIndex = entry[node].index;
427 if ((*winner_index & *mask) != (new_index & *mask))
429 if (cmp(loserKey, new_key))
431 if (cmp(*winner_key, new_key))
433 entry[node].key = *winner_key;
434 entry[node].index = *winner_index;
438 entry[node].key = new_key;
439 entry[node].index = new_index;
442 *winner_key = loserKey;
443 *winner_index = loserIndex;
455 #endif //STXXL_PQ_EXTERNAL_LOSER_TREE
460 STXXL_VERBOSE1(
"ext_merger::double_k (before) k=" << k <<
" log_k=" << log_k <<
" arity_bound=" << arity_bound <<
" arity=" << arity <<
" #free=" << free_segments.size());
463 assert(free_segments.empty());
467 for (unsigned_type i = 2 * k - 1; i >= k; i--)
469 states[i].make_inf();
471 free_segments.push(i);
478 STXXL_VERBOSE1(
"ext_merger::double_k (after) k=" << k <<
" log_k=" << log_k <<
" arity_bound=" << arity_bound <<
" arity=" << arity <<
" #free=" << free_segments.size());
479 assert(!free_segments.empty());
482 rebuild_loser_tree();
489 STXXL_VERBOSE1(
"ext_merger::compact_tree (before) k=" << k <<
" log_k=" << log_k <<
" #free=" << free_segments.size());
494 unsigned_type target = 0;
495 for (unsigned_type from = 0; from < k; from++)
497 if (!is_segment_empty(from))
499 assert(is_segment_allocated(from));
502 assert(!is_segment_allocated(target));
503 states[target].swap(states[from]);
510 while (k > 1 && target <= (k / 2))
517 free_segments.clear();
518 for ( ; target < k; target++)
520 assert(!is_segment_allocated(target));
521 states[target].make_inf();
523 free_segments.push(target);
526 STXXL_VERBOSE1(
"ext_merger::compact_tree (after) k=" << k <<
" log_k=" << log_k <<
" #free=" << free_segments.size());
530 rebuild_loser_tree();
537 std::swap(cmp, obj.cmp);
538 std::swap(free_segments, obj.free_segments);
539 std::swap(size_, obj.size_);
540 std::swap(log_k, obj.log_k);
542 swap_1D_arrays(entry, obj.entry, arity_bound);
543 swap_1D_arrays(states, obj.states, arity_bound);
550 unsigned_type mem_cons()
const
552 return (STXXL_MIN<unsigned_type>(arity + 1, arity_bound) * block_type::raw_size);
560 template <
class OutputIterator>
561 void multi_merge(OutputIterator begin, OutputIterator end)
563 size_type length = end - begin;
565 STXXL_VERBOSE1(
"ext_merger::multi_merge from " << k <<
" sequence(s), length = " << length);
571 assert(length <= size_);
575 #if STXXL_PARALLEL && STXXL_PARALLEL_PQ_MULTIWAY_MERGE_EXTERNAL
576 typedef stxxl::int64 diff_type;
577 typedef std::pair<typename block_type::iterator, typename block_type::iterator> sequence;
579 std::vector<sequence> seqs;
580 std::vector<unsigned_type> orig_seq_index;
585 for (unsigned_type i = 0; i < k; ++i)
587 if (states[i].current == states[i].block->size || is_sentinel(*states[i]))
590 seqs.push_back(std::make_pair(states[i].block->begin() + states[i].current, states[i].block->end()));
591 orig_seq_index.push_back(i);
593 #if STXXL_CHECK_ORDER_IN_SORTS
594 if (!is_sentinel(*seqs.back().first) && !stxxl::is_sorted(seqs.back().first, seqs.back().second, inv_cmp))
596 STXXL_VERBOSE1(
"length " << i <<
" " << (seqs.back().second - seqs.back().first));
597 for (value_type * v = seqs.back().first + 1; v < seqs.back().second; ++v)
599 if (inv_cmp(*v, *(v - 1)))
601 STXXL_VERBOSE1(
"Error at position " << i <<
"/" << (v - seqs.back().first - 1) <<
"/" << (v - seqs.back().first) <<
" " << *(v - 1) <<
" " << *v);
605 STXXL_VERBOSE1(
"Wrong sentinel at position " << (v - seqs.back().first));
613 if (states[i].bids != NULL && !states[i].bids->empty())
614 pool->
hint(states[i].bids->front());
617 assert(seqs.size() > 0);
619 #if STXXL_CHECK_ORDER_IN_SORTS
620 value_type last_elem;
623 diff_type rest = length;
627 value_type min_last = cmp.min_value();
628 diff_type total_size = 0;
630 for (unsigned_type i = 0; i < seqs.size(); ++i)
632 diff_type seq_i_size = seqs[i].second - seqs[i].first;
635 total_size += seq_i_size;
636 if (inv_cmp(*(seqs[i].second - 1), min_last))
637 min_last = *(seqs[i].second - 1);
639 STXXL_VERBOSE1(
"front block of seq " << i <<
": front=" << *(seqs[i].first) <<
" back=" << *(seqs[i].second - 1) <<
" len=" << seq_i_size);
641 STXXL_VERBOSE1(
"front block of seq " << i <<
": empty");
645 assert(total_size > 0);
646 assert(!is_sentinel(min_last));
648 STXXL_VERBOSE1(
"min_last " << min_last <<
" total size " << total_size <<
" num_seq " << seqs.size());
650 diff_type less_equal_than_min_last = 0;
652 for (unsigned_type i = 0; i < seqs.size(); ++i)
656 typename block_type::iterator position =
657 std::upper_bound(seqs[i].first, seqs[i].second, min_last, inv_cmp);
661 STXXL_VERBOSE1(
"seq " << i <<
": " << (position - seqs[i].first) <<
" greater equal than " << min_last);
663 less_equal_than_min_last += (position - seqs[i].first);
666 diff_type output_size = STXXL_MIN(less_equal_than_min_last, rest);
668 STXXL_VERBOSE1(
"output_size=" << output_size <<
" = min(leq_t_ml=" << less_equal_than_min_last <<
", rest=" << rest <<
")");
670 assert(output_size > 0);
674 begin = parallel::multiway_merge(seqs.begin(), seqs.end(), begin, inv_cmp, output_size);
677 size_ -= output_size;
679 for (unsigned_type i = 0; i < seqs.size(); ++i)
681 sequence_state & state = states[orig_seq_index[i]];
683 state.current = seqs[i].first - state.block->begin();
685 assert(seqs[i].first <= seqs[i].second);
687 if (seqs[i].first == seqs[i].second)
689 assert(state.current == state.block->size);
690 if (state.bids == NULL || state.bids->empty())
692 STXXL_VERBOSE1(
"seq " << i <<
": ext_merger::multi_merge(...) it was the last block in the sequence ");
697 #if STXXL_CHECK_ORDER_IN_SORTS
698 last_elem = *(seqs[i].second - 1);
700 STXXL_VERBOSE1(
"seq " << i <<
": ext_merger::multi_merge(...) there is another block ");
701 bid_type bid = state.bids->front();
702 state.bids->pop_front();
704 if (!(state.bids->empty()))
706 STXXL_VERBOSE2(
"seq " << i <<
": ext_merger::multi_merge(...) more blocks exist, hinting the next");
707 pool->
hint(state.bids->front());
709 pool->
read(state.block, bid)->
wait();
710 STXXL_VERBOSE1(
"seq " << i <<
": first element of read block " << bid <<
" " << *(state.block->begin()) <<
" cached in " << state.block);
711 if (!(state.bids->empty()))
712 pool->
hint(state.bids->front());
714 seqs[i] = std::make_pair(state.block->begin() + state.current, state.block->end());
715 block_manager::get_instance()->delete_block(bid);
717 #if STXXL_CHECK_ORDER_IN_SORTS
718 STXXL_VERBOSE1(
"before " << last_elem <<
" after " << *seqs[i].first <<
" newly loaded block " << bid);
719 if (!stxxl::is_sorted(seqs[i].first, seqs[i].second, inv_cmp))
721 STXXL_VERBOSE1(
"length " << i <<
" " << (seqs[i].second - seqs[i].first));
722 for (value_type * v = seqs[i].first + 1; v < seqs[i].second; ++v)
724 if (inv_cmp(*v, *(v - 1)))
726 STXXL_VERBOSE1(
"Error at position " << i <<
"/" << (v - seqs[i].first - 1) <<
"/" << (v - seqs[i].first) <<
" " << *(v - 1) <<
" " << *v);
730 STXXL_VERBOSE1(
"Wrong sentinel at position " << (v - seqs[i].first));
741 for (unsigned_type i = 0; i < seqs.size(); ++i)
743 unsigned_type seg = orig_seq_index[i];
744 if (is_segment_empty(seg))
746 STXXL_VERBOSE1(
"deallocated " << seg);
747 deallocate_segment(seg);
751 #else // STXXL_PARALLEL && STXXL_PARALLEL_PQ_MULTIWAY_MERGE_EXTERNAL
754 for (unsigned_type i = 0; i < k; ++i)
756 if (states[i].bids != NULL && !states[i].bids->empty())
757 pool->
hint(states[i].bids->front());
763 assert(entry[0].index == 0);
764 assert(free_segments.empty());
767 for (size_type i = 0; i < length; ++i, ++(states[0]), ++begin)
768 *begin = *(states[0]);
770 entry[0].key = **states;
771 if (is_segment_empty(0))
772 deallocate_segment(0);
777 merge_iterator(states[0], states[1], begin, length, cmp);
778 rebuild_loser_tree();
779 if (is_segment_empty(0) && is_segment_allocated(0))
780 deallocate_segment(0);
782 if (is_segment_empty(1) && is_segment_allocated(1))
783 deallocate_segment(1);
788 if (is_segment_empty(3))
789 merge3_iterator(states[0], states[1], states[2], begin, length, cmp);
791 merge4_iterator(states[0], states[1], states[2], states[3], begin, length, cmp);
792 rebuild_loser_tree();
793 if (is_segment_empty(0) && is_segment_allocated(0))
794 deallocate_segment(0);
796 if (is_segment_empty(1) && is_segment_allocated(1))
797 deallocate_segment(1);
799 if (is_segment_empty(2) && is_segment_allocated(2))
800 deallocate_segment(2);
802 if (is_segment_empty(3) && is_segment_allocated(3))
803 deallocate_segment(3);
806 case 3: multi_merge_f<OutputIterator, 3>(begin, end);
808 case 4: multi_merge_f<OutputIterator, 4>(begin, end);
810 case 5: multi_merge_f<OutputIterator, 5>(begin, end);
812 case 6: multi_merge_f<OutputIterator, 6>(begin, end);
814 case 7: multi_merge_f<OutputIterator, 7>(begin, end);
816 case 8: multi_merge_f<OutputIterator, 8>(begin, end);
818 case 9: multi_merge_f<OutputIterator, 9>(begin, end);
820 case 10: multi_merge_f<OutputIterator, 10>(begin, end);
822 default: multi_merge_k(begin, end);
831 const unsigned_type num_segments_used = std::min<unsigned_type>(arity, k) - free_segments.size();
832 const unsigned_type num_segments_trigger = k - (3 * k / 5);
838 STXXL_VERBOSE3(
"ext_merger compact? k=" << k <<
" #used=" << num_segments_used
839 <<
" <= #trigger=" << num_segments_trigger <<
" ==> "
840 << ((k > 1 && num_segments_used <= num_segments_trigger) ?
"yes" :
"no ")
842 << ((k == 4 && !free_segments.empty() && !is_segment_empty(3)) ?
"yes" :
"no ")
843 <<
" #free=" << free_segments.size());
844 if (k > 1 && ((num_segments_used <= num_segments_trigger) ||
845 (k == 4 && !free_segments.empty() && !is_segment_empty(3))))
853 #if STXXL_PQ_EXTERNAL_LOSER_TREE
855 template <
class OutputIterator>
856 void multi_merge_k(OutputIterator begin, OutputIterator end)
859 value_type current_key;
860 unsigned_type current_index;
861 unsigned_type kReg = k;
862 OutputIterator done = end;
863 OutputIterator target = begin;
864 unsigned_type winner_index = entry[0].index;
865 value_type winner_key = entry[0].key;
867 while (target != done)
870 *target = *(states[winner_index]);
873 ++(states[winner_index]);
875 winner_key = *(states[winner_index]);
878 if (is_sentinel(winner_key))
879 deallocate_segment(winner_index);
883 for (unsigned_type i = (winner_index + kReg) >> 1; i > 0; i >>= 1)
885 current_pos = entry + i;
886 current_key = current_pos->key;
887 if (cmp(winner_key, current_key))
889 current_index = current_pos->index;
890 current_pos->key = winner_key;
891 current_pos->index = winner_index;
892 winner_key = current_key;
893 winner_index = current_index;
899 entry[0].index = winner_index;
900 entry[0].key = winner_key;
903 template <
class OutputIterator,
unsigned LogK>
904 void multi_merge_f(OutputIterator begin, OutputIterator end)
906 OutputIterator done = end;
907 OutputIterator target = begin;
908 unsigned_type winner_index = entry[0].index;
909 Entry * reg_entry = entry;
910 sequence_state * reg_states = states;
911 value_type winner_key = entry[0].key;
913 assert(log_k >= LogK);
914 while (target != done)
917 *target = *(reg_states[winner_index]);
920 ++(reg_states[winner_index]);
922 winner_key = *(reg_states[winner_index]);
926 if (is_sentinel(winner_key))
927 deallocate_segment(winner_index);
933 #define TreeStep(L) \
934 if (1 << LogK >= 1 << L) { \
935 Entry * pos ## L = reg_entry + ((winner_index + (1 << LogK)) >> (((int(LogK - L) + 1) >= 0) ? ((LogK - L) + 1) : 0)); \
936 value_type key ## L = pos ## L->key; \
937 if (cmp(winner_key, key ## L)) { \
938 unsigned_type index ## L = pos ## L->index; \
939 pos ## L->key = winner_key; \
940 pos ## L->index = winner_index; \
941 winner_key = key ## L; \
942 winner_index = index ## L; \
957 reg_entry[0].index = winner_index;
958 reg_entry[0].key = winner_key;
960 #endif //STXXL_PQ_EXTERNAL_LOSER_TREE
963 bool is_space_available()
const
965 return k < arity || !free_segments.empty();
971 template <
class Merger>
972 void insert_segment(Merger & another_merger, size_type segment_size)
974 STXXL_VERBOSE1(
"ext_merger::insert_segment(merger,...)" <<
this);
976 if (segment_size > 0)
979 if (free_segments.empty())
983 assert(!free_segments.empty());
984 unsigned_type free_slot = free_segments.top();
989 assert(segment_size);
990 unsigned_type nblocks = segment_size / block_type::size;
992 STXXL_VERBOSE1(
"ext_merger::insert_segment nblocks=" << nblocks);
995 STXXL_VERBOSE1(
"ext_merger::insert_segment(merger,...) WARNING: inserting a segment with " <<
996 nblocks <<
" blocks");
997 STXXL_VERBOSE1(
"THIS IS INEFFICIENT: TRY TO CHANGE PRIORITY QUEUE PARAMETERS");
999 unsigned_type first_size = segment_size % block_type::size;
1000 if (first_size == 0)
1002 first_size = block_type::size;
1006 std::list<bid_type> * bids =
new std::list<bid_type>(nblocks);
1007 bm->
new_blocks(alloc_strategy(), bids->begin(), bids->end());
1008 block_type * first_block =
new block_type;
1010 another_merger.multi_merge(
1011 first_block->begin() + (block_type::size - first_size),
1012 first_block->end());
1014 STXXL_VERBOSE1(
"last element of first block " << *(first_block->end() - 1));
1015 assert(!cmp(*(first_block->begin() + (block_type::size - first_size)), *(first_block->end() - 1)));
1019 for (
typename std::list<bid_type>::iterator curbid = bids->begin(); curbid != bids->end(); ++curbid)
1021 block_type * b = pool->
steal();
1022 another_merger.multi_merge(b->begin(), b->end());
1023 STXXL_VERBOSE1(
"first element of following block " << *curbid <<
" " << *(b->begin()));
1024 STXXL_VERBOSE1(
"last element of following block " << *curbid <<
" " << *(b->end() - 1));
1025 assert(!cmp(*(b->begin()), *(b->end() - 1)));
1026 pool->
write(b, *curbid);
1027 STXXL_VERBOSE1(
"written to block " << *curbid <<
" cached in " << b);
1030 insert_segment(bids, first_block, first_size, free_slot);
1032 size_ += segment_size;
1034 #if STXXL_PQ_EXTERNAL_LOSER_TREE
1036 value_type dummyKey;
1037 unsigned_type dummyIndex;
1038 unsigned_type dummyMask;
1039 update_on_insert((free_slot + k) >> 1, *(states[free_slot]), free_slot,
1040 &dummyKey, &dummyIndex, &dummyMask);
1041 #endif //STXXL_PQ_EXTERNAL_LOSER_TREE
1046 STXXL_VERBOSE1(
"Merged segment with zero size.");
1050 size_type size()
const {
return size_; }
1059 unsigned_type first_size, unsigned_type slot)
1061 STXXL_VERBOSE1(
"ext_merger::insert_segment(bidlist,...) " <<
this <<
" " << bidlist->size() <<
" " << slot);
1062 assert(!is_segment_allocated(slot));
1063 assert(first_size > 0);
1065 sequence_state & new_sequence = states[slot];
1066 new_sequence.current = block_type::size - first_size;
1067 std::swap(new_sequence.block, first_block);
1069 std::swap(new_sequence.bids, bidlist);
1072 assert(bidlist->empty());
1075 new_sequence.allocated =
true;
1076 assert(is_segment_allocated(slot));
1080 void deallocate_segment(unsigned_type slot)
1082 STXXL_VERBOSE1(
"ext_merger::deallocate_segment() deleting segment " << slot <<
" allocated=" <<
int(is_segment_allocated(slot)));
1083 assert(is_segment_allocated(slot));
1084 states[slot].allocated =
false;
1085 states[slot].make_inf();
1088 free_segments.push(slot);
1092 bool is_segment_empty(unsigned_type slot)
const
1094 return is_sentinel(*(states[slot]));
1099 bool is_segment_allocated(unsigned_type slot)
const
1101 return states[slot].allocated;
1108 __STXXL_END_NAMESPACE
1110 #endif // !STXXL_PQ_EXT_MERGER_HEADER
void insert_segment(std::list< bid_type > *bidlist, block_type *first_block, unsigned_type first_size, unsigned_type slot)
Definition: pq_ext_merger.h:1058
Inverts the order of a comparison functor by swapping its arguments.
Definition: pq_helpers.h:145
Implements dynamically resizable buffered writing and prefetched reading pool.
Definition: read_write_pool.h:28
void delete_blocks(const BIDIteratorClass &bidbegin, const BIDIteratorClass &bidend)
Deallocates blocks.
Definition: mng.h:218
bool hint(bid_type bid)
Gives a hint for prefetching a block.
Definition: read_write_pool.h:135
void new_blocks(const DiskAssignFunctor &functor, BIDIteratorClass bidbegin, BIDIteratorClass bidend, unsigned_type offset=0)
Allocates new blocks.
Definition: mng.h:90
request_ptr write(block_type *&block, bid_type bid)
Passes a block to the pool for writing.
Definition: read_write_pool.h:102
virtual void wait(bool measure_time=true)=0
Suspends calling thread until completion of the request.
request_ptr read(block_type *&block, bid_type bid)
Reads block. If this block is cached block is not read but passed from the cache. ...
Definition: read_write_pool.h:151
Block manager class.
Definition: mng.h:59
block_type * steal()
Take out a block from the pool.
Definition: read_write_pool.h:116
External merger, based on the loser tree data structure. !
Definition: pq_ext_merger.h:127
size_type size_write() const
Returns number of blocks owned by the write_pool.
Definition: read_write_pool.h:75