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
|
// scanandorder.h
#pragma once
/* todo:
_ handle compound keys with differing directions. we don't handle this yet: neither here nor in indexes i think!!!
_ limit amount of data
*/
/* see also IndexDetails::getKeysFromObject, which needs some merging with this. */
class KeyType : boost::noncopyable {
public:
JSObj pattern; // e.g., { ts : -1 }
public:
KeyType(JSObj _keyPattern) {
pattern = _keyPattern;
assert( !pattern.isEmpty() );
}
// returns the key value for o
JSObj getKeyFromObject(JSObj o) {
return o.extractFields(pattern);
}
};
/* todo:
_ respect limit
_ check for excess mem usage
_ response size limit from runquery; push it up a bit.
*/
inline bool fillQueryResultFromObj(BufBuilder& b, set<string> *filter, JSObj& js) {
if( filter ) {
JSObj x;
bool ok = x.addFields(js, *filter) > 0;
if( ok )
b.append((void*) x.objdata(), x.objsize());
return ok;
}
b.append((void*) js.objdata(), js.objsize());
return true;
}
typedef multimap<JSObj,JSObj> BestMap;
class ScanAndOrder {
BestMap best;
int startFrom;
int limit; // max to send back.
KeyType order;
int dir;
unsigned approxSize;
void _add(JSObj& k, JSObj o) {
best.insert(make_pair(k,o));
}
// T may be iterator or reverse_iterator
void _addIfBetter(JSObj& k, JSObj o, BestMap::iterator i) {
const JSObj& worstBestKey = i->first;
if( worstBestKey.woCompare(k) == dir ) {
// k is better, 'upgrade'
best.erase(i);
_add(k, o);
}
}
public:
ScanAndOrder(int _startFrom, int _limit, JSObj _order) :
startFrom(_startFrom), order(_order) {
limit = _limit > 0 ? _limit + startFrom : 0x7fffffff;
approxSize = 0;
// todo: do order right for compound keys. this is temp.
dir = 1;
Element e = order.pattern.firstElement();
if( e.type() == Number && e.number() < 0 ) {
dir = -1;
}
}
void add(JSObj o) {
JSObj k = order.getKeyFromObject(o);
if( (int) best.size() < limit ) {
approxSize += k.objsize();
uassert( approxSize < 1 * 1024 * 1024 );
_add(k, o);
return;
}
BestMap::iterator i;
if( dir < 0 )
i = best.begin();
else {
assert( best.end() != best.begin() );
i = best.end(); i--;
}
_addIfBetter(k, o, i);
}
template<class T>
void _fill(BufBuilder& b, set<string> *filter, int& nout, T begin, T end) {
int n = 0;
int nFilled = 0;
for( T i = begin; i != end; i++ ) {
n++;
if( n <= startFrom )
continue;
JSObj& o = i->second;
if( fillQueryResultFromObj(b, filter, o) ) {
nFilled++;
if( nFilled >= limit )
goto done;
uassert( b.len() < 4000000 ); // appserver limit
}
}
done:
nout = nFilled;
}
/* scanning complete. stick the query result in b for n objects. */
void fill(BufBuilder& b, set<string> *filter, int& nout) {
if( dir > 0 )
_fill(b, filter, nout, best.begin(), best.end());
else
_fill(b, filter, nout, best.rbegin(), best.rend());
}
};
|
