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