#if !defined(lint) && !defined(DOS)
static char rcsid[] = "$Id: mailindx.c,v 4.116 1994/10/11 01:17:12 mikes Exp $";
#endif
/*----------------------------------------------------------------------

            T H E    P I N E    M A I L   S Y S T E M

   Laurence Lundblade and Mike Seibel
   Networks and Distributed Computing
   Computing and Communications
   University of Washington
   Administration Builiding, AG-44
   Seattle, Washington, 98195, USA
   Internet: lgl@CAC.Washington.EDU
             mikes@CAC.Washington.EDU

   Please address all bugs and comments to "pine-bugs@cac.washington.edu"

   Copyright 1989-1994  University of Washington

   USENET News reading additions in part by L Lundblade / NorthWestNet, 1993
   lgl@nwnet.net

    Permission to use, copy, modify, and distribute this software and its
   documentation for any purpose and without fee to the University of
   Washington is hereby granted, provided that the above copyright notice
   appears in all copies and that both the above copyright notice and this
   permission notice appear in supporting documentation, and that the name
   of the University of Washington not be used in advertising or publicity
   pertaining to distribution of the software without specific, written
   prior permission.  This software is made available "as is", and
   THE UNIVERSITY OF WASHINGTON DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED,
   WITH REGARD TO THIS SOFTWARE, INCLUDING WITHOUT LIMITATION ALL IMPLIED
   WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, AND IN
   NO EVENT SHALL THE UNIVERSITY OF WASHINGTON BE LIABLE FOR ANY SPECIAL,
   INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
   LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, TORT
   (INCLUDING NEGLIGENCE) OR STRICT LIABILITY, ARISING OUT OF OR IN CONNECTION
   WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  
   Pine and Pico are trademarks of the University of Washington.
   No commercial use of these trademarks may be made without prior
   written permission of the University of Washington.

   Pine is in part based on The Elm Mail System:
    ***********************************************************************
    *  The Elm Mail System  -  Revision: 2.13                             *
    *                                                                     *
    * 			Copyright (c) 1986, 1987 Dave Taylor              *
    * 			Copyright (c) 1988, 1989 USENET Community Trust   *
    ***********************************************************************
 

  ----------------------------------------------------------------------*/

/*======================================================================
    mailindx.c
    Implements the mail index screen
     - most code here builds the header list and displays it

 ====*/
 
#include "headers.h"


static struct key index_keys[] = 
     {{"?","Help",0},         {"O","OTHER CMDS",0},  {"M","Main Menu",0},
      {"V","[ViewMsg]",0},    {"P","PrevMsg",0},     {"N","NextMsg",0},
      {"-","PrevPage",0},     {"Spc","NextPage",0},  {"D","Delete",0},
      {"U","Undelete",0},     {"R","Reply",0},       {"F","Forward",0}, 

      {"?","Help",0},         {"O","OTHER CMDS",0},  {"Q","Quit",0},
      {"C","Compose",0},      {"L","ListFldrs",0},   {"G","GotoFldr",0},
      {"Tab","NextNew",0},    {"W","WhereIs",0},     {"Y","prYnt",0},
      {"T","TakeAddr",0},     {"S","Save",0},        {"E","Export",0},

      {"?","Help",0},         {"O","OTHER CMDS",0},  {"X",NULL,0},
      {"&","unXclude",0},     {";","Select",0},	     {"A","Apply",0},
      {"$","SortIndex",0},    {"J","Jump",0},        {"H","HdrMode",0},
      {"B","Bounce",0},       {"*","Flag",0},        {"|","Pipe",0},

      {"?","Help",0},         {"O","OTHER CMDS",0},  {NULL,NULL,0},
      {"Z","ZoomMode",0},     {NULL,NULL,0},	     {NULL,NULL,0},
      {NULL,NULL,0},	      {NULL,NULL,0},	     {NULL,NULL,0},
      {NULL,NULL,0},	      {NULL,NULL,0},	     {NULL,NULL,0}};
static struct key_menu index_keymenu = {0,0,0,0,0,0, index_keys};
#define PREVM_KEY 4
#define NEXTM_KEY 5
#define EXCLUDE_KEY 26
#define UNEXCLUDE_KEY 27
#define SELECT_KEY 28
#define APPLY_KEY 29
#define VIEW_FULL_HEADERS_KEY 32
#define BOUNCE_KEY 33
#define FLAG_KEY 34
#define VIEW_PIPE_KEY 35
#define ZOOM_KEY 39

static struct key nr_anon_index_keys[] = 
       {{"?","Help",0},      {"W","WhereIs", 0},      {"Q","Quit",0},
        {"V","[ViewMsg]",0}, {"P","PrevMsg",0},       {"N","NextMsg",0},
        {"-","PrevPage",0},  {"Spc","NextPage",0},    {"F","Fwd Email",0},
        {"J","Jump",0},      {"$","SortIndex",0},     {NULL,NULL,0}}; 
static struct key_menu nr_anon_index_keymenu = {sizeof(nr_anon_index_keys)/(sizeof(nr_anon_index_keys[0])*12), 0, 0,0,0,0, nr_anon_index_keys};

static struct key nr_index_keys[] = 
       {{"?","Help",0},      {"O","OTHER CMDS",0},    {"Q","Quit",0},
        {"V","[ViewMsg]",0}, {"P","PrevMsg",0},       {"N","NextMsg",0},
        {"-","PrevPage",0},  {"Spc","NextPage",0},    {"F","Fwd Email",0},
        {"J","Jump",0},      {"Y","prYnt",0},         {"S","Save",0}, 

        {"?","Help",0},      {"O","OTHER CMDS",0},    {"E","Export",0},
        {"C","Compose",0},   {"$","SortIndex",0},     {NULL,NULL,0},
        {NULL,NULL,0},       {"W","WhereIs",0},       {NULL,NULL,0},
        {NULL,NULL,0},       {NULL,NULL,0},           {NULL,NULL,0}};
static struct key_menu nr_index_keymenu = {sizeof(nr_index_keys)/(sizeof(nr_index_keys[0])*12), 0, 0,0,0,0, nr_index_keys};
  
static struct key simple_index_keys[] = 
       {{"?","Help",0},      {NULL,NULL, 0},       {"E","ExitSelect",0},
        {"S","[Select]",0},  {"P","PrevMsg",0},    {"N","NextMsg",0},
        {"-","PrevPage",0},  {"Spc","NextPage",0}, {NULL,NULL,0},
        {NULL,NULL,0},       {NULL,NULL,0}   ,     {NULL,NULL,0}}; 
static struct key_menu simple_index_keymenu = {sizeof(simple_index_keys)/(sizeof(simple_index_keys[0])*12), 0, 0, 0, 0, 0, simple_index_keys};


static OtherMenu what_keymenu = FirstMenu;


/*-----------
  Saved state to redraw message index body 
  ----*/
struct entry_state {
    unsigned short hilite:1;
    unsigned short bolded:1;
    long     id;
};


static struct index_state {
    long        msg_at_top,
	        lines_per_page;
    struct      entry_state *entry_state;
    MSGNO_S    *msgmap;
    MAILSTREAM *stream;
} *current_index_state = NULL;


/*
 * cache used by get_sub() so it doesn't have to do a fetchstructure
 * and malloc/free for every qsort comparison...
 */
#if	defined(DOS) && !defined(_WINDOWS)
#define	SUB_CACHE_LEN	128
typedef struct {
    short used;				/* whether entry's been used or not */
    char  buf[SUB_CACHE_LEN];		/* actual subject string */
} scache_ent;


static struct scache {
    short	last;			/* last one referenced */
    long	size,			/* number of elements */
		msgno[2];		/* which message in which entry */
    scache_ent  ent[2];			/* subject and cache info for msg */
    char       *cname;			/* file containing cache */
    FILE       *cfile;
} *scache = NULL;
#else
static struct scache {
    long   size;
    char **ent;
} *scache = NULL;
#endif



#ifdef ANSI
void     update_index(struct pine *, struct index_state *);
long     top_ent_calc(MAILSTREAM *, MSGNO_S *, long, long);
char    *get_sub(long);
int      compare_subjects(const QSType *, const QSType *);
int      compare_subject_2(const QSType *, const QSType *);
int      compare_from(const QSType *, const QSType *);
int      compare_to(const QSType *, const QSType *);
int      compare_cc(const QSType *, const QSType *);
int      compare_message_dates(const QSType *, const QSType *);
int      compare_size(const QSType *, const QSType *);
int      compare_arrival(const QSType *, const QSType *);
HLINE_S *get_index_cache(long);
long	 line_hash(char *);
int      i_cache_size(long);
int      i_cache_width();
void	 msgno_flush_selected(MSGNO_S *, long);
void	 second_subject_sort(long *, long, long);
void	 init_subject_cache(long);
int	 subject_cache_slot(long);
char	*subject_cache_ent(long);
char	*subject_cache_add(long, char *);
void	 clear_subject_cache();
#ifdef	DOS
void     i_cache_hit(long);
void     icread(void);
void	 icwrite(void);
#endif

#else
void     update_index();
long	 top_ent_calc();
char    *get_sub();
HLINE_S *get_index_cache();
long	 line_hash();
int	 i_cache_size();
int	 i_cache_width();
void	 msgno_flush_selected();
void	 second_subject_sort();
void	 init_subject_cache();
int	 subject_cache_slot();
char	*subject_cache_ent();
char	*subject_cache_add();
void	 clear_subject_cache();

#endif
void	 sort_blip();




/*----------------------------------------------------------------------


  ----*/
