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, 2011
   7    the Free Software Foundation, Inc.
   8
   9    Written by:
  10    Miguel de Icaza, 1994, 1995, 1998
  11    Janne Kukonlehto, 1994, 1995
  12    Jakub Jelinek, 1995
  13    Joseph M. Hinkle, 1996
  14    Norbert Warmuth, 1997
  15    Pavel Machek, 1998
  16    Roland Illig <roland.illig@gmx.de>, 2004, 2005
  17    Slava Zanko <slavazanko@google.com>, 2009
  18    Andrew Borodin <aborodin@vmail.ru>, 2009
  19    Ilia Maslakov <il.smind@gmail.com>, 2009
  20
  21    This file is part of the Midnight Commander.
  22
  23    The Midnight Commander is free software: you can redistribute it
  24    and/or modify it under the terms of the GNU General Public License as
  25    published by the Free Software Foundation, either version 3 of the License,
  26    or (at your option) any later version.
  27
  28    The Midnight Commander is distributed in the hope that it will be useful,
  29    but WITHOUT ANY WARRANTY; without even the implied warranty of
  30    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  31    GNU General Public License for more details.
  32
  33    You should have received a copy of the GNU General Public License
  34    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  35  */
  36
  37 /*
  38    This cache provides you with a fast lookup to map file offsets into
  39    line/column pairs and vice versa. The interface to the mapping is
  40    provided by the functions mcview_coord_to_offset() and
  41    mcview_offset_to_coord().
  42
  43    The cache is implemented as a simple sorted array holding entries
  44    that map some of the offsets to their line/column pair. Entries that
  45    are not cached themselves are interpolated (exactly) from their
  46    neighbor entries. The algorithm used for determining the line/column
  47    for a specific offset needs to be kept synchronized with the one used
  48    in display().
  49  */
  50
  51 #include <config.h>
  52
  53 #include <string.h>             /* for g_memmove() */
  54 #ifdef MC_ENABLE_DEBUGGING_CODE
  55 #include <inttypes.h>           /* uintmax_t */
  56 #endif
  57
  58 #include "lib/global.h"
  59 #include "lib/tty/tty.h"
  60 #include "internal.h"
  61
  62 /*** global variables ****************************************************************************/
  63
  64 /*** file scope macro definitions ****************************************************************/
  65
  66 #define VIEW_COORD_CACHE_GRANUL 1024
  67 #define CACHE_CAPACITY_DELTA 64
  68
  69 /*** file scope type declarations ****************************************************************/
  70
  71 typedef gboolean (*cmp_func_t) (const coord_cache_entry_t * a, const coord_cache_entry_t * b);
  72
  73 /*** file scope variables ************************************************************************/
  74
  75 /*** file scope functions ************************************************************************/
  76 /* --------------------------------------------------------------------------------------------- */
  77
  78 /* insert new cache entry into the cache */
  79 static void
  80 mcview_ccache_add_entry (coord_cache_t * cache, size_t pos, const coord_cache_entry_t * entry)
  81 {
  82     if ((cache == NULL) || (entry == NULL))
  83         return;
  84
  85     pos = min (pos, cache->size);
  86
  87     /* increase cache capacity if needed */
  88     if (cache->size == cache->capacity)
  89     {
  90         cache->capacity += CACHE_CAPACITY_DELTA;
  91         cache->cache = g_realloc (cache->cache, cache->capacity * sizeof (coord_cache_entry_t *));
  92     }
  93
  94     /* insert new entry */
  95     if (pos != cache->size)
  96         g_memmove (cache->cache[pos + 1], cache->cache[pos],
  97                    (cache->size - pos) * sizeof (coord_cache_entry_t *));
  98     cache->cache[pos] = g_memdup (entry, sizeof (coord_cache_entry_t));
  99     cache->size++;
 100 }
 101
 102 /* --------------------------------------------------------------------------------------------- */
 103
 104 static gboolean
 105 mcview_coord_cache_entry_less_offset (const coord_cache_entry_t * a, const coord_cache_entry_t * b)
 106 {
 107     return (a->cc_offset < b->cc_offset);
 108 }
 109
 110 /* --------------------------------------------------------------------------------------------- */
 111
 112 static gboolean
 113 mcview_coord_cache_entry_less_plain (const coord_cache_entry_t * a, const coord_cache_entry_t * b)
 114 {
 115     if (a->cc_line < b->cc_line)
 116         return TRUE;
 117
 118     if (a->cc_line == b->cc_line)
 119         return (a->cc_column < b->cc_column);
 120
 121     return FALSE;
 122 }
 123
 124
 125 /* --------------------------------------------------------------------------------------------- */
 126
 127 static gboolean
 128 mcview_coord_cache_entry_less_nroff (const coord_cache_entry_t * a, const coord_cache_entry_t * b)
 129 {
 130     if (a->cc_line < b->cc_line)
 131         return TRUE;
 132
 133     if (a->cc_line == b->cc_line)
 134         return (a->cc_nroff_column < b->cc_nroff_column);
 135
 136     return FALSE;
 137 }
 138
 139
 140 /* --------------------------------------------------------------------------------------------- */
 141 /** Find and return the index of the last cache entry that is
 142  * smaller than ''coord'', according to the criterion ''sort_by''. */
 143
 144 static inline size_t
 145 mcview_ccache_find (mcview_t * view, const coord_cache_entry_t * coord, cmp_func_t cmp_func)
 146 {
 147     size_t base = 0;
 148     size_t limit = view->coord_cache->size;
 149
 150 #ifdef HAVE_ASSERT_H
 151     assert (limit != 0);
 152 #endif
 153
 154     while (limit > 1)
 155     {
 156         size_t i;
 157
 158         i = base + limit / 2;
 159         if (cmp_func (coord, view->coord_cache->cache[i]))
 160         {
 161             /* continue the search in the lower half of the cache */
 162         }
 163         else
 164         {
 165             /* continue the search in the upper half of the cache */
 166             base = i;
 167         }
 168         limit = (limit + 1) / 2;
 169     }
 170     return base;
 171 }
 172
 173 /* --------------------------------------------------------------------------------------------- */
 174 /*** public functions ****************************************************************************/
 175 /* --------------------------------------------------------------------------------------------- */
 176
 177 coord_cache_t *
 178 coord_cache_new (void)
 179 {
 180     coord_cache_t *cache;
 181
 182     cache = g_new (coord_cache_t, 1);
 183     cache->size = 0;
 184     cache->capacity = CACHE_CAPACITY_DELTA;
 185     cache->cache = g_malloc0 (cache->capacity * sizeof (coord_cache_entry_t *));
 186
 187     return cache;
 188 }
 189
 190 /* --------------------------------------------------------------------------------------------- */
 191
 192 void
 193 coord_cache_free (coord_cache_t * cache)
 194 {
 195     if (cache != NULL)
 196     {
 197         size_t i;
 198
 199         for (i = 0; i < cache->size; i++)
 200             g_free (cache->cache[i]);
 201
 202         g_free (cache->cache);
 203         g_free (cache);
 204     }
 205 }
 206
 207 /* --------------------------------------------------------------------------------------------- */
 208
 209 #ifdef MC_ENABLE_DEBUGGING_CODE
 210
 211 void
 212 mcview_ccache_dump (mcview_t * view)
 213 {
 214     FILE *f;
 215     off_t offset, line, column, nextline_offset, filesize;
 216     guint i;
 217     const coord_cache_t *cache = view->coord_cache;
 218
 219 #ifdef HAVE_ASSERT_H
 220     assert (cache != NULL);
 221 #endif
 222
 223     filesize = mcview_get_filesize (view);
 224
 225     f = fopen ("mcview-ccache.out", "w");
 226     if (f == NULL)
 227         return;
 228     (void) setvbuf (f, NULL, _IONBF, 0);
 229
 230     /* cache entries */
 231     for (i = 0; i < cache->size; i++)
 232     {
 233         (void) fprintf (f,
 234                         "entry %8u  offset %8" PRIuMAX
 235                         "  line %8" PRIuMAX "  column %8" PRIuMAX
 236                         "  nroff_column %8" PRIuMAX "\n",
 237                         (unsigned int) i,
 238                         (uintmax_t) cache->cache[i]->cc_offset,
 239                         (uintmax_t) cache->cache[i]->cc_line,
 240                         (uintmax_t) cache->cache[i]->cc_column,
 241                         (uintmax_t) cache->cache[i]->cc_nroff_column);
 242     }
 243     (void) fprintf (f, "\n");
 244
 245     /* offset -> line/column translation */
 246     for (offset = 0; offset < filesize; offset++)
 247     {
 248         mcview_offset_to_coord (view, &line, &column, offset);
 249         (void) fprintf (f,
 250                         "offset %8" PRIuMAX "  line %8" PRIuMAX "  column %8" PRIuMAX "\n",
 251                         (uintmax_t) offset, (uintmax_t) line, (uintmax_t) column);
 252     }
 253
 254     /* line/column -> offset translation */
 255     for (line = 0; TRUE; line++)
 256     {
 257         mcview_coord_to_offset (view, &nextline_offset, line + 1, 0);
 258         (void) fprintf (f, "nextline_offset %8" PRIuMAX "\n", (uintmax_t) nextline_offset);
 259
 260         for (column = 0; TRUE; column++)
 261         {
 262             mcview_coord_to_offset (view, &offset, line, column);
 263             if (offset >= nextline_offset)
 264                 break;
 265
 266             (void) fprintf (f,
 267                             "line %8" PRIuMAX "  column %8" PRIuMAX "  offset %8" PRIuMAX "\n",
 268                             (uintmax_t) line, (uintmax_t) column, (uintmax_t) offset);
 269         }
 270
 271         if (nextline_offset >= filesize - 1)
 272             break;
 273     }
 274
 275     (void) fclose (f);
 276 }
 277 #endif
 278
 279 /* --------------------------------------------------------------------------------------------- */
 280 /** Look up the missing components of ''coord'', which are given by
 281  * ''lookup_what''. The function returns the smallest value that
 282  * matches the existing components of ''coord''.
 283  */
 284
 285 void
 286 mcview_ccache_lookup (mcview_t * view, coord_cache_entry_t * coord, enum ccache_type lookup_what)
 287 {
 288     size_t i;
 289     coord_cache_t *cache;
 290     coord_cache_entry_t current, next, entry;
 291     enum ccache_type sorter;
 292     off_t limit;
 293     cmp_func_t cmp_func;
 294
 295     enum
 296     {
 297         NROFF_START,
 298         NROFF_BACKSPACE,
 299         NROFF_CONTINUATION
 300     } nroff_state;
 301
 302     if (view->coord_cache == NULL)
 303         view->coord_cache = coord_cache_new ();
 304
 305     cache = view->coord_cache;
 306
 307     if (cache->size == 0)
 308     {
 309         current.cc_offset = 0;
 310         current.cc_line = 0;
 311         current.cc_column = 0;
 312         current.cc_nroff_column = 0;
 313         mcview_ccache_add_entry (cache, 0, &current);
 314     }
 315
 316     sorter = (lookup_what == CCACHE_OFFSET) ? CCACHE_LINECOL : CCACHE_OFFSET;
 317
 318     if (sorter == CCACHE_OFFSET)
 319         cmp_func = mcview_coord_cache_entry_less_offset;
 320     else if (view->text_nroff_mode)
 321         cmp_func = mcview_coord_cache_entry_less_nroff;
 322     else
 323         cmp_func = mcview_coord_cache_entry_less_plain;
 324
 325
 326     tty_enable_interrupt_key ();
 327
 328   retry:
 329     /* find the two neighbor entries in the cache */
 330     i = mcview_ccache_find (view, coord, cmp_func);
 331     /* now i points to the lower neighbor in the cache */
 332
 333     current = *cache->cache[i];
 334     if (i + 1 < view->coord_cache->size)
 335         limit = cache->cache[i + 1]->cc_offset;
 336     else
 337         limit = current.cc_offset + VIEW_COORD_CACHE_GRANUL;
 338
 339     entry = current;
 340     nroff_state = NROFF_START;
 341     for (; current.cc_offset < limit; current = next)
 342     {
 343         int c, nextc;
 344
 345         if (!mcview_get_byte (view, current.cc_offset, &c))
 346             break;
 347
 348         if (!cmp_func (&current, coord))
 349         {
 350             if (lookup_what == CCACHE_OFFSET && view->text_nroff_mode && nroff_state != NROFF_START)
 351             {
 352                 /* don't break here */
 353             }
 354             else
 355             {
 356                 break;
 357             }
 358         }
 359
 360         /* Provide useful default values for ''next'' */
 361         next.cc_offset = current.cc_offset + 1;
 362         next.cc_line = current.cc_line;
 363         next.cc_column = current.cc_column + 1;
 364         next.cc_nroff_column = current.cc_nroff_column + 1;
 365
 366         /* and override some of them as necessary. */
 367         if (c == '\r')
 368         {
 369             mcview_get_byte_indexed (view, current.cc_offset, 1, &nextc);
 370
 371             /* Ignore '\r' if it is followed by '\r' or '\n'. If it is
 372              * followed by anything else, it is a Mac line ending and
 373              * produces a line break.
 374              */
 375             if (nextc == '\r' || nextc == '\n')
 376             {
 377                 next.cc_column = current.cc_column;
 378                 next.cc_nroff_column = current.cc_nroff_column;
 379             }
 380             else
 381             {
 382                 next.cc_line = current.cc_line + 1;
 383                 next.cc_column = 0;
 384                 next.cc_nroff_column = 0;
 385             }
 386
 387         }
 388         else if (nroff_state == NROFF_BACKSPACE)
 389         {
 390             next.cc_nroff_column = current.cc_nroff_column - 1;
 391
 392         }
 393         else if (c == '\t')
 394         {
 395             next.cc_column = mcview_offset_rounddown (current.cc_column, 8) + 8;
 396             next.cc_nroff_column = mcview_offset_rounddown (current.cc_nroff_column, 8) + 8;
 397
 398         }
 399         else if (c == '\n')
 400         {
 401             next.cc_line = current.cc_line + 1;
 402             next.cc_column = 0;
 403             next.cc_nroff_column = 0;
 404
 405         }
 406         else
 407         {
 408             /* Use all default values from above */
 409         }
 410
 411         switch (nroff_state)
 412         {
 413         case NROFF_START:
 414         case NROFF_CONTINUATION:
 415             nroff_state = mcview_is_nroff_sequence (view, current.cc_offset)
 416                 ? NROFF_BACKSPACE : NROFF_START;
 417             break;
 418         case NROFF_BACKSPACE:
 419             nroff_state = NROFF_CONTINUATION;
 420             break;
 421         }
 422
 423         /* Cache entries must guarantee that for each i < j,
 424          * line[i] <= line[j] and column[i] < column[j]. In the case of
 425          * nroff sequences and '\r' characters, this is not guaranteed,
 426          * so we cannot save them. */
 427         if (nroff_state == NROFF_START && c != '\r')
 428             entry = next;
 429     }
 430
 431     if (i + 1 == cache->size && entry.cc_offset != cache->cache[i]->cc_offset)
 432     {
 433         mcview_ccache_add_entry (cache, cache->size, &entry);
 434
 435         if (!tty_got_interrupt ())
 436             goto retry;
 437     }
 438
 439     tty_disable_interrupt_key ();
 440
 441     if (lookup_what == CCACHE_OFFSET)
 442     {
 443         coord->cc_offset = current.cc_offset;
 444     }
 445     else
 446     {
 447         coord->cc_line = current.cc_line;
 448         coord->cc_column = current.cc_column;
 449         coord->cc_nroff_column = current.cc_nroff_column;
 450     }
 451 }
 452
 453 /* --------------------------------------------------------------------------------------------- */