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-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 /* --------------------------------------------------------------------------------------------- */
/* */
root/src/viewer/coord_cache.c

DEFINITIONS
