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-2016
   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 #ifdef HAVE_ASSERT_H
 150     assert (limit != 0);
 151 #endif
 152
 153     while (limit > 1)
 154     {
 155         size_t i;
 156
 157         i = base + limit / 2;
 158         if (cmp_func (coord, view->coord_cache->cache[i]))
 159         {
 160             /* continue the search in the lower half of the cache */
 161         }
 162         else
 163         {
 164             /* continue the search in the upper half of the cache */
 165             base = i;
 166         }
 167         limit = (limit + 1) / 2;
 168     }
 169     return base;
 170 }
 171
 172 /* --------------------------------------------------------------------------------------------- */
 173 /*** public functions ****************************************************************************/
 174 /* --------------------------------------------------------------------------------------------- */
 175
 176 coord_cache_t *
 177 coord_cache_new (void)
 178 {
 179     coord_cache_t *cache;
 180
 181     cache = g_new (coord_cache_t, 1);
 182     cache->size = 0;
 183     cache->capacity = CACHE_CAPACITY_DELTA;
 184     cache->cache = g_malloc0 (cache->capacity * sizeof (*cache->cache));
 185
 186     return cache;
 187 }
 188
 189 /* --------------------------------------------------------------------------------------------- */
 190
 191 void
 192 coord_cache_free (coord_cache_t * cache)
 193 {
 194     if (cache != NULL)
 195     {
 196         size_t i;
 197
 198         for (i = 0; i < cache->size; i++)
 199             g_free (cache->cache[i]);
 200
 201         g_free (cache->cache);
 202         g_free (cache);
 203     }
 204 }
 205
 206 /* --------------------------------------------------------------------------------------------- */
 207
 208 #ifdef MC_ENABLE_DEBUGGING_CODE
 209
 210 void
 211 mcview_ccache_dump (WView * view)
 212 {
 213     FILE *f;
 214     off_t offset, line, column, nextline_offset, filesize;
 215     guint i;
 216     const coord_cache_t *cache = view->coord_cache;
 217
 218 #ifdef HAVE_ASSERT_H
 219     assert (cache != NULL);
 220 #endif
 221
 222     filesize = mcview_get_filesize (view);
 223
 224     f = fopen ("mcview-ccache.out", "w");
 225     if (f == NULL)
 226         return;
 227     (void) setvbuf (f, NULL, _IONBF, 0);
 228
 229     /* cache entries */
 230     for (i = 0; i < cache->size; i++)
 231     {
 232         (void) fprintf (f,
 233                         "entry %8u  offset %8" PRIuMAX
 234                         "  line %8" PRIuMAX "  column %8" PRIuMAX
 235                         "  nroff_column %8" PRIuMAX "\n",
 236                         (unsigned int) i,
 237                         (uintmax_t) cache->cache[i]->cc_offset,
 238                         (uintmax_t) cache->cache[i]->cc_line,
 239                         (uintmax_t) cache->cache[i]->cc_column,
 240                         (uintmax_t) cache->cache[i]->cc_nroff_column);
 241     }
 242     (void) fprintf (f, "\n");
 243
 244     /* offset -> line/column translation */
 245     for (offset = 0; offset < filesize; offset++)
 246     {
 247         mcview_offset_to_coord (view, &line, &column, offset);
 248         (void) fprintf (f,
 249                         "offset %8" PRIuMAX "  line %8" PRIuMAX "  column %8" PRIuMAX "\n",
 250                         (uintmax_t) offset, (uintmax_t) line, (uintmax_t) column);
 251     }
 252
 253     /* line/column -> offset translation */
 254     for (line = 0; TRUE; line++)
 255     {
 256         mcview_coord_to_offset (view, &nextline_offset, line + 1, 0);
 257         (void) fprintf (f, "nextline_offset %8" PRIuMAX "\n", (uintmax_t) nextline_offset);
 258
 259         for (column = 0; TRUE; column++)
 260         {
 261             mcview_coord_to_offset (view, &offset, line, column);
 262             if (offset >= nextline_offset)
 263                 break;
 264
 265             (void) fprintf (f,
 266                             "line %8" PRIuMAX "  column %8" PRIuMAX "  offset %8" PRIuMAX "\n",
 267                             (uintmax_t) line, (uintmax_t) column, (uintmax_t) offset);
 268         }
 269
 270         if (nextline_offset >= filesize - 1)
 271             break;
 272     }
 273
 274     (void) fclose (f);
 275 }
 276 #endif
 277
 278 /* --------------------------------------------------------------------------------------------- */
 279 /** Look up the missing components of ''coord'', which are given by
 280  * ''lookup_what''. The function returns the smallest value that
 281  * matches the existing components of ''coord''.
 282  */
 283
 284 void
 285 mcview_ccache_lookup (WView * view, coord_cache_entry_t * coord, enum ccache_type lookup_what)
 286 {
 287     size_t i;
 288     coord_cache_t *cache;
 289     coord_cache_entry_t current, next, entry;
 290     enum ccache_type sorter;
 291     off_t limit;
 292     cmp_func_t cmp_func;
 293
 294     enum
 295     {
 296         NROFF_START,
 297         NROFF_BACKSPACE,
 298         NROFF_CONTINUATION
 299     } nroff_state;
 300
 301     if (view->coord_cache == NULL)
 302         view->coord_cache = coord_cache_new ();
 303
 304     cache = view->coord_cache;
 305
 306     if (cache->size == 0)
 307     {
 308         current.cc_offset = 0;
 309         current.cc_line = 0;
 310         current.cc_column = 0;
 311         current.cc_nroff_column = 0;
 312         mcview_ccache_add_entry (cache, 0, &current);
 313     }
 314
 315     sorter = (lookup_what == CCACHE_OFFSET) ? CCACHE_LINECOL : CCACHE_OFFSET;
 316
 317     if (sorter == CCACHE_OFFSET)
 318         cmp_func = mcview_coord_cache_entry_less_offset;
 319     else if (view->text_nroff_mode)
 320         cmp_func = mcview_coord_cache_entry_less_nroff;
 321     else
 322         cmp_func = mcview_coord_cache_entry_less_plain;
 323
 324
 325     tty_enable_interrupt_key ();
 326
 327   retry:
 328     /* find the two neighbor entries in the cache */
 329     i = mcview_ccache_find (view, coord, cmp_func);
 330     /* now i points to the lower neighbor in the cache */
 331
 332     current = *cache->cache[i];
 333     if (i + 1 < view->coord_cache->size)
 334         limit = cache->cache[i + 1]->cc_offset;
 335     else
 336         limit = current.cc_offset + VIEW_COORD_CACHE_GRANUL;
 337
 338     entry = current;
 339     nroff_state = NROFF_START;
 340     for (; current.cc_offset < limit; current = next)
 341     {
 342         int c;
 343
 344         if (!mcview_get_byte (view, current.cc_offset, &c))
 345             break;
 346
 347         if (!cmp_func (&current, coord))
 348         {
 349             if (lookup_what == CCACHE_OFFSET && view->text_nroff_mode && nroff_state != NROFF_START)
 350             {
 351                 /* don't break here */
 352             }
 353             else
 354             {
 355                 break;
 356             }
 357         }
 358
 359         /* Provide useful default values for ''next'' */
 360         next.cc_offset = current.cc_offset + 1;
 361         next.cc_line = current.cc_line;
 362         next.cc_column = current.cc_column + 1;
 363         next.cc_nroff_column = current.cc_nroff_column + 1;
 364
 365         /* and override some of them as necessary. */
 366         if (c == '\r')
 367         {
 368             int nextc = -1;
 369
 370             mcview_get_byte_indexed (view, current.cc_offset, 1, &nextc);
 371
 372             /* Ignore '\r' if it is followed by '\r' or '\n'. If it is
 373              * followed by anything else, it is a Mac line ending and
 374              * produces a line break.
 375              */
 376             if (nextc == '\r' || nextc == '\n')
 377             {
 378                 next.cc_column = current.cc_column;
 379                 next.cc_nroff_column = current.cc_nroff_column;
 380             }
 381             else
 382             {
 383                 next.cc_line = current.cc_line + 1;
 384                 next.cc_column = 0;
 385                 next.cc_nroff_column = 0;
 386             }
 387
 388         }
 389         else if (nroff_state == NROFF_BACKSPACE)
 390         {
 391             next.cc_nroff_column = current.cc_nroff_column - 1;
 392
 393         }
 394         else if (c == '\t')
 395         {
 396             next.cc_column = mcview_offset_rounddown (current.cc_column, 8) + 8;
 397             next.cc_nroff_column = mcview_offset_rounddown (current.cc_nroff_column, 8) + 8;
 398
 399         }
 400         else if (c == '\n')
 401         {
 402             next.cc_line = current.cc_line + 1;
 403             next.cc_column = 0;
 404             next.cc_nroff_column = 0;
 405
 406         }
 407         else
 408         {
 409             /* Use all default values from above */
 410         }
 411
 412         switch (nroff_state)
 413         {
 414         case NROFF_START:
 415         case NROFF_CONTINUATION:
 416             nroff_state = mcview_is_nroff_sequence (view, current.cc_offset)
 417                 ? NROFF_BACKSPACE : NROFF_START;
 418             break;
 419         case NROFF_BACKSPACE:
 420             nroff_state = NROFF_CONTINUATION;
 421             break;
 422         default:
 423             break;
 424         }
 425
 426         /* Cache entries must guarantee that for each i < j,
 427          * line[i] <= line[j] and column[i] < column[j]. In the case of
 428          * nroff sequences and '\r' characters, this is not guaranteed,
 429          * so we cannot save them. */
 430         if (nroff_state == NROFF_START && c != '\r')
 431             entry = next;
 432     }
 433
 434     if (i + 1 == cache->size && entry.cc_offset != cache->cache[i]->cc_offset)
 435     {
 436         mcview_ccache_add_entry (cache, cache->size, &entry);
 437
 438         if (!tty_got_interrupt ())
 439             goto retry;
 440     }
 441
 442     tty_disable_interrupt_key ();
 443
 444     if (lookup_what == CCACHE_OFFSET)
 445     {
 446         coord->cc_offset = current.cc_offset;
 447     }
 448     else
 449     {
 450         coord->cc_line = current.cc_line;
 451         coord->cc_column = current.cc_column;
 452         coord->cc_nroff_column = current.cc_nroff_column;
 453     }
 454 }
 455
 456 /* --------------------------------------------------------------------------------------------- */