1 /****************************************************************************** 2 * 3 * SPDX-FileCopyrightText: 2008 Szymon Tomasz Stefanek <pragma@kvirc.net> 4 * 5 * SPDX-License-Identifier: GPL-2.0-or-later 6 * 7 *******************************************************************************/ 8 9 #pragma once 10 11 #include "core/item.h" 12 13 #include "MessageCore/StringUtil" 14 15 // See the MessageList::ItemPrivate::insertChildItem() function below for an explanation of this macro. 16 #if __GNUC__ >= 3 // krazy:exclude=cpp 17 #define GCC_DONT_INLINE_THIS __attribute__((noinline)) 18 #else 19 #define GCC_DONT_INLINE_THIS 20 #endif 21 22 namespace MessageList 23 { 24 namespace Core 25 { 26 class ItemPrivate 27 { 28 public: ItemPrivate(Item * owner)29 explicit ItemPrivate(Item *owner) 30 : q(owner) 31 , mChildItems(nullptr) 32 , mParent(nullptr) 33 , mThisItemIndexGuess(0) 34 , mInitialExpandStatus(Item::NoExpandNeeded) 35 , mIsViewable(false) 36 , mUseReceiver(false) 37 { 38 } 39 ~ItemPrivate()40 virtual ~ItemPrivate() 41 { 42 } 43 44 /** 45 * Implements "in the middle" insertions of child items. 46 * The template argument class must export a static inline bool firstGreaterOrEqual( Item *, Item * ) 47 * function which must return true when the first parameter item is considered to be greater 48 * or equal to the second parameter item and false otherwise. 49 * 50 * The insertion function *IS* our very bottleneck on flat views 51 * (when there are items with a lot of children). This is somewhat pathological... 52 * beside the binary search based insertion sort we actually can only do "statement level" optimization. 53 * I've found no better algorithms so far. If someone has a clever idea, please write to pragma 54 * at kvirc dot net :) 55 * 56 * GCC_DONT_INLINE_THIS is a macro defined above to __attribute__((noinline)) 57 * if the current compiler is gcc. Without this attribute gcc attempts to inline THIS 58 * function inside the callers. The problem is that while inlining this function 59 * it doesn't inline the INNER comparison functions (which we _WANT_ to be inlined) 60 * because they would make the caller function too big. 61 * 62 * This is what gcc reports with -Winline: 63 * 64 * /home/pragma/kmail-soc/kmail/messagelistview/item.h:352: warning: inlining failed in call to 65 * 'static bool MessageList::ItemSubjectComparator::firstGreaterOrEqual(MessageList::Item*, MessageList::Item*)': 66 * --param large-function-growth limit reached while inlining the caller 67 * /home/pragma/kmail-soc/kmail/messagelistview/model.cpp:239: warning: called from here 68 * 69 * The comparison functions then appear in the symbol table: 70 * 71 * etherea kmail # nm /usr/kde/4.0/lib/libkmailprivate.so | grep Comparator 72 * 00000000005d2c10 W _ZN5KMail15MessageList18ItemDateComparator19firstGreaterOrEqualEPNS0_4ItemES3_ 73 * 00000000005d2cb0 W _ZN5KMail15MessageList20ItemSenderComparator19firstGreaterOrEqualEPNS0_4ItemES3_ 74 * 00000000005d2c50 W _ZN5KMail15MessageList21ItemSubjectComparator19firstGreaterOrEqualEPNS0_4ItemES3_ 75 * ... 76 * 77 * With this attribute, instead, gcc doesn't complain at all and the inner comparisons 78 * *seem* to be inlined correctly (there is no sign of them in the symbol table). 79 */ insertChildItem(Model * model,Item * child)80 template<class ItemComparator, bool bAscending> int GCC_DONT_INLINE_THIS insertChildItem(Model *model, Item *child) 81 { 82 if (!mChildItems) { 83 return q->appendChildItem(model, child); 84 } 85 86 int cnt = mChildItems->count(); 87 if (cnt < 1) { 88 return q->appendChildItem(model, child); 89 } 90 91 int idx; 92 Item *pivot; 93 94 if (bAscending) { 95 pivot = mChildItems->at(cnt - 1); 96 97 if (ItemComparator::firstGreaterOrEqual(child, pivot)) { // gcc: <-- inline this instead, thnx 98 return q->appendChildItem(model, child); // this is very likely in date based comparisons (FIXME: not in other ones) 99 } 100 101 // Binary search based insertion 102 int l = 0; 103 int h = cnt - 1; 104 105 for (;;) { 106 idx = (l + h) / 2; 107 pivot = mChildItems->at(idx); 108 if (ItemComparator::firstGreaterOrEqual(pivot, child)) { // gcc: <-- inline this instead, thnx 109 if (l < h) { 110 h = idx - 1; 111 } else { 112 break; 113 } 114 } else { 115 if (l < h) { 116 l = idx + 1; 117 } else { 118 idx++; 119 break; 120 } 121 } 122 } 123 } else { 124 pivot = mChildItems->at(0); 125 if (ItemComparator::firstGreaterOrEqual(child, pivot)) { // gcc: <-- inline this instead, thnx 126 idx = 0; // this is very likely in date based comparisons (FIXME: not in other ones) 127 } else { 128 // Binary search based insertion 129 int l = 0; 130 int h = cnt - 1; 131 132 for (;;) { 133 idx = (l + h) / 2; 134 pivot = mChildItems->at(idx); 135 if (ItemComparator::firstGreaterOrEqual(child, pivot)) { // gcc: <-- inline this instead, thnx 136 if (l < h) { 137 h = idx - 1; 138 } else { 139 break; 140 } 141 } else { 142 if (l < h) { 143 l = idx + 1; 144 } else { 145 idx++; 146 break; 147 } 148 } 149 } 150 } 151 } 152 153 Q_ASSERT(idx >= 0); 154 Q_ASSERT(idx <= mChildItems->count()); 155 156 if (mIsViewable && model) { 157 model->beginInsertRows(model->index(q, 0), idx, idx); // BLEAH :D 158 } 159 160 mChildItems->insert(idx, child); 161 child->setIndexGuess(idx); 162 if (mIsViewable) { 163 if (model) { 164 model->endInsertRows(); // BLEAH :D 165 } 166 child->setViewable(model, true); 167 } 168 169 return idx; 170 } 171 172 /** 173 * Checks if the specified child item is actually in the wrong 174 * position in the child list and returns true in that case. 175 * Returns false if the item is already in the right position 176 * and no re-sorting is needed. 177 */ childItemNeedsReSorting(Item * child)178 template<class ItemComparator, bool bAscending> bool childItemNeedsReSorting(Item *child) 179 { 180 if (!mChildItems) { 181 return false; // not my child! (ugh... should assert ?) 182 } 183 184 const int idx = q->indexOfChildItem(child); 185 186 if (idx > 0) { 187 Item *prev = mChildItems->at(idx - 1); 188 if (bAscending) { 189 // child must be greater or equal to the previous item 190 if (!ItemComparator::firstGreaterOrEqual(child, prev)) { 191 return true; // wrong order: needs re-sorting 192 } 193 } else { 194 // previous must be greater or equal to the child item 195 if (!ItemComparator::firstGreaterOrEqual(prev, child)) { 196 return true; // wrong order: needs re-sorting 197 } 198 } 199 } 200 201 if (idx < (mChildItems->count() - 1)) { 202 Item *next = mChildItems->at(idx + 1); 203 if (bAscending) { 204 // next must be greater or equal to child 205 if (!ItemComparator::firstGreaterOrEqual(next, child)) { 206 return true; // wrong order: needs re-sorting 207 } 208 } else { 209 // child must be greater or equal to next 210 if (!ItemComparator::firstGreaterOrEqual(child, next)) { 211 return true; // wrong order: needs re-sorting 212 } 213 } 214 } 215 216 return false; 217 } 218 219 /** 220 * Internal handler for managing the children list. 221 */ 222 void childItemDead(Item *child); 223 224 Item *const q; 225 226 QList<Item *> *mChildItems; ///< List of children, may be 0 227 Item *mParent = nullptr; ///< The parent view item 228 time_t mMaxDate; ///< The maximum date in the subtree 229 time_t mDate; ///< The date of the message (or group date) 230 size_t mSize; ///< The size of the message in bytes 231 QString mSender; ///< The sender of the message (or group sender) 232 QString mReceiver; ///< The receiver of the message (or group receiver) 233 QString mSubject; ///< The subject of the message (or group subject) 234 QString mFolder; ///< The folder of the message 235 qint64 mItemId; ///< The Akonadi item id 236 qint64 mParentCollectionId; ///< The Akonadi ID of collection that this particular item comes from (can be virtual collection) 237 Akonadi::MessageStatus mStatus; ///< The status of the message (may be extended to groups in the future) 238 int mThisItemIndexGuess; ///< The guess for the index in the parent's child list 239 Item::Type mType : 4; ///< The type of this item 240 Item::InitialExpandStatus mInitialExpandStatus : 4; ///< The expand status we have to honor when we attach to the viewable root 241 bool mIsViewable : 1; ///< Is this item attached to the viewable root ? 242 bool mUseReceiver : 1; ///< senderOrReceiver() returns receiver rather than sender 243 }; 244 245 /** 246 * A helper class used with MessageList::Item::childItemNeedsReSorting() and 247 * MessageList::Item::insertChildItem(). 248 */ 249 class ItemSizeComparator 250 { 251 public: firstGreaterOrEqual(Item * first,Item * second)252 static inline bool firstGreaterOrEqual(Item *first, Item *second) 253 { 254 if (first->size() < second->size()) { 255 return false; 256 } 257 // When the sizes are equal compare by date too 258 if (first->size() == second->size()) { 259 return first->date() >= second->date(); 260 } 261 return true; 262 } 263 }; 264 265 /** 266 * A helper class used with MessageList::Item::childItemNeedsReSorting() and 267 * MessageList::Item::insertChildItem(). 268 */ 269 class ItemDateComparator 270 { 271 public: firstGreaterOrEqual(Item * first,Item * second)272 static inline bool firstGreaterOrEqual(Item *first, Item *second) 273 { 274 // When the dates are equal compare by subject too 275 // This is useful, for example, in kernel mailing list where people 276 // send out multiple messages with patch parts at exactly the same time. 277 if (first->date() == second->date()) { 278 return first->subject() >= second->subject(); 279 } 280 if (first->date() == static_cast<uint>(-1)) { // invalid is always smaller 281 return false; 282 } 283 if (second->date() == static_cast<uint>(-1)) { 284 return true; 285 } 286 if (first->date() < second->date()) { 287 return false; 288 } 289 return true; 290 } 291 }; 292 293 /** 294 * A helper class used with MessageList::Item::childItemNeedsReSorting() and 295 * MessageList::Item::insertChildItem(). 296 */ 297 class ItemMaxDateComparator 298 { 299 public: firstGreaterOrEqual(Item * first,Item * second)300 static inline bool firstGreaterOrEqual(Item *first, Item *second) 301 { 302 if (first->maxDate() < second->maxDate()) { 303 return false; 304 } 305 if (first->maxDate() == second->maxDate()) { 306 return first->subject() >= second->subject(); 307 } 308 return true; 309 } 310 }; 311 312 /** 313 * A helper class used with MessageList::Item::childItemNeedsReSorting() and 314 * MessageList::Item::insertChildItem(). 315 */ 316 class ItemSubjectComparator 317 { 318 public: firstGreaterOrEqual(Item * first,Item * second)319 static inline bool firstGreaterOrEqual(Item *first, Item *second) 320 { 321 const int ret = MessageCore::StringUtil::stripOffPrefixes(first->subject()) 322 .compare(MessageCore::StringUtil::stripOffPrefixes(second->subject()), Qt::CaseInsensitive); 323 if (ret < 0) { 324 return false; 325 } 326 // compare by date when subjects are equal 327 if (ret == 0) { 328 return first->date() >= second->date(); 329 } 330 return true; 331 } 332 }; 333 334 /** 335 * A helper class used with MessageList::Item::childItemNeedsReSorting() and 336 * MessageList::Item::insertChildItem(). 337 */ 338 class ItemSenderComparator 339 { 340 public: firstGreaterOrEqual(Item * first,Item * second)341 static inline bool firstGreaterOrEqual(Item *first, Item *second) 342 { 343 const int ret = first->displaySender().compare(second->displaySender(), Qt::CaseInsensitive); 344 if (ret < 0) { 345 return false; 346 } 347 // compare by date when senders are equal 348 if (ret == 0) { 349 return first->date() >= second->date(); 350 } 351 return true; 352 } 353 }; 354 355 /** 356 * A helper class used with MessageList::Item::childItemNeedsReSorting() and 357 * MessageList::Item::insertChildItem(). 358 */ 359 class ItemReceiverComparator 360 { 361 public: firstGreaterOrEqual(Item * first,Item * second)362 static inline bool firstGreaterOrEqual(Item *first, Item *second) 363 { 364 const int ret = first->displayReceiver().compare(second->displayReceiver(), Qt::CaseInsensitive); 365 if (ret < 0) { 366 return false; 367 } 368 // compare by date when receivers are equal 369 if (ret == 0) { 370 return first->date() >= second->date(); 371 } 372 return true; 373 } 374 }; 375 376 /** 377 * A helper class used with MessageList::Item::childItemNeedsReSorting() and 378 * MessageList::Item::insertChildItem(). 379 */ 380 class ItemSenderOrReceiverComparator 381 { 382 public: firstGreaterOrEqual(Item * first,Item * second)383 static inline bool firstGreaterOrEqual(Item *first, Item *second) 384 { 385 const int ret = first->displaySenderOrReceiver().compare(second->displaySenderOrReceiver(), Qt::CaseInsensitive); 386 if (ret < 0) { 387 return false; 388 } 389 // compare by date when sender/receiver are equal 390 if (ret == 0) { 391 return first->date() >= second->date(); 392 } 393 return true; 394 } 395 }; 396 397 /** 398 * A helper class used with MessageList::Item::childItemNeedsReSorting() and 399 * MessageList::Item::insertChildItem(). 400 */ 401 class ItemActionItemStatusComparator 402 { 403 public: firstGreaterOrEqual(Item * first,Item * second)404 static inline bool firstGreaterOrEqual(Item *first, Item *second) 405 { 406 if (first->status().isToAct()) { 407 if (second->status().isToAct()) { 408 return first->date() >= second->date(); 409 } 410 return true; 411 } 412 if (second->status().isToAct()) { 413 return false; 414 } 415 return first->date() >= second->date(); 416 } 417 }; 418 419 /** 420 * A helper class used with MessageList::Item::childItemNeedsReSorting() and 421 * MessageList::Item::insertChildItem(). 422 */ 423 class ItemUnreadStatusComparator 424 { 425 public: firstGreaterOrEqual(Item * first,Item * second)426 static inline bool firstGreaterOrEqual(Item *first, Item *second) 427 { 428 if (!first->status().isRead()) { 429 // fist is unread 430 if (!second->status().isRead()) { 431 return first->date() >= second->date(); // both are unread 432 } 433 // unread comes always first with respect to non-unread 434 return true; 435 } 436 if (!second->status().isRead()) { 437 return false; 438 } 439 // both are read 440 return first->date() >= second->date(); 441 } 442 }; 443 444 /** 445 * A helper class used with MessageList::Item::childItemNeedsReSorting() and 446 * MessageList::Item::insertChildItem(). 447 */ 448 class ItemImportantStatusComparator 449 { 450 public: firstGreaterOrEqual(Item * first,Item * second)451 static inline bool firstGreaterOrEqual(Item *first, Item *second) 452 { 453 if (!first->status().isImportant()) { 454 // fist is unread 455 if (!second->status().isImportant()) { 456 return first->date() >= second->date(); // both are unread 457 } 458 // unread comes always first with respect to non-unread 459 return true; 460 } 461 if (!second->status().isImportant()) { 462 return false; 463 } 464 // both are read 465 return first->date() >= second->date(); 466 } 467 }; 468 469 /** 470 * A helper class used with MessageList::Item::childItemNeedsReSorting() and 471 * MessageList::Item::insertChildItem(). 472 */ 473 class ItemAttachmentStatusComparator 474 { 475 public: firstGreaterOrEqual(Item * first,Item * second)476 static inline bool firstGreaterOrEqual(Item *first, Item *second) 477 { 478 if (!first->status().hasAttachment()) { 479 // fist is unread 480 if (!second->status().hasAttachment()) { 481 return first->date() >= second->date(); // both are unread 482 } 483 // unread comes always first with respect to non-unread 484 return true; 485 } 486 if (!second->status().hasAttachment()) { 487 return false; 488 } 489 // both are read 490 return first->date() >= second->date(); 491 } 492 }; 493 } // namespace Core 494 } // namespace MessageList 495 496