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 <inttypes.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 %8" PRIuMAX
 232                         "  line %8" PRIuMAX "  column %8" PRIuMAX
 233                         "  nroff_column %8" PRIuMAX "\n",
 234                         (unsigned int) i,
 235                         (uintmax_t) cache->cache[i]->cc_offset,
 236                         (uintmax_t) cache->cache[i]->cc_line,
 237                         (uintmax_t) cache->cache[i]->cc_column,
 238                         (uintmax_t) cache->cache[i]->cc_nroff_column);
 239     }
 240     (void) fprintf (f, "\n");
 241
 242     /* offset -> line/column translation */
 243     for (offset = 0; offset < filesize; offset++)
 244     {
 245         mcview_offset_to_coord (view, &line, &column, offset);
 246         (void) fprintf (f,
 247                         "offset %8" PRIuMAX "  line %8" PRIuMAX "  column %8" PRIuMAX "\n",
 248                         (uintmax_t) offset, (uintmax_t) line, (uintmax_t) column);
 249     }
 250
 251     /* line/column -> offset translation */
 252     for (line = 0; TRUE; line++)
 253     {
 254         mcview_coord_to_offset (view, &nextline_offset, line + 1, 0);
 255         (void) fprintf (f, "nextline_offset %8" PRIuMAX "\n", (uintmax_t) nextline_offset);
 256
 257         for (column = 0; TRUE; column++)
 258         {
 259             mcview_coord_to_offset (view, &offset, line, column);
 260             if (offset >= nextline_offset)
 261                 break;
 262
 263             (void) fprintf (f,
 264                             "line %8" PRIuMAX "  column %8" PRIuMAX "  offset %8" PRIuMAX "\n",
 265                             (uintmax_t) line, (uintmax_t) column, (uintmax_t) offset);
 266         }
 267
 268         if (nextline_offset >= filesize - 1)
 269             break;
 270     }
 271
 272     (void) fclose (f);
 273 }
 274 #endif
 275
 276 /* --------------------------------------------------------------------------------------------- */
 277 /** Look up the missing components of ''coord'', which are given by
 278  * ''lookup_what''. The function returns the smallest value that
 279  * matches the existing components of ''coord''.
 280  */
 281
 282 void
 283 mcview_ccache_lookup (mcview_t * view, coord_cache_entry_t * coord, enum ccache_type lookup_what)
 284 {
 285     size_t i;
 286     coord_cache_t *cache;
 287     coord_cache_entry_t current, next, entry;
 288     enum ccache_type sorter;
 289     off_t limit;
 290     cmp_func_t cmp_func;
 291
 292     enum
 293     {
 294         NROFF_START,
 295         NROFF_BACKSPACE,
 296         NROFF_CONTINUATION
 297     } nroff_state;
 298
 299     if (view->coord_cache == NULL)
 300         view->coord_cache = coord_cache_new ();
 301
 302     cache = view->coord_cache;
 303
 304     if (cache->size == 0)
 305     {
 306         current.cc_offset = 0;
 307         current.cc_line = 0;
 308         current.cc_column = 0;
 309         current.cc_nroff_column = 0;
 310         mcview_ccache_add_entry (cache, 0, &current);
 311     }
 312
 313     sorter = (lookup_what == CCACHE_OFFSET) ? CCACHE_LINECOL : CCACHE_OFFSET;
 314
 315     if (sorter == CCACHE_OFFSET)
 316         cmp_func = mcview_coord_cache_entry_less_offset;
 317     else if (view->text_nroff_mode)
 318         cmp_func = mcview_coord_cache_entry_less_nroff;
 319     else
 320         cmp_func = mcview_coord_cache_entry_less_plain;
 321
 322
 323     tty_enable_interrupt_key ();
 324
 325   retry:
 326     /* find the two neighbor entries in the cache */
 327     i = mcview_ccache_find (view, coord, cmp_func);
 328     /* now i points to the lower neighbor in the cache */
 329
 330     current = *cache->cache[i];
 331     if (i + 1 < view->coord_cache->size)
 332         limit = cache->cache[i + 1]->cc_offset;
 333     else
 334         limit = current.cc_offset + VIEW_COORD_CACHE_GRANUL;
 335
 336     entry = current;
 337     nroff_state = NROFF_START;
 338     for (; current.cc_offset < limit; current = next)
 339     {
 340         int c, nextc;
 341
 342         if (!mcview_get_byte (view, current.cc_offset, &c))
 343             break;
 344
 345         if (!cmp_func (&current, coord))
 346         {
 347             if (lookup_what == CCACHE_OFFSET && view->text_nroff_mode && nroff_state != NROFF_START)
 348             {
 349                 /* don't break here */
 350             }
 351             else
 352             {
 353                 break;
 354             }
 355         }
 356
 357         /* Provide useful default values for ''next'' */
 358         next.cc_offset = current.cc_offset + 1;
 359         next.cc_line = current.cc_line;
 360         next.cc_column = current.cc_column + 1;
 361         next.cc_nroff_column = current.cc_nroff_column + 1;
 362
 363         /* and override some of them as necessary. */
 364         if (c == '\r')
 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         }
 419
 420         /* Cache entries must guarantee that for each i < j,
 421          * line[i] <= line[j] and column[i] < column[j]. In the case of
 422          * nroff sequences and '\r' characters, this is not guaranteed,
 423          * so we cannot save them. */
 424         if (nroff_state == NROFF_START && c != '\r')
 425             entry = next;
 426     }
 427
 428     if (i + 1 == cache->size && entry.cc_offset != cache->cache[i]->cc_offset)
 429     {
 430         mcview_ccache_add_entry (cache, cache->size, &entry);
 431
 432         if (!tty_got_interrupt ())
 433             goto retry;
 434     }
 435
 436     tty_disable_interrupt_key ();
 437
 438     if (lookup_what == CCACHE_OFFSET)
 439     {
 440         coord->cc_offset = current.cc_offset;
 441     }
 442     else
 443     {
 444         coord->cc_line = current.cc_line;
 445         coord->cc_column = current.cc_column;
 446         coord->cc_nroff_column = current.cc_nroff_column;
 447     }
 448 }
 449
 450 /* --------------------------------------------------------------------------------------------- */