cde/programs/dtmail/dtmail/Sort.C

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   6  * These libraries and programs are free software; you can
   7  * redistribute them and/or modify them under the terms of the GNU
   8  * Lesser General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option)
  10  * any later version.
  11  *
  12  * These libraries and programs are distributed in the hope that
  13  * they will be useful, but WITHOUT ANY WARRANTY; without even the
  14  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these librararies and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  23 /*
  24  *+SNOTICE
  25  *
  26  *      $TOG: Sort.C /main/10 1998/10/22 11:25:16 mgreess $
  27  *
  28  *      RESTRICTED CONFIDENTIAL INFORMATION:
  29  *
  30  *      The information in this document is subject to special
  31  *      restrictions in a confidential disclosure agreement between
  32  *      HP, IBM, Sun, USL, SCO and Univel.  Do not distribute this
  33  *      document outside HP, IBM, Sun, USL, SCO, or Univel without
  34  *      Sun's specific written approval.  This document and all copies
  35  *      and derivative works thereof must be returned or destroyed at
  36  *      Sun's request.
  37  *
  38  *      Copyright 1993 Sun Microsystems, Inc.  All rights reserved.
  39  *
  40  *+ENOTICE
  41  */
  42
  43 #include <stdlib.h>
  44 #include <ctype.h>
  45 #include <EUSCompat.h>
  46 #include <DtMail/IO.hh>
  47 #include "Sort.hh"
  48 #include "str_utils.h"
  49
  50 //
  51 // Sort the mailbox according to 'howToSort'.
  52 //
  53 // RETURNS:
  54 //      The location of the displayed message after the sort.
  55 //
  56 int
  57 Sort::sortMessages(MsgScrollingList     *displayList,
  58                    DtMail::MailBox      *mbox,
  59                    sortBy               howToSort)
  60 {
  61   // TODO - CHECK ERROR !!!
  62   DtMailEnv              error;
  63   char                  *primary_key_str;
  64   int                    primary_key_int;
  65   int                    secondary_key_int;
  66   DtMailValueSeq        value;
  67   int                   numberMessages;
  68   MsgHndArray           *msgHandles;
  69   MsgHndArray           *deletedMsgHandles;
  70   int                   displayed;
  71   MsgStruct             *displayed_ms;
  72   DtMailBoolean         useToHeaderWhenMailIsFromMe = DTM_FALSE;
  73   passwd                pw;
  74
  75   //
  76   // Remember the displayed_ms message.
  77   //
  78   displayed = displayList->get_displayed_item();
  79   displayed_ms = displayList->get_message_struct(displayed);
  80
  81   msgHandles = displayList->get_messages();
  82   deletedMsgHandles = displayList->get_deleted_messages();
  83   if (howToSort == SortSender)
  84   {
  85       useToHeaderWhenMailIsFromMe =
  86         displayList->senderIsToHeaderWhenMailFromMe();
  87       GetPasswordEntry(pw);
  88   }
  89
  90   if (msgHandles != NULL && mbox != NULL)
  91   {
  92     //
  93     // Add in the deleted messages for the purpose of sorting.
  94     //
  95     if (NULL != deletedMsgHandles)
  96     {
  97         numberMessages = deletedMsgHandles->length();
  98         for (int i = 0; i < numberMessages; i++)
  99         {
 100             MsgStruct *ms = deletedMsgHandles->at(i);
 101             msgHandles->insert(ms);
 102         }
 103     }
 104
 105     numberMessages = msgHandles->length();
 106     if (numberMessages > 0)
 107     {
 108       //
 109       // Need list for all of the messages.
 110       // +2 for 2 artificial records R(0) and R(n+1).  See Knuth (5.2.4)
 111       // Algorithm L
 112       // In addition, the data must be placed in the array with the
 113       // dummy records at the beginning and end of the array.
 114
 115       messageRecord     * messages = new messageRecord[numberMessages +2];
 116
 117       register unsigned int     offset;
 118       register unsigned int     msgno;
 119       DtMail::Message           * msg = NULL;
 120       DtMail::Envelope  * envelope = NULL;
 121
 122       //
 123       // Get the messages from the list.
 124       //
 125       for(msgno=0 ; msgno<numberMessages; msgno++)
 126       {
 127         offset = msgno + 1;
 128
 129         //
 130         // Get the handle and envelope and header.
 131         //
 132         messages[offset].msg_struct = msgHandles->at(msgno);
 133
 134         if (howToSort != SortMsgNum)
 135         {
 136             // Don't need envelope to sort by MsgNum since that is
 137             // a front end concept
 138             msg = mbox->getMessage(error,
 139                                 messages[offset].msg_struct->message_handle);
 140
 141             if (error.isSet())
 142             {
 143                 fprintf(stderr,
 144                         "dtmail: getMessage: Could not get message # %d: %s\n",
 145                         msgno, (const char *)error);
 146             }
 147
 148             if (msg != NULL)
 149             {
 150                 envelope = msg->getEnvelope(error);
 151                 if (error.isSet())
 152                 {
 153                     fprintf(stderr,
 154                 "dtmail: getEnvelope: Could not get envelope for # %d: %s\n",
 155                             msgno, (const char *)error);
 156                 }
 157             }
 158             if (msg == NULL || envelope == NULL) continue;
 159         }
 160
 161         primary_key_str = NULL;
 162         primary_key_int = 0;
 163
 164         // Set up the secondary sort key using the received timestamp.
 165         envelope->getHeader(error, DtMailMessageReceivedTime, DTM_TRUE, value);
 166         if (error.isSet())
 167           secondary_key_int = 0;
 168         else
 169         {
 170             DtMailValueDate ds;
 171             ds = (*(value[0])).toDate();
 172             secondary_key_int = (int)ds.dtm_date;
 173         }
 174         value.clear();
 175
 176         //
 177         // The header that we will sort on depends on how we were
 178         // told to sort.
 179         //
 180         switch (howToSort)
 181         {
 182
 183         case SortSender:
 184           envelope->getHeader(error, DtMailMessageSender, DTM_TRUE, value);
 185           if (error.isSet())
 186             primary_key_str = strdup("");
 187           else
 188           {
 189               // Stole from MsgScrollingList
 190               DtMailAddressSeq  *addr_seq = (value[0])->toAddress();
 191               DtMailValueAddress *addr = (*addr_seq)[0];
 192
 193               //
 194               // If we are displaying the To: header when mail is from me,
 195               // check to see if I sent this mail and use to contents of the
 196               // To: header in place of the Sender (aka From: header).
 197               //
 198               if (DTM_TRUE == useToHeaderWhenMailIsFromMe)
 199               {
 200                   const char            *ptr;
 201                   int                   len;
 202                   DtMailValueSeq        tovalue;
 203
 204                   if (NULL != addr)
 205                   {
 206                       ptr = strchr(addr->dtm_address, '@');
 207                       if (NULL != ptr)
 208                         len = ptr - addr->dtm_address;
 209                       else
 210                         len = strlen(addr->dtm_address);
 211
 212                       if (strncmp(pw.pw_name, addr->dtm_address, len) == 0)
 213                       {
 214                           envelope->getHeader(
 215                                         error, DtMailMessageTo,
 216                                         DTM_TRUE, tovalue);
 217                           if (error.isNotSet())
 218                           {
 219                               addr_seq = (tovalue[0])->toAddress();
 220                               addr = (*addr_seq)[0];
 221                           }
 222                       }
 223                   }
 224               }
 225
 226               if (!addr)
 227                 primary_key_str = strdup("");
 228               else if (addr->dtm_person)
 229                 primary_key_str = strdup(addr->dtm_person);
 230               else
 231               {
 232                 char *str;
 233                 if (NULL != addr->dtm_address)
 234                   str = strdup(addr->dtm_address);
 235                 else
 236                   str = strdup("");
 237                 primary_key_str = strdup(str);
 238               }
 239           }
 240           break;
 241
 242         case SortSubject:
 243           envelope->getHeader(error, DtMailMessageSubject, DTM_TRUE, value);
 244           if (error.isSet())
 245             primary_key_str = strdup("");
 246           else
 247           {
 248             // Skip over "Re:, Re[n]:"
 249             const char *p;
 250
 251             p = *(value[0]);
 252             if (strncasecmp(p, "Re", 2) == 0)
 253             {
 254                 p += 2;
 255                 while (isspace(*p)) p++;
 256                 if (*p == '[')
 257                 {
 258                     p++;
 259                     while (isspace(*p)) p++;
 260                     while (isalnum(*p)) p++;
 261                     while (isspace(*p)) p++;
 262                     if (*p == ']') p++;
 263                     while (isspace(*p)) p++;
 264                 }
 265                 if (*p == ':') p++;
 266             }
 267
 268             primary_key_str = strdup(p);
 269           }
 270           break;
 271
 272         case SortSize:
 273           envelope->getHeader(
 274                         error,
 275                         DtMailMessageContentLength,
 276                         DTM_TRUE,
 277                         value);
 278           if (error.isNotSet())
 279             primary_key_int = (int) strtol(*(value[0]), NULL, 10);
 280           break;
 281
 282         case SortStatus:
 283           envelope->getHeader(error, DtMailMessageStatus, DTM_TRUE, value);
 284
 285           // Want sort order to be Read, Unread, New
 286           if (error.isSet())
 287           {
 288                 // No Status means New
 289                 primary_key_int = 2;
 290           }
 291           else
 292           {
 293                 const char *s;
 294                 s = *(value[0]);
 295
 296                 if (s == NULL) {
 297                         // New
 298                         primary_key_int = 2;
 299                 } else if (strcmp(s, "RO") == 0) {
 300                         // Read
 301                         primary_key_int = 0;
 302                 } else {
 303                         // Unread
 304                         primary_key_int = 1;
 305                 }
 306           }
 307           break;
 308
 309         case SortMsgNum:
 310           primary_key_int = messages[offset].msg_struct->sessionNumber;
 311           break;
 312
 313         case SortTimeDate:
 314           // FALLTHRU
 315         default:
 316           // Default is to use the time received timestamp setup above.
 317           primary_key_int = secondary_key_int;
 318         }
 319
 320         messages[offset].primary_key_str = primary_key_str;
 321         messages[offset].primary_key_int = primary_key_int;
 322         messages[offset].secondary_key_int = secondary_key_int;
 323
 324         value.clear();
 325       }
 326
 327       //
 328       // Sort them.
 329       //
 330       _msort((char *)messages,
 331              numberMessages,
 332              sizeof(messageRecord),
 333              0,                         // Link (offset) is at ZERO.
 334              _sortCmp);
 335
 336       //
 337       // Rearrange the pointers to msg_structs in the original MsgHndArray.
 338       //
 339       int i;
 340
 341       i = messages[0].link;
 342       for (offset = 0; offset < numberMessages ; offset++)
 343       {
 344         msgHandles->replace(offset, messages[i].msg_struct);
 345         if (messages[i].primary_key_str != NULL)
 346           free(messages[i].primary_key_str);
 347         i = messages[i].link;
 348       }
 349
 350       // Renumber the session numbers.
 351       for(msgno=0 ; msgno<numberMessages; msgno++)
 352       {
 353         MsgStruct *ms = msgHandles->at(msgno);
 354         ms->sessionNumber = msgno;
 355       }
 356
 357       // Now cleanup.
 358       delete messages;
 359     }
 360
 361     //
 362     // Remove the deleted messages.
 363     //
 364     if (NULL != deletedMsgHandles)
 365     {
 366         numberMessages = deletedMsgHandles->length();
 367         for (int i = 0; i < numberMessages; i++)
 368         {
 369             MsgStruct *ms = deletedMsgHandles->at(i);
 370             msgHandles->remove_entry(ms);
 371         }
 372     }
 373
 374     //
 375     // Figure out the new offset for displayed_ms message
 376     //
 377     numberMessages = msgHandles->length();
 378     for (int i = 0; i < numberMessages; i++)
 379     {
 380         MsgStruct *ms = msgHandles->at(i);
 381         if (ms == displayed_ms) displayed = i + 1;
 382     }
 383   }
 384
 385   return displayed;
 386 }
 387
 388 //
 389 // msort() is a list-merge sort routine generalized from Knuth (5.2.4)
 390 // Algorithm L.  This routine requires 2 artificial records: R0 and
 391 // Rn+1 where n = number of elements "nel".  "offset" is the byte-offset
 392 // of the "link" field.  "width" is the size of each record.  "base" is
 393 // the base address of the starting record (i.e. R0.)
 394 //
 395 // (Code lifted from msort.c in the original mailtool).
 396 //
 397
 398 #define Record(i)       (base + (width * (i)))
 399 #define Link(i)         (*((int *) (Record(i) + offset)))
 400
 401 Sort::_msort (char      * base,
 402               int         nel,
 403               int         width,
 404               int         offset,
 405               int       (*compar)(char  **one,
 406                                   char  **two))
 407 {
 408   register int  i;
 409   register int  t;
 410   register int  s;
 411   register int  p;
 412   register int  q;
 413   char  *k1;
 414   char  *k2;
 415
 416   if (nel < 2) {
 417     Link(0) = 1;
 418     return (0);
 419   }
 420
 421   /* Prepare two lists. */
 422   Link(0) = 1;
 423   Link(nel+1) = 2;
 424   for (i = nel - 2; i >= 1; i--) {
 425     Link(i) = -(i+2);
 426   }
 427   Link(nel-1) = 0;
 428   Link(nel) = 0;
 429
 430   while (1) {
 431     /* Begin new pass */
 432     s = 0;
 433     t = nel + 1;
 434     p = Link(s);
 435     q = Link(t);
 436     if (q == 0) {
 437       return (0);
 438     }
 439
 440         int     loopCount = 0;
 441     while (1) {
 442         loopCount++;
 443       /* Compare Kp: Kq */
 444       k1 = Record(p);
 445       k2 = Record(q);
 446       if ((*compar)(&k1, &k2) <= 0) {
 447         /* Advance p */
 448         i = abs(p);
 449         Link(s) = (Link(s) < 0) ? -i : i;
 450         s = p;
 451         p = Link(p);
 452         if (p > 0) {
 453           continue;
 454         }
 455
 456         /* Complete the sublist */
 457         Link(s) = q;
 458         s = t;
 459         do {
 460           t = q;
 461           q = Link(q);
 462         } while (q > 0);
 463       } else {
 464         /* Advance q */
 465         i = abs(q);
 466         Link(s) = (Link(s) < 0) ? -i : i;
 467         s = q;
 468         q = Link(q);
 469         if (q > 0) {
 470           continue;
 471         }
 472
 473         /* Complete the sublist */
 474         Link(s) = p;
 475         s = t;
 476         do {
 477           t = p;
 478           p = Link(p);
 479         } while (p > 0);
 480       }
 481
 482       /* End of pass? */
 483       p = -p;
 484       q = -q;
 485       if (q == 0) {
 486         i = abs(p);
 487         Link(s) = (Link(s) < 0) ? -i : i;
 488         Link(t) = 0;
 489         break;
 490       }
 491     }
 492   }
 493 }
 494
 495 //
 496 // These were used in msort() only. They are #undef'ed as a precaution only.
 497 //
 498 #undef Link
 499 #undef Record
 500
 501 //
 502 // Sort the two records.
 503 //
 504 int
 505 Sort::_sortCmp(char ** one, char ** two)
 506 {
 507   //
 508   // Cast the pointers to the known type.
 509   //
 510   register messageRecord        * first = (messageRecord *) *one;
 511   register messageRecord        * second = (messageRecord *) *two;
 512
 513   if (first->primary_key_str == NULL)
 514   {
 515     if (first->primary_key_int < second->primary_key_int)
 516       return -1;
 517     else if (first->primary_key_int > second->primary_key_int)
 518       return 2;
 519     else if (first->secondary_key_int < second->secondary_key_int)
 520       return -1;
 521     else if (first->secondary_key_int > second->secondary_key_int)
 522       return 2;
 523     else
 524       return 0;
 525   }
 526   else
 527   {
 528     int retval = strcmp(first->primary_key_str, second->primary_key_str);
 529     if (retval)
 530       return retval;
 531     else if (first->secondary_key_int < second->secondary_key_int)
 532       return -1;
 533     else if (first->secondary_key_int > second->secondary_key_int)
 534       return 2;
 535     else
 536       return 0;
 537   }
 538 }