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
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-2025
   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 <https://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 "  line %8" PRIuMAX "  column %8" PRIuMAX
 195                         "  nroff_column %8" PRIuMAX "\n",
 196                         (unsigned int) i, (uintmax_t) e->cc_offset, (uintmax_t) e->cc_line,
 197                         (uintmax_t) e->cc_column, (uintmax_t) e->cc_nroff_column);
 198     }
 199     (void) fprintf (f, "\n");
 200 
 201     // offset -> line/column translation
 202     for (offset = 0; offset < filesize; offset++)
 203     {
 204         mcview_offset_to_coord (view, &line, &column, offset);
 205         (void) fprintf (f, "offset %8" PRIuMAX "  line %8" PRIuMAX "  column %8" PRIuMAX "\n",
 206                         (uintmax_t) offset, (uintmax_t) line, (uintmax_t) column);
 207     }
 208 
 209     // line/column -> offset translation
 210     for (line = 0; TRUE; line++)
 211     {
 212         mcview_coord_to_offset (view, &nextline_offset, line + 1, 0);
 213         (void) fprintf (f, "nextline_offset %8" PRIuMAX "\n", (uintmax_t) nextline_offset);
 214 
 215         for (column = 0; TRUE; column++)
 216         {
 217             mcview_coord_to_offset (view, &offset, line, column);
 218             if (offset >= nextline_offset)
 219                 break;
 220 
 221             (void) fprintf (f, "line %8" PRIuMAX "  column %8" PRIuMAX "  offset %8" PRIuMAX "\n",
 222                             (uintmax_t) line, (uintmax_t) column, (uintmax_t) offset);
 223         }
 224 
 225         if (nextline_offset >= filesize - 1)
 226             break;
 227     }
 228 
 229     (void) fclose (f);
 230 }
 231 #endif
 232 
 233 /* --------------------------------------------------------------------------------------------- */
 234 /** Look up the missing components of ''coord'', which are given by
 235  * ''lookup_what''. The function returns the smallest value that
 236  * matches the existing components of ''coord''.
 237  */
 238 
 239 void
 240 mcview_ccache_lookup (WView *view, coord_cache_entry_t *coord, enum ccache_type lookup_what)
     /*   */
 241 {
 242     size_t i;
 243     GPtrArray *cache;
 244     coord_cache_entry_t current, next, entry;
 245     enum ccache_type sorter;
 246     off_t limit;
 247     cmp_func_t cmp_func;
 248 
 249     enum
 250     {
 251         NROFF_START,
 252         NROFF_BACKSPACE,
 253         NROFF_CONTINUATION
 254     } nroff_state;
 255 
 256     if (view->coord_cache == NULL)
 257         view->coord_cache = g_ptr_array_new_full (CACHE_CAPACITY_DELTA, g_free);
 258 
 259     cache = view->coord_cache;
 260 
 261     if (cache->len == 0)
 262     {
 263         memset (&current, 0, sizeof (current));
 264         mcview_ccache_add_entry (cache, &current);
 265     }
 266 
 267     sorter = (lookup_what == CCACHE_OFFSET) ? CCACHE_LINECOL : CCACHE_OFFSET;
 268 
 269     if (sorter == CCACHE_OFFSET)
 270         cmp_func = mcview_coord_cache_entry_less_offset;
 271     else if (view->mode_flags.nroff)
 272         cmp_func = mcview_coord_cache_entry_less_nroff;
 273     else
 274         cmp_func = mcview_coord_cache_entry_less_plain;
 275 
 276     tty_enable_interrupt_key ();
 277 
 278 retry:
 279     // find the two neighbor entries in the cache
 280     i = mcview_ccache_find (view, coord, cmp_func);
 281     // now i points to the lower neighbor in the cache
 282 
 283     current = *coord_cache_index (cache, i);
 284     if (i + 1 < view->coord_cache->len)
 285         limit = coord_cache_index (cache, i + 1)->cc_offset;
 286     else
 287         limit = current.cc_offset + VIEW_COORD_CACHE_GRANUL;
 288 
 289     entry = current;
 290     nroff_state = NROFF_START;
 291     for (; current.cc_offset < limit; current = next)
 292     {
 293         int c;
 294 
 295         if (!mcview_get_byte (view, current.cc_offset, &c))
 296             break;
 297 
 298         if (!cmp_func (&current, coord)
 299             && (lookup_what != CCACHE_OFFSET || !view->mode_flags.nroff
 300                 || nroff_state == NROFF_START))
 301             break;
 302 
 303         // Provide useful default values for 'next'
 304         next.cc_offset = current.cc_offset + 1;
 305         next.cc_line = current.cc_line;
 306         next.cc_column = current.cc_column + 1;
 307         next.cc_nroff_column = current.cc_nroff_column + 1;
 308 
 309         // and override some of them as necessary.
 310         if (c == '\r')
 311         {
 312             int nextc = -1;
 313 
 314             mcview_get_byte_indexed (view, current.cc_offset, 1, &nextc);
 315 
 316             /* Ignore '\r' if it is followed by '\r' or '\n'. If it is
 317              * followed by anything else, it is a Mac line ending and
 318              * produces a line break.
 319              */
 320             if (nextc == '\r' || nextc == '\n')
 321             {
 322                 next.cc_column = current.cc_column;
 323                 next.cc_nroff_column = current.cc_nroff_column;
 324             }
 325             else
 326             {
 327                 next.cc_line = current.cc_line + 1;
 328                 next.cc_column = 0;
 329                 next.cc_nroff_column = 0;
 330             }
 331         }
 332         else if (nroff_state == NROFF_BACKSPACE)
 333             next.cc_nroff_column = current.cc_nroff_column - 1;
 334         else if (c == '\t')
 335         {
 336             next.cc_column = mcview_offset_rounddown (current.cc_column, 8) + 8;
 337             next.cc_nroff_column = mcview_offset_rounddown (current.cc_nroff_column, 8) + 8;
 338         }
 339         else if (c == '\n')
 340         {
 341             next.cc_line = current.cc_line + 1;
 342             next.cc_column = 0;
 343             next.cc_nroff_column = 0;
 344         }
 345         else
 346         {
 347             ;  // Use all default values from above
 348         }
 349 
 350         switch (nroff_state)
 351         {
 352         case NROFF_START:
 353         case NROFF_CONTINUATION:
 354             nroff_state =
 355                 mcview_is_nroff_sequence (view, current.cc_offset) ? NROFF_BACKSPACE : NROFF_START;
 356             break;
 357         case NROFF_BACKSPACE:
 358             nroff_state = NROFF_CONTINUATION;
 359             break;
 360         default:
 361             break;
 362         }
 363 
 364         /* Cache entries must guarantee that for each i < j,
 365          * line[i] <= line[j] and column[i] < column[j]. In the case of
 366          * nroff sequences and '\r' characters, this is not guaranteed,
 367          * so we cannot save them. */
 368         if (nroff_state == NROFF_START && c != '\r')
 369             entry = next;
 370     }
 371 
 372     if (i + 1 == cache->len && entry.cc_offset != coord_cache_index (cache, i)->cc_offset)
 373     {
 374         mcview_ccache_add_entry (cache, &entry);
 375 
 376         if (!tty_got_interrupt ())
 377             goto retry;
 378     }
 379 
 380     tty_disable_interrupt_key ();
 381 
 382     if (lookup_what == CCACHE_OFFSET)
 383         coord->cc_offset = current.cc_offset;
 384     else
 385     {
 386         coord->cc_line = current.cc_line;
 387         coord->cc_column = current.cc_column;
 388         coord->cc_nroff_column = current.cc_nroff_column;
 389     }
 390 }
 391 
 392 /* --------------------------------------------------------------------------------------------- */
/* */
root/src/viewer/coord_cache.c

DEFINITIONS
