Return to scroll.c CVS log

Up to [Apple XNU] / GNUtools / emacs / src

Annotation of GNUtools/emacs/src/scroll.c, revision 1.1

1.1     ! root        1: /* Calculate what ins/del line to do, and do it, for Emacs redisplay.
        !             2:    Copyright (C) 1985, 1986, 1990 Free Software Foundation, Inc.
        !             3: 
        !             4: This file is part of GNU Emacs.
        !             5: 
        !             6: GNU Emacs is free software; you can redistribute it and/or modify
        !             7: it under the terms of the GNU General Public License as published by
        !             8: the Free Software Foundation; either version 1, or (at your option)
        !             9: any later version.
        !            10: 
        !            11: GNU Emacs is distributed in the hope that it will be useful,
        !            12: but WITHOUT ANY WARRANTY; without even the implied warranty of
        !            13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
        !            14: GNU General Public License for more details.
        !            15: 
        !            16: You should have received a copy of the GNU General Public License
        !            17: along with GNU Emacs; see the file COPYING.  If not, write to
        !            18: the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
        !            19: 
        !            20: 
        !            21: #include <stdio.h>
        !            22: #include "config.h"
        !            23: #include "termchar.h"
        !            24: #include "termhooks.h"
        !            25: #include "dispextern.h"
        !            26: 
        !            27: #define max(a, b) ((a) > (b) ? (a) : (b))
        !            28: #define min(a, b) ((a) < (b) ? (a) : (b))
        !            29: 
        !            30: struct matrix_elt
        !            31:   {
        !            32:     /* Cost of outputting through this line
        !            33:        if no insert/delete is done just above it.  */
        !            34:     int writecost;
        !            35:     /* Cost of outputting through this line
        !            36:        if an insert is done just above it.  */
        !            37:     int insertcost;
        !            38:     /* Cost of outputting through this line
        !            39:        if a delete is done just above it.  */
        !            40:     int deletecost;
        !            41:     /* Number of inserts so far in this run of inserts,
        !            42:        for the cost in insertcost.  */
        !            43:     char insertcount;
        !            44:     /* Number of deletes so far in this run of deletes,
        !            45:        for the cost in deletecost.  */
        !            46:     char deletecount;
        !            47:   };
        !            48: 
        !            49: /* This exceeds the sum of any reasonable number of INFINITY's.  */
        !            50: #define SUPER_INFINITY (1000 * INFINITY)
        !            51: 
        !            52: /* See CalcIDCosts for on the arrays below */
        !            53: int *ILcost;
        !            54: int *DLcost;
        !            55: int *ILncost;
        !            56: int *DLncost;
        !            57: 
        !            58: scrolling_1 (window_size, unchanged_at_top, unchanged_at_bottom,
        !            59:             draw_cost, old_hash, new_hash, free_at_end)
        !            60:      int window_size, unchanged_at_top, unchanged_at_bottom;
        !            61:      int *draw_cost;
        !            62:      int *old_hash;
        !            63:      int *new_hash;
        !            64:      int free_at_end;
        !            65: {
        !            66:   struct matrix_elt *matrix;
        !            67:   matrix = ((struct matrix_elt *)
        !            68:            alloca ((window_size + 1) * (window_size + 1) * sizeof *matrix));
        !            69: 
        !            70:   calculate_scrolling (matrix, window_size, unchanged_at_bottom,
        !            71:                       draw_cost, old_hash, new_hash,
        !            72:                       free_at_end);
        !            73:   do_scrolling (matrix, window_size, unchanged_at_top);
        !            74: }
        !            75: 
        !            76: /* Determine, in matrix[i,j], the cost of updating the first j old lines
        !            77:    into the first i new lines.
        !            78:    This involves using insert or delete somewhere if i != j.
        !            79:    For each matrix elements, three kinds of costs are recorded:
        !            80:    the smallest cost that ends with an insert, the smallest
        !            81:    cost that ends with a delete, and the smallest cost that
        !            82:    ends with neither one.  These are kept separate because
        !            83:    on some terminals the cost of doing an insert varies
        !            84:    depending on whether one was just done, etc.  */
        !            85: 
        !            86: /* draw_cost[VPOS] is the cost of outputting new line at VPOS.
        !            87:    old_hash[VPOS] is the hash code of the old line at VPOS.
        !            88:    new_hash[VPOS] is the hash code of the new line at VPOS.
        !            89:    Note that these are not true screen vpos's, but relative
        !            90:    to the place at which the first mismatch between old and
        !            91:    new contents appears.  */
        !            92: 
        !            93: calculate_scrolling (matrix, window_size, lines_below,
        !            94:                     draw_cost, old_hash, new_hash,
        !            95:                     free_at_end)
        !            96:      /* matrix is of size window_size + 1 on each side.  */
        !            97:      struct matrix_elt *matrix;
        !            98:      int window_size;
        !            99:      int *draw_cost;
        !           100:      int *old_hash;
        !           101:      int *new_hash;
        !           102:      int free_at_end;
        !           103: {
        !           104:   register int i, j;
        !           105:   register struct matrix_elt *p, *p1;
        !           106:   register int cost, cost1;
        !           107: 
        !           108:   int lines_moved = window_size + (scroll_region_ok ? 0 : lines_below);
        !           109:   /* We subtract 1 to compensate for the fact that i and j have values
        !           110:      starting with 1.  */
        !           111:   int *first_insert_cost = &ILcost[screen_height - lines_moved - 1];
        !           112:   int *first_delete_cost = &DLcost[screen_height - lines_moved - 1];
        !           113:   int *next_insert_cost = &ILncost[screen_height - lines_moved - 1];
        !           114:   int *next_delete_cost = &DLncost[screen_height - lines_moved - 1];
        !           115: 
        !           116:   /* initialize the top left corner of the matrix */
        !           117:   matrix->writecost = 0;
        !           118:   matrix->insertcost = SUPER_INFINITY;
        !           119:   matrix->deletecost = SUPER_INFINITY;
        !           120:   matrix->insertcount = 0;
        !           121:   matrix->deletecount = 0;
        !           122: 
        !           123:   /* initialize the left edge of the matrix */
        !           124:   cost = first_insert_cost[1] - next_insert_cost[1];
        !           125:   for (i = 1; i <= window_size; i++)
        !           126:     {
        !           127:       p = matrix + i * (window_size + 1);
        !           128:       cost += draw_cost[i] + next_insert_cost[i];
        !           129:       p->insertcost = cost;
        !           130:       p->writecost = SUPER_INFINITY;
        !           131:       p->deletecost = SUPER_INFINITY;
        !           132:       p->insertcount = i;
        !           133:       p->deletecount = 0;
        !           134:     }
        !           135: 
        !           136:   /* initialize the top edge of the matrix */
        !           137:   cost = first_delete_cost[1] - next_delete_cost[1];
        !           138:   for (j = 1; j <= window_size; j++)
        !           139:     {
        !           140:       cost += next_delete_cost[j];
        !           141:       matrix[j].deletecost = cost;
        !           142:       matrix[j].writecost = SUPER_INFINITY;
        !           143:       matrix[j].insertcost = SUPER_INFINITY;
        !           144:       matrix[j].deletecount = j;
        !           145:       matrix[j].insertcount = 0;
        !           146:     }
        !           147: 
        !           148:   /* `i' represents the vpos among new screen contents.
        !           149:      `j' represents the vpos among the old screen contents.  */
        !           150:   p = matrix + window_size + 2;        /* matrix [1, 1] */
        !           151:   for (i = 1; i <= window_size; i++, p++)
        !           152:     for (j = 1; j <= window_size; j++, p++)
        !           153:       {
        !           154:        /* p contains the address of matrix [i, j] */
        !           155: 
        !           156:        /* First calculate the cost assuming we do
        !           157:           not insert or delete above this line.
        !           158:           That is, if we update through line i-1
        !           159:           based on old lines through j-1,
        !           160:           and then just change old line j to new line i.  */
        !           161:        p1 = p - window_size - 2; /* matrix [i-1, j-1] */
        !           162:        cost = p1->writecost;
        !           163:        if (cost > p1->insertcost)
        !           164:          cost = p1->insertcost;
        !           165:        if (cost > p1->deletecost)
        !           166:          cost = p1->deletecost;
        !           167:        if (old_hash[j] != new_hash[i])
        !           168:          cost += draw_cost[i];
        !           169:        p->writecost = cost;
        !           170: 
        !           171:        /* Calculate the cost if we do an insert-line
        !           172:           before outputting this line.
        !           173:           That is, we update through line i-1
        !           174:           based on old lines through j,
        !           175:           do an insert-line on line i,
        !           176:           and then output line i from scratch,
        !           177:           leaving old lines starting from j for reuse below.  */
        !           178:        p1 = p - window_size - 1; /* matrix [i-1, j] */
        !           179:        /* No need to think about doing a delete followed
        !           180:           immediately by an insert.  It cannot be as good
        !           181:           as not doing either of them.  */
        !           182:        if (free_at_end == i)
        !           183:          {
        !           184:            cost = p1->writecost;
        !           185:            cost1 = p1->insertcost;
        !           186:          }
        !           187:        else
        !           188:          {
        !           189:            cost = p1->writecost + first_insert_cost[i];
        !           190:            if (p1->insertcount > i)
        !           191:              abort ();
        !           192:            cost1 = p1->insertcost + next_insert_cost[i - p1->insertcount];
        !           193:          }
        !           194:        p->insertcost = min (cost, cost1) + draw_cost[i];
        !           195:        p->insertcount = (cost < cost1) ? 1 : p1->insertcount + 1;
        !           196:        if (p->insertcount > i)
        !           197:          abort ();
        !           198: 
        !           199:        /* Calculate the cost if we do a delete line after
        !           200:           outputting this line.
        !           201:           That is, we update through line i
        !           202:           based on old lines through j-1,
        !           203:           and throw away old line j.  */
        !           204:        p1 = p - 1;             /* matrix [i, j-1] */
        !           205:        /* No need to think about doing an insert followed
        !           206:           immediately by a delete.  */
        !           207:        if (free_at_end == i)
        !           208:          {
        !           209:            cost = p1->writecost;
        !           210:            cost1 = p1->deletecost;
        !           211:          }
        !           212:        else
        !           213:          {
        !           214:            cost = p1->writecost + first_delete_cost[i];
        !           215:            cost1 = p1->deletecost + next_delete_cost[i];
        !           216:          }
        !           217:        p->deletecost = min (cost, cost1);
        !           218:        p->deletecount = (cost < cost1) ? 1 : p1->deletecount + 1;
        !           219:       }
        !           220: }
        !           221: 
        !           222: /* Perform insert-lines and delete-lines operations
        !           223:  according to the costs in the matrix.
        !           224:  Updates the contents of current_screen to record what was done. */
        !           225: 
        !           226: do_scrolling (matrix, window_size, unchanged_at_top)
        !           227:      struct matrix_elt *matrix;
        !           228:      int window_size;
        !           229:      int unchanged_at_top;
        !           230: {
        !           231:   register struct matrix_elt *p;
        !           232:   register int i, j;
        !           233:   struct queue { int count, pos; } *queue;
        !           234:   int offset = unchanged_at_top;
        !           235:   int qi = 0;
        !           236:   int window = 0;
        !           237:   register int tem;
        !           238:   int next;
        !           239: 
        !           240:   queue = (struct queue *) alloca (screen_height * sizeof (struct queue));
        !           241: 
        !           242:   bcopy (current_screen->contents, temp_screen->contents,
        !           243:         current_screen->height * sizeof (char *));
        !           244:   bcopy (current_screen->used, temp_screen->used,
        !           245:         current_screen->height * sizeof (int));
        !           246:   bcopy (current_screen->highlight, temp_screen->highlight,
        !           247:         current_screen->height);
        !           248:   bzero (temp_screen->enable, temp_screen->height);
        !           249: 
        !           250: /* First do all deletions of lines; queue up insertions.
        !           251:    Also move lines to correct slots in current_screen.  */
        !           252: 
        !           253:   i = j = window_size;
        !           254: 
        !           255:   while (i > 0 || j > 0)
        !           256:     {
        !           257:       p = matrix + i * (window_size + 1) + j;
        !           258:       tem = p->insertcost;
        !           259:       if (tem < p->writecost && tem < p->deletecost)
        !           260:        {
        !           261:          /* Insert should be done at vpos i-1, plus maybe some before */
        !           262:          queue[qi].count = p->insertcount;
        !           263:          i -= p->insertcount;
        !           264:          queue[qi++].pos = i + unchanged_at_top;
        !           265:        }
        !           266:       else if (p->deletecost < p->writecost)
        !           267:        {
        !           268:          /* Old line at vpos j-1, and maybe some before it,
        !           269:             should be deleted */
        !           270:          j -= p->deletecount;
        !           271:          if (!window)
        !           272:            {
        !           273:              set_terminal_window (window_size + unchanged_at_top);
        !           274:              window = 1;
        !           275:            }
        !           276:          ins_del_lines (j + unchanged_at_top, - p->deletecount);
        !           277:        }
        !           278:       else
        !           279:        {
        !           280:          /* Best thing done here is no insert or delete */
        !           281:          /* Old line at vpos j-1 ends up at vpos i-1 */
        !           282:          current_screen->contents[i + offset - 1]
        !           283:            = temp_screen->contents[j + offset - 1];
        !           284:          current_screen->used[i + offset - 1]
        !           285:            = temp_screen->used[j + offset - 1];
        !           286:          current_screen->highlight[i + offset - 1]
        !           287:            = temp_screen->highlight[j + offset - 1];
        !           288: 
        !           289:          temp_screen->enable[j + offset - 1] = 1;
        !           290:          i--;
        !           291:          j--;
        !           292:        }
        !           293:     }
        !           294: 
        !           295:   if (!window && qi)
        !           296:     {
        !           297:       set_terminal_window (window_size + unchanged_at_top);
        !           298:       window = 1;
        !           299:     }
        !           300: 
        !           301:   /* Now do all insertions */
        !           302: 
        !           303:   next = unchanged_at_top;
        !           304:   for (i = qi - 1; i >= 0; i--)
        !           305:     {
        !           306:       ins_del_lines (queue[i].pos, queue[i].count);
        !           307:       /* Mark the inserted lines as clear,
        !           308:         and put into them the line-contents strings
        !           309:         that were discarded during the deletions.
        !           310:         Those are the ones for which temp_screen->enable was not set.  */
        !           311:       tem = queue[i].pos;
        !           312:       for (j = tem + queue[i].count - 1; j >= tem; j--)
        !           313:        {
        !           314:          current_screen->enable[j] = 0;
        !           315:          while (temp_screen->enable[next]) next++;
        !           316:          current_screen->contents[j] = temp_screen->contents[next++];
        !           317:        }
        !           318:     }
        !           319: 
        !           320:   if (window)
        !           321:     set_terminal_window (0);
        !           322: }
        !           323: 
        !           324: /* Return number of lines in common between current screen contents
        !           325:    and the text to be displayed,
        !           326:    considering only vpos range START to END (not including END).
        !           327:    Ignores short lines (length < 20) on the assumption that
        !           328:    avoiding redrawing such a line will have little weight.  */
        !           329: 
        !           330: int
        !           331: scrolling_max_lines_saved (start, end, oldhash, newhash, cost)
        !           332:      int start, end;
        !           333:      int *oldhash, *newhash, *cost;
        !           334: {
        !           335:   struct { int hash; int count; } lines[01000];
        !           336:   register int i, h;
        !           337:   register int matchcount = 0;
        !           338: 
        !           339:   bzero (lines, sizeof lines);
        !           340: 
        !           341:   /* Put new lines' hash codes in hash table.  */
        !           342:   for (i = start; i < end; i++)
        !           343:     {
        !           344:       if (cost[i] > 20)
        !           345:        {
        !           346:          h = newhash[i] & 0777;
        !           347:          lines[h].hash = newhash[i];
        !           348:          lines[h].count++;
        !           349:        }
        !           350:     }
        !           351: 
        !           352:   /* Look up old line hash codes in the hash table.
        !           353:      Count number of matches between old lines and new.  */
        !           354: 
        !           355:   for (i = start; i < end; i++)
        !           356:     {
        !           357:       h = oldhash[i] & 0777;
        !           358:       if (oldhash[i] == lines[h].hash)
        !           359:        {
        !           360:          matchcount++;
        !           361:          if (--lines[h].count == 0)
        !           362:            lines[h].hash = 0;
        !           363:        }
        !           364:     }
        !           365: 
        !           366:   return matchcount;
        !           367: }
        !           368: 
        !           369: /* Return a measure of the cost of moving the lines
        !           370:    starting with vpos FROM, up to but not including vpos TO,
        !           371:    down by AMOUNT lines (AMOUNT may be negative).
        !           372:    These are the same arguments that might be given to
        !           373:    scroll_screen_lines to perform this scrolling.  */
        !           374: 
        !           375: scroll_cost (from, to, amount)
        !           376:      int from, to, amount;
        !           377: {
        !           378:   /* Compute how many lines, at bottom of screen,
        !           379:      will not be involved in actual motion.  */
        !           380:   int ok_below = screen_height - to;
        !           381:   if (amount > 0) ok_below -= amount;
        !           382:   if (! scroll_region_ok) ok_below = 0;
        !           383: 
        !           384:   if (amount == 0)
        !           385:     return 0;
        !           386: 
        !           387:   if (amount < 0)
        !           388:     {
        !           389:       int temp = to;
        !           390:       to = from + amount;
        !           391:       from = temp + amount;
        !           392:       amount = - amount;
        !           393:     }
        !           394: 
        !           395:   from += ok_below;
        !           396:   to += ok_below;
        !           397: 
        !           398:   return (ILcost[from] + (amount - 1) * ILncost[from]
        !           399:          + DLcost[to] + (amount - 1) * DLncost[to]);
        !           400: }
        !           401: 
        !           402: /* Calculate the insert and delete line costs.
        !           403: 
        !           404:    We keep the ID costs in a precomputed array based on the position
        !           405:    at which the I or D is performed.  Also, there are two kinds of ID
        !           406:    costs: the "once-only" and the "repeated".  This is to handle both
        !           407:    those terminals that are able to insert N lines at a time (once-
        !           408:    only) and those that must repeatedly insert one line.
        !           409: 
        !           410:    The cost to insert N lines at line L is
        !           411:            [tt.t_ILov  + (screen_height + 1 - L) * tt.t_ILpf] +
        !           412:        N * [tt.t_ILnov + (screen_height + 1 - L) * tt.t_ILnpf]
        !           413: 
        !           414:    ILov represents the basic insert line overhead.  ILpf is the padding
        !           415:    required to allow the terminal time to move a line: insertion at line
        !           416:    L changes (screen_height + 1 - L) lines.
        !           417: 
        !           418:    The first bracketed expression above is the overhead; the second is
        !           419:    the multiply factor.  Both are dependent only on the position at
        !           420:    which the insert is performed.  We store the overhead in ILcost and
        !           421:    the multiply factor in ILncost.  Note however that any insertion
        !           422:    must include at least one multiply factor.  Rather than compute this
        !           423:    as ILcost[line]+ILncost[line], we add ILncost into ILcost.  This is
        !           424:    reasonable because of the particular algorithm used in calcM.
        !           425: 
        !           426:    Deletion is essentially the same as insertion.
        !           427:  */
        !           428: 
        !           429: CalcIDCosts (ins_line_string, multi_ins_string,
        !           430:             del_line_string, multi_del_string,
        !           431:             setup_string, cleanup_string)
        !           432:      char *ins_line_string, *multi_ins_string;
        !           433:      char *del_line_string, *multi_del_string;
        !           434:      char *setup_string, *cleanup_string;
        !           435: {
        !           436:   /* Discourage long scrolls slightly on fast lines.
        !           437:      This says that scrolling nearly the full length of the screen
        !           438:      is not worth it if reprinting takes less than 1/4 second.  */
        !           439:   int extra = baud_rate / (10 * 4 * screen_height);
        !           440: 
        !           441:   if (ILcost != 0)
        !           442:     {
        !           443:       ILcost = (int *) xrealloc (ILcost, screen_height * sizeof (int));
        !           444:       DLcost = (int *) xrealloc (DLcost, screen_height * sizeof (int));
        !           445:       ILncost = (int *) xrealloc (ILncost, screen_height * sizeof (int));
        !           446:       DLncost = (int *) xrealloc (DLncost, screen_height * sizeof (int));
        !           447:     }
        !           448:   else
        !           449:     {
        !           450:       ILcost = (int *) xmalloc (screen_height * sizeof (int));
        !           451:       DLcost = (int *) xmalloc (screen_height * sizeof (int));
        !           452:       ILncost = (int *) xmalloc (screen_height * sizeof (int));
        !           453:       DLncost = (int *) xmalloc (screen_height * sizeof (int));
        !           454:     }
        !           455: 
        !           456:   CalcIDCosts1 (ins_line_string, multi_ins_string,
        !           457:                setup_string, cleanup_string,
        !           458:                ILcost, ILncost, extra);
        !           459:   CalcIDCosts1 (del_line_string, multi_del_string,
        !           460:                setup_string, cleanup_string,
        !           461:                DLcost, DLncost, 0);
        !           462: }
        !           463: 
        !           464: CalcIDCosts1 (one_line_string, multi_string,
        !           465:              setup_string, cleanup_string,
        !           466:              costvec, ncostvec, extra)
        !           467:      char *one_line_string, *multi_string;
        !           468:      char *setup_string, *cleanup_string;
        !           469:      int *costvec, *ncostvec;
        !           470:      int extra;
        !           471: {
        !           472:   if (calculate_costs_hook)
        !           473:     (*calculate_costs_hook) (extra, costvec, ncostvec);
        !           474:   else if (dont_calculate_costs)
        !           475:     CalcLID (0, 0, 0, 0, costvec, ncostvec);
        !           476:   else if (multi_string)
        !           477:     CalcLID (string_cost (multi_string),
        !           478:             per_line_cost (multi_string),
        !           479:             extra, 0, costvec, ncostvec);
        !           480:   else if (one_line_string)
        !           481:     CalcLID (string_cost (setup_string) + string_cost (cleanup_string), 0,
        !           482:             string_cost (one_line_string) + extra,
        !           483:             per_line_cost (one_line_string),
        !           484:             costvec, ncostvec);
        !           485:   else
        !           486:     CalcLID (9999, 0, 9999, 0,
        !           487:             costvec, ncostvec);
        !           488: }
        !           489: 
        !           490: /* Calculate the line ID overhead and multiply factor values */
        !           491: CalcLID (ov1, pf1, ovn, pfn, ov, mf)
        !           492:      int ov1, ovn;
        !           493:      int pf1, pfn;
        !           494:      register int *ov, *mf;
        !           495: {
        !           496:   register int i;
        !           497:   register int insert_overhead = ov1 * 10 + screen_height * pf1;
        !           498:   register int next_insert_cost = ovn * 10 + screen_height * pfn;
        !           499: 
        !           500:   for (i = 0; i < screen_height; i++)
        !           501:     {
        !           502:       *mf++ = next_insert_cost / 10;
        !           503:       next_insert_cost -= pfn;
        !           504:       *ov++ = (insert_overhead + next_insert_cost) / 10;
        !           505:       insert_overhead -= pf1;
        !           506:     }
        !           507: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.