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

DEFINITIONS
