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 /* --------------------------------------------------------------------------------------------- */
  71
  72 /* Find and return the index of the last cache entry that is
  73  * smaller than ''coord'', according to the criterion ''sort_by''. */
  74 static guint
  75 mcview_ccache_find (mcview_t * view, const struct coord_cache_entry *cache,
  76                     const struct coord_cache_entry *coord, enum ccache_type sort_by)
  77 {
  78     guint base, i, limit;
  79
  80     limit = view->coord_cache->len;
  81     assert (limit != 0);
  82
  83     base = 0;
  84     while (limit > 1) {
  85         i = base + limit / 2;
  86         if (mcview_coord_cache_entry_less (coord, &cache[i], sort_by, view->text_nroff_mode)) {
  87             /* continue the search in the lower half of the cache */
  88         } else {
  89             /* continue the search in the upper half of the cache */
  90             base = i;
  91         }
  92         limit = (limit + 1) / 2;
  93     }
  94     return base;
  95 }
  96
  97
  98 /* --------------------------------------------------------------------------------------------- */
  99
 100 /*** public functions ****************************************************************************/
 101
 102 /* --------------------------------------------------------------------------------------------- */
 103
 104 gboolean
 105 mcview_coord_cache_entry_less (const struct coord_cache_entry *a,
 106                                const struct coord_cache_entry *b, enum ccache_type crit,
 107                                gboolean nroff_mode)
 108 {
 109     if (crit == CCACHE_OFFSET)
 110         return (a->cc_offset < b->cc_offset);
 111
 112     if (a->cc_line < b->cc_line)
 113         return TRUE;
 114
 115     if (a->cc_line == b->cc_line) {
 116         if (nroff_mode) {
 117             return (a->cc_nroff_column < b->cc_nroff_column);
 118         } else {
 119             return (a->cc_column < b->cc_column);
 120         }
 121     }
 122     return FALSE;
 123 }
 124
 125 /* --------------------------------------------------------------------------------------------- */
 126
 127 #ifdef MC_ENABLE_DEBUGGING_CODE
 128
 129 void
 130 mcview_ccache_dump (mcview_t * view)
 131 {
 132     FILE *f;
 133     off_t offset, line, column, nextline_offset, filesize;
 134     guint i;
 135     const struct coord_cache_entry *cache;
 136
 137     assert (view->coord_cache != NULL);
 138
 139     filesize = mcview_get_filesize (view);
 140     cache = &(g_array_index (view->coord_cache, struct coord_cache_entry, 0));
 141
 142     f = fopen ("mcview-ccache.out", "w");
 143     if (f == NULL)
 144         return;
 145     (void) setvbuf (f, NULL, _IONBF, 0);
 146
 147     /* cache entries */
 148     for (i = 0; i < view->coord_cache->len; i++) {
 149         (void) fprintf (f,
 150                         "entry %8u  "
 151                         "offset %8" OFFSETTYPE_PRId "  "
 152                         "line %8" OFFSETTYPE_PRId "  "
 153                         "column %8" OFFSETTYPE_PRId "  "
 154                         "nroff_column %8" OFFSETTYPE_PRId "\n",
 155                         (unsigned int) i, cache[i].cc_offset, cache[i].cc_line,
 156                         cache[i].cc_column, cache[i].cc_nroff_column);
 157     }
 158     (void) fprintf (f, "\n");
 159
 160     /* offset -> line/column translation */
 161     for (offset = 0; offset < filesize; offset++) {
 162         mcview_offset_to_coord (view, &line, &column, offset);
 163         (void) fprintf (f,
 164                         "offset %8" OFFSETTYPE_PRId "  "
 165                         "line %8" OFFSETTYPE_PRId "  "
 166                         "column %8" OFFSETTYPE_PRId "\n", offset, line, column);
 167     }
 168
 169     /* line/column -> offset translation */
 170     for (line = 0; TRUE; line++) {
 171         mcview_coord_to_offset (view, &nextline_offset, line + 1, 0);
 172         (void) fprintf (f, "nextline_offset %8" OFFSETTYPE_PRId "\n", nextline_offset);
 173
 174         for (column = 0; TRUE; column++) {
 175             mcview_coord_to_offset (view, &offset, line, column);
 176             if (offset >= nextline_offset)
 177                 break;
 178
 179             (void) fprintf (f,
 180                             "line %8" OFFSETTYPE_PRId "  column %8" OFFSETTYPE_PRId "  offset %8"
 181                             OFFSETTYPE_PRId "\n", line, column, offset);
 182         }
 183
 184         if (nextline_offset >= filesize - 1)
 185             break;
 186     }
 187
 188     (void) fclose (f);
 189 }
 190 #endif
 191
 192 /* --------------------------------------------------------------------------------------------- */
 193
 194
 195 /* Look up the missing components of ''coord'', which are given by
 196  * ''lookup_what''. The function returns the smallest value that
 197  * matches the existing components of ''coord''.
 198  */
 199 void
 200 mcview_ccache_lookup (mcview_t * view, struct coord_cache_entry *coord,
 201                       enum ccache_type lookup_what)
 202 {
 203     guint i;
 204     struct coord_cache_entry *cache, current, next, entry;
 205     enum ccache_type sorter;
 206     off_t limit;
 207     enum {
 208         NROFF_START,
 209         NROFF_BACKSPACE,
 210         NROFF_CONTINUATION
 211     } nroff_state;
 212
 213     if (!view->coord_cache) {
 214         view->coord_cache = g_array_new (FALSE, FALSE, sizeof (struct coord_cache_entry));
 215         current.cc_offset = 0;
 216         current.cc_line = 0;
 217         current.cc_column = 0;
 218         current.cc_nroff_column = 0;
 219         g_array_append_val (view->coord_cache, current);
 220     }
 221
 222     sorter = (lookup_what == CCACHE_OFFSET) ? CCACHE_LINECOL : CCACHE_OFFSET;
 223
 224     tty_enable_interrupt_key ();
 225
 226   retry:
 227     /* find the two neighbor entries in the cache */
 228     cache = &(g_array_index (view->coord_cache, struct coord_cache_entry, 0));
 229     i = mcview_ccache_find (view, cache, coord, sorter);
 230     /* now i points to the lower neighbor in the cache */
 231
 232     current = cache[i];
 233     if (i + 1 < view->coord_cache->len)
 234         limit = cache[i + 1].cc_offset;
 235     else
 236         limit = current.cc_offset + VIEW_COORD_CACHE_GRANUL;
 237
 238     entry = current;
 239     nroff_state = NROFF_START;
 240     for (; current.cc_offset < limit; current = next) {
 241         int c, nextc;
 242
 243         if (! mcview_get_byte (view, current.cc_offset, &c))
 244             break;
 245
 246         if (!mcview_coord_cache_entry_less (&current, coord, sorter, view->text_nroff_mode)) {
 247             if (lookup_what == CCACHE_OFFSET && view->text_nroff_mode && nroff_state != NROFF_START) {
 248                 /* don't break here */
 249             } else {
 250                 break;
 251             }
 252         }
 253
 254         /* Provide useful default values for ''next'' */
 255         next.cc_offset = current.cc_offset + 1;
 256         next.cc_line = current.cc_line;
 257         next.cc_column = current.cc_column + 1;
 258         next.cc_nroff_column = current.cc_nroff_column + 1;
 259
 260         /* and override some of them as necessary. */
 261         if (c == '\r') {
 262             mcview_get_byte_indexed (view, current.cc_offset, 1, &nextc);
 263
 264             /* Ignore '\r' if it is followed by '\r' or '\n'. If it is
 265              * followed by anything else, it is a Mac line ending and
 266              * produces a line break.
 267              */
 268             if (nextc == '\r' || nextc == '\n') {
 269                 next.cc_column = current.cc_column;
 270                 next.cc_nroff_column = current.cc_nroff_column;
 271             } else {
 272                 next.cc_line = current.cc_line + 1;
 273                 next.cc_column = 0;
 274                 next.cc_nroff_column = 0;
 275             }
 276
 277         } else if (nroff_state == NROFF_BACKSPACE) {
 278             next.cc_nroff_column = current.cc_nroff_column - 1;
 279
 280         } else if (c == '\t') {
 281             next.cc_column = mcview_offset_rounddown (current.cc_column, 8) + 8;
 282             next.cc_nroff_column = mcview_offset_rounddown (current.cc_nroff_column, 8) + 8;
 283
 284         } else if (c == '\n') {
 285             next.cc_line = current.cc_line + 1;
 286             next.cc_column = 0;
 287             next.cc_nroff_column = 0;
 288
 289         } else {
 290             /* Use all default values from above */
 291         }
 292
 293         switch (nroff_state) {
 294         case NROFF_START:
 295         case NROFF_CONTINUATION:
 296             if (mcview_is_nroff_sequence (view, current.cc_offset))
 297                 nroff_state = NROFF_BACKSPACE;
 298             else
 299                 nroff_state = NROFF_START;
 300             break;
 301         case NROFF_BACKSPACE:
 302             nroff_state = NROFF_CONTINUATION;
 303             break;
 304         }
 305
 306         /* Cache entries must guarantee that for each i < j,
 307          * line[i] <= line[j] and column[i] < column[j]. In the case of
 308          * nroff sequences and '\r' characters, this is not guaranteed,
 309          * so we cannot save them. */
 310         if (nroff_state == NROFF_START && c != '\r')
 311             entry = next;
 312     }
 313
 314     if (i + 1 == view->coord_cache->len && entry.cc_offset != cache[i].cc_offset) {
 315         g_array_append_val (view->coord_cache, entry);
 316
 317         if (!tty_got_interrupt ())
 318             goto retry;
 319     }
 320
 321     tty_disable_interrupt_key ();
 322
 323     if (lookup_what == CCACHE_OFFSET) {
 324         coord->cc_offset = current.cc_offset;
 325     } else {
 326         coord->cc_line = current.cc_line;
 327         coord->cc_column = current.cc_column;
 328         coord->cc_nroff_column = current.cc_nroff_column;
 329     }
 330 }
 331
 332 /* --------------------------------------------------------------------------------------------- */