Hi Marwan,
I wrote the first crappy jumplist, and the bisection code. I agree that loosing
jump history is not good for the jumplist, and I am happy with your changes.
Here is a second attempt at fixing bisect.
But first some clarifications:
> Bisection and the jumplist are just entirely unrelated
No they are not. The state during bisection (lower and upper bound) are stored
as the last two jumps before current in the jumplist.
> I don't think that it's a good idea to change the jumplist internal data
> structure as a side effect of bisection, it just doesn't make sense.
In yesterday's patch I did not touch your improved jumplist. I just change two
lines in the bisection code (sc_bisect) and exposed zathura_jumplist_save (to
rewrite jumps in sc_bisect). I'm going an other route with the attached patches,
though.
> AFAICS, nothing is broken as far as bisection itself is concerned
Your jumplist code is fine (I did not touch it beside from exposing
zathura_jumplist_save). What was broken was the middle case in the bisection
code (lines 859 and 886 in shortcuts.c). The problem is related to this bisect
step:
-1 ......... 0 .........-2 .....................
Here pages increase from left to right and the numbers represent jumps (0 is
current jump).
Bisecting to the right with the broken bisect (the one after your jumplist code)
would lead to
-2 ........ -1 .........-3 .....0.................
This case (and its mirror, jumping left) are the only troublesome cases.
The thing is that the bisection code uses the jumplist to keep the lower and
upper bounds of the current bisect step as the last two jumps in the jumplist. I
didn't want to add a new "bisect mode" with more state...
Also I like the idea that bisect always uses the last two jumps as there is no
need for a "bisect initialization" telling zathura the initial bounds.
There are two ways to make sure the two jumps before current are always the
current bisect bounds:
1. Slightly rewrite history as done in the first patch I sent yesterday.
2. Insert new jumps when needed, as done in the attached patches.
I agree that loosing history is bad. The attached patches do not loose jump
history, but they mess a little with jump order (inserts a jump before last from
time to time).
In the case above
-1 ......... 0 .........-2 .....................
Bisecting to the right from 0 will now lead to
-2
-3 ......... -1 ....0....-4 .......................
It just inserts the upper bound before the current jump in the jump history and
then bisects. This way, the -1 and -2 jumps after a bisect step are still the
bounds for the bisection algorithm.
About the attached patches:
girara-list-insert.patch adds insert functionality to girara lists
zathura-fix-bisect-v2.patch adds zathura_jumplist_insert + fixes bisect
Abdó Roig-Maranges.
>From 74c5c4f11f07059d5fb1f79332ae7a7da31bd45b Mon Sep 17 00:00:00 2001
From: Abdo Roig-Maranges <abdo.r...@gmail.com>
Date: Tue, 2 Jul 2013 11:28:22 +0200
Subject: [PATCH] Add insert functionality to girara_list data structure
Add function girara_list_insert to insert an element to a list before a
given position.
---
datastructures.c | 9 +++++++++
datastructures.h | 10 ++++++++++
2 files changed, 19 insertions(+)
diff --git a/datastructures.c b/datastructures.c
index 795b696..0ccd7d1 100644
--- a/datastructures.c
+++ b/datastructures.c
@@ -126,6 +126,15 @@ girara_list_append(girara_list_t* list, void* data)
}
void
+girara_list_insert(girara_list_t* list, girara_list_iterator_t* pos, void* data)
+{
+ g_return_if_fail(list);
+ g_return_if_fail(pos);
+ g_return_if_fail(!list->cmp); /* can't insert at pos and keep sorted */
+ list->start = g_list_insert_before(list->start, pos->element, data);
+}
+
+void
girara_list_prepend(girara_list_t* list, void* data)
{
g_return_if_fail(list);
diff --git a/datastructures.h b/datastructures.h
index 3ee6cae..431f962 100644
--- a/datastructures.h
+++ b/datastructures.h
@@ -74,6 +74,16 @@ void girara_list_free(girara_list_t* list);
void girara_list_append(girara_list_t* list, void* data);
/**
+ * Insert an element to the list before a given position.
+ *
+ * @param list The girara list object
+ * @param pos Insert before this element
+ * @param data The element
+ */
+void
+girara_list_insert(girara_list_t* list, girara_list_iterator_t* pos, void* data);
+
+/**
* Prepend an element to the list.
*
* @param list The girara list object
--
1.8.3.2
>From 7a5b84c137ed227ec6d7bb58cf65712d07cc4ff5 Mon Sep 17 00:00:00 2001
From: Abdo Roig-Maranges <abdo.r...@gmail.com>
Date: Tue, 2 Jul 2013 11:47:50 +0200
Subject: [PATCH 1/2] Adds a function to insert jump before current jump
Adds zathura_jumplist_insert, that inserts current page in a new jump
before current jump in the jumplist.
Also merges zathura_jumplist_append and zathura_jumplist_add. The only
call to the first was at the end of the second.
---
zathura.c | 71 +++++++++++++++++++++++++++++++++++++++++++--------------------
zathura.h | 9 +++++++-
2 files changed, 57 insertions(+), 23 deletions(-)
diff --git a/zathura.c b/zathura.c
index 0165e40..3f09bb3 100644
--- a/zathura.c
+++ b/zathura.c
@@ -59,9 +59,9 @@ static ssize_t zathura_page_cache_lru_invalidate(zathura_t* zathura);
static void zathura_page_cache_invalidate_all(zathura_t* zathura);
static bool zathura_page_cache_is_full(zathura_t* zathura, bool* result);
static void zathura_jumplist_reset_current(zathura_t* zathura);
-static void zathura_jumplist_append_jump(zathura_t* zathura);
static void zathura_jumplist_save(zathura_t* zathura);
+
/* function implementation */
zathura_t*
zathura_create(void)
@@ -1231,25 +1231,6 @@ zathura_jumplist_reset_current(zathura_t* zathura)
}
}
-static void
-zathura_jumplist_append_jump(zathura_t* zathura)
-{
- g_return_if_fail(zathura != NULL && zathura->jumplist.list != NULL);
-
- zathura_jump_t *jump = g_malloc(sizeof(zathura_jump_t));
- jump->page = 0;
- jump->x = 0.0;
- jump->y = 0.0;
- girara_list_append(zathura->jumplist.list, jump);
-
- if (zathura->jumplist.size == 0) {
- zathura->jumplist.cur = girara_list_iterator(zathura->jumplist.list);
- }
-
- ++zathura->jumplist.size;
- zathura_jumplist_trim(zathura);
-}
-
void
zathura_jumplist_trim(zathura_t* zathura)
{
@@ -1296,9 +1277,55 @@ zathura_jumplist_add(zathura_t* zathura)
}
}
- zathura_jumplist_append_jump(zathura);
+ zathura_jump_t *jump = g_malloc(sizeof(zathura_jump_t));
+ jump->page = pagenum;
+ jump->x = x;
+ jump->y = y;
+ girara_list_append(zathura->jumplist.list, jump);
+
+ if (zathura->jumplist.size == 0) {
+ zathura->jumplist.cur = girara_list_iterator(zathura->jumplist.list);
+ }
+
+ ++zathura->jumplist.size;
+ zathura_jumplist_trim(zathura);
zathura_jumplist_reset_current(zathura);
- zathura_jumplist_save(zathura);
+}
+
+void
+zathura_jumplist_insert(zathura_t* zathura)
+{
+ g_return_if_fail(zathura != NULL && zathura->jumplist.list != NULL);
+ zathura_jumplist_hide_inputbar(zathura);
+
+ unsigned int pagenum = zathura_document_get_current_page_number(zathura->document);
+ double x = zathura_adjustment_get_ratio(gtk_scrolled_window_get_hadjustment(GTK_SCROLLED_WINDOW(zathura->ui.session->gtk.view)));
+ double y = zathura_adjustment_get_ratio(gtk_scrolled_window_get_vadjustment(GTK_SCROLLED_WINDOW(zathura->ui.session->gtk.view)));
+
+ if (zathura->jumplist.size != 0) {
+ zathura_jumplist_reset_current(zathura);
+
+ zathura_jump_t* cur = zathura_jumplist_current(zathura);
+
+ if (cur != NULL) {
+ if (cur->page == pagenum && cur->x == x && cur->y == y) {
+ return;
+ }
+ }
+ }
+
+ zathura_jump_t *jump = g_malloc(sizeof(zathura_jump_t));
+ jump->page = pagenum;
+ jump->x = x;
+ jump->y = y;
+ girara_list_insert(zathura->jumplist.list, zathura->jumplist.cur, jump);
+
+ if (zathura->jumplist.size == 0) {
+ zathura->jumplist.cur = girara_list_iterator(zathura->jumplist.list);
+ }
+
+ ++zathura->jumplist.size;
+ zathura_jumplist_trim(zathura);
}
bool
diff --git a/zathura.h b/zathura.h
index ac22636..cc29954 100644
--- a/zathura.h
+++ b/zathura.h
@@ -381,13 +381,20 @@ void zathura_jumplist_forward(zathura_t* zathura);
void zathura_jumplist_backward(zathura_t* zathura);
/**
- * Add current page as a new item to the jumplist after current position
+ * Add current page as a new jump at the end of the jumplist
*
* @param zathura The zathura session
*/
void zathura_jumplist_add(zathura_t* zathura);
/**
+ * Insert current page as a new jump before current jump.
+ *
+ * @param zathura The zathura session
+ */
+void zathura_jumplist_insert(zathura_t* zathura);
+
+/**
* Trim entries from the beginning of the jumplist to maintain it's maximum size constraint.
*
* @param zathura The zathura session
--
1.8.3.2
>From 4df3b7fe2cf0dce3436aec17f0addb46b0ae25c9 Mon Sep 17 00:00:00 2001
From: Abdo Roig-Maranges <abdo.r...@gmail.com>
Date: Tue, 2 Jul 2013 12:05:35 +0200
Subject: [PATCH 2/2] Adapts bisect functionality to changes in the jumplist
Bisect functionality is broken in this case:
-1 ...... 0 .......-2 ..................
in this picture pages go from left to right and numbers indicate
jumps (0 = current).
Bisecting to the right in the current broken bisect leads to
-2 ......-1 .......-3 .. 0 .............
Bisect code relies in that the 2 jumps before current are the bounds in
the current bisect step.
To achieve this in the case above (the only one that leads to troubles),
we insert a new jump before 0, with the page of the upper bound at
-2. This leads to
-2
-3 ......-1 .. 0 ..-4 .... .............
This way, -1 and -2 are again the bisect bounds for the current jump 0
without loosing jump history.
---
shortcuts.c | 10 ++++++----
1 file changed, 6 insertions(+), 4 deletions(-)
diff --git a/shortcuts.c b/shortcuts.c
index bfb4cf3..8531f97 100644
--- a/shortcuts.c
+++ b/shortcuts.c
@@ -859,9 +859,10 @@ sc_bisect(girara_session_t* session, girara_argument_t* argument,
} else if (have_prev2 && cur_page <= prev2_page) {
/* save current position at previous jump point */
if (cur_page < prev2_page) {
- zathura_jumplist_backward(zathura);
zathura_jumplist_add(zathura);
- zathura_jumplist_forward(zathura);
+
+ page_set(zathura, prev2_page);
+ zathura_jumplist_insert(zathura);
page_set(zathura, (cur_page + prev2_page)/2);
zathura_jumplist_add(zathura);
@@ -886,9 +887,10 @@ sc_bisect(girara_session_t* session, girara_argument_t* argument,
} else if (have_prev2 && prev2_page <= cur_page) {
/* save current position at previous jump point */
if (prev2_page < cur_page) {
- zathura_jumplist_backward(zathura);
zathura_jumplist_add(zathura);
- zathura_jumplist_forward(zathura);
+
+ page_set(zathura, prev2_page);
+ zathura_jumplist_insert(zathura);
page_set(zathura, (cur_page + prev2_page)/2);
zathura_jumplist_add(zathura);
--
1.8.3.2
_______________________________________________
zathura mailing list
zathura@lists.pwmt.org
http://lists.pwmt.org/mailman/listinfo/zathura
