src/viewer/coord_cache.c

   1 /*
   2    Internal file viewer for the Midnight Commander
   3    Function for work with coordinate cache (ccache)
   4
   5    Copyright (C) 1994, 1995, 1996, 1998, 1999, 2000, 2001, 2002, 2003,
   6    2004, 2005, 2006, 2007, 2009 Free Software Foundation, Inc.
   7
   8    Written by: 1994, 1995, 1998 Miguel de Icaza
   9                1994, 1995 Janne Kukonlehto
  10                1995 Jakub Jelinek
  11                1996 Joseph M. Hinkle
  12                1997 Norbert Warmuth
  13                1998 Pavel Machek
  14                2004 Roland Illig <roland.illig@gmx.de>
  15                2005 Roland Illig <roland.illig@gmx.de>
  16                2009 Slava Zanko <slavazanko@google.com>
  17                2009 Andrew Borodin <aborodin@vmail.ru>
  18                2009 Ilia Maslakov <il.smind@gmail.com>
  19
  20    This file is part of the Midnight Commander.
  21
  22    The Midnight Commander is free software; you can redistribute it
  23    and/or modify it under the terms of the GNU General Public License as
  24    published by the Free Software Foundation; either version 2 of the
  25    License, or (at your option) any later version.
  26
  27    The Midnight Commander is distributed in the hope that it will be
  28    useful, but WITHOUT ANY WARRANTY; without even the implied warranty
  29    of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  30    General Public License for more details.
  31
  32    You should have received a copy of the GNU General Public License
  33    along with this program; if not, write to the Free Software
  34    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
  35    MA 02110-1301, USA.
  36  */
  37
  38 /*
  39    This cache provides you with a fast lookup to map file offsets into
  40    line/column pairs and vice versa. The interface to the mapping is
  41    provided by the functions mcview_coord_to_offset() and
  42    mcview_offset_to_coord().
  43
  44    The cache is implemented as a simple sorted array holding entries
  45    that map some of the offsets to their line/column pair. Entries that
  46    are not cached themselves are interpolated (exactly) from their
  47    neighbor entries. The algorithm used for determining the line/column
  48    for a specific offset needs to be kept synchronized with the one used
  49    in display().
  50 */
  51
  52 #include <config.h>
  53
  54 #include "../src/global.h"
  55 #include "../src/tty/tty.h"
  56 #include "internal.h"
  57
  58 #define VIEW_COORD_CACHE_GRANUL 1024
  59
  60 /*** global variables ****************************************************************************/
  61
  62 /*** file scope macro definitions ****************************************************************/
  63
  64 /*** file scope type declarations ****************************************************************/
  65
  66 /*** file scope variables ************************************************************************/
  67
  68 /*** file scope functions ************************************************************************/
  69
  70 /*** public functions ****************************************************************************/
  71
  72 /* --------------------------------------------------------------------------------------------- */
  73
  74 gboolean
  75 mcview_coord_cache_entry_less (const struct coord_cache_entry *a,
  76                                const struct coord_cache_entry *b, enum ccache_type crit,
  77                                gboolean nroff_mode)
  78 {
  79     if (crit == CCACHE_OFFSET)
  80         return (a->cc_offset < b->cc_offset);
  81
  82     if (a->cc_line < b->cc_line)
  83         return TRUE;
  84
  85     if (a->cc_line == b->cc_line) {
  86         if (nroff_mode) {
  87             return (a->cc_nroff_column < b->cc_nroff_column);
  88         } else {
  89             return (a->cc_column < b->cc_column);
  90         }
  91     }
  92     return FALSE;
  93 }
  94
  95 /* --------------------------------------------------------------------------------------------- */
  96
  97 #ifdef MC_ENABLE_DEBUGGING_CODE
  98
  99 void
 100 mcview_ccache_dump (mcview_t * view)
 101 {
 102     FILE *f;
 103     off_t offset, line, column, nextline_offset, filesize;
 104     guint i;
 105     const struct coord_cache_entry *cache;
 106
 107     assert (view->coord_cache != NULL);
 108
 109     filesize = mcview_get_filesize (view);
 110     cache = &(g_array_index (view->coord_cache, struct coord_cache_entry, 0));
 111
 112     f = fopen ("mcview-ccache.out", "w");
 113     if (f == NULL)
 114         return;
 115     (void) setvbuf (f, NULL, _IONBF, 0);
 116
 117     /* cache entries */
 118     for (i = 0; i < view->coord_cache->len; i++) {
 119         (void) fprintf (f,
 120                         "entry %8u  "
 121                         "offset %8" OFFSETTYPE_PRId "  "
 122                         "line %8" OFFSETTYPE_PRId "  "
 123                         "column %8" OFFSETTYPE_PRId "  "
 124                         "nroff_column %8" OFFSETTYPE_PRId "\n",
 125                         (unsigned int) i, cache[i].cc_offset, cache[i].cc_line,
 126                         cache[i].cc_column, cache[i].cc_nroff_column);
 127     }
 128     (void) fprintf (f, "\n");
 129
 130     /* offset -> line/column translation */
 131     for (offset = 0; offset < filesize; offset++) {
 132         mcview_offset_to_coord (view, &line, &column, offset);
 133         (void) fprintf (f,
 134                         "offset %8" OFFSETTYPE_PRId "  "
 135                         "line %8" OFFSETTYPE_PRId "  "
 136                         "column %8" OFFSETTYPE_PRId "\n", offset, line, column);
 137     }
 138
 139     /* line/column -> offset translation */
 140     for (line = 0; TRUE; line++) {
 141         mcview_coord_to_offset (view, &nextline_offset, line + 1, 0);
 142         (void) fprintf (f, "nextline_offset %8" OFFSETTYPE_PRId "\n", nextline_offset);
 143
 144         for (column = 0; TRUE; column++) {
 145             mcview_coord_to_offset (view, &offset, line, column);
 146             if (offset >= nextline_offset)
 147                 break;
 148
 149             (void) fprintf (f,
 150                             "line %8" OFFSETTYPE_PRId "  column %8" OFFSETTYPE_PRId "  offset %8"
 151                             OFFSETTYPE_PRId "\n", line, column, offset);
 152         }
 153
 154         if (nextline_offset >= filesize - 1)
 155             break;
 156     }
 157
 158     (void) fclose (f);
 159 }
 160 #endif
 161
 162 /* --------------------------------------------------------------------------------------------- */
 163
 164 /* Find and return the index of the last cache entry that is
 165  * smaller than ''coord'', according to the criterion ''sort_by''. */
 166 guint
 167 mcview_ccache_find (mcview_t * view, const struct coord_cache_entry *cache,
 168                     const struct coord_cache_entry *coord, enum ccache_type sort_by)
 169 {
 170     guint base, i, limit;
 171
 172     limit = view->coord_cache->len;
 173     assert (limit != 0);
 174
 175     base = 0;
 176     while (limit > 1) {
 177         i = base + limit / 2;
 178         if (mcview_coord_cache_entry_less (coord, &cache[i], sort_by, view->text_nroff_mode)) {
 179             /* continue the search in the lower half of the cache */
 180         } else {
 181             /* continue the search in the upper half of the cache */
 182             base = i;
 183         }
 184         limit = (limit + 1) / 2;
 185     }
 186     return base;
 187 }
 188
 189
 190 /* --------------------------------------------------------------------------------------------- */
 191
 192 /* Look up the missing components of ''coord'', which are given by
 193  * ''lookup_what''. The function returns the smallest value that
 194  * matches the existing components of ''coord''.
 195  */
 196 void
 197 mcview_ccache_lookup (mcview_t * view, struct coord_cache_entry *coord,
 198                       enum ccache_type lookup_what)
 199 {
 200     guint i;
 201     struct coord_cache_entry *cache, current, next, entry;
 202     enum ccache_type sorter;
 203     off_t limit;
 204     enum {
 205         NROFF_START,
 206         NROFF_BACKSPACE,
 207         NROFF_CONTINUATION
 208     } nroff_state;
 209
 210     if (!view->coord_cache) {
 211         view->coord_cache = g_array_new (FALSE, FALSE, sizeof (struct coord_cache_entry));
 212         current.cc_offset = 0;
 213         current.cc_line = 0;
 214         current.cc_column = 0;
 215         current.cc_nroff_column = 0;
 216         g_array_append_val (view->coord_cache, current);
 217     }
 218
 219     sorter = (lookup_what == CCACHE_OFFSET) ? CCACHE_LINECOL : CCACHE_OFFSET;
 220
 221     tty_enable_interrupt_key ();
 222
 223   retry:
 224     /* find the two neighbor entries in the cache */
 225     cache = &(g_array_index (view->coord_cache, struct coord_cache_entry, 0));
 226     i = mcview_ccache_find (view, cache, coord, sorter);
 227     /* now i points to the lower neighbor in the cache */
 228
 229     current = cache[i];
 230     if (i + 1 < view->coord_cache->len)
 231         limit = cache[i + 1].cc_offset;
 232     else
 233         limit = current.cc_offset + VIEW_COORD_CACHE_GRANUL;
 234
 235     entry = current;
 236     nroff_state = NROFF_START;
 237     for (; current.cc_offset < limit; current = next) {
 238         int c, nextc;
 239
 240         if (! mcview_get_byte (view, current.cc_offset, &c))
 241             break;
 242
 243         if (!mcview_coord_cache_entry_less (&current, coord, sorter, view->text_nroff_mode)) {
 244             if (lookup_what == CCACHE_OFFSET && view->text_nroff_mode && nroff_state != NROFF_START) {
 245                 /* don't break here */
 246             } else {
 247                 break;
 248             }
 249         }
 250
 251         /* Provide useful default values for ''next'' */
 252         next.cc_offset = current.cc_offset + 1;
 253         next.cc_line = current.cc_line;
 254         next.cc_column = current.cc_column + 1;
 255         next.cc_nroff_column = current.cc_nroff_column + 1;
 256
 257         /* and override some of them as necessary. */
 258         if (c == '\r') {
 259             mcview_get_byte_indexed (view, current.cc_offset, 1, &nextc);
 260
 261             /* Ignore '\r' if it is followed by '\r' or '\n'. If it is
 262              * followed by anything else, it is a Mac line ending and
 263              * produces a line break.
 264              */
 265             if (nextc == '\r' || nextc == '\n') {
 266                 next.cc_column = current.cc_column;
 267                 next.cc_nroff_column = current.cc_nroff_column;
 268             } else {
 269                 next.cc_line = current.cc_line + 1;
 270                 next.cc_column = 0;
 271                 next.cc_nroff_column = 0;
 272             }
 273
 274         } else if (nroff_state == NROFF_BACKSPACE) {
 275             next.cc_nroff_column = current.cc_nroff_column - 1;
 276
 277         } else if (c == '\t') {
 278             next.cc_column = mcview_offset_rounddown (current.cc_column, 8) + 8;
 279             next.cc_nroff_column = mcview_offset_rounddown (current.cc_nroff_column, 8) + 8;
 280
 281         } else if (c == '\n') {
 282             next.cc_line = current.cc_line + 1;
 283             next.cc_column = 0;
 284             next.cc_nroff_column = 0;
 285
 286         } else {
 287             /* Use all default values from above */
 288         }
 289
 290         switch (nroff_state) {
 291         case NROFF_START:
 292         case NROFF_CONTINUATION:
 293             if (mcview_is_nroff_sequence (view, current.cc_offset))
 294                 nroff_state = NROFF_BACKSPACE;
 295             else
 296                 nroff_state = NROFF_START;
 297             break;
 298         case NROFF_BACKSPACE:
 299             nroff_state = NROFF_CONTINUATION;
 300             break;
 301         }
 302
 303         /* Cache entries must guarantee that for each i < j,
 304          * line[i] <= line[j] and column[i] < column[j]. In the case of
 305          * nroff sequences and '\r' characters, this is not guaranteed,
 306          * so we cannot save them. */
 307         if (nroff_state == NROFF_START && c != '\r')
 308             entry = next;
 309     }
 310
 311     if (i + 1 == view->coord_cache->len && entry.cc_offset != cache[i].cc_offset) {
 312         g_array_append_val (view->coord_cache, entry);
 313
 314         if (!tty_got_interrupt ())
 315             goto retry;
 316     }
 317
 318     tty_disable_interrupt_key ();
 319
 320     if (lookup_what == CCACHE_OFFSET) {
 321         coord->cc_offset = current.cc_offset;
 322     } else {
 323         coord->cc_line = current.cc_line;
 324         coord->cc_column = current.cc_column;
 325         coord->cc_nroff_column = current.cc_nroff_column;
 326     }
 327 }
 328
 329 /* --------------------------------------------------------------------------------------------- */