/usr/lib/grass64/include/grass/iostream/empq.h is in grass-dev 6.4.3-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 | /****************************************************************************
*
* MODULE: iostream
*
* COPYRIGHT (C) 2007 Laura Toma
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
*****************************************************************************/
#ifndef __EMPQ_H
#define __EMPQ_H
#include <stdio.h>
#include <assert.h>
#include "ami_config.h" //for SAVE_MEMORY
#include "ami_stream.h"
#include "mm.h"
#include "mm_utils.h" //for MEMORY_LOG, getAvailableMemory
#include "imbuffer.h"
#include "embuffer.h"
#include "pqheap.h"
#include "minmaxheap.h"
template<class T,class Key> class ExtendedEltMergeType;
#define ExtendedMergeStream AMI_STREAM<ExtendedEltMergeType<T,Key> >
/**********************************************************
DEBUGGING FLAGS
***********************************************************/
//enables printing messages when buffers are emptied
//#define EMPQ_EMPTY_BUF_PRINT
//enables printing when pq gets filled from buffers
//#define EMPQ_PQ_FILL_PRINT
//enables priting inserts
//#define EMPQ_PRINT_INSERT
//enables printing deletes
//#define EMPQ_PRINT_EXTRACTALL
//enables printing the empq on insert/extract_all_min
//#define EMPQ_PRINT_EMPQ
//enable priting the size of the EMPQ and nb of active streams
//on fillpq() amd on empty_buff_0
//#define EMPQ_PRINT_SIZE
//enable printing 'fill pq from B0' in extract_min()
//#define EMPQ_PRINT_FILLPQ_FROM_BUFF0
//enable expensive size asserts
//#define EMPQ_ASSERT_EXPENSIVE
/**********************************************************/
/* external memory priority queue
Functionality:
Keep a pqueue PQ of size \theta(M) in memory. Keep a buffer B0 of
size \theta(M) in memory. keep an array of external-memory
buffers, one for each level 1..log_m{n/m} (where N is the maximum
number of items in pqueue at any time).
invariants:
1. PQ contains the smallest items in the structure.
2. each stream of any external memory buffers is sorted in
increasing order.
insert(x): if (x < maximum_item(PQ) exchange x with
maximum_item(PQ); if buffer B0 is full, empty it; insert x in B0;
extract_min():
analysis:
1. inserts: once the buffer B0 is empty, the next sizeof(B0)
inserts are free; one insert can cause many I/Os if cascading
emptying of external buffers Bi occurs. Emptying level-i buffer
costs <arity>^i*sizeof(B0)/B I/Os and occurs every
N/<arity>^i*sizeof(B0) inserts (or less, if deletes too). It can be
proved that the amortized time of 1 insert is 1/B*maxnb_buffers.
*/
/*
T is assumed to be a class for which getPriority() and getValue()
are implemented; for simplicity it is assumed that the comparison
operators have been overloaded on T such that
x < y <==> x.getPriority() < y.getPriority()
*/
template<class T, class Key>
class em_pqueue {
private:
//in memory priority queue
MinMaxHeap<T> *pq;
//pqueue size
unsigned long pqsize;
//in-memory buffer
im_buffer<T> *buff_0;
//in-memory buffer size
unsigned long bufsize;
//external memory buffers
em_buffer<T,Key>** buff;
/* number of external memory buffers statically allocated in the
beginning; since the number of buffers needed is \log_m{n/m}, we
cannot know it in advance; estimate it roughly and then reallocate
it dynamically on request;
TO DO: dynamic reallocation with a bigger nb of external buffer
if structure becomes full */
unsigned short max_nbuf;
//index of next external buffer entry available for use (i.e. is NULL)
unsigned short crt_buf;
//external buffer arity
unsigned int buf_arity;
public:
//create an em_pqueue of specified size
em_pqueue(long pq_sz, long buf_sz, unsigned short nb_buf,
unsigned int buf_ar);
//create an em_pqueue capable to store <= N elements
em_pqueue();
em_pqueue(long N) { em_pqueue(); }; // N not used
#ifdef SAVE_MEMORY
// create an empq, initialize its pq with im and insert amis in
// buff[0]; im should not be used/deleted after that outside empq
em_pqueue(MinMaxHeap<T> *im, AMI_STREAM<T> *amis);
#endif
//copy constructor
em_pqueue(const em_pqueue &ep);
//clean up
~em_pqueue();
//return the nb of elements in the structure
unsigned long size();
//return true if empty
bool is_empty();
//return true if full
bool is_full() {
cout << "em_pqueue::is_full(): sorry not implemented\n";
exit(1);
}
//return the element with minimum priority in the structure
bool min(T& elt);
//delete the element with minimum priority in the structure;
//return false if pq is empty
bool extract_min(T& elt);
//extract all elts with min key, add them and return their sum
bool extract_all_min(T& elt);
//insert an element; return false if insertion fails
bool insert(const T& elt);
//return maximum capacity of i-th external buffer
long maxlen(unsigned short i);
//return maximum capacity of em_pqueue
long maxlen();
// delete all the data in the pq; reset to empty but don't free memory
void clear();
//print structure
void print_range();
void print();
//print the detailed size of empq (pq, buf_0, buff[i])
void print_size();
friend ostream& operator<<(ostream& s, const em_pqueue &empq) {
s << "EM_PQ: pq size=" << empq.pqsize
<< ", buff_0 size=" << empq.bufsize
<< ", ext_bufs=" << empq.crt_buf
<< "(max " << empq.max_nbuf << ")\n";
s << "IN_MEMORY PQ: \n" << *(empq.pq) << "\n";
s << "IN_MEMORY BUFFER: \n" << *(empq.buff_0) << "\n";
for (unsigned short i=0; i < empq.crt_buf; i++) {
//s << "EM_BUFFER " << i << ":\n" ;
s << *(empq.buff[i]);
}
return s;
}
protected:
//return the nb of active streams in the buffer
int active_streams() {
int totstr = 0;
for (unsigned short i = 0; i< crt_buf; i++) {
totstr+= buff[i]->get_nbstreams();
}
return totstr;
}
//called when buff_0 is full to empty it on external level_1 buffer;
//can produce cascading emptying
bool empty_buff_0();
//sort and empty buffer i into buffer (i+1) recursively;
//called recursively by empty_buff_0() to empty subsequent buffers
//i must be a valid (i<crt_buf) full buffer
void empty_buff(unsigned short i);
/* merge the first <K> elements of the streams of input buffer,
starting at position <buf.deleted[i]> in each stream; there are
<buf.arity> streams in total; write output in <outstream>; the
items written in outstream are of type <merge_output_type> which
extends T with the stream nb and buffer nb the item comes from;
this information is needed later to distribute items back; do not
delete the K merged elements from the input streams; <bufid> is the
id of the buffer whose streams are being merged;
the input streams are assumed sorted in increasing order of keys; */
AMI_err merge_buffer(em_buffer<T,Key> *buf,
ExtendedMergeStream *outstr, long K);
/* merge the first <K> elements of the input streams; there are
<arity> streams in total; write output in <outstream>;
the input streams are assumed sorted in increasing order of their
keys; */
AMI_err merge_streams(ExtendedMergeStream** instr,
unsigned short arity,
ExtendedMergeStream *outstr, long K);
//deletes one element from <buffer, stream>
void delete_str_elt(unsigned short buf_id,
unsigned int stream_id);
/* copy the minstream in the internal pqueue while merging with
buff_0; the smallest <pqsize> elements between minstream and
buff_0 will be inserted in internal pqueue; also, the elements
from minstram which are inserted in pqueue must be marked as
deleted in the source streams; */
void merge_bufs2pq(ExtendedMergeStream *minstream);
//clean buffers in case some streams have been emptied
void cleanup();
//called when pq must be filled from external buffers
bool fillpq();
//print the nb of elements in each stream
void print_stream_sizes();
};
#endif
|