1 /* 2 * Copyright (c) 2021 Huawei Device Co., Ltd. 3 * Licensed under the Apache License, Version 2.0 (the "License"); 4 * you may not use this file except in compliance with the License. 5 * You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software 10 * distributed under the License is distributed on an "AS IS" BASIS, 11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 * See the License for the specific language governing permissions and 13 * limitations under the License. 14 */ 15 16 #ifndef TABLE_INDEX_MAP_H 17 #define TABLE_INDEX_MAP_H 18 19 #include <cstdint> 20 #include <deque> 21 #include <functional> 22 #include <vector> 23 #include "sqlite3.h" 24 #include "ts_common.h" 25 26 namespace SysTuning { 27 namespace TraceStreamer { 28 class IndexMap { 29 public: IndexMap()30 IndexMap() {} ~IndexMap()31 ~IndexMap() {} 32 33 IndexMap(TableRowId start, TableRowId end); 34 void CovertToIndexMap(); 35 static void Sort(); 36 void Print(); 37 void Init(); 38 void Merge(IndexMap* other); 39 void FilterId(unsigned char op, sqlite3_value* argv); 40 void FilterTS(unsigned char op, sqlite3_value* argv, const std::deque<InternalTime>& times); 41 template <class T> MixRange(unsigned char op,T value,const std::deque<T> & dataQueue)42 void MixRange(unsigned char op, T value, const std::deque<T>& dataQueue) 43 { 44 filters_++; 45 auto invalidValue = std::numeric_limits<T>::max(); 46 bool remove = false; 47 if (HasData()) { 48 CovertToIndexMap(); 49 remove = true; 50 } 51 auto size = dataQueue.size(); 52 rowIndexBak_.clear(); 53 bool changed = false; 54 switch (op) { 55 case SQLITE_INDEX_CONSTRAINT_EQ: 56 if (remove) { 57 for (auto i = rowIndex_.begin(); i != rowIndex_.end();) { 58 if (dataQueue[*i] != value) { 59 i++; 60 } else { 61 changed = true; 62 rowIndexBak_.push_back(*i); 63 i++; 64 } 65 } 66 if (changed) { 67 rowIndex_ = rowIndexBak_; 68 } 69 } else { 70 for (auto i = 0; i < size; i++) { 71 if (dataQueue[i] == value) { 72 rowIndex_.push_back(i); 73 } 74 } 75 } 76 indexType_ = INDEX_TYPE_OUTER_INDEX; 77 FixSize(); 78 break; 79 case SQLITE_INDEX_CONSTRAINT_NE: 80 if (remove) { 81 for (auto i = rowIndex_.begin(); i != rowIndex_.end();) { 82 if (dataQueue[*i] == value) { 83 i++; 84 } else { 85 changed = true; 86 rowIndexBak_.push_back(*i); 87 i++; 88 } 89 } 90 if (changed) { 91 rowIndex_ = rowIndexBak_; 92 } 93 } else { 94 for (auto i = 0; i < size; i++) { 95 if (dataQueue[i] != value) { 96 rowIndex_.push_back(i); 97 } 98 } 99 } 100 indexType_ = INDEX_TYPE_OUTER_INDEX; 101 FixSize(); 102 break; 103 case SQLITE_INDEX_CONSTRAINT_ISNULL: 104 if (remove) { 105 for (auto i = rowIndex_.begin(); i != rowIndex_.end();) { 106 if (dataQueue[*i] != invalidValue) { 107 i++; 108 } else { 109 changed = true; 110 rowIndexBak_.push_back(*i); 111 i++; 112 } 113 } 114 if (changed) { 115 rowIndex_ = rowIndexBak_; 116 } 117 } else { 118 for (auto i = 0; i < size; i++) { 119 if (dataQueue[i] == invalidValue) { 120 rowIndex_.push_back(i); 121 } 122 } 123 } 124 indexType_ = INDEX_TYPE_OUTER_INDEX; 125 FixSize(); 126 break; 127 case SQLITE_INDEX_CONSTRAINT_ISNOTNULL: 128 if (remove) { 129 for (auto i = rowIndex_.begin(); i != rowIndex_.end();) { 130 if (dataQueue[*i] == invalidValue) { 131 i++; 132 } else { 133 changed = true; 134 rowIndexBak_.push_back(*i); 135 i++; 136 } 137 } 138 if (changed) { 139 rowIndex_ = rowIndexBak_; 140 } 141 } else { 142 for (auto i = 0; i < size; i++) { 143 if (dataQueue[i] != invalidValue) { 144 rowIndex_.push_back(i); 145 } 146 } 147 } 148 indexType_ = INDEX_TYPE_OUTER_INDEX; 149 FixSize(); 150 break; 151 case SQLITE_INDEX_CONSTRAINT_GT: 152 if (remove) { 153 for (auto i = rowIndex_.begin(); i != rowIndex_.end();) { 154 if (dataQueue[*i] <= value) { 155 i++; 156 } else { 157 changed = true; 158 rowIndexBak_.push_back(*i); 159 i++; 160 } 161 } 162 if (changed) { 163 rowIndex_ = rowIndexBak_; 164 } 165 } else { 166 for (auto i = 0; i < size; i++) { 167 if (dataQueue[i] > value) { 168 rowIndex_.push_back(i); 169 } 170 } 171 } 172 indexType_ = INDEX_TYPE_OUTER_INDEX; 173 FixSize(); 174 break; 175 case SQLITE_INDEX_CONSTRAINT_GE: 176 if (remove) { 177 for (auto i = rowIndex_.begin(); i != rowIndex_.end();) { 178 if (dataQueue[*i] < value) { 179 i++; 180 } else { 181 changed = true; 182 rowIndexBak_.push_back(*i); 183 i++; 184 } 185 } 186 if (changed) { 187 rowIndex_ = rowIndexBak_; 188 } 189 } else { 190 for (auto i = 0; i < size; i++) { 191 if (dataQueue[i] >= invalidValue) { 192 rowIndex_.push_back(i); 193 } 194 } 195 } 196 indexType_ = INDEX_TYPE_OUTER_INDEX; 197 FixSize(); 198 break; 199 case SQLITE_INDEX_CONSTRAINT_LE: 200 if (remove) { 201 for (auto i = rowIndex_.begin(); i != rowIndex_.end();) { 202 if (dataQueue[*i] > value) { 203 i++; 204 } else { 205 changed = true; 206 rowIndexBak_.push_back(*i); 207 i++; 208 } 209 } 210 if (changed) { 211 rowIndex_ = rowIndexBak_; 212 } 213 } else { 214 for (auto i = 0; i < size; i++) { 215 if (dataQueue[i] < invalidValue) { 216 rowIndex_.push_back(i); 217 } 218 } 219 } 220 indexType_ = INDEX_TYPE_OUTER_INDEX; 221 FixSize(); 222 break; 223 case SQLITE_INDEX_CONSTRAINT_LT: 224 if (remove) { 225 for (auto i = rowIndex_.begin(); i != rowIndex_.end();) { 226 if (dataQueue[*i] >= value) { 227 i++; 228 } else { 229 changed = true; 230 rowIndexBak_.push_back(*i); 231 i++; 232 } 233 } 234 if (changed) { 235 rowIndex_ = rowIndexBak_; 236 } 237 } else { 238 for (auto i = 0; i < size; i++) { 239 if (dataQueue[i] < invalidValue) { 240 rowIndex_.push_back(i); 241 } 242 } 243 } 244 indexType_ = INDEX_TYPE_OUTER_INDEX; 245 FixSize(); 246 break; 247 248 default: 249 break; 250 } // end of switch (op) 251 empty_ = false; 252 } FixSize()253 void FixSize() 254 { 255 if (indexType_ == INDEX_TYPE_OUTER_INDEX) { 256 end_ = rowIndex_.size(); 257 current_ = 0; 258 } 259 } Remove(TableRowId row)260 void Remove(TableRowId row) 261 { 262 (void)std::remove(rowIndex_.begin(), rowIndex_.end(), row); 263 } Set(TableRowId start,TableRowId end)264 void Set(TableRowId start, TableRowId end) 265 { 266 if (indexType_ == INDEX_TYPE_ID) { 267 end_ = std::min(end_, end); 268 current_ = start_ = std::max(start_, start); 269 } 270 } 271 272 size_t Size() const; 273 274 void Next(); 275 276 bool Eof() const; 277 278 TableRowId CurrentRow() const; 279 280 void SortBy(bool desc); 281 void Intersect(TableRowId start, TableRowId end); 282 283 // the follow functions require that thecolData is sotred 284 template <typename Row, typename Val, typename GetV = const Val&(const Row&)> IntersectabcEqual(const std::deque<Row> & rows,Val v,GetV getValue)285 void IntersectabcEqual(const std::deque<Row>& rows, Val v, GetV getValue) 286 { 287 auto start = std::lower_bound(rows.begin() + start_, rows.begin() + end_, v); 288 auto end = std::upper_bound(start, rows.begin() + end_, v); 289 auto newStart = std::distance(rows.begin(), start); 290 auto newEnd = std::distance(rows.begin(), end); 291 Intersect(newStart, newEnd); 292 return; 293 } 294 295 template <typename Row, typename Val, typename GetV = const Val&(const Row&)> IntersectGreaterEqual(const std::deque<Row> & rows,Val v,GetV getValue)296 void IntersectGreaterEqual(const std::deque<Row>& rows, Val v, GetV getValue) 297 { 298 auto start = std::lower_bound(rows.begin() + start_, rows.begin() + end_, v, 299 [&](const Row& row, const Val& v) { return v > getValue(row); }); 300 auto newStart = std::distance(rows.begin(), start); 301 Intersect(newStart, INVALID_INT32); 302 return; 303 } 304 305 template <typename Row, typename Val, typename GetV = const Val&(const Row&)> IntersectLessEqual(const std::deque<Row> & rows,Val v,GetV getValue)306 void IntersectLessEqual(const std::deque<Row>& rows, Val v, GetV getValue) 307 { 308 auto end = std::upper_bound(rows.begin() + start_, rows.begin() + end_, v, 309 [&](const Row& row, const Val& v) { return v > getValue(row); }); 310 auto newEnd = std::distance(rows.begin(), end); 311 Intersect(0, newEnd); 312 return; 313 } 314 template <typename T> RemoveNullElements(const std::deque<T> & rows,T v)315 void RemoveNullElements(const std::deque<T>& rows, T v) 316 { 317 auto invalidValue = std::numeric_limits<T>::max(); 318 bool remove = false; 319 if (HasData()) { 320 CovertToIndexMap(); 321 remove = true; 322 } 323 324 if (remove) { 325 for (auto i = rowIndex_.begin(); i != rowIndex_.end();) { 326 if (rows[*i] == invalidValue) { 327 i = rowIndex_.erase(i); 328 } else { 329 i++; 330 } 331 } 332 } else { 333 auto size = rows.size(); 334 for (auto i = 0; i < size; i++) { 335 if (rows[i] != invalidValue) { 336 rowIndex_.push_back(i); 337 } 338 } 339 } 340 indexType_ = INDEX_TYPE_OUTER_INDEX; 341 FixSize(); 342 return; 343 } 344 bool HasData() const; 345 std::vector<TableRowId> rowIndex_ = {}; 346 std::vector<TableRowId> rowIndexBak_ = {}; 347 348 private: 349 TableRowId end_ = INVALID_INT32; 350 TableRowId current_ = 0; 351 TableRowId start_ = 0; 352 enum FindIndexType { 353 INDEX_TYPE_ID, 354 INDEX_TYPE_OUTER_INDEX, 355 }; 356 FindIndexType indexType_ = INDEX_TYPE_ID; 357 uint32_t indexSize_ = 0; 358 uint32_t index_ = 0; 359 360 enum IndexType { COMPACT, SPARSE }; 361 uint8_t type_ = COMPACT; 362 bool empty_ = true; 363 bool desc_ = false; 364 bool converted_ = false; 365 uint8_t filters_ = 0; 366 bool intersectEable_ = false; 367 }; 368 } // namespace TraceStreamer 369 } // namespace SysTuning 370 371 #endif // TABLE_INDEX_MAP_H 372