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