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 <string.h>             /* for g_memmove() */
  55 #ifdef MC_ENABLE_DEBUGGING_CODE
  56 #include <stdint.h>             /* uintmax_t */
  57 #endif
  58
  59 #include "lib/global.h"
  60 #include "lib/tty/tty.h"
  61 #include "internal.h"
  62
  63 /*** global variables ****************************************************************************/
  64
  65 /*** file scope macro definitions ****************************************************************/
  66
  67 #define VIEW_COORD_CACHE_GRANUL 1024
  68 #define CACHE_CAPACITY_DELTA 64
  69
  70 /*** file scope type declarations ****************************************************************/
  71
  72 typedef gboolean (*cmp_func_t) (const coord_cache_entry_t * a, const coord_cache_entry_t * b);
  73
  74 /*** file scope variables ************************************************************************/
  75
  76 /*** file scope functions ************************************************************************/
  77 /* --------------------------------------------------------------------------------------------- */
  78
  79 /* insert new cache entry into the cache */
  80 static void
  81 mcview_ccache_add_entry (coord_cache_t * cache, size_t pos, const coord_cache_entry_t * entry)
  82 {
  83     if ((cache == NULL) || (entry == NULL))
  84         return;
  85
  86     pos = min (pos, cache->size);
  87
  88     /* increase cache capacity if needed */
  89     if (cache->size == cache->capacity)
  90     {
  91         cache->capacity += CACHE_CAPACITY_DELTA;
  92         cache->cache = g_realloc (cache->cache, cache->capacity * sizeof (coord_cache_entry_t *));
  93     }
  94
  95     /* insert new entry */
  96     if (pos != cache->size)
  97         g_memmove (cache->cache[pos + 1], cache->cache[pos],
  98                    (cache->size - pos) * sizeof (coord_cache_entry_t *));
  99     cache->cache[pos] = g_memdup (entry, sizeof (coord_cache_entry_t));
 100     cache->size++;
 101 }
 102
 103 /* --------------------------------------------------------------------------------------------- */
 104
 105 static gboolean
 106 mcview_coord_cache_entry_less_offset (const coord_cache_entry_t * a, const coord_cache_entry_t * b)
 107 {
 108     return (a->cc_offset < b->cc_offset);
 109 }
 110
 111 /* --------------------------------------------------------------------------------------------- */
 112
 113 static gboolean
 114 mcview_coord_cache_entry_less_plain (const coord_cache_entry_t * a, const coord_cache_entry_t * b)
 115 {
 116     if (a->cc_line < b->cc_line)
 117         return TRUE;
 118
 119     if (a->cc_line == b->cc_line)
 120         return (a->cc_column < b->cc_column);
 121
 122     return FALSE;
 123 }
 124
 125
 126 /* --------------------------------------------------------------------------------------------- */
 127
 128 static gboolean
 129 mcview_coord_cache_entry_less_nroff (const coord_cache_entry_t * a, const coord_cache_entry_t * b)
 130 {
 131     if (a->cc_line < b->cc_line)
 132         return TRUE;
 133
 134     if (a->cc_line == b->cc_line)
 135         return (a->cc_nroff_column < b->cc_nroff_column);
 136
 137     return FALSE;
 138 }
 139
 140
 141 /* --------------------------------------------------------------------------------------------- */
 142 /** Find and return the index of the last cache entry that is
 143  * smaller than ''coord'', according to the criterion ''sort_by''. */
 144
 145 static inline size_t
 146 mcview_ccache_find (mcview_t * view, const coord_cache_entry_t * coord, cmp_func_t cmp_func)
 147 {
 148     size_t base = 0;
 149     size_t limit = view->coord_cache->size;
 150
 151     assert (limit != 0);
 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 (coord_cache_entry_t *));
 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 (mcview_t * 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     assert (cache != NULL);
 219
 220     filesize = mcview_get_filesize (view);
 221
 222     f = fopen ("mcview-ccache.out", "w");
 223     if (f == NULL)
 224         return;
 225     (void) setvbuf (f, NULL, _IONBF, 0);
 226
 227     /* cache entries */
 228     for (i = 0; i < cache->size; i++)
 229     {
 230         (void) fprintf (f,
 231                         "entry %8u  offset %8ju  line %8ju  column %8ju  nroff_column %8ju\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 %8ju  line %8ju  column %8ju\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 %8ju\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 %8ju  column %8ju  offset %8ju\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 (mcview_t * 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, nextc;
 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             mcview_get_byte_indexed (view, current.cc_offset, 1, &nextc);
 365
 366             /* Ignore '\r' if it is followed by '\r' or '\n'. If it is
 367              * followed by anything else, it is a Mac line ending and
 368              * produces a line break.
 369              */
 370             if (nextc == '\r' || nextc == '\n')
 371             {
 372                 next.cc_column = current.cc_column;
 373                 next.cc_nroff_column = current.cc_nroff_column;
 374             }
 375             else
 376             {
 377                 next.cc_line = current.cc_line + 1;
 378                 next.cc_column = 0;
 379                 next.cc_nroff_column = 0;
 380             }
 381
 382         }
 383         else if (nroff_state == NROFF_BACKSPACE)
 384         {
 385             next.cc_nroff_column = current.cc_nroff_column - 1;
 386
 387         }
 388         else if (c == '\t')
 389         {
 390             next.cc_column = mcview_offset_rounddown (current.cc_column, 8) + 8;
 391             next.cc_nroff_column = mcview_offset_rounddown (current.cc_nroff_column, 8) + 8;
 392
 393         }
 394         else if (c == '\n')
 395         {
 396             next.cc_line = current.cc_line + 1;
 397             next.cc_column = 0;
 398             next.cc_nroff_column = 0;
 399
 400         }
 401         else
 402         {
 403             /* Use all default values from above */
 404         }
 405
 406         switch (nroff_state)
 407         {
 408         case NROFF_START:
 409         case NROFF_CONTINUATION:
 410             nroff_state = mcview_is_nroff_sequence (view, current.cc_offset)
 411                 ? NROFF_BACKSPACE : NROFF_START;
 412             break;
 413         case NROFF_BACKSPACE:
 414             nroff_state = NROFF_CONTINUATION;
 415             break;
 416         }
 417
 418         /* Cache entries must guarantee that for each i < j,
 419          * line[i] <= line[j] and column[i] < column[j]. In the case of
 420          * nroff sequences and '\r' characters, this is not guaranteed,
 421          * so we cannot save them. */
 422         if (nroff_state == NROFF_START && c != '\r')
 423             entry = next;
 424     }
 425
 426     if (i + 1 == cache->size && entry.cc_offset != cache->cache[i]->cc_offset)
 427     {
 428         mcview_ccache_add_entry (cache, cache->size, &entry);
 429
 430         if (!tty_got_interrupt ())
 431             goto retry;
 432     }
 433
 434     tty_disable_interrupt_key ();
 435
 436     if (lookup_what == CCACHE_OFFSET)
 437     {
 438         coord->cc_offset = current.cc_offset;
 439     }
 440     else
 441     {
 442         coord->cc_line = current.cc_line;
 443         coord->cc_column = current.cc_column;
 444         coord->cc_nroff_column = current.cc_nroff_column;
 445     }
 446 }
 447
 448 /* --------------------------------------------------------------------------------------------- */