void
do_index_border(cntxt, folder, stream, msgmap, style, which_keys, flags)
     CONTEXT_S   *cntxt;
     char        *folder;
     MAILSTREAM  *stream;
     MSGNO_S     *msgmap;
     IndexType    style;
     int         *which_keys, flags;
{
    if(flags & INDX_CLEAR)
      ClearScreen();

    if(flags & INDX_HEADER)
      set_titlebar((stream == ps_global->mail_stream)
		     ? (style == MsgIndex || style == MultiMsgIndex)
		         ? "FOLDER INDEX"
			 : "ZOOMED FOLDER INDEX"
		     : (!strcmp(folder, INTERRUPTED_MAIL))
			 ? "COMPOSE: SELECT INTERRUPTED"
			 : "COMPOSE: SELECT POSTPONED",
		   stream, cntxt, folder, msgmap, 1, MessageNumber, 0, 0);

    if(flags & INDX_FOOTER) {
	struct key_menu *km;
	bitmap_t	 bitmap;

	setbitmap(bitmap);
	if(ps_global->anonymous)
	  km = &nr_anon_index_keymenu;
	else if(ps_global->nr_mode)
          km = &nr_index_keymenu;
	else if(ps_global->mail_stream != stream)
	  km = &simple_index_keymenu;
	else{
	    km = &index_keymenu;

#ifndef DOS
	    if(F_OFF(F_ENABLE_PIPE,ps_global))
#endif
	      clrbitn(VIEW_PIPE_KEY, bitmap);  /* always clear for DOS */
	    if(F_OFF(F_ENABLE_FULL_HDR,ps_global))
	      clrbitn(VIEW_FULL_HEADERS_KEY, bitmap);
	    if(F_OFF(F_ENABLE_BOUNCE,ps_global))
	      clrbitn(BOUNCE_KEY, bitmap);
	    if(F_OFF(F_ENABLE_FLAG,ps_global))
	      clrbitn(FLAG_KEY, bitmap);
	    if(F_OFF(F_ENABLE_AGG_OPS,ps_global) || style == ZoomIndex){
		clrbitn(SELECT_KEY, bitmap);
		clrbitn(APPLY_KEY, bitmap);

		/*
		 * Since "Zoom" is alone on the last keymenu page
		 * if it's not enabled, hide that menu altogether
		 */
		if(style != ZoomIndex){
		    clrbitn(ZOOM_KEY, bitmap);
		    km->how_many = 3;
		}
		else
		  km->how_many = 4;
	    }
	    else
	      km->how_many = 4;

	    if(IS_NEWS(stream))
	      index_keys[EXCLUDE_KEY].label = "eXclude";
	    else {
		clrbitn(UNEXCLUDE_KEY, bitmap);
		index_keys[EXCLUDE_KEY].label = "eXpunge";
	    }

	    if(style == MultiMsgIndex){
		clrbitn(PREVM_KEY, bitmap);
		clrbitn(NEXTM_KEY, bitmap);
	    }
	}
        draw_keymenu(km, bitmap, ps_global->ttyo->screen_cols,
						-2, 0, what_keymenu, 0);
	what_keymenu = SameTwelve;
	if(which_keys)
	  *which_keys = km->which;  /* pass back to caller */
    }
}

      
    
/*----------------------------------------------------------------------
        Main loop executing commands for the mail index screen

   Args: state -- the pine_state structure for next/prev screen pointers
                  and to pass to the index manager...
 ----*/

void
mail_index_screen(state)
     struct pine *state;
{
    dprint(1, (debugfile, "\n\n ---- MAIL INDEX ----\n"));
    if(!state->mail_stream) {
	q_status_message(0, 1, 3, "No folder is currently open");
        state->prev_screen = mail_index_screen;
	state->next_screen = main_menu_screen;
	return;
    }

    index_lister(state, state->context_current, state->cur_folder,
		 state->mail_stream, state->msgmap);
    state->prev_screen = mail_index_screen;
}



/*----------------------------------------------------------------------
        Main loop executing commands for the mail index screen

   Args: state -- pine_state structure for display flags and such
         msgmap -- c-client/pine message number mapping struct
 ----*/

int
index_lister(state, cntxt, folder, stream, msgmap)
     struct pine *state;
     CONTEXT_S   *cntxt;
     char        *folder;
     MAILSTREAM  *stream;
     MSGNO_S     *msgmap;
{
    int		 ch, orig_ch, which_keys, force;
    long	 i, j, k;
    IndexType    style, old_style = MsgIndex;
    struct index_state index_state;
#ifdef	DOS
    extern void (*while_waiting)();
#endif

    dprint(1, (debugfile, "\n\n ---- INDEX MANAGER ----\n"));
    
    ch                    = 'x';	/* For displaying msg 1st time thru */
    force                 = 0;
    state->mangled_screen = 1;
    what_keymenu          = FirstMenu;
    memset((void *)&index_state, 0, sizeof(struct index_state));
    index_state.msgmap    = msgmap;

    if((index_state.stream = stream) != state->mail_stream)
      clear_index_cache();	/* BUG: should better tie stream to cache */

    while (1) {
	/*------- Check for new mail -------*/
        new_mail(NULL,force,ch == NO_OP_IDLE ? 0 : ch == NO_OP_COMMAND ? 1:2);
	force = 0;			/* may not need to next time around */

        if(streams_died())
          state->mangled_header = 1;

        if(state->mangled_screen) {
            state->mangled_header = 1;
            state->mangled_body   = 1;
            state->mangled_footer = 1;
            state->mangled_screen = 0;
            if(!state->painted_footer_on_startup)
	      ClearScreen();
        }

	/*
	 * events may have occured that require us to shift from
	 * mode to another...
	 */
	style = (any_lflagged(msgmap, MN_HIDE))
		  ? ZoomIndex
		  : (mn_total_cur(msgmap) > 1L) ? MultiMsgIndex : MsgIndex;
	if(style != old_style){
            state->mangled_header = 1;
            state->mangled_footer = 1;
	    old_style = style;
	}

        /*------------ Update the title bar -----------*/
	if(state->mangled_header) {
            do_index_border(cntxt, folder, stream, msgmap, style, NULL,
			    INDX_HEADER);
	    state->mangled_header = 0;
	} 
	else if(mn_get_total(msgmap) > 0) {
	    /*
	     * No fetchstructure necessary befor mail_elt as the elt's
	     * should have been loaded with the correct flags when we did
	     * a fetchflags as part of get_lflags the first time we painted
	     * the index...
	     */
	    update_titlebar_message(msgmap);
            update_titlebar_status(mail_elt(stream, mn_m2raw(msgmap,
							 mn_get_cur(msgmap))));
	}

        /*------------ draw the index body ---------------*/
	update_index(state, &index_state);
        ps_global->redrawer = redraw_index_body;
	current_index_state = &index_state;

        /*------------ draw the footer/key menus ---------------*/
	if(state->mangled_footer) {
            if(!state->painted_footer_on_startup)
              do_index_border(cntxt, folder, stream, msgmap, style,
			      &which_keys, INDX_FOOTER);

	    state->mangled_footer = 0;
	}

        state->painted_body_on_startup   = 0;
        state->painted_footer_on_startup = 0;

	/*-- Display any queued message (eg, new mail, command result --*/
        display_message(ch);
	MoveCursor(state->ttyo->screen_rows - 3, 0);

        /* Let read_command do the fflush(stdout) */

        /*---------- Read command and validate it ----------------*/
#ifdef	DOS
#ifdef	MOUSE
	if(stream == ps_global->mail_stream){
	    extern int register_mfunc();
	    extern unsigned long mouse_in_index();

	    register_mfunc(mouse_in_index, 2, 0, state->ttyo->screen_rows-4,
			   state->ttyo->screen_cols);
	}
#endif
	/*
	 * AND pre-build header lines.  This works just fine under
	 * DOS since we wait for characters in a loop. Something will
         * will have to change under UNIX if we want to do the same.
	 */
	while_waiting = build_header_cache;
#ifdef	_WINDOWS
	mswin_allowexit (MSWIN_EXIT_SENDCHAR, NULL,
			 F_ON(F_USE_FK, ps_global) ? OPF3 : 'q');
#endif
#endif
	ch = read_command();
#ifdef	DOS
	while_waiting = NULL;
#ifdef	MOUSE
	if(stream == ps_global->mail_stream){
	    extern void clear_mfunc();
	    clear_mfunc();
	}
#endif
#ifdef	_WINDOWS
	mswin_allowexit (MSWIN_EXIT_DENY, "Complete current operation", '\0');
#endif
#endif

        orig_ch = ch;

	if(ch < 0x0100 && isupper(ch))		/* force lower case */
	  ch = tolower(ch);
	else if(ch >= PF1 && ch <= PF12 && which_keys > 0 && which_keys < 4)
	  ch = (which_keys == 1) ? PF2OPF(ch) :	/* map f-key to menu page */
		(which_keys == 2) ? PF2OOPF(ch) : PF2OOOPF(ch);

	ch = validatekeys(ch);

	/*----------- Execute the command ------------------*/
	switch(ch) {

            /*---------- Roll keymenu ----------*/
          case PF2:
          case OPF2:
          case OOPF2:
          case OOOPF2:
	  case 'o':
            if(ps_global->anonymous) {
	      if(ch == PF2)
		ch = 'w';
              goto df;
	    }
            if(ch == 'o')
	      warn_other_cmds();
	    what_keymenu = NextTwelve;
	    state->mangled_footer = 1;
	    break;


            /*---------- Scroll back up ----------*/
	  case PF7:
	  case '-' :
          case ctrl('Y'): 
	  case KEY_PGUP:
	    j = -1L;
	    for(k = i = index_state.msg_at_top; ; i--){
		if(!get_lflag(stream, msgmap, i, MN_HIDE)){
		    k = i;
		    if(++j >= index_state.lines_per_page){
			if((index_state.msg_at_top = i) == 1L)
			  q_status_message(0, 0, 1, "First Index page");

			break;
		    }
	       }

		if(i <= 1L){
		    if(mn_get_cur(msgmap) == 1L)
		      q_status_message(0, 0, 1, "Already at start of Index");

		    break;
		}
	    }

	    if(mn_total_cur(msgmap) == 1L)
	      mn_set_cur(msgmap, k);

	    break;


            /*---------- Scroll forward, next page ----------*/
	  case PF8:  /* NEXT PAGE */
	  case '+':
          case ctrl('V'): 
	  case KEY_PGDN:
	  case ' ':
	    j = -1L;
	    for(k = i = index_state.msg_at_top; ; i++){
		if(!get_lflag(stream, msgmap, i, MN_HIDE)){
		    k = i;
		    if(++j >= index_state.lines_per_page){
			if(i+index_state.lines_per_page>=mn_get_total(msgmap))
			  q_status_message(0, 0, 1, "Last Index page");

			index_state.msg_at_top = i;
			break;
		    }
		}

		if(i >= mn_get_total(msgmap)){
		    if(mn_get_cur(msgmap) == k)
		      q_status_message(0, 0, 1, "Already at end of Index");

		    break;
		}
	    }

	    if(mn_total_cur(msgmap) == 1L)
	      mn_set_cur(msgmap, k);

	    break;


            /*---------- Suspend Pine ----------*/
          case ctrl('Z'):
            if(!have_job_control())
              goto df;

            if(F_OFF(F_CAN_SUSPEND, ps_global)) {
                q_status_message(1, 1, 3,
                            "\007Pine suspension not enabled - see help text");
                break;
            }
	    else
	      do_suspend(state);
            /*-- Fall through to redraw --*/

            /*---------- Redraw/resize ----------*/
          case KEY_RESIZE:
	  case ctrl('L'):
            state->mangled_screen = 1;		/* force repaint and... */
	    if(ch == KEY_RESIZE)
	      clear_index_cache();		/* don't flush on ^L or ^Z */
	    else
	      force = 1;			/* check for new mail on ^L */

            break;


            /*---------- No op command ----------*/
          case NO_OP_IDLE:
	  case NO_OP_COMMAND:
            break;	/* no op check for new mail */


            /*---------- Default -- all other command ----------*/
          default:
          df:
	    if(stream == state->mail_stream){
		process_cmd(state, msgmap, ch,
			    (style == MsgIndex || style == MultiMsgIndex)?1:2,
			    orig_ch, &force);
		if(state->next_screen != SCREEN_FUN_NULL){
		    current_index_state = NULL;
		    if(index_state.entry_state)
		      fs_give((void **)&(index_state.entry_state));

		    return(0);
		}
		else{
		    if(stream != state->mail_stream){
			/*
			 * Must have had an failed open.  repair our
			 * pointers...
			 */
			index_state.stream = stream = state->mail_stream;
			index_state.msgmap = msgmap = state->msgmap;
		    }

		    current_index_state = &index_state;
		}
	    }
	    else{			/* special processing */
		switch(ch){
		  case '?':		/* help! */
		  case PF1:
		    helper(h_simple_index,
			   (!strcmp(folder, INTERRUPTED_MAIL))
			     ? "HELP FOR SELECTING INTERRUPTED MSG"
			     : "HELP FOR SELECTING POSTPONED MSG",
			   1);
		    state->mangled_screen = 1;
		    break;

		  case 'e':		/* exit */
		  case 'E':
		  case PF3:
		    return(1);
		    break;

		  case 's':		/* select */
		  case ctrl('M'):
		  case ctrl('J'):
		  case PF4:
		    return(0);

		  case 'p':		/* previous */
		  case ctrl('P'):
		  case KEY_UP:
		  case PF5:
		    mn_dec_cur(stream, msgmap);
		    break;

		  case 'n':		/* next */
		  case ctrl('N'):
		  case KEY_DOWN:
		  case PF6:
		    mn_inc_cur(stream, msgmap);
		    break;

		  default :
		    bogus_command(ch, NULL);
		    break;
		}
	    }
	}				/* The big switch */
    }					/* the BIG while loop! */
}



