From 335c1779eb3da810bef6caac65c1902f5d5a4c74 Mon Sep 17 00:00:00 2001 From: Andrew Borodin Date: Fri, 27 Nov 2009 22:10:49 +0300 Subject: [PATCH] First step of viewer coordinates cache reimplementation. Reimplemented some of coordinates cache internals. Array is used instead of GList. If needed, array is reallocated. Signed-off-by: Andrew Borodin --- src/viewer/coord_cache.c | 184 ++++++++++++++++++++++++++++++++++------------- src/viewer/internal.h | 14 ++-- src/viewer/lib.c | 4 +- src/viewer/move.c | 13 ++-- 4 files changed, 150 insertions(+), 65 deletions(-) diff --git a/src/viewer/coord_cache.c b/src/viewer/coord_cache.c index 95dd2937b..35acef38d 100644 --- a/src/viewer/coord_cache.c +++ b/src/viewer/coord_cache.c @@ -51,39 +51,106 @@ #include +#include /* for g_memmove() */ + #include "../src/global.h" #include "../src/tty/tty.h" #include "internal.h" -#define VIEW_COORD_CACHE_GRANUL 1024 - /*** global variables ****************************************************************************/ /*** file scope macro definitions ****************************************************************/ +#define VIEW_COORD_CACHE_GRANUL 1024 +#define CACHE_CAPACITY_DELTA 64 + /*** file scope type declarations ****************************************************************/ +typedef gboolean (*cmp_func_t) (const coord_cache_entry_t *a, + const coord_cache_entry_t *b); + /*** file scope variables ************************************************************************/ /*** file scope functions ************************************************************************/ /* --------------------------------------------------------------------------------------------- */ +/* insert new cache entry into the cache */ +static void +mcview_ccache_add_entry (coord_cache_t *cache, + size_t pos, const coord_cache_entry_t *entry) +{ + if ((cache == NULL) || (entry == NULL)) + return; + + pos = min (pos, cache->size); + + /* increase cache capacity if needed */ + if (cache->size == cache->capacity) { + cache->capacity += CACHE_CAPACITY_DELTA; + cache->cache = g_realloc (cache->cache, + cache->capacity * sizeof (coord_cache_entry_t *)); + } + + /* insert new entry */ + if (pos != cache->size) + g_memmove (cache->cache[pos + 1], cache->cache[pos], + (cache->size - pos) * sizeof (coord_cache_entry_t *)); + cache->cache[pos] = g_memdup (entry, sizeof (coord_cache_entry_t)); + cache->size++; +} + +static gboolean +mcview_coord_cache_entry_less_offset (const coord_cache_entry_t *a, + const coord_cache_entry_t *b) +{ + return (a->cc_offset < b->cc_offset); +} + +static gboolean +mcview_coord_cache_entry_less_plain (const coord_cache_entry_t *a, + const coord_cache_entry_t *b) +{ + if (a->cc_line < b->cc_line) + return TRUE; + + if (a->cc_line == b->cc_line) + return (a->cc_column < b->cc_column); + + return FALSE; +} + + +static gboolean +mcview_coord_cache_entry_less_nroff (const coord_cache_entry_t *a, + const coord_cache_entry_t *b) +{ + if (a->cc_line < b->cc_line) + return TRUE; + + if (a->cc_line == b->cc_line) + return (a->cc_nroff_column < b->cc_nroff_column); + + return FALSE; +} + + /* Find and return the index of the last cache entry that is * smaller than ''coord'', according to the criterion ''sort_by''. */ -static guint -mcview_ccache_find (mcview_t * view, const coord_cache_entry_t *cache, - const coord_cache_entry_t *coord, enum ccache_type sort_by) +static inline size_t +mcview_ccache_find (mcview_t *view, const coord_cache_entry_t *coord, + cmp_func_t cmp_func) { - guint base, i, limit; + size_t base = 0; + size_t limit = view->coord_cache->size; - limit = view->coord_cache->len; assert (limit != 0); - base = 0; while (limit > 1) { + size_t i; + i = base + limit / 2; - if (mcview_coord_cache_entry_less (coord, &cache[i], sort_by, view->text_nroff_mode)) { + if (cmp_func (coord, view->coord_cache->cache[i])) { /* continue the search in the lower half of the cache */ } else { /* continue the search in the upper half of the cache */ @@ -94,32 +161,39 @@ mcview_ccache_find (mcview_t * view, const coord_cache_entry_t *cache, return base; } - /* --------------------------------------------------------------------------------------------- */ /*** public functions ****************************************************************************/ /* --------------------------------------------------------------------------------------------- */ -gboolean -mcview_coord_cache_entry_less (const coord_cache_entry_t *a, - const coord_cache_entry_t *b, enum ccache_type crit, - gboolean nroff_mode) +coord_cache_t * +coord_cache_new (void) { - if (crit == CCACHE_OFFSET) - return (a->cc_offset < b->cc_offset); + coord_cache_t *cache; - if (a->cc_line < b->cc_line) - return TRUE; + cache = g_new (coord_cache_t, 1); + cache->size = 0; + cache->capacity = CACHE_CAPACITY_DELTA; + cache->cache = g_malloc0 (cache->capacity * sizeof (coord_cache_entry_t *)); - if (a->cc_line == b->cc_line) { - if (nroff_mode) { - return (a->cc_nroff_column < b->cc_nroff_column); - } else { - return (a->cc_column < b->cc_column); - } + return cache; +} + +/* --------------------------------------------------------------------------------------------- */ + +void +coord_cache_free (coord_cache_t *cache) +{ + if (cache != NULL) { + size_t i; + + for (i = 0; i < cache->size; i++) + g_free (cache->cache[i]); + + g_free (cache->cache); + g_free (cache); } - return FALSE; } /* --------------------------------------------------------------------------------------------- */ @@ -132,12 +206,11 @@ mcview_ccache_dump (mcview_t * view) FILE *f; off_t offset, line, column, nextline_offset, filesize; guint i; - const coord_cache_entry_t *cache; + const coord_cache_t *cache = view->coord_cache; - assert (view->coord_cache != NULL); + assert (cache != NULL); filesize = mcview_get_filesize (view); - cache = &(g_array_index (view->coord_cache, coord_cache_entry, 0)); f = fopen ("mcview-ccache.out", "w"); if (f == NULL) @@ -145,15 +218,15 @@ mcview_ccache_dump (mcview_t * view) (void) setvbuf (f, NULL, _IONBF, 0); /* cache entries */ - for (i = 0; i < view->coord_cache->len; i++) { + for (i = 0; i < view->coord_cache->size; i++) { (void) fprintf (f, "entry %8u " "offset %8" OFFSETTYPE_PRId " " "line %8" OFFSETTYPE_PRId " " "column %8" OFFSETTYPE_PRId " " "nroff_column %8" OFFSETTYPE_PRId "\n", - (unsigned int) i, cache[i].cc_offset, cache[i].cc_line, - cache[i].cc_column, cache[i].cc_nroff_column); + (unsigned int) i, cache->cache[i].cc_offset, cache[i]->cache.cc_line, + cache->cache[i].cc_column, cache->cache[i].cc_nroff_column); } (void) fprintf (f, "\n"); @@ -200,38 +273,52 @@ void mcview_ccache_lookup (mcview_t * view, coord_cache_entry_t *coord, enum ccache_type lookup_what) { - guint i; - coord_cache_entry_t *cache, current, next, entry; + size_t i; + coord_cache_t *cache; + coord_cache_entry_t current, next, entry; enum ccache_type sorter; off_t limit; + cmp_func_t cmp_func; + enum { NROFF_START, NROFF_BACKSPACE, NROFF_CONTINUATION } nroff_state; - if (!view->coord_cache) { - view->coord_cache = g_array_new (FALSE, FALSE, sizeof (coord_cache_entry_t)); + if (view->coord_cache == NULL) + view->coord_cache = coord_cache_new (); + + cache = view->coord_cache; + + if (cache->size == 0) { current.cc_offset = 0; current.cc_line = 0; current.cc_column = 0; current.cc_nroff_column = 0; - g_array_append_val (view->coord_cache, current); + mcview_ccache_add_entry (cache, 0, ¤t); } sorter = (lookup_what == CCACHE_OFFSET) ? CCACHE_LINECOL : CCACHE_OFFSET; + if (sorter == CCACHE_OFFSET) + cmp_func = mcview_coord_cache_entry_less_offset; + else if (view->text_nroff_mode) + cmp_func = mcview_coord_cache_entry_less_nroff; + else + cmp_func = mcview_coord_cache_entry_less_plain; + + tty_enable_interrupt_key (); retry: /* find the two neighbor entries in the cache */ - cache = &(g_array_index (view->coord_cache, coord_cache_entry_t, 0)); - i = mcview_ccache_find (view, cache, coord, sorter); + i = mcview_ccache_find (view, coord, cmp_func); /* now i points to the lower neighbor in the cache */ - current = cache[i]; - if (i + 1 < view->coord_cache->len) - limit = cache[i + 1].cc_offset; + current = *cache->cache[i]; + if (i + 1 < view->coord_cache->size) + limit = cache->cache[i + 1]->cc_offset; else limit = current.cc_offset + VIEW_COORD_CACHE_GRANUL; @@ -243,8 +330,9 @@ mcview_ccache_lookup (mcview_t * view, coord_cache_entry_t *coord, if (! mcview_get_byte (view, current.cc_offset, &c)) break; - if (!mcview_coord_cache_entry_less (¤t, coord, sorter, view->text_nroff_mode)) { - if (lookup_what == CCACHE_OFFSET && view->text_nroff_mode && nroff_state != NROFF_START) { + if (!cmp_func (¤t, coord)) { + if (lookup_what == CCACHE_OFFSET + && view->text_nroff_mode && nroff_state != NROFF_START) { /* don't break here */ } else { break; @@ -293,10 +381,8 @@ mcview_ccache_lookup (mcview_t * view, coord_cache_entry_t *coord, switch (nroff_state) { case NROFF_START: case NROFF_CONTINUATION: - if (mcview_is_nroff_sequence (view, current.cc_offset)) - nroff_state = NROFF_BACKSPACE; - else - nroff_state = NROFF_START; + nroff_state = mcview_is_nroff_sequence (view, current.cc_offset) + ? NROFF_BACKSPACE : NROFF_START; break; case NROFF_BACKSPACE: nroff_state = NROFF_CONTINUATION; @@ -311,8 +397,8 @@ mcview_ccache_lookup (mcview_t * view, coord_cache_entry_t *coord, entry = next; } - if (i + 1 == view->coord_cache->len && entry.cc_offset != cache[i].cc_offset) { - g_array_append_val (view->coord_cache, entry); + if (i + 1 == cache->size && entry.cc_offset != cache->cache[i]->cc_offset) { + mcview_ccache_add_entry (cache, cache->size, &entry); if (!tty_got_interrupt ()) goto retry; diff --git a/src/viewer/internal.h b/src/viewer/internal.h index 107af1423..26512908a 100644 --- a/src/viewer/internal.h +++ b/src/viewer/internal.h @@ -77,6 +77,12 @@ typedef struct { off_t cc_nroff_column; } coord_cache_entry_t; +typedef struct { + size_t size; + size_t capacity; + coord_cache_entry_t **cache; +} coord_cache_t; + struct mcview_nroff_struct; typedef struct mcview_struct { @@ -123,7 +129,7 @@ typedef struct mcview_struct { /* Additional editor state */ gboolean hexedit_lownibble; /* Are we editing the last significant nibble? */ - GArray *coord_cache; /* Cache for mapping offsets to cursor positions */ + coord_cache_t *coord_cache; /* Cache for mapping offsets to cursor positions */ /* Display information */ screen_dimen dpy_frame_size; /* Size of the frame surrounding the real viewer */ @@ -205,9 +211,9 @@ cb_ret_t mcview_dialog_callback (Dlg_head *h, Widget *sender, dlg_msg_t msg, int parm, void *data); /* coord_cache.c: */ -gboolean mcview_coord_cache_entry_less (const coord_cache_entry_t *, - const coord_cache_entry_t *, enum ccache_type, - gboolean); +coord_cache_t *coord_cache_new (void); +void coord_cache_free (coord_cache_t *cache); + #ifdef MC_ENABLE_DEBUGGING_CODE void mcview_ccache_dump (mcview_t *view); #endif diff --git a/src/viewer/lib.c b/src/viewer/lib.c index 4d0914001..0006f4f3a 100644 --- a/src/viewer/lib.c +++ b/src/viewer/lib.c @@ -193,9 +193,7 @@ mcview_done (mcview_t * view) mcview_close_datasource (view); /* the growing buffer is freed with the datasource */ - if (view->coord_cache) { - g_array_free (view->coord_cache, TRUE), view->coord_cache = NULL; - } + coord_cache_free (view->coord_cache), view->coord_cache = NULL; if (!(view->converter == INVALID_CONV || view->converter != str_cnv_from_term)) { str_close_conv (view->converter); diff --git a/src/viewer/move.c b/src/viewer/move.c index 5c782e6e2..1d52bb12b 100644 --- a/src/viewer/move.c +++ b/src/viewer/move.c @@ -389,12 +389,9 @@ mcview_offset_to_coord (mcview_t * view, off_t * ret_line, off_t * ret_column, o coord.cc_offset = offset; mcview_ccache_lookup (view, &coord, CCACHE_LINECOL); - if (ret_line) - *ret_line = coord.cc_line; - - if (ret_column) - *ret_column = (view->text_nroff_mode) - ? coord.cc_nroff_column : coord.cc_column; + *ret_line = coord.cc_line; + *ret_column = (view->text_nroff_mode) + ? coord.cc_nroff_column : coord.cc_column; } /* --------------------------------------------------------------------------------------------- */ @@ -404,9 +401,7 @@ mcview_place_cursor (mcview_t * view) { const screen_dimen top = view->data_area.top; const screen_dimen left = view->data_area.left; - screen_dimen col; - - col = view->cursor_col; + screen_dimen col = view->cursor_col; if (!view->hexview_in_text && view->hexedit_lownibble) col++; widget_move (&view->widget, top + view->cursor_row, left + col); -- 2.11.4.GIT