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