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