/*----------------------------------------------------------------------
  Manage index body painting

  Args: state - pine struct containing selected message data
	index_state - struct describing what's currently displayed

  Returns: none.

  The idea is pretty simple.  Maintain an array of index line id's that
  are displayed and their hilited state.  Decide what's to be displayed
  and update the screen appropriately.  All index screen painting
  is done here.  Pretty simple, huh?
 ----*/
void
update_index(state, screen)
     struct pine         *state;
     struct index_state  *screen;
{
    long     i, n;

    if(!screen)
      return;

#ifdef _WINDOWS
    mswin_beginupdate();
#endif

    /*---- reset the works if necessary ----*/
    if(state->mangled_body && screen->entry_state){
	fs_give((void **)&(screen->entry_state));
	screen->lines_per_page = 0;
    }

    state->mangled_body = 0;

    /*---- make sure we have a place to write state ----*/
    if(screen->lines_per_page != max(0, state->ttyo->screen_rows - 5)){
	int old = screen->lines_per_page;
	screen->lines_per_page = max(0, state->ttyo->screen_rows - 5);
	if(!old){
	    size_t len = screen->lines_per_page * sizeof(struct entry_state);
	    screen->entry_state = (struct entry_state *) fs_get(len);
	}
	else
	  fs_resize((void **)&(screen->entry_state),
		    (size_t)screen->lines_per_page);

	for(; old < screen->lines_per_page; old++)	/* init new entries */
	  screen->entry_state[old].id = -1;
    }

    /*---- figure out the first message on the display ----*/
    screen->msg_at_top = top_ent_calc(screen->stream, screen->msgmap,
				      screen->msg_at_top,
				      screen->lines_per_page);

    /*---- march thru display lines, painting whatever is needed ----*/
    for(i = 0L, n = screen->msg_at_top; i < screen->lines_per_page; i++){
	if(n < 1 || n > mn_get_total(screen->msgmap)){
	    if(screen->entry_state[i].id){
		screen->entry_state[i].hilite = 0;
		screen->entry_state[i].bolded = 0;
		screen->entry_state[i].id     = 0L;
		MoveCursor(2 + (int)i, 0);
		CleartoEOLN();
	    }
	}
	else{
	    int      cur = mn_is_cur(screen->msgmap, n),
		     sel = get_lflag(screen->stream,screen->msgmap,n,MN_SLCT);
	    HLINE_S *h   = build_header_line(screen->stream,screen->msgmap,n);

	    if(h->id != screen->entry_state[i].id
	       || (cur != screen->entry_state[i].hilite)
	       || (sel != screen->entry_state[i].bolded)){
		MoveCursor(2 + (int)i, 0);
		if(F_ON(F_FORCE_LOW_SPEED,ps_global) || ps_global->low_speed){
		    Writechar((sel) ? 'X' :
			        (cur && h->line[0] == ' ') ? '-' :
			          h->line[0], 0);
		    Writechar((cur) ? '>' : h->line[1], 0);

		    if(h->id != screen->entry_state[i].id)
		      PutLine0(2 + (int)i, 2, &h->line[2]);
		}
		else{
		    char *draw = h->line;

		    if(cur)
		      StartInverse();

		    if(sel && (F_OFF(F_SELECTED_SHOWN_BOLD, state)
			       || !StartBold())){
			Writechar('X', 0);
			draw++;
		    }

		    Write_to_screen(draw);

		    if(sel && draw == h->line)		/* wrote 'X'? */
		      EndBold();

		    if(cur)
		      EndInverse();
		}
	    }

	    screen->entry_state[i].hilite = cur;
	    screen->entry_state[i].bolded = sel;
	    screen->entry_state[i].id     = h->id;
	}

	/*--- increment n ---*/
	while(++n <= mn_get_total(screen->msgmap)
	      && get_lflag(screen->stream, screen->msgmap, n, MN_HIDE))
	  ;
    }

#ifdef _WINDOWS
    mswin_endupdate();
#endif
    fflush(stdout);
}



/*----------------------------------------------------------------------
     Calculate the message number that should be at the top of the display

  Args: current - the current message number
        lines_per_page - the number of lines for the body of the index only

  Returns: -1 if the current message is -1 
           the message entry for the first message at the top of the screen.

When paging in the index it is always on even page boundies, and the
current message is always on the page thus the top of the page is
completely determined by the current message and the number of lines
on the page. 
 ----*/
long
top_ent_calc(stream, msgs, at_top, lines_per_page)
     MAILSTREAM *stream;
     MSGNO_S *msgs;
     long     at_top, lines_per_page;
{
    long current;

    current = (mn_total_cur(msgs) <= 1L) ? mn_get_cur(msgs) : at_top;

    if(current < 0L)
      return(-1);

    if(lines_per_page == 0L)
      return(current);

    if(any_lflagged(msgs, (MN_HIDE|MN_EXLD))){
	long n, m = 0L, t = 1L;

	for(n = 1L; n <= mn_get_total(msgs); n++)
	  if(!get_lflag(stream, msgs, n, MN_HIDE)
	     && (++m % lines_per_page) == 1L){
	      if(n > current)
		break;

	      t = n;
	  }

	return(t);
    }
    else
      return(lines_per_page * ((current - 1L)/ lines_per_page) + 1L);
}


/*----------------------------------------------------------------------
    This redraws the body of the index screen possibly taking into
account and changes in the size of the screen. All the state needed to
repaint is in the static variables so this can be called from
anywhere.
 ----*/
void
redraw_index_body()
{
    ps_global->mangled_body = 1;
    update_index(ps_global, current_index_state);
}



/*----------------------------------------------------------------------
      Create a string summarizing the message header for index on screen

   Args: stream -- mail stream to fetch envelope info from
	 msgmap -- message number to pine sort mapping
	 msgno  -- Message number to create line for

  Result: returns a malloced string
          saves string in a cache for next call for same header
 ----*/

