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