src/viewer/coord

src/viewer/coord_cache.c
/* */
This source file includes following definitions.
mcview_ccache_add_entry
mcview_coord_cache_entry_less_offset
mcview_coord_cache_entry_less_plain
mcview_coord_cache_entry_less_nroff
mcview_ccache_find
coord_cache_new
coord_cache_free
mcview_ccache_dump
mcview_ccache_lookup
   1 /*
   2    Internal file viewer for the Midnight Commander
   3    Function for work with coordinate cache (ccache)
   4 
   5    Copyright (C) 1994-2019
   6    Free Software Foundation, Inc.
   7 
   8    Written by:
   9    Miguel de Icaza, 1994, 1995, 1998
  10    Janne Kukonlehto, 1994, 1995
  11    Jakub Jelinek, 1995
  12    Joseph M. Hinkle, 1996
  13    Norbert Warmuth, 1997
  14    Pavel Machek, 1998
  15    Roland Illig <roland.illig@gmx.de>, 2004, 2005
  16    Slava Zanko <slavazanko@google.com>, 2009
  17    Andrew Borodin <aborodin@vmail.ru>, 2009
  18    Ilia Maslakov <il.smind@gmail.com>, 2009
  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 3 of the License,
  25    or (at your option) any later version.
  26 
  27    The Midnight Commander is distributed in the hope that it will be useful,
  28    but WITHOUT ANY WARRANTY; without even the implied warranty of
  29    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  30    GNU 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, see <http://www.gnu.org/licenses/>.
  34  */
  35 
  36 /*
  37    This cache provides you with a fast lookup to map file offsets into
  38    line/column pairs and vice versa. The interface to the mapping is
  39    provided by the functions mcview_coord_to_offset() and
  40    mcview_offset_to_coord().
  41 
  42    The cache is implemented as a simple sorted array holding entries
  43    that map some of the offsets to their line/column pair. Entries that
  44    are not cached themselves are interpolated (exactly) from their
  45    neighbor entries. The algorithm used for determining the line/column
  46    for a specific offset needs to be kept synchronized with the one used
  47    in display().
  48  */
  49 
  50 #include <config.h>
  51 
  52 #include <string.h>             /* memmove() */
  53 #ifdef MC_ENABLE_DEBUGGING_CODE
  54 #include <inttypes.h>           /* uintmax_t */
  55 #endif
  56 
  57 #include "lib/global.h"
  58 #include "lib/tty/tty.h"
  59 #include "internal.h"
  60 
  61 /*** global variables ****************************************************************************/
  62 
  63 /*** file scope macro definitions ****************************************************************/
  64 
  65 #define VIEW_COORD_CACHE_GRANUL 1024
  66 #define CACHE_CAPACITY_DELTA 64
  67 
  68 /*** file scope type declarations ****************************************************************/
  69 
  70 typedef gboolean (*cmp_func_t) (const coord_cache_entry_t * a, const coord_cache_entry_t * b);
  71 
  72 /*** file scope variables ************************************************************************/
  73 
  74 /*** file scope functions ************************************************************************/
  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 (*cache->cache));
  91     }
  92 
  93     /* insert new entry */
  94     if (pos != cache->size)
  95         memmove (cache->cache[pos + 1], cache->cache[pos],
  96                  (cache->size - pos) * sizeof (*cache->cache));
  97     cache->cache[pos] = g_memdup (entry, sizeof (*entry));
  98     cache->size++;
  99 }
 100 
 101 /* --------------------------------------------------------------------------------------------- */
 102 
 103 static gboolean
 104 mcview_coord_cache_entry_less_offset (const coord_cache_entry_t * a, const coord_cache_entry_t * b)
     /*   */
 105 {
 106     return (a->cc_offset < b->cc_offset);
 107 }
 108 
 109 /* --------------------------------------------------------------------------------------------- */
 110 
 111 static gboolean
 112 mcview_coord_cache_entry_less_plain (const coord_cache_entry_t * a, 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 /* --------------------------------------------------------------------------------------------- */
 125 
 126 static gboolean
 127 mcview_coord_cache_entry_less_nroff (const coord_cache_entry_t * a, const coord_cache_entry_t * b)
     /*   */
 128 {
 129     if (a->cc_line < b->cc_line)
 130         return TRUE;
 131 
 132     if (a->cc_line == b->cc_line)
 133         return (a->cc_nroff_column < b->cc_nroff_column);
 134 
 135     return FALSE;
 136 }
 137 
 138 
 139 /* --------------------------------------------------------------------------------------------- */
 140 /** Find and return the index of the last cache entry that is
 141  * smaller than ''coord'', according to the criterion ''sort_by''. */
 142 
 143 static inline size_t
 144 mcview_ccache_find (WView * view, const coord_cache_entry_t * coord, cmp_func_t cmp_func)
     /*   */
 145 {
 146     size_t base = 0;
 147     size_t limit = view->coord_cache->size;
 148 
 149     g_assert (limit != 0);
 150 
 151     while (limit > 1)
 152     {
 153         size_t i;
 154 
 155         i = base + limit / 2;
 156         if (cmp_func (coord, view->coord_cache->cache[i]))
 157         {
 158             /* continue the search in the lower half of the cache */
 159         }
 160         else
 161         {
 162             /* continue the search in the upper half of the cache */
 163             base = i;
 164         }
 165         limit = (limit + 1) / 2;
 166     }
 167     return base;
 168 }
 169 
 170 /* --------------------------------------------------------------------------------------------- */
 171 /*** public functions ****************************************************************************/
 172 /* --------------------------------------------------------------------------------------------- */
 173 
 174 coord_cache_t *
 175 coord_cache_new (void)
     /*   */
 176 {
 177     coord_cache_t *cache;
 178 
 179     cache = g_new (coord_cache_t, 1);
 180     cache->size = 0;
 181     cache->capacity = CACHE_CAPACITY_DELTA;
 182     cache->cache = g_malloc0 (cache->capacity * sizeof (*cache->cache));
 183 
 184     return cache;
 185 }
 186 
 187 /* --------------------------------------------------------------------------------------------- */
 188 
 189 void
 190 coord_cache_free (coord_cache_t * cache)
     /*   */
 191 {
 192     if (cache != NULL)
 193     {
 194         size_t i;
 195 
 196         for (i = 0; i < cache->size; i++)
 197             g_free (cache->cache[i]);
 198 
 199         g_free (cache->cache);
 200         g_free (cache);
 201     }
 202 }
 203 
 204 /* --------------------------------------------------------------------------------------------- */
 205 
 206 #ifdef MC_ENABLE_DEBUGGING_CODE
 207 
 208 void
 209 mcview_ccache_dump (WView * view)
     /*   */
 210 {
 211     FILE *f;
 212     off_t offset, line, column, nextline_offset, filesize;
 213     guint i;
 214     const coord_cache_t *cache = view->coord_cache;
 215 
 216     g_assert (cache != NULL);
 217 
 218     filesize = mcview_get_filesize (view);
 219 
 220     f = fopen ("mcview-ccache.out", "w");
 221     if (f == NULL)
 222         return;
 223     (void) setvbuf (f, NULL, _IONBF, 0);
 224 
 225     /* cache entries */
 226     for (i = 0; i < cache->size; i++)
 227     {
 228         (void) fprintf (f,
 229                         "entry %8u  offset %8" PRIuMAX
 230                         "  line %8" PRIuMAX "  column %8" PRIuMAX
 231                         "  nroff_column %8" PRIuMAX "\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 %8" PRIuMAX "  line %8" PRIuMAX "  column %8" PRIuMAX "\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 %8" PRIuMAX "\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 %8" PRIuMAX "  column %8" PRIuMAX "  offset %8" PRIuMAX "\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 (WView * 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->mode_flags.nroff)
 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;
 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->mode_flags.nroff
 346                 && 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             int nextc = -1;
 366 
 367             mcview_get_byte_indexed (view, current.cc_offset, 1, &nextc);
 368 
 369             /* Ignore '\r' if it is followed by '\r' or '\n'. If it is
 370              * followed by anything else, it is a Mac line ending and
 371              * produces a line break.
 372              */
 373             if (nextc == '\r' || nextc == '\n')
 374             {
 375                 next.cc_column = current.cc_column;
 376                 next.cc_nroff_column = current.cc_nroff_column;
 377             }
 378             else
 379             {
 380                 next.cc_line = current.cc_line + 1;
 381                 next.cc_column = 0;
 382                 next.cc_nroff_column = 0;
 383             }
 384 
 385         }
 386         else if (nroff_state == NROFF_BACKSPACE)
 387         {
 388             next.cc_nroff_column = current.cc_nroff_column - 1;
 389 
 390         }
 391         else if (c == '\t')
 392         {
 393             next.cc_column = mcview_offset_rounddown (current.cc_column, 8) + 8;
 394             next.cc_nroff_column = mcview_offset_rounddown (current.cc_nroff_column, 8) + 8;
 395 
 396         }
 397         else if (c == '\n')
 398         {
 399             next.cc_line = current.cc_line + 1;
 400             next.cc_column = 0;
 401             next.cc_nroff_column = 0;
 402 
 403         }
 404         else
 405         {
 406             /* Use all default values from above */
 407         }
 408 
 409         switch (nroff_state)
 410         {
 411         case NROFF_START:
 412         case NROFF_CONTINUATION:
 413             nroff_state = mcview_is_nroff_sequence (view, current.cc_offset)
 414                 ? NROFF_BACKSPACE : NROFF_START;
 415             break;
 416         case NROFF_BACKSPACE:
 417             nroff_state = NROFF_CONTINUATION;
 418             break;
 419         default:
 420             break;
 421         }
 422 
 423         /* Cache entries must guarantee that for each i < j,
 424          * line[i] <= line[j] and column[i] < column[j]. In the case of
 425          * nroff sequences and '\r' characters, this is not guaranteed,
 426          * so we cannot save them. */
 427         if (nroff_state == NROFF_START && c != '\r')
 428             entry = next;
 429     }
 430 
 431     if (i + 1 == cache->size && entry.cc_offset != cache->cache[i]->cc_offset)
 432     {
 433         mcview_ccache_add_entry (cache, cache->size, &entry);
 434 
 435         if (!tty_got_interrupt ())
 436             goto retry;
 437     }
 438 
 439     tty_disable_interrupt_key ();
 440 
 441     if (lookup_what == CCACHE_OFFSET)
 442     {
 443         coord->cc_offset = current.cc_offset;
 444     }
 445     else
 446     {
 447         coord->cc_line = current.cc_line;
 448         coord->cc_column = current.cc_column;
 449         coord->cc_nroff_column = current.cc_nroff_column;
 450     }
 451 }
 452 
 453 /* --------------------------------------------------------------------------------------------- */
/* */
root/src/viewer/coord_cache.c

DEFINITIONS
