1 /* 2 * Copyright 2006-2008 The FLWOR Foundation. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 #ifndef ZORBA_RUNTIME_GFLWOR_ORDERBY 17 #define ZORBA_RUNTIME_GFLWOR_ORDERBY 18 19 #include "zorbautils/checked_vector.h" 20 21 #include "common/shared_types.h" 22 23 #include "runtime/base/plan_iterator.h" 24 #include "runtime/core/gflwor/common.h" 25 26 27 namespace zorba 28 { 29 namespace flwor 30 { 31 32 class OrderByIterator; 33 34 class OrderValue; 35 36 37 /***************************************************************************//** 38 Wrapper for a OrderSpec. 39 40 - Syntax: 41 42 OrderSpec ::= ExprSingle OrderModifier 43 44 OrderModifier ::= ("ascending" | "descending")? 45 ("empty" ("greatest" | "least"))? 46 ("collation" URILiteral)? 47 48 - Data Members: 49 50 theInput : The iterator computing the value of this orderby column for 51 each binding of the in-scope variables. 52 theEmptyLeast : Whether the empty seq should be considered the smallest or 53 the largest value. 54 theDescending : Whether to order in descending order or not. 55 theNativeCompare : If true, then every pair of values in this orderby column 56 have data types such that the values can be compared using 57 the Item::equal() method (instead of the more expensive 58 CompareIterator::valueCompare() method). 59 theCollation : The collation to use when comparing values of this orderby 60 column (if the values are of type xs:string or subtype). 61 theCollator : Pointer to the collator obj corresponding to theCollation. 62 The pointer is assigned by the OrderByClause::open() method. 63 Note: no need to delete theCollator in ~OrderSpec() because 64 the obj is managed by the collation cache. 65 ********************************************************************************/ 66 class OrderSpec : public ::zorba::serialization::SerializeBaseClass 67 { 68 public: 69 PlanIter_t theDomainIter; 70 71 bool theEmptyLeast; 72 bool theDescending; 73 bool theNativeCompare; 74 std::string theCollation; 75 XQPCollator * theCollator; 76 77 public: 78 SERIALIZABLE_CLASS(OrderSpec) 79 SERIALIZABLE_CLASS_CONSTRUCTOR(OrderSpec) 80 void serialize(::zorba::serialization::Archiver& ar); 81 82 public: OrderSpec()83 OrderSpec() : theNativeCompare(false), theCollator(NULL) {} 84 85 OrderSpec( 86 PlanIter_t domainIter, 87 bool emptyLeast, 88 bool descending, 89 bool nativeCompare, 90 const std::string& collation); 91 ~OrderSpec()92 ~OrderSpec() {} 93 94 void accept(PlanIterVisitor&) const; 95 96 uint32_t getStateSizeOfSubtree() const; 97 98 void open(PlanState& aPlanState, uint32_t& offset) const; 99 void reset(PlanState& aPlanState) const; 100 void close(PlanState& aPlanState) const; 101 }; 102 103 104 /***************************************************************************//** 105 A SortTuple ST stores the key values computed by the ordering exprs of an 106 orderby clause for some input-stream tuple T. 107 108 For the generalized flwor, ST also stores the position of T in a data table 109 that buffers the input tuple stream in inder to sort it. 110 111 For a simple flwor, the T data is an iterator I over a temp sequence that 112 stores the result of the return clause computed for the current input- 113 stream tuple. 114 ********************************************************************************/ 115 class SortTuple 116 { 117 public: 118 std::vector<store::Item*> theKeyValues; 119 ulong theDataPos; 120 121 public: SortTuple()122 SortTuple() { } 123 ~SortTuple()124 ~SortTuple() { } 125 clear()126 void clear() 127 { 128 ulong numColumns = (ulong)theKeyValues.size(); 129 for (ulong i = 0; i < numColumns; ++i) 130 { 131 if (theKeyValues[i] != NULL) 132 { 133 theKeyValues[i]->removeReference(); 134 theKeyValues[i] = NULL; 135 } 136 } 137 138 theKeyValues.clear(); 139 } 140 }; 141 142 143 /******************************************************************************* 144 theOderMap : The table that materializes a flwor tuple stream in inder to 145 sort it. The entries of this table are instances of OrderByTuple. 146 theNumTuples : The number of tuples in theOrderMap. 147 theCurTuplePos : A position inside theOrderMap. Used to return individual flwor 148 results after the full result set has been materialized and 149 sorted. 150 ********************************************************************************/ 151 class OrderByState : public PlanIteratorState 152 { 153 friend class OrderByIterator; 154 155 public: 156 typedef std::vector<SortTuple> SortTable; 157 typedef std::vector<StreamTuple> DataTable; 158 159 protected: 160 SortTable theSortTable; 161 DataTable theDataTable; 162 ulong theNumTuples; 163 ulong theCurTuplePos; 164 165 public: 166 OrderByState(); 167 168 ~OrderByState(); 169 170 void init(PlanState& planState, std::vector<OrderSpec>* orderSpecs); 171 172 void reset(PlanState&); 173 174 private: 175 void clearSortTable(); 176 }; 177 178 179 /******************************************************************************* 180 181 ********************************************************************************/ 182 class OrderByIterator : public Batcher<OrderByIterator> 183 { 184 private: 185 bool theStable; 186 std::vector<OrderSpec> theOrderSpecs; 187 188 PlanIter_t theTupleIter; 189 190 std::vector<ForVarIter_t> theInputForVars; 191 std::vector<LetVarIter_t> theInputLetVars; 192 std::vector<std::vector<PlanIter_t> > theOutputForVarsRefs; 193 std::vector<std::vector<PlanIter_t> > theOutputLetVarsRefs; 194 195 public: 196 SERIALIZABLE_CLASS(OrderByIterator) 197 SERIALIZABLE_CLASS_CONSTRUCTOR2(OrderByIterator, Batcher<OrderByIterator>) 198 void serialize(::zorba::serialization::Archiver& ar); 199 200 public: 201 OrderByIterator( 202 static_context* sctx, 203 const QueryLoc& loc, 204 bool stable, 205 std::vector<OrderSpec>& orderSpecs, 206 PlanIter_t tupleIterator, 207 std::vector<ForVarIter_t>& inputForVars, 208 std::vector<LetVarIter_t>& inputLetVars, 209 std::vector<std::vector<PlanIter_t> >& outputForVarsRefs, 210 std::vector<std::vector<PlanIter_t> >& outputLetVarsRefs); 211 212 ~OrderByIterator(); 213 214 void openImpl(PlanState& planState, uint32_t& offset); 215 bool nextImpl(store::Item_t& result, PlanState& planState) const; 216 void resetImpl(PlanState& planState) const; 217 void closeImpl(PlanState& planState); 218 219 virtual uint32_t getStateSize() const; 220 virtual uint32_t getStateSizeOfSubtree() const; 221 222 virtual void accept(PlanIterVisitor&) const; 223 224 private: 225 void materializeResultForSort( 226 OrderByState* iterState, 227 PlanState& planState) const; 228 229 void bindOrderBy( 230 OrderByState* iterState, 231 PlanState& planState) const; 232 }; 233 234 235 }//namespace gflwor 236 } //namespace zorba 237 238 239 #endif /* ZORBA_RUNTIME_GFLWOR_ORDERBY */ 240 241 /* 242 * Local variables: 243 * mode: c++ 244 * End: 245 */ 246 /* vim:set et sw=2 ts=2: */ 247