HLINE_S *
build_header_line(stream, msgmap, msgno)
     MAILSTREAM *stream;
     MSGNO_S    *msgmap;
     long        msgno;
{
    ENVELOPE     *envelope;
    MESSAGECACHE *cache;
    ADDRESS      *addr;
    int           status_length, size_length, subject_length, from_length;
    char          status[20], from[MAX_SCREEN_COLS/2+1], size[12],
                  subject[MAX_SCREEN_COLS+1], to_us;
    char         *s, *s_tmp, *buffer;
    HLINE_S      *hline;
    struct date   d;


    dprint(8, (debugfile, "=== build_header_line (%ld) called ===\n", msgno));

    if(*(buffer = (hline = get_index_cache(msgno))->line) != '\0') {
        dprint(9, (debugfile, "Returning %p -> <%s (%d), %ld>\n",
		   hline, buffer, strlen(buffer), hline->id));
	return(hline);
    }

    envelope = mail_fetchstructure(stream, mn_m2raw(msgmap, msgno), NULL);
    cache    = mail_elt(stream, mn_m2raw(msgmap, msgno));
    if(!envelope || !cache) {
        sprintf(buffer,"    %-3ld", msgno);
	hline->id = line_hash(buffer);
        return(hline);
    }

    /*
     * check that the envelope returned has something to display.
     * if empty, indicate that no message info found...
     */
    if(!envelope->remail && !envelope->return_path && !envelope->date &&
       !envelope->from && !envelope->sender && !envelope->reply_to &&
       !envelope->subject && !envelope->to && !envelope->cc &&
       !envelope->bcc && !envelope->in_reply_to && !envelope->message_id &&
       !envelope->newsgroups){
	sprintf(buffer,"    %-3ld        %-*.*s", msgno,
		max(i_cache_width()-15, 0), max(i_cache_width()-15, 0),
		"[ No Message Text Available ]");
	hline->id = line_hash(buffer);
	return(hline);
    }

    /*------------------------------------------------------
       Four parts:
          status:  arrow cursor, date, msgno, status, 15 chars unless more
		     than 3 digits in msgno
          from:    may show To:, always at least 18 chars, half of space over
		     80 is used for this field
          size:    currently in bytes up to 99K, always 10 chars
                     when line counts become available, always 8 chars
          subject: uses up all the leftover space
 over all minimum: 80 chars 
       ----------------------------------------------------------------------*/

    /*-- status --*/
    parse_date(envelope->date, &d);
    to_us = (cache->flagged) ? '*' : ' ';
    for(addr = envelope->to; addr && to_us == ' '; addr = addr->next)
      if(address_is_us(addr, ps_global))
	to_us = '+';

#ifdef	LATER
    if(to_us == ' '){				/* look for reset-to */
	char    *fields[2], *resent, *p;
	ADDRESS *resent_addr = NULL;

	fields[0] = "Resent-To";
	fields[1] = NULL;
	resent = xmail_fetchheader_lines(stream,mn_m2raw(msgmap,msgno),fields);
	if(resent){
	    if(p = strchr(resent, ':')){
		for(++p; *p && isspace(*p); p++)
		  ;

		removing_trailing_white_space(p);
		rfc822_parse_adrlist(&resent_addr, p, ps_global->maildomain);
		for(addr = resent_addr; addr && to_us == ' '; addr=addr->next)
		  if(address_is_us(addr, ps_global))
		    to_us = '+';

		mail_free_address(&resent_addr);
	    }

	    fs_give((void **)&resent);
	}
    }
#endif

    sprintf(status, "%c %s %-3ld %s %2d ", to_us, status_string(stream, cache),
	    msgno, month_abbrev(d.month), d.day);
    status_length = strlen(status);

    /*--- from ---*/
    if(!ps_global->nr_mode) {
	ADDRESS *addr = envelope->to ? envelope->to
				     : envelope->cc ? envelope->cc : NULL;
        from_length = 18 + max(0, ps_global->ttyo->screen_cols - 80 + 1)/2;
        if(addr &&
	   (!envelope->from || address_is_us(envelope->from, ps_global))) {
            char    *a_string = addr_list_string(addr);
	    sprintf(from, "To: %-*.*s", from_length - 4, from_length - 4,
                    a_string);
	    fs_give((void **)&a_string);
        }
	else
	  mail_fetchfrom(from, stream, mn_m2raw(msgmap, msgno),
			 (long)from_length);
    }
    else
      from[0] = '\0';

    from_length = strlen(from);

    /*--- size ---*/
    if(!ps_global->nr_mode && stream->mailbox[0] != '*'){
        if(cache->rfc822_size < 100000) {
            s_tmp = comatose(cache->rfc822_size);
            sprintf(size, " %-*.*s(%s) ", 6 - strlen(s_tmp),
                6 - strlen(s_tmp), "       ", s_tmp);
        } else if(cache->rfc822_size < 10000000) {
            s_tmp = comatose(cache->rfc822_size/1000);
            sprintf(size, " %-*.*s(%sK) ", 5 - strlen(s_tmp),
                5 - strlen(s_tmp), "       ", s_tmp);
        } else {
            strcpy(size, "  (****)");
        }
    } else {
        size[0] = ' ';
        size[1] = '\0';
    }
    size_length = strlen(size);

        
    /*-- subject --*/
    subject_length = max(ps_global->ttyo->screen_cols, 80) -
			          status_length - from_length - size_length;
    dprint(9, (debugfile, "subject_length : %d\n", subject_length));
    mail_fetchsubject(subject, stream,  mn_m2raw(msgmap, msgno),
		      (long)subject_length);
    for(s = subject + strlen(subject); s < subject + subject_length; s++)
      *s = ' ';
    *s = '\0';
    dprint(9, (debugfile, "strlen(subject : %d\n", strlen(subject)));

    /*--- Put them all together ---*/
    sprintf(buffer, "%s%s%s%s", status, from, size, subject);
    /* Truncate it to proper size */
    buffer[min(ps_global->ttyo->screen_cols, i_cache_width())] = '\0';
    hline->id = line_hash(buffer);
    dprint(9, (debugfile, "Returning %p -> <%s (%d), %ld>\n",
	       hline, buffer, strlen(buffer), hline->id));
    return(hline);
}


long
line_hash(s)
     char *s;
{
    register long xsum = 0L;

    while(*s)
      xsum = ((((xsum << 4) & 0xffffffff) + (xsum >> 24)) & 0x0fffffff) + *s++;

    return(xsum ? xsum : 1L);
}


/*-----
  The following are used to report on sorting progress to the user

This code is not ideal as it varies depending on how the mail driver
performs with respect to fetching envelopes.  For some c-client drivers
the initial fetch of the envelope is expensive and it is cached after
that. For others every fetch is expensive.  The code here deals with
with the case were only the first fetch is expensive. It reports
progress based on how many messages have been fetched, assuming the sort
will complete very rapidly when all the messages have been fetched. 

DISPLAY_COUNT is the number of compares to wait before checking to see
if time has elapsed to output another status message. This is mostly
for the sake of efficiency.

There is also a bit map that keeps track of which messages have been
fetched that is used to keep an accurate count of the number of messages
that have been fetched. The sort algorithm fetched envelopes in a random
order and possibly many times. 

For c-client drivers for which every fetch envelope is expensive, this
algorithm will quickly (well maybe quickly) report that the sort is
100% complete and continue sorting for a lot longer.  Sorting in this
case is actually pretty impractical in the first place, but it may be
possible to roughly predict how long the sort will take. For example
the number of comparison for qsort is roughly n * log(n). A prediction
of 1.5 * n * log(n) might be reasonably accurate. Randomizing the
order before the messages are sorted will make the prediction more
accurate, and the search time more uniform. 

  ----*/
#define    DISPLAY_COUNT  20
static long compare_count = 0;
static long last_mess;
static int  mess_count;

#ifndef DOS
/* Bit map for keeping track of messages fetched so progress of
   sort can be reported 
 */
static unsigned short *fetched_map;
static long	       fetched_count;

#define  GET_FETCHED_MAP(x)  (fetched_map[(x)/16] & (0x1 << ((x) & 0xf)))
#define  SET_FETCHED_MAP(x)  (fetched_map[(x)/16] |= (0x1 << ((x) & 0xf)))
#endif 

/*----------------------------------------------------------------------
   Output timely messages indicating that were still sorting
  ----*/
