1 #if !defined(lint) && !defined(DOS)
2 static char rcsid
[] = "$Id: sort.c 1142 2008-08-13 17:22:21Z hubert@u.washington.edu $";
6 * ========================================================================
7 * Copyright 2013-2017 Eduardo Chappa
8 * Copyright 2006-2007 University of Washington
10 * Licensed under the Apache License, Version 2.0 (the "License");
11 * you may not use this file except in compliance with the License.
12 * You may obtain a copy of the License at
14 * http://www.apache.org/licenses/LICENSE-2.0
16 * ========================================================================
19 #include "../pith/headers.h"
20 #include "../pith/sort.h"
21 #include "../pith/state.h"
22 #include "../pith/status.h"
23 #include "../pith/msgno.h"
24 #include "../pith/flag.h"
25 #include "../pith/pineelt.h"
26 #include "../pith/thread.h"
27 #include "../pith/search.h"
28 #include "../pith/pattern.h"
29 #include "../pith/util.h"
30 #include "../pith/signal.h"
31 #include "../pith/busy.h"
32 #include "../pith/icache.h"
36 * global place to store mail_sort and mail_thread results
38 struct global_sort_data g_sort
;
44 void sort_sort_callback(MAILSTREAM
*, unsigned long *, unsigned long);
45 int percent_sorted(void);
46 int pine_compare_long(const qsort_t
*, const qsort_t
*);
47 int pine_compare_long_rev(const qsort_t
*, const qsort_t
*);
48 int pine_compare_scores(const qsort_t
*, const qsort_t
*);
49 void build_score_array(MAILSTREAM
*, MSGNO_S
*);
50 void free_score_array(void);
53 /*----------------------------------------------------------------------
54 Map sort types to names
57 sort_name(SortOrder so
)
60 * Make sure the first upper case letter of any new sort name is
61 * unique. The command char and label for sort selection is
62 * derived from this name and its first upper case character.
63 * See mailcmd.c:select_sort().
65 return((so
== SortArrival
) ? "Arrival" :
66 (so
== SortDate
) ? "Date" :
67 (so
== SortSubject
) ? "Subject" :
68 (so
== SortCc
) ? "Cc" :
69 (so
== SortFrom
) ? "From" :
70 (so
== SortTo
) ? "To" :
71 (so
== SortSize
) ? "siZe" :
72 (so
== SortSubject2
) ? "OrderedSubj" :
73 (so
== SortScore
) ? "scorE" :
74 (so
== SortThread
) ? "tHread" :
79 /*----------------------------------------------------------------------
80 Sort the current folder into the order set in the msgmap
86 The idea of the deferred sort is to let the user interrupt a long sort
87 and have a chance to do a different command, such as a sort by arrival
88 or a Goto. The next newmail call will increment the deferred variable,
89 then the user may do a command, then the newmail call after that
90 causes the sort to happen if it is still needed.
93 sort_folder(MAILSTREAM
*stream
, MSGNO_S
*msgmap
, SortOrder new_sort
,
94 int new_rev
, unsigned int flags
)
96 long raw_current
, i
, j
;
97 unsigned long *sort
= NULL
;
99 char sort_msg
[MAX_SCREEN_COLS
+1];
100 SortOrder current_sort
;
104 dprint((2, "Sorting by %s%s\n",
105 sort_name(new_sort
), new_rev
? "/reverse" : ""));
110 current_sort
= mn_get_sort(msgmap
);
111 current_rev
= mn_get_revsort(msgmap
);
113 * If we were previously threading (spare == 1) and now we're switching
114 * sorts (other than just a rev switch) then erase the information
115 * about the threaded state (collapsed and so forth).
117 if(stream
&& stream
->spare
&& (current_sort
!= new_sort
))
118 erase_threading_info(stream
, msgmap
);
120 if(mn_get_total(msgmap
) <= 1L
121 && !(mn_get_total(msgmap
) == 1L
122 && (new_sort
== SortThread
|| new_sort
== SortSubject2
))){
123 mn_set_sort(msgmap
, new_sort
);
124 mn_set_revsort(msgmap
, new_rev
);
125 if(!mn_get_mansort(msgmap
))
126 mn_set_mansort(msgmap
, (flags
& SRT_MAN
) ? 1 : 0);
131 raw_current
= mn_m2raw(msgmap
, mn_get_cur(msgmap
));
133 if(new_sort
== SortArrival
){
135 * NOTE: RE c-client sorting, our idea of arrival is really
136 * just the natural sequence order. C-client, and probably
137 * rightly so, considers "arrival" the order based on the
138 * message's internal date. This is more costly to compute
139 * since it means touching the message store (say "nntp"?),
140 * so we just preempt it here.
142 * Someday c-client will support "unsorted" and do what
143 * we're doing here. That day this gets scrapped.
146 mn_set_sort(msgmap
, new_sort
);
147 mn_set_revsort(msgmap
, new_rev
);
149 if(current_sort
!= new_sort
|| current_rev
!= new_rev
||
150 any_lflagged(msgmap
, MN_EXLD
))
151 clear_index_cache(stream
, 0);
153 if(any_lflagged(msgmap
, MN_EXLD
)){
155 * BEWARE: "exclusion" may leave holes in the unsorted sort order
156 * so we have to do a real sort if that is the case.
158 qsort(msgmap
->sort
+1, (size_t) mn_get_total(msgmap
),
160 new_rev
? pine_compare_long_rev
: pine_compare_long
);
162 else if(mn_get_total(msgmap
) > 0L){
164 clear_index_cache(stream
, 0);
165 for(i
= 1L, j
= mn_get_total(msgmap
); j
>= 1; i
++, j
--)
169 for(i
= 1L; i
<= mn_get_total(msgmap
); i
++)
173 /* reset the inverse array */
174 msgno_reset_isort(msgmap
);
176 else if(new_sort
== SortScore
){
179 * We have to build a temporary array which maps raw msgno to
180 * score. We use the index cache machinery to build the array.
183 mn_set_sort(msgmap
, new_sort
);
184 mn_set_revsort(msgmap
, new_rev
);
187 /* TRANSLATORS: tell user they are waiting for Sorting of %s, the foldername */
188 snprintf(sort_msg
, sizeof(sort_msg
), _("Sorting \"%s\""),
189 strsquish(tmp_20k_buf
+ 500, 500, ps_global
->cur_folder
,
190 ps_global
->ttyo
->screen_cols
- 20));
191 we_cancel
= busy_cue(sort_msg
, NULL
, 0);
195 * We do this so that we don't have to lookup the scores with function
196 * calls for each qsort compare.
198 build_score_array(stream
, msgmap
);
200 qsort(msgmap
->sort
+1, (size_t) mn_get_total(msgmap
),
201 sizeof(long), pine_compare_scores
);
203 clear_index_cache(stream
, 0);
209 * Flip the sort if necessary (cheaper to do it once than for
210 * every comparison in pine_compare_scores.
212 if(new_rev
&& mn_get_total(msgmap
) > 1L){
213 long *ep
= &msgmap
->sort
[mn_get_total(msgmap
)],
214 *sp
= &msgmap
->sort
[1], tmp
;
224 /* reset the inverse array */
225 msgno_reset_isort(msgmap
);
229 mn_set_sort(msgmap
, new_sort
);
230 mn_set_revsort(msgmap
, new_rev
);
231 clear_index_cache(stream
, 0);
234 int (*sort_func
)() = NULL
;
237 * IMAP sort doesn't give us any way to get progress,
238 * so just spin the bar rather than show zero percent
239 * forever while a slow sort's going on...
241 if(!(stream
&& stream
->dtb
&& stream
->dtb
->name
242 && !strucmp(stream
->dtb
->name
, "imap")
243 && LEVELSORT(stream
)))
244 sort_func
= percent_sorted
;
246 snprintf(sort_msg
, sizeof(sort_msg
), _("Sorting \"%s\""),
247 strsquish(tmp_20k_buf
+ 500, 500, ps_global
->cur_folder
,
248 ps_global
->ttyo
->screen_cols
- 20));
249 we_cancel
= busy_cue(sort_msg
, sort_func
, 0);
253 * Limit the sort/thread if messages are hidden from view
254 * by lighting searched bit of every interesting msg in
255 * the folder and call c-client thread/sort to do the dirty work.
257 * Unfortunately it isn't that easy. IMAP servers are not able to
258 * handle medium to large sized sequence sets (more than 1000
259 * characters in the command line breaks some) so we have to try
260 * to handle it locally. By lighting the searched bits and
261 * providing a NULL search program we get a special c-client
262 * interface. This means that c-client will attempt to send the
263 * sequence set with the SORT or THREAD but it may get back
264 * a BAD response because of long command lines. In that case,
265 * if it is a SORT call, c-client will issue the full SORT
266 * without the sequence sets and will then filter the results
267 * locally. So sort_sort_callback will see the correctly
268 * filtered results. If it is a mail_thread call, a similar thing
269 * will be done. If a BAD is received, then there is no way to
270 * easily filter the results. C-client (in this special case where
271 * we provide a NULL search program) will set tree->num to zero
272 * for nodes of the thread tree which were supposed to be
273 * filtered out of the thread. Then pine, in sort_thread_callback,
274 * will treat those as dummy nodes (nodes which are part of the
275 * tree logically but where we don't have access to the messages).
276 * This will give us a different answer than we would have gotten
277 * if the restricted thread would have worked, but it's something.
279 * It isn't in general possible to give some shorter search set
280 * in place of the long sequence set because the long sequence set
281 * may be the result of several filter rules or of excluded
282 * messages in news (in this 2nd case maybe we could give
283 * a shorter search set).
285 * We note also that the too-long commands in imap is a general
286 * imap deficiency. It comes up in particular also in SEARCH
287 * commands. Pine likes to exclude the hidden messages from the
288 * SEARCH. SEARCH will be handled transparently by the local
289 * c-client by first issuing the full SEARCH command, if that
290 * comes back with a BAD and there is a pgm->msgno at the top
291 * level of pgm, then c-client will re-issue the SEARCH command
292 * but without the msgno sequence set in hopes that the resulting
293 * command will now be short enough, and then it will filter out
294 * the sequence set locally. If that doesn't work, it will
295 * download the messages and do the SEARCH locally. That is
296 * controllable by a flag bit.
298 for(i
= 1L; i
<= stream
->nmsgs
; i
++)
299 if((mc
= mail_elt(stream
, i
)) != NULL
)
300 mc
->searched
= !get_lflag(stream
, NULL
, i
, MN_EXLD
);
302 g_sort
.msgmap
= msgmap
;
303 if(new_sort
== SortThread
|| new_sort
== SortSubject2
){
307 * Install callback to collect thread results
308 * and update sort mapping. Problem this solves
309 * is that of receiving exists/expunged events
310 * within sort/thread response. Since we update
311 * the sorted table within those handlers, we
312 * can get out of sync when we replace possibly
313 * stale sort/thread results once the function
314 * call's returned. Make sense? Thought so.
316 mail_parameters(NULL
, SET_THREADRESULTS
,
317 (void *) sort_thread_callback
);
319 thread
= mail_thread(stream
,
320 (new_sort
== SortThread
)
321 ? "REFERENCES" : "ORDEREDSUBJECT",
324 mail_parameters(NULL
, SET_THREADRESULTS
, (void *) NULL
);
327 new_sort
= current_sort
;
328 new_rev
= current_rev
;
329 q_status_message1(SM_ORDER
, 3, 3,
330 "Sort Failed! Restored %.200s sort.",
331 sort_name(new_sort
));
335 mail_free_threadnode(&thread
);
339 * Set up the sort program.
340 * NOTE: we deal with reverse bit below.
342 g_sort
.prog
= mail_newsortpgm();
343 g_sort
.prog
->function
= (new_sort
== SortSubject
)
345 : (new_sort
== SortFrom
)
347 : (new_sort
== SortTo
)
349 : (new_sort
== SortCc
)
351 : (new_sort
== SortDate
)
353 : (new_sort
== SortSize
)
357 mail_parameters(NULL
, SET_SORTRESULTS
,
358 (void *) sort_sort_callback
);
360 /* Where the rubber meets the road. */
361 sort
= mail_sort(stream
, NULL
, NULL
, g_sort
.prog
, 0L);
363 mail_parameters(NULL
, SET_SORTRESULTS
, (void *) NULL
);
366 new_sort
= current_sort
;
367 new_rev
= current_rev
;
368 q_status_message1(SM_ORDER
, 3, 3,
369 "Sort Failed! Restored %s sort.",
370 sort_name(new_sort
));
374 fs_give((void **) &sort
);
376 mail_free_sortpgm(&g_sort
.prog
);
383 * Flip the sort if necessary (cheaper to do it once than for
384 * every comparison underneath mail_sort()
386 if(new_rev
&& mn_get_total(msgmap
) > 1L){
387 long *ep
= &msgmap
->sort
[mn_get_total(msgmap
)],
388 *sp
= &msgmap
->sort
[1], tmp
;
397 /* reset the inverse array */
398 msgno_reset_isort(msgmap
);
401 * Flip the thread numbers around.
402 * This puts us in a weird state that requires keeping track
403 * of. The direction of the thread list hasn't changed, but the
404 * thrdnos have and the display direction has.
406 * For Sort thrdno 1 thread list head
408 * thrdno . v nextthd this direction
410 * thrdno n thread list tail
412 * Rev Sort thrdno 1 thread list tail
414 * thrdno . ^ nextthd this direction
416 * thrdno n thread list head
418 if(new_sort
== SortThread
|| new_sort
== SortSubject2
){
421 thrd
= fetch_head_thread(stream
);
422 for(j
= msgmap
->max_thrdno
; thrd
&& j
>= 1L; j
--){
426 thrd
= fetch_thread(stream
,
435 /* Fix up sort structure */
436 mn_set_sort(msgmap
, new_sort
);
437 mn_set_revsort(msgmap
, new_rev
);
439 * Once a folder has been sorted manually, we continue treating it
440 * as manually sorted until it is closed.
442 if(!mn_get_mansort(msgmap
))
443 mn_set_mansort(msgmap
, (flags
& SRT_MAN
) ? 1 : 0);
445 if(!msgmap
->hilited
){
447 * If current is hidden, change current to visible parent.
448 * It can only be hidden if we are threading.
450 * Don't do this if hilited is set, because it means we're in the
451 * middle of an aggregate op, and this will mess up our selection.
452 * "hilited" means we've done a pseudo_selected, which we'll later
453 * fix with restore_selected.
456 mn_reset_cur(msgmap
, first_sorted_flagged(new_rev
? F_NONE
: F_SRCHBACK
,
458 mn_raw2m(msgmap
, raw_current
),
461 mn_reset_cur(msgmap
, mn_raw2m(msgmap
, raw_current
));
466 if(!sp_mail_box_changed(stream
))
467 sp_set_unsorted_newmail(stream
, 0);
470 * Turn off the MN_USOR flag. Don't bother going through the
471 * function call and the message number mappings.
476 for(i
= 1L; i
<= stream
->nmsgs
; i
++)
477 if((mc
= mail_elt(stream
, i
)) != NULL
&& (pelt
= mc
->sparep
) != NULL
)
484 sort_sort_callback(MAILSTREAM
*stream
, long unsigned int *list
, long unsigned int nmsgs
)
488 dprint((2, "sort_sort_callback\n"));
490 if(mn_get_total(g_sort
.msgmap
) < nmsgs
)
491 alpine_panic("Message count shrank after sort!");
493 /* copy ulongs to array of longs */
494 for(i
= nmsgs
; i
> 0; i
--)
495 g_sort
.msgmap
->sort
[i
] = list
? (long) list
[i
-1] : i
-1;
497 /* reset the inverse array */
498 msgno_reset_isort(g_sort
.msgmap
);
500 dprint((2, "sort_sort_callback done\n"));
505 * Return value for use by progress bar.
511 * C-client's sort routine exports two types of status
512 * indicators. One's the progress thru loading the cache (typically
513 * the elephantine bulk of the delay, and the progress thru the
514 * actual sort (typically qsort). Our job is to balance the two
517 return(g_sort
.prog
&& g_sort
.prog
->nmsgs
518 ? (((((g_sort
.prog
->progress
.cached
* 100)
519 / g_sort
.prog
->nmsgs
) * 9) / 10)
520 + (((g_sort
.prog
->progress
.sorted
) * 10)
521 / g_sort
.prog
->nmsgs
))
527 * This is only used at startup time. It sets ps->def_sort and
528 * ps->def_sort_rev. The syntax of the sort_spec is type[/reverse].
529 * A reverse without a type is the same as arrival/reverse. A blank
530 * argument also means arrival/reverse.
533 decode_sort(char *sort_spec
, SortOrder
*def_sort
, int *def_sort_rev
)
536 char *fix_this
= NULL
;
539 if(!sort_spec
|| !*sort_spec
){
540 *def_sort
= SortArrival
;
545 if(struncmp(sort_spec
, "reverse", strlen(sort_spec
)) == 0){
546 *def_sort
= SortArrival
;
552 if((sep
= strindex(sort_spec
, '/')) != NULL
){
556 if(struncmp(sep
, "reverse", strlen(sep
)) == 0)
564 for(x
= 0; ps_global
->sort_types
[x
] != EndofList
; x
++)
565 if(struncmp(sort_name(ps_global
->sort_types
[x
]),
566 sort_spec
, strlen(sort_spec
)) == 0)
572 if(ps_global
->sort_types
[x
] == EndofList
)
575 *def_sort
= ps_global
->sort_types
[x
];
576 *def_sort_rev
= reverse
;
581 /*----------------------------------------------------------------------
582 Compare raw message numbers
585 pine_compare_long(const qsort_t
*a
, const qsort_t
*b
)
587 long *mess_a
= (long *)a
, *mess_b
= (long *)b
, mdiff
;
589 return((mdiff
= *mess_a
- *mess_b
) ? ((mdiff
> 0L) ? 1 : -1) : 0);
593 * reverse version of pine_compare_long
596 pine_compare_long_rev(const qsort_t
*a
, const qsort_t
*b
)
598 long *mess_a
= (long *)a
, *mess_b
= (long *)b
, mdiff
;
600 return((mdiff
= *mess_a
- *mess_b
) ? ((mdiff
< 0L) ? 1 : -1) : 0);
607 * This calculate all of the scores and also puts them into a temporary array
608 * for speed when sorting.
611 build_score_array(MAILSTREAM
*stream
, MSGNO_S
*msgmap
)
613 SEARCHSET
*searchset
;
614 long msgno
, cnt
, nmsgs
, rawmsgno
;
618 nmsgs
= mn_get_total(msgmap
);
619 g_score_arr
= (long *) fs_get((nmsgs
+1) * sizeof(score
));
620 memset(g_score_arr
, 0, (nmsgs
+1) * sizeof(score
));
623 * Build a searchset that contains everything except those that have
624 * already been looked up.
627 for(msgno
=1L; msgno
<= stream
->nmsgs
; msgno
++)
628 if((mc
= mail_elt(stream
, msgno
)) != NULL
)
631 for(cnt
=0L, msgno
=1L; msgno
<= nmsgs
; msgno
++){
632 rawmsgno
= mn_m2raw(msgmap
, msgno
);
633 if(get_msg_score(stream
, rawmsgno
) == SCORE_UNDEF
634 && rawmsgno
> 0L && stream
&& rawmsgno
<= stream
->nmsgs
635 && (mc
= mail_elt(stream
, rawmsgno
))){
642 searchset
= build_searchset(stream
);
643 (void)calculate_some_scores(stream
, searchset
, 0);
644 mail_free_searchset(&searchset
);
648 * Copy scores to g_score_arr. They should all be defined now but if
649 * they aren't assign score zero.
651 for(rawmsgno
= 1L; rawmsgno
<= nmsgs
; rawmsgno
++){
652 score
= get_msg_score(stream
, rawmsgno
);
653 g_score_arr
[rawmsgno
] = (score
== SCORE_UNDEF
) ? 0L : score
;
659 free_score_array(void)
662 fs_give((void **) &g_score_arr
);
666 /*----------------------------------------------------------------------
670 pine_compare_scores(const qsort_t
*a
, const qsort_t
*b
)
672 long *mess_a
= (long *)a
, *mess_b
= (long *)b
, mdiff
;
675 return((sdiff
= g_score_arr
[*mess_a
] - g_score_arr
[*mess_b
])
676 ? ((sdiff
> 0L) ? 1 : -1)
677 : ((mdiff
= *mess_a
- *mess_b
) ? ((mdiff
> 0) ? 1 : -1) : 0));
682 reset_sort_order(unsigned int flags
)
684 long rflags
= ROLE_DO_OTHER
;
687 SortOrder the_sort_order
;
690 /* set default order */
691 the_sort_order
= ps_global
->def_sort
;
692 sort_is_rev
= ps_global
->def_sort_rev
;
694 if(ps_global
->mail_stream
&& nonempty_patterns(rflags
, &pstate
)){
695 for(pat
= first_pattern(&pstate
); pat
; pat
= next_pattern(&pstate
)){
696 if(match_pattern(pat
->patgrp
, ps_global
->mail_stream
, NULL
,
697 NULL
, NULL
, SE_NOSERVER
|SE_NOPREFETCH
))
701 if(pat
&& pat
->action
&& !pat
->action
->bogus
702 && pat
->action
->sort_is_set
){
703 the_sort_order
= pat
->action
->sortorder
;
704 sort_is_rev
= pat
->action
->revsort
;
708 sort_folder(ps_global
->mail_stream
, ps_global
->msgmap
,
709 the_sort_order
, sort_is_rev
, flags
);