void
sort_blip()
{
    compare_count++;
    if((compare_count % DISPLAY_COUNT) == 0) {
        display_message(NO_OP_COMMAND);
#ifdef DOS
        /* Use the old simple one without the fetched map */
        if(time(0) - last_mess > 10) {
            q_status_message1(0, 2, 5, "Still sorting..%s",
                              repeat_char(mess_count, '.'));
#else
        if(time(0) - last_mess > 5) {
            q_status_message2(0, 0, 3,"Sorting \"%s\" - %s%% complete",
                              ps_global->cur_folder,
			      long2string((fetched_count*100)/
					   mn_get_total(ps_global->msgmap)));
#endif
            mess_count++;
            last_mess = time(0);
        }
    }
}


/*----------------------------------------------------------------------
  Compare function for sorting on subjects. Ignores case, space and "re:"
  ----*/
int
compare_subjects(a, b)
    const QSType *a, *b;
{
    char *suba, *subb;
    long *mess_a = (long *)a, *mess_b = (long *)b;
    int   diff, res;
    long  mdiff;

    sort_blip();

    suba = get_sub(*mess_a);
    subb = get_sub(*mess_b);

    diff = strucmp(suba, subb);

    if(diff == 0) mdiff = *mess_a - *mess_b;
    /* convert to int */
    res = diff != 0 ? diff :
           mdiff != 0L ? (mdiff > 0L ? 1 : -1) : 0;
    return(mn_get_revsort(ps_global->msgmap) ? -res : res);
}

/*----------------------------------------------------------------------
   Get the subject if a message suitable for sorting.  This removes
 all re[*]: or [ from the beginning of a message
 ----*/
char *
get_sub(mess)
     long mess;
{
    ENVELOPE *e;
    char *s, *s3, *ss;
    int   l;

    if(!(ss = subject_cache_ent(mess))){
	e = mail_fetchstructure(ps_global->mail_stream, mess, NULL);
	if(e && e->subject) {
	    /* ---- Clean junk off the front of the subject ----*/
	    for(s = e->subject; *s && (isspace(*s) || *s == '['); s++)
	      ;

	    if((*s == 'R' || *s == 'r') && (*(s+1) == 'E' || *(s+1) == 'e')
	       && (*(s+2) == ':' || *(s+2) == '[')){
		s += 3;
		if(*(s+2) == '['){
		    while(*s && *s != ':')
		      s++;

		    s++;
		}
	    }

	    while(*s && (isspace(*s) || *s == '['))
	      s++;

	    if(*(ss = subject_cache_add(mess, s))){
		/*----- Now, truncate junk off the back end of the subject---*/
		for(s3 = NULL, s = ss; *s; s++)	/* blast ws and ']' */
		  s3 = (!isspace(*s) && *s != ']') ? NULL : (!s3) ? s : s3;

		if(s3)
		  *s3 = '\0';

		if((l=(s3 ? s3 : s)-ss) > 5 && !strucmp(ss+l-5,"(fwd)"))
		  ss[l-5] = '\0';

		for(s3 = NULL, s = ss; *s; s++)	/* blast ws and ']' */
		  s3 = (!isspace(*s) && *s != ']') ? NULL : (!s3) ? s : s3;

		if(s3)
		  *s3 = '\0';
	    }
	}
	else
	  ss = subject_cache_add(mess, "");

	dprint(9, (debugfile, "SUB-GET-%s-GET-SUB\n", ss))
    }
    else{
	dprint(9, (debugfile, "SUB-HIT-%s-HIT-SUB\n", ss))
    }

#ifndef DOS
    if(fetched_map != NULL && !GET_FETCHED_MAP(mess)) {
        SET_FETCHED_MAP(mess);
        fetched_count++;
    }
#endif
    return(ss);
}



/*----------------------------------------------------------------------
   Compare the To: fields for sorting. Ignore case
   ----*/
int 
compare_to(a, b)
    const QSType *a, *b;
{
    long     *mess_a = (long *)a, *mess_b = (long *)b;
    ENVELOPE *e;
    char     *b_addr, *a_addr;
    int       res, diff;
    long      mdiff;

    sort_blip();

    e = mail_fetchstructure(ps_global->mail_stream, *mess_a, NULL);
    if(e == NULL || e->to == NULL)
      a_addr = cpystr("");
    else
      a_addr = cpystr(addr_string(e->to));

    e = mail_fetchstructure(ps_global->mail_stream, *mess_b, NULL);
    if(e == NULL || e->to == NULL)
      b_addr = cpystr("");
    else
      b_addr = cpystr(addr_string(e->to));

    diff = strcmp(a_addr, b_addr);

    fs_give((void **)&a_addr);
    fs_give((void **)&b_addr);
#ifndef DOS
    if(!GET_FETCHED_MAP(*mess_a)) {
        SET_FETCHED_MAP(*mess_a);
        fetched_count++;
    }
    if(!GET_FETCHED_MAP(*mess_b)) {
        SET_FETCHED_MAP(*mess_b);
        fetched_count++;
    }
#endif    

    if(diff == 0) mdiff = *mess_a - *mess_b;
    /* convert to int */
    res = diff != 0 ? diff :
           mdiff != 0L ? (mdiff > 0L ? 1 : -1) : 0;
    return(mn_get_revsort(ps_global->msgmap) ? -res : res);
}


/*----------------------------------------------------------------------
   Compares the From: field for sorting. Ignores case.
  BUG should do something when the sender is us
  ----*/
int 
compare_from(a, b)
    const QSType *a, *b;
{
    long     *mess_a = (long *)a, *mess_b = (long *)b;
    ENVELOPE *e;
    char      froma[200];
    int       diff, res;
    long      mdiff;

    sort_blip();

    e = mail_fetchstructure(ps_global->mail_stream, *mess_a, NULL);
    if(e == NULL || e->from == NULL || e->from->mailbox == NULL)  
      froma[0] = '\0';
    else
      strncpy(froma, e->from->mailbox, sizeof(froma) - 1);
    froma[sizeof(froma) - 1] = '\0';

    e = mail_fetchstructure(ps_global->mail_stream, *mess_b, NULL);
#ifndef DOS
    if(!GET_FETCHED_MAP(*mess_a)) {
        SET_FETCHED_MAP(*mess_a);
        fetched_count++;
    }
    if(!GET_FETCHED_MAP(*mess_b)) {
        SET_FETCHED_MAP(*mess_b);
        fetched_count++;
    }
#endif

    if(e != NULL && e->from != NULL && e->from->mailbox != NULL) {
        diff = strucmp(froma, e->from->mailbox);
        if(diff == 0) mdiff = *mess_a - *mess_b;
        /* convert to int */
        res = diff != 0 ? diff :
           mdiff != 0L ? (mdiff > 0L ? 1 : -1) : 0;
	return(mn_get_revsort(ps_global->msgmap) ? -res : res);
    }
    mdiff = *mess_a - *mess_b;
    return(mdiff != 0L ? (mdiff > 0L ? 1 : -1) : 0);
}


/*----------------------------------------------------------------------
   Compare the Cc: fields for sorting. Ignore case.
   ----*/
int 
compare_cc(a, b)
    const QSType *a, *b;
{
    long     *mess_a = (long *)a, *mess_b = (long *)b;
    ENVELOPE *e;
    char     *b_addr, *a_addr;
    int       diff, res;
    long      mdiff;

    sort_blip();

    e = mail_fetchstructure(ps_global->mail_stream, *mess_a, NULL);
    if(e == NULL || e->cc == NULL)
      a_addr = cpystr("");
    else
      a_addr = cpystr(addr_string(e->to));

    e = mail_fetchstructure(ps_global->mail_stream, *mess_b, NULL);
    if(e == NULL || e->cc == NULL)
      b_addr = cpystr("");
    else
      b_addr = cpystr(addr_string(e->to));

    diff = strcmp(a_addr, b_addr);
    fs_give((void **)&a_addr);
    fs_give((void **)&b_addr);
    if(diff == 0) mdiff = *mess_a - *mess_b;

#ifndef DOS
    if(!GET_FETCHED_MAP(*mess_a)) {
        SET_FETCHED_MAP(*mess_a);
        fetched_count++;
    }
    if(!GET_FETCHED_MAP(*mess_b)) {
        SET_FETCHED_MAP(*mess_b);
        fetched_count++;
    }
#endif
    /* convert to int */
    res = diff != 0 ? diff :
           mdiff != 0L ? (mdiff > 0L ? 1 : -1) : 0;
    return(mn_get_revsort(ps_global->msgmap) ? -res : res);
}


/*----------------------------------------------------------------------
   Compare dates
  ----*/
int
compare_message_dates(a, b)
    const QSType *a, *b;
{
    long       *mess_a = (long *)a, *mess_b = (long *)b;
    int         diff, res;
    long        mdiff;
    ENVELOPE   *e;
    struct date d_a, d_b;

    sort_blip();

    mdiff = *mess_a - *mess_b;
    res = mdiff != 0L ? (mdiff > 0L ? 1 : -1) : 0;

    e = mail_fetchstructure(ps_global->mail_stream, *mess_a, NULL);

    if(e != NULL && e->date != NULL) {
      parse_date(e->date, &d_a);
      e = mail_fetchstructure(ps_global->mail_stream, *mess_b, NULL);
      if(e == NULL || e->date == NULL)  /* B is NULL, A is not */
        return(1);
      parse_date(e->date, &d_b);
    }else {
      e = mail_fetchstructure(ps_global->mail_stream, *mess_b, NULL);
      if(e == NULL || e->date == NULL)  /* both A and B are NULL */
        return(res);
      return(-1);  /* A is NULL, B is not */
    }

    dprint(9,(debugfile,"before GMT: wkday:%d  month:%d  year:%d  day:%d  hour:%d  min:%d  sec:%d  off_gmt:%d\n",
            d_a.wkday, d_a.month, d_a.year, d_a.day, d_a.hour, d_a.minute,
              d_a.sec,d_a.hours_off_gmt));

    convert_to_gmt(&d_a);

    dprint(9,(debugfile,"after GMT: wkday:%d  month:%d  year:%d  day:%d  hour:%d  min:%d  sec:%d\n",
            d_a.wkday, d_a.month, d_a.year, d_a.day, d_a.hour, d_a.minute,
              d_a.sec));

    convert_to_gmt(&d_b);
    
    diff = compare_dates(&d_a, &d_b);
#ifndef DOS
    if(!GET_FETCHED_MAP(*mess_a)) {
        SET_FETCHED_MAP(*mess_a);
        fetched_count++;
    }
    if(!GET_FETCHED_MAP(*mess_b)) {
        SET_FETCHED_MAP(*mess_b);
        fetched_count++;
    }
#endif
    
    /* convert to int */
    res = diff != 0 ? diff :
           mdiff != 0L ? (mdiff > 0L ? 1 : -1) : 0;
    return(mn_get_revsort(ps_global->msgmap) ? -res : res);
}

    

/*----------------------------------------------------------------------
  Compare size of messages for sorting
 ----*/
int
compare_size(a, b)
    const QSType *a, *b;
{
    long 	 *mess_a = (long *)a, *mess_b = (long *)b;
    long	  size_a, size_b, sdiff, mdiff;
    MESSAGECACHE *mc;
    int		  res;

    sort_blip();

    mail_fetchstructure(ps_global->mail_stream, *mess_a, NULL);
    mc = mail_elt(ps_global->mail_stream, *mess_a);
    size_a = mc != NULL ? mc->rfc822_size : -1;

    mail_fetchstructure(ps_global->mail_stream, *mess_b, NULL);
    mc = mail_elt(ps_global->mail_stream, *mess_b);
    size_b = mc != NULL ? mc->rfc822_size : -1;

    sdiff = size_a - size_b;
    if(sdiff == 0L) mdiff = *mess_a - *mess_b;

#ifndef DOS
    if(!GET_FETCHED_MAP(*mess_a)) {
        SET_FETCHED_MAP(*mess_a);
        fetched_count++;
    }
    if(!GET_FETCHED_MAP(*mess_b)) {
        SET_FETCHED_MAP(*mess_b);
        fetched_count++;
    }
#endif    

    /* convert to int */
    res = sdiff != 0L ? (sdiff > 0 ? 1 : -1) :
           mdiff != 0L ? (mdiff > 0L ? 1 : -1) : 0;
    return(mn_get_revsort(ps_global->msgmap) ? -res : res);
}


/*----------------------------------------------------------------------
  Compare raw message numbers 
 ----*/
int
compare_arrival(a, b)
    const QSType *a, *b;
{
    long *mess_a = (long *)a, *mess_b = (long *)b, mdiff;
    int   res;

    res = (mdiff = *mess_a - *mess_b) ? (mdiff > 0L ? 1 : -1) : 0;
    return(mn_get_revsort(ps_global->msgmap) ? -res : res);
}


/*----------------------------------------------------------------------
   Compare subject groups, then arrival order
  ----*/
#if	defined(DOS) && !defined(_WINDOWS)
static FILE *second_sort_file;	/* Can't afford an array with DOS */
static char *second_sort_file_name = NULL;
#else
static long *second_sort;	/* Array of message numbers */
#endif

int
compare_subject_2(a, b)
    const QSType *a, *b;
{
    long       *mess_a = (long *)a, *mess_b = (long *)b;
    long        a1, b1;

#if	defined(DOS) && !defined(_WINDOWS)
    /* There ought to be a better way than seeking all over 
       the disk, but too lazy at the moment */
    fseek(second_sort_file, *mess_a * sizeof(long), 0);
    fread((void *)&a1, sizeof(a1), (size_t)1, second_sort_file);
    fseek(second_sort_file, *mess_b * sizeof(long), 0);
    fread((void *)&b1, sizeof(b1), (size_t)1, second_sort_file);
#else
    a1 = second_sort[*mess_a];
    b1 = second_sort[*mess_b];
#endif
    
    return((int) ((a1 == b1) ? *mess_a - *mess_b : a1 - b1));
}


    
/*----------------------------------------------------------------------
     Sort messages on subject, grouping subjects by age

Args: sort -- The resulting sorted array of message numbers
      max_msgno -- The number of message in this view
      total_max -- The largest possible message number

This is part of the new style of subject sort akin to message threading
based on subject.  All the subjects are grouped together and then the 
groups are ordered based on the oldest. message in the group. 

Here the groups of subjects are sorted.  It was determined that the
fastest way to do this sort was to first sort the whole folder by
subject and then reorder the groups of subjects. It requires 
n * log(n) + n comparisons. Unfortunately it does require an extra
full array of message numbers, but it's really impossible to 
perform this sort without at least this much space. 

The second array is indexed by raw message numbers and contains
smallest raw message number of the messages in the same subject group.

This code here can easily be used to calculate information for true
message threading.  For example a data structure that had one entry
per unique subject.  The data structure would probably only need to contain
the *sorted* message number of the first message in the thread and the 
number of messages in the thread. That would be assuming that the sort
array is sorted in the appropriate order. 

On DOS were memory is expensive the secondary array is a disk files instead
of being in memory. (Though for many formats sorting on DOS will be 
extremely painful until some local caching of sort terms is invented. 
 ----*/
void
second_subject_sort(sort, max_msgno, total_max)
     long     *sort, max_msgno, total_max;
{
    char  *sub_group, *sub;
    long   start_sub_group, s, t, min_sub_group_msgno, next_thread_start;

    /*----  Nothing to do if more than one message  -----*/
    if(max_msgno < 1 || total_max < 1)
      return; 

#if	defined(DOS) && !defined(_WINDOWS)
    second_sort_file_name = temp_nam(NULL, "sf");
    second_sort_file      = fopen(second_sort_file_name, "wb+");
#else
    second_sort      = (long *) fs_get(sizeof(long) * (size_t)(total_max + 1));
#endif
    sub_group           = get_sub(sort[1]);
    start_sub_group     = 1;
    min_sub_group_msgno = sort[1];


    /*---- Create second array of subject groups ------*/
    for(s = 2; s <= max_msgno; s++) {
        sub = get_sub(sort[s]);
        if(strucmp(sub_group, sub)) {
            /*-- on to next subject --*/
            for(t = start_sub_group; t < s; t++) {
#if	defined(DOS) && !defined(_WINDOWS)
                fseek(second_sort_file, sort[t] * sizeof(long), 0);
                fwrite((void *)&min_sub_group_msgno,
                       sizeof(min_sub_group_msgno),
                       (size_t)1,  second_sort_file);
#else
                second_sort[sort[t]] = min_sub_group_msgno;
#endif                
	    }
            start_sub_group     = s;
            sub_group           = sub;
            min_sub_group_msgno = sort[s];
        }

        min_sub_group_msgno = min(min_sub_group_msgno, sort[s]);
    }
    for(t = start_sub_group; t < s; t++) {
#if	defined(DOS) && !defined(_WINDOWS)
        fseek(second_sort_file, sort[t] * sizeof(long), 0);
        fwrite((void *)&min_sub_group_msgno, sizeof(min_sub_group_msgno),
                       (size_t)1,  second_sort_file);
#else
        second_sort[sort[t]] = min_sub_group_msgno;
#endif
    }

#ifdef DEBUG
    for(t = 1; t < max_msgno; t++) 
      dprint(9, (debugfile, "Second_sort[%3ld] is %3ld\n", t, second_sort[t]));
#endif


    /*----- Actually perform the sort -------*/
    qsort(sort+1, (size_t)max_msgno, sizeof(long), compare_subject_2);

#ifdef DEBUG
    for(t = 1; t < max_msgno; t++) 
      dprint(9, (debugfile, "Sorted Second_sort[%3ld] is %3ld\n", t,
                 second_sort[t]));
#endif

    /*---- Now clean up --------*/
#if	defined(DOS) && !defined(_WINDOWS)
    fclose(second_sort_file);
    unlink(second_sort_file_name);
    fs_give((void **)&second_sort_file_name);
#else    
    fs_give((void **)&second_sort);
#endif
}




/*----------------------------------------------------------------------
    Sort the current folder into the order set in the msgmap
  ----*/
void
sort_current_folder()
{
    long        mess_no, i, *sort;
    MSGNO_S    *sortmap = NULL;
    SortOrder   so;
#ifndef DOS
    unsigned short *l;
#endif

    so = mn_get_sort(ps_global->msgmap);
    if(!ps_global->msgmap || !(sort = ps_global->msgmap->sort))
      return;

    dprint(2, (debugfile, "Sorting by %s%s\n", sort_name(so),
	       mn_get_revsort(ps_global->msgmap) ? "/reverse" : ""));

    /*
     * translate the selected numbers into an array of raw numbers
     * temporarily, then translate it back after the sort so the
     * same physical messages are selected...
     */
    mn_init(&sortmap, 0L);
    mn_set_cur(sortmap, mn_m2raw(ps_global->msgmap,
				 mn_first_cur(ps_global->msgmap)));
    while((i = mn_next_cur(ps_global->msgmap)) > 0L)
      mn_add_cur(sortmap, mn_m2raw(ps_global->msgmap, i));

    qsort(sort+1, (size_t)mn_get_total(ps_global->msgmap), sizeof(long),
	  compare_arrival);

    if(so != SortArrival){
        if((so == SortSubject) || (so == SortSubject2))		/* nmsgs cuz MN_EXLD */
	  init_subject_cache(ps_global->mail_stream->nmsgs);

	if(mn_get_total(ps_global->msgmap) > 20)
	  q_status_message2(0, 0, 0, "Sorting \"%s\" by %s",
			  ps_global->cur_folder, sort_name(so));

        /*========= Sorting ================================================*/
#ifndef DOS
        /*--- fetched map for keep track of progress of sort ----*/
        compare_count = 0;
        fetched_count = 0;
        fetched_map   = (unsigned short *)fs_get(
                         (ps_global->mail_stream->nmsgs/16 + 1)
                                              * sizeof(unsigned short));
	for(l = fetched_map;
	    l < &fetched_map[mn_get_total(ps_global->msgmap)/16];
	    *l++ = 0); 
#endif

        compare_count = 0;
        mess_count    = 0;
        last_mess     = time(0);
        qsort(sort+1, (size_t)mn_get_total(ps_global->msgmap), sizeof(long),
              so == SortSubject  ? compare_subjects :
               so == SortFrom     ? compare_from :
                so == SortTo       ? compare_to :
                 so == SortCc       ? compare_cc :
                  so == SortDate     ? compare_message_dates :
                   so == SortSubject2 ? compare_subjects:
                                         compare_size);

	/*---- special case -- reorder the groups of subjects ------*/
	if(so == SortSubject2) 
	  second_subject_sort(sort, mn_get_total(ps_global->msgmap),
			      ps_global->mail_stream->nmsgs);

#ifndef DOS
        fs_give((void **)&fetched_map); 
#endif
	clear_subject_cache();
    }

    /*
     * restore the selected array of message numbers.  No expunge could
     * have happened yet, so we don't worry about raw2m returning 0...
     */
    mn_reset_cur(ps_global->msgmap, mn_raw2m(ps_global->msgmap,
					     mn_first_cur(sortmap)));
    while((i = mn_next_cur(sortmap)) > 0L)
      mn_add_cur(ps_global->msgmap, mn_raw2m(ps_global->msgmap, i));

    mn_give(&sortmap);
}


/*----------------------------------------------------------------------
    Map sort types to names

----> Here is where SortSubject2 (psuedo threads) is selected over
      SortSubject (alphabetical).  Change order of these two in sort_types
      array to change which sort is used. 
  ----*/
char *    
sort_name(so)
  SortOrder so;
{
    /*
     * Make sure the first upper case letter of any new sort name is
     * unique.  The command char and label for sort selection is 
     * derived from this name and its first upper case character.
     * See mailcmd.c:select_sort().
     */
    return((so == SortArrival)  ? "Arrival" :
	    (so == SortDate)	 ? "Date" :
	     (so == SortSubject)  ? "Subject" :
	      (so == SortCc)	   ? "Cc" :
	       (so == SortFrom)	    ? "From" :
		(so == SortTo)	     ? "To" :
		 (so == SortSize)     ? "siZe" :
		  (so == SortSubject2) ? "OrderedSubj" :
					  "BOTCH");
}



/*----------------------------------------------------------------------
    initialize the subject cache
  ----*/
void
init_subject_cache(n)
    long n;
{
    scache = (struct scache *) fs_get(sizeof(struct scache));
    memset((void *)scache, 0, sizeof(struct scache));
    scache->size = n;
#if	defined(DOS) && !defined(_WINDOWS)
    scache->cname = temp_nam(NULL, "sc");
    scache->cfile = fopen(scache->cname, "wb+");
    /* BUG? go into non-caching mode if failure below? */
    while(n-- >= 0L){
	if(fwrite(&scache->ent[1], sizeof(scache_ent), (size_t)1,
		  scache->cfile) != 1){
	    sprintf(tmp_20k_buf, "subject cache: %s",
		    error_description(errno));
	    fatal(tmp_20k_buf);
	}
    }
#else
    scache->ent  = (char **)fs_get((size_t)(n+1L) * sizeof(char *));
    memset((void *)scache->ent, 0, (size_t)(n+1L) * sizeof(char *));
#endif
}


/*----------------------------------------------------------------------
    return the subject of the given number if it's in the cache, otw NULL
  ----*/
char *
subject_cache_ent(n)
    long n;
{
#if	defined(DOS) && !defined(_WINDOWS)
    char *buf;
    int   i;

    /* if the one we want's in core, return it */
    buf = (scache->msgno[i=0] == n || scache->msgno[i=1] == n)
	    ? scache->ent[i].buf : NULL;

    /* else pick one of the slots, and fetch n's subject off disk */
    if(!buf){
	i = subject_cache_slot(n);
	buf = scache->ent[i].used ? scache->ent[i].buf : NULL;
    }

    scache->last = i;
    return(buf);
#else
    return(scache->ent[n]);
#endif
}


/*----------------------------------------------------------------------
    added the givin subject to the cache
  ----*/
char *
subject_cache_add(n, s)
    long n;
    char *s;
{
#if	defined(DOS) && !defined(_WINDOWS)
    int i;
    
    if(scache->msgno[i=0] != n && scache->msgno[i=1] != n)
      i = subject_cache_slot(n);

    scache->last = i;
    scache->ent[i].used = 1;
    scache->msgno[i] = n;
    strncpy(scache->ent[i].buf, s, SUB_CACHE_LEN-1);
    scache->ent[i].buf[SUB_CACHE_LEN-1] = '\0';
    return(scache->ent[i].buf);
#else
    return(scache->ent[n] = cpystr(s));
#endif
}


/*----------------------------------------------------------------------
    pick the next slot, and fetch n's subject off disk
  ----*/
int
subject_cache_slot(n)
    long n;
{
#if	defined(DOS) && !defined(_WINDOWS)
    int i;

    i = scache->last ? 0 : 1;
    if(scache->msgno[i]){
	fseek(scache->cfile, scache->msgno[i] * sizeof(scache_ent), 0);
	fwrite(&scache->ent[i], sizeof(scache_ent), (size_t)1,
	       scache->cfile);
    }

    scache->msgno[i] = n;
    if(fseek(scache->cfile, scache->msgno[i] * sizeof(scache_ent), 0)
       || fread(&scache->ent[i], sizeof(scache_ent), (size_t)1,
		scache->cfile) != 1){
	sprintf(tmp_20k_buf, "Can't access subject cache: ",
		error_description(errno));
	fatal(tmp_20k_buf);
    }

    return(i);
#endif
}


/*----------------------------------------------------------------------
    flush the subject cache
  ----*/
void
clear_subject_cache()
{
    if(scache){
#if	defined(DOS) && !defined(_WINDOWS)
	fclose(scache->cfile);
	unlink(scache->cname);
	fs_give((void **)&scache->cname);
#else
	for(; scache->size; scache->size--)
	  if(scache->ent[scache->size])
	    fs_give((void **)&scache->ent[scache->size]);

#endif
	fs_give((void **)&scache);
    }
}



/*
 *           * * *  Message number management functions  * * *
 */


/*----------------------------------------------------------------------
  Initialize a message manipulation structure for the given total

   Accepts: msgs - pointer to message manipulation struct
	    n - number to test
   Returns: true if n is in selected array, false otherwise

  ----*/
void
msgno_init(msgs, tot)
     MSGNO_S **msgs;
     long      tot;
{
    long   slop = (tot + 1L) % 64;
    size_t len;

    if(!msgs)
      return;

    if(!(*msgs)){
	(*msgs) = (MSGNO_S *)fs_get(sizeof(MSGNO_S));
	memset((void *)(*msgs), 0, sizeof(MSGNO_S));
    }

    (*msgs)->sel_cur  = 0L;
    (*msgs)->sel_cnt  = 1L;
    (*msgs)->sel_size = 8L;
    len		      = (size_t)(*msgs)->sel_size * sizeof(long);
    if((*msgs)->select)
      fs_resize((void **)&((*msgs)->select), len);
    else
      (*msgs)->select = (long *)fs_get(len);

    (*msgs)->select[0] = (tot) ? 1L : 0L;

    (*msgs)->sort_size = (tot + 1L) + (64 - slop);
    len		       = (size_t)(*msgs)->sort_size * sizeof(long);
    if((*msgs)->sort)
      fs_resize((void **)&((*msgs)->sort), len);
    else
      (*msgs)->sort = (long *)fs_get(len);

    memset((void *)(*msgs)->sort, 0, len);
    for(slop = 1L ; slop <= tot; slop++)	/* reusing "slop" */
      (*msgs)->sort[slop] = slop;

    (*msgs)->max_msgno    = tot;
    (*msgs)->sort_order   = ps_global->def_sort;
    (*msgs)->reverse_sort = ps_global->def_sort_rev;
    (*msgs)->flagged_hid  = 0L;
    (*msgs)->flagged_exld = 0L;
    (*msgs)->flagged_tmp  = 0L;
}



/*----------------------------------------------------------------------
 Increment the current message number

   Accepts: msgs - pointer to message manipulation struct
  ----*/
void
msgno_inc(stream, msgs)
     MAILSTREAM *stream;
     MSGNO_S    *msgs;
{
    long i;

    if(!msgs || mn_get_total(msgs) < 1L)
      return;

    for(i = msgs->select[msgs->sel_cur] + 1; i <= mn_get_total(msgs); i++){
	if(!get_lflag(stream, msgs, i, MN_HIDE)){
	    (msgs)->select[((msgs)->sel_cur)] = i;
	    break;
	}
    }
}
 


/*----------------------------------------------------------------------
  Decrement the current message number

   Accepts: msgs - pointer to message manipulation struct
  ----*/
void
msgno_dec(stream, msgs)
     MAILSTREAM *stream;
     MSGNO_S     *msgs;
{
    long i;

    if(!msgs || mn_get_total(msgs) < 1L)
      return;

    for(i = (msgs)->select[((msgs)->sel_cur)] - 1L; i >= 1L; i--){
	if(!get_lflag(stream, msgs, i, MN_HIDE)){
	    (msgs)->select[((msgs)->sel_cur)] = i;
	    break;
	}
    }
}



/*----------------------------------------------------------------------
  Got thru the message mapping table, and remove messages with DELETED flag

   Accepts: stream -- mail stream to removed message references from
	    msgs -- pointer to message manipulation struct
	    f -- flags to use a purge criteria
  ----*/
void
msgno_exclude(stream, msgs)
     MAILSTREAM *stream;
     MSGNO_S     *msgs;
{
    long	  i, j, span;
    int		  shift;

    if(!msgs || msgs->max_msgno < 1L)
      return;

    /*
     * With 3.91 we're using a new strategy for finding and operating
     * on all the messages with deleted status.  The idea is to do a
     * mail_search for deleted messages so the elt's "searched" bit gets
     * set, and then to scan the elt's for them and set our local bit
     * to indicate they're excluded...
     */
    (void)count_flagged(stream, "DELETED");

    for(i = 1L; i <= msgs->max_msgno; ){
	if(mail_elt(stream, mn_m2raw(msgs, i))->searched){
	    /*--- clear all flags to keep our counts consistent  ---*/
	    set_lflag(stream, msgs, i, (MN_HIDE|MN_SLCT), 0);
	    set_lflag(stream, msgs, i, MN_EXLD, 1); /* mark excluded */

	    /* --- erase knowledge in sort array (shift array down) --- */
	    for(j = i + 1; j <= msgs->max_msgno; j++)
	      msgs->sort[j-1] = msgs->sort[j];
/* BUG: should compress strings of deleted message numbers */

	    msgs->max_msgno = max(0L, msgs->max_msgno - 1L);
	    msgno_flush_selected(msgs, i);
	}
	else
	  i++;
    }

    /*
     * If we excluded away a zoomed display, unhide everything...
     */
    if(msgs->max_msgno > 0L && any_lflagged(msgs, MN_HIDE) >= msgs->max_msgno)
      for(i = 1L; i <= msgs->max_msgno; i++)
	set_lflag(stream, msgs, i, MN_HIDE, 0);
}



/*----------------------------------------------------------------------
  Got thru the message mapping table, and remove messages with given flag

   Accepts: stream -- mail stream to removed message references from
	    msgs -- pointer to message manipulation struct
	    f -- flags to use a purge criteria
  ----*/
void
msgno_include(stream, msgs)
     MAILSTREAM *stream;
     MSGNO_S     *msgs;
{
    long   i, slop, old_total, old_size;
    size_t len;

    for(i = 1L; i <= stream->nmsgs; i++)
      if(get_lflag(stream, NULL, i, MN_EXLD)){
	  old_total        = msgs->max_msgno;
	  old_size         = msgs->sort_size;
	  slop             = (msgs->max_msgno + 1L) % 64;
	  msgs->sort_size  = (msgs->max_msgno + 1L) + (64 - slop);
	  len		   = (size_t) msgs->sort_size * sizeof(long);
	  if(msgs->sort){
	      if(old_size != msgs->sort_size)
		fs_resize((void **)&(msgs->sort), len);
	  }
	  else
	    msgs->sort = (long *)fs_get(len);

	  msgs->sort[++msgs->max_msgno] = i;
	  set_lflag(stream, msgs, msgs->max_msgno, MN_EXLD, 0);

	  if(old_total <= 0L){			/* if no previous messages, */
	      if(!msgs->select){		/* select the new message   */
		  msgs->sel_size = 8L;
		  len		 = (size_t)msgs->sel_size * sizeof(long);
		  msgs->select   = (long *)fs_get(len);
	      }

	      msgs->sel_cnt   = 1L;
	      msgs->sel_cur   = 0L;
	      msgs->select[0] = 1L;
	  }
      }
}



/*----------------------------------------------------------------------
 Add the given number of raw message numbers to the end of the
 current list...

   Accepts: msgs - pointer to message manipulation struct
	    n - number to add
   Returns: with fixed up msgno struct

   Only have to adjust the sort array, as since new mail can't cause
   selection!
  ----*/
void
msgno_add_raw(msgs, n)
     MSGNO_S *msgs;
     long     n;
{
    long   slop, old_total, old_size, old_hid;
    size_t len;

    if(!msgs || n <= 0L)
      return;

    old_total        = msgs->max_msgno;
    old_size         = msgs->sort_size;
    msgs->max_msgno += n;
    slop             = (msgs->max_msgno + 1L) % 64;
    msgs->sort_size  = (msgs->max_msgno + 1L) + (64 - slop);
    len		     = (size_t) msgs->sort_size * sizeof(long);
    if(msgs->sort){
	if(old_size != msgs->sort_size)
	  fs_resize((void **)&(msgs->sort), len);
    }
    else
      msgs->sort = (long *)fs_get(len);

    for(slop = old_total + 1L; slop <= msgs->max_msgno; slop++)
      msgs->sort[slop] = slop;

    if(old_total <= 0L){			/* if no previous messages, */
	if(!msgs->select){			/* select the new message   */
	    msgs->sel_size = 8L;
	    len		   = (size_t)msgs->sel_size * sizeof(long);
	    msgs->select   = (long *)fs_get(len);
	}

	msgs->sel_cnt   = 1L;
	msgs->sel_cur   = 0L;
	msgs->select[0] = 1L;
    }
}



/*----------------------------------------------------------------------
  Remove all knowledge of the given raw message number

   Accepts: msgs - pointer to message manipulation struct
	    n - number to remove
   Returns: with fixed up msgno struct

   After removing *all* references, adjust the sort array and
   various pointers accordingly...
  ----*/
void
msgno_flush_raw(msgs, n)
     MSGNO_S *msgs;
     long     n;
{
    long i, old_sorted = 0L;
    int  shift = 0;

    if(!msgs)
      return;

    /*---- blast n from sort array ----*/
    for(i = 1L; i <= msgs->max_msgno; i++){
	if(msgs->sort[i] == n){
	    old_sorted = i;
	    shift++;
	}

	if(shift)
	  msgs->sort[i] = msgs->sort[i + 1L];

	if(msgs->sort[i] > n)
	  msgs->sort[i] -= 1L;
    }

    /*---- now, fixup select array ----*/
    msgs->max_msgno = max(0L, msgs->max_msgno - 1L);
    msgno_flush_selected(msgs, old_sorted);
}



/*----------------------------------------------------------------------
  Remove all knowledge of the given selected message number

   Accepts: msgs - pointer to message manipulation struct
	    n - number to remove
   Returns: with fixed up selec members in msgno struct

   Remove reference and fix up selected message numbers beyond
   the specified number
  ----*/
void
msgno_flush_selected(msgs, n)
     MSGNO_S *msgs;
     long     n;
{
    long i;
    int  shift = 0;

    for(i = 0L; i < msgs->sel_cnt; i++){
	if(!shift && (msgs->select[i] == n))
	  shift++;

	if(shift && i + 1L < msgs->sel_cnt)
	  msgs->select[i] = msgs->select[i + 1L];

	if(n < msgs->select[i] || msgs->select[i] > msgs->max_msgno)
	  msgs->select[i] -= 1L;
    }

    if(shift && msgs->sel_cnt > 1L)
      msgs->sel_cnt -= 1L;
}



/*----------------------------------------------------------------------
  Test to see if the given message number is in the selected message
  list...

   Accepts: msgs - pointer to message manipulation struct
	    n - number to test
   Returns: true if n is in selected array, false otherwise

  ----*/
int
msgno_in_select(msgs, n)
     MSGNO_S *msgs;
     long     n;
{
    long i;

    if(msgs)
      for(i = 0L; i < msgs->sel_cnt; i++)
	if(msgs->select[i] == n)
	  return(1);

    return(0);
}



/*----------------------------------------------------------------------
  return our index number for the given raw message number

   Accepts: msgs - pointer to message manipulation struct
	    n - number to locate
   Returns: our index number of given raw message

  ----*/
long
msgno_in_sort(msgs, n)
     MSGNO_S *msgs;
     long     n;
{
    static long start = 1L;
    long        i;

    if(mn_get_total(msgs) < 1L)
      return(-1L);
    else if(mn_get_sort(msgs) == SortArrival && !any_lflagged(msgs, MN_EXLD))
      return((mn_get_revsort(msgs)) ? 1 + mn_get_total(msgs) - n  : n);

    if(start > mn_get_total(msgs))		/* reset start? */
      start = 1L;

    i = start;
    do {
	if(mn_m2raw(msgs, i) == n)
	  return(start = i);

	if(++i > mn_get_total(msgs))
	  i = 1L;
    }
    while(i != start);

    return(0L);
}



/*
 *           * * *  Index entry cache manager  * * *
 */

/*
 * at some point, this could be made part of the pine_state struct.
 * the only changes here would be to pass the ps pointer around
 */
static struct index_cache {
   void	  *cache;				/* pointer to cache */
   char	  *name;				/* pointer to cache name */
   long    num;					/* # of last index in cache */
   size_t  size;				/* size of each index line  */
} icache = { NULL, 0L, 0 };
  
/*
 * cache size growth increment
 */

#ifdef	DOS
/*
 * the idea is to have the cache increment be a multiple of the block
 * size (4K), for efficient swapping of blocks.  we can pretty much
 * assume 81 character lines.
 *
 * REMEMBER: number of lines in the incore cache has to be a mutliple 
 *           of the cache growth increment!
 */
#define	IC_SIZE		(50L)			/* cache growth increment  */
#define	ICC_SIZE	(50L)			/* enties in incore cache  */
#define FUDGE           (46L)			/* extra chars to make 4096*/

static char	*incore_cache = NULL;		/* pointer to incore cache */
static long      cache_block_s = 0L;		/* save recomputing time   */
static long      cache_base = 0L;		/* index of line 0 in block*/
#else
#define	IC_SIZE		100
#endif

/*
 * important values for cache building
 */
static MAILSTREAM *bc_this_stream = NULL;
static long  bc_start, bc_current;
static short bc_done = 0;


/*
 * way to return the current cache entry size
 */
int
i_cache_width()
{
    return(icache.size - sizeof(HLINE_S));
}


/* 
 * i_cache_size - make sure the cache is big enough to contain
 * requested entry
 */
int
i_cache_size(indx)
    long         indx;
{
    long j;
    size_t  newsize = sizeof(HLINE_S)
		     + (max(ps_global->ttyo->screen_cols, 80) * sizeof(char));

    if(j = (newsize % sizeof(long)))		/* alignment hack */
      newsize += (sizeof(long) - (size_t)j);

    if(icache.size != newsize){
	clear_index_cache();			/* clear cache, start over! */
	icache.size = newsize;
    }

    if(indx > (j = icache.num - 1L)){		/* make room for entry! */
	size_t  tmplen = icache.size;
	char   *tmpline;

	while(indx >= icache.num)
	  icache.num += IC_SIZE;

#ifdef	DOS
	tmpline = fs_get(tmplen);
	memset(tmpline, 0, tmplen);
	if(icache.cache == NULL){
	    if(!icache.name)
	      icache.name = temp_nam(NULL, "pi");

	    if((icache.cache = (void *)fopen(icache.name,"w+b")) == NULL){
		sprintf(tmp_20k_buf, "Can't open index cache: %s",icache.name);
		fatal(tmp_20k_buf);
	    }

	    for(j = 0; j < icache.num; j++){
	        if(fwrite(tmpline,tmplen,(size_t)1,(FILE *)icache.cache) != 1)
		  fatal("Can't write index cache in resize");

		if(j%ICC_SIZE == 0){
		  if(fwrite(tmpline,(size_t)FUDGE,
				(size_t)1,(FILE *)icache.cache) != 1)
		    fatal("Can't write FUDGE factor in resize");
	        }
	    }
	}
	else{
	    /* init new entries */
	    fseek((FILE *)icache.cache, 0L, 2);		/* seek to end */

	    for(;j < icache.num; j++){
	        if(fwrite(tmpline,tmplen,(size_t)1,(FILE *)icache.cache) != 1)
		  fatal("Can't write index cache in resize");

		if(j%ICC_SIZE == 0){
		  if(fwrite(tmpline,(size_t)FUDGE,
				(size_t)1,(FILE *)icache.cache) != 1)
		    fatal("Can't write FUDGE factor in resize");
	        }
	    }
	}

	fs_give((void **)&tmpline);
#else
	if(icache.cache == NULL){
	    icache.cache = (void *)fs_get((icache.num+1)*tmplen);
	    memset(icache.cache, 0, (icache.num+1)*tmplen);
	}
	else{
            fs_resize((void **)&(icache.cache), (size_t)(icache.num+1)*tmplen);
	    tmpline = (char *)icache.cache + ((j+1) * tmplen);
	    memset(tmpline, 0, (icache.num - j) * tmplen);
	}
#endif
    }

    return(1);
}

#ifdef	DOS
/*
 * read a block into the incore cache
 */
void
icread()
{
    size_t n;

    if(fseek((FILE *)icache.cache, (cache_base/ICC_SIZE) * cache_block_s, 0))
      fatal("ran off end of index cache file in icread");

    n = fread((void *)incore_cache, (size_t)cache_block_s, 
		(size_t)1, (FILE *)icache.cache);

    if(n != 1L)
      fatal("Can't read index cache block in from disk");
}


/*
 * write the incore cache out to disk
 */
void
icwrite()
{
    size_t n;

    if(fseek((FILE *)icache.cache, (cache_base/ICC_SIZE) * cache_block_s, 0))
      fatal("ran off end of index cache file in icwrite");

    n = fwrite((void *)incore_cache, (size_t)cache_block_s,
		(size_t)1, (FILE *)icache.cache);

    if(n != 1L)
      fatal("Can't write index cache block in from disk");
}


/*
 * make sure the neccessary block of index lines is in core
 */
void
i_cache_hit(indx)
    long         indx;
{
    dprint(9, (debugfile, "i_cache_hit: %ld\n", indx));
    /* no incore cache, create it */
    if(!incore_cache){
	cache_block_s = (((long)icache.size * ICC_SIZE) + FUDGE)*sizeof(char);
	incore_cache  = (char *)fs_get((size_t)cache_block_s);
	cache_base = (indx/ICC_SIZE) * ICC_SIZE;
	icread();
	return;
    }

    if(indx >= cache_base && indx < (cache_base + ICC_SIZE))
	return;

    icwrite();

    cache_base = (indx/ICC_SIZE) * ICC_SIZE;
    icread();
}
#endif


/*
 * return the index line associated with the given message number
 */
HLINE_S *
get_index_cache(msgno)
    long         msgno;
{
    if(!i_cache_size(--msgno)){
	q_status_message(0, 1, 3, "get_index_cache failed!");
	return(NULL);
    }

#ifdef	DOS
    i_cache_hit(msgno);			/* get entry into core */
    return((HLINE_S *)(incore_cache 
	      + ((msgno%ICC_SIZE) * (long)max(icache.size,FUDGE))));
#else
    return((HLINE_S *) ((char *)(icache.cache) 
	   + (msgno * (long)icache.size * sizeof(char))));
#endif
}


/*
 * the idea is to pre-build and cache index lines while waiting
 * for command input.
 */
void
build_header_cache()
{
    long lines_per_page = max(0,ps_global->ttyo->screen_rows - 5);

    if(mn_get_total(ps_global->msgmap) == 0 || ps_global->mail_stream == NULL
       || (bc_this_stream == ps_global->mail_stream && bc_done >= 2)
       || any_lflagged(ps_global->msgmap, (MN_HIDE|MN_EXLD|MN_SLCT)))
      return;

    if(bc_this_stream != ps_global->mail_stream){ /* reset? */
	bc_this_stream = ps_global->mail_stream;
	bc_current = bc_start = top_ent_calc(ps_global->mail_stream,
					     ps_global->msgmap,
					     mn_get_cur(ps_global->msgmap),
					     lines_per_page);
	bc_done  = 0;
    }

    if(!bc_done && bc_current > mn_get_total(ps_global->msgmap)){ /* wrap? */
	bc_current = bc_start - lines_per_page;
	bc_done++;
    }
    else if(bc_done == 1 && (bc_current % lines_per_page) == 1)
      bc_current -= (2L * lines_per_page);

    if(bc_current < 1){
	bc_done = 2;			/* really done! */
	return;
    }

    (void)build_header_line(ps_global->mail_stream, ps_global->msgmap,
			    bc_current++);
}


/*
 * erase a particular entry in the cache
 */
void
clear_index_cache_ent(indx)
    long indx;
{
    HLINE_S *tmp = get_index_cache(indx);

    tmp->line[0] = '\0';
    tmp->id      = 0L;
}


/*
 * clear the index cache associated with the current mailbox
 */
void
clear_index_cache()
{
#ifdef	DOS
    cache_base = 0L;
    if(incore_cache)
      fs_give((void **)&incore_cache);

    if(icache.cache){
	fclose((FILE *)icache.cache);
	icache.cache = NULL;
    }

    if(icache.name){
	unlink(icache.name);
	fs_give((void **)&icache.name);
    }
#else
    if(icache.cache)
      fs_give((void **)&(icache.cache));
#endif
    icache.num  = 0L;
    icache.size = 0;
    bc_this_stream = NULL;
}


#ifdef	DOS
/*
 * flush the incore_cache, but not the whole enchilada
 */
void
flush_index_cache()
{
    if(incore_cache){
	if(mn_get_total(ps_global->msgmap) > 0L)
	  icwrite();			/* write this block out to disk */

	fs_give((void **)&incore_cache);
	cache_base = 0L;
    }
}
#endif
