[gtk/wip/otte/sortlistmodel: 24/38] timsort: Add progress estimation

[Benjamin Otte <otte src gnome org>]

commit 9103131ea1b537aa6a9e8c954ed54a1b4534e000
Author: Benjamin Otte <otte redhat com>
Date:   Sun Jul 12 17:57:03 2020 +0200

    timsort: Add progress estimation

 gtk/gtktimsort.c        | 45 +++++++++++++++++++++++++++++++++++++++++++++
 gtk/gtktimsortprivate.h |  2 ++
 2 files changed, 47 insertions(+)
---
diff --git a/gtk/gtktimsort.c b/gtk/gtktimsort.c
index 4ddb6c9245..548bb292b5 100644
--- a/gtk/gtktimsort.c
+++ b/gtk/gtktimsort.c
@@ -266,6 +266,51 @@ gtk_tim_sort_set_max_merge_size (GtkTimSort *self,
   self->max_merge_size = max_merge_size;
 }
 
+/**
+ * gtk_tim_sort_get_progress:
+ * @self: a #GtkTimSort
+ *
+ * Does a progress estimate about sort progress, estimates relative
+ * to the number of items to sort.
+ *
+ * Note that this is entirely a progress estimate and does not have
+ * a relationship with items put in their correct place.  
+ * It is also an estimate, so no guarantees are made about accuracy,
+ * other than that it will only report 100% completion when it is
+ * indeed done sorting.
+ *
+ * To get a percentage, you need to divide this number by the total
+ * number of elements that are being sorted.
+ *
+ * Returns: Rough guess of sort progress
+ **/
+gsize
+gtk_tim_sort_get_progress (GtkTimSort *self)
+{
+#define DEPTH 4
+  gsize i;
+  gsize last, progress;
+
+  g_return_val_if_fail (self != NULL, 0);
+
+  if (self->pending_runs == 0)
+    return 0;
+
+  last = self->run[0].len;
+  progress = 0;
+
+  for (i = 1; i < DEPTH + 1 && i < self->pending_runs; i++)
+    {
+      progress += (DEPTH + 1 - i) * MAX (last, self->run[i].len);
+      last = MIN (last, self->run[i].len);
+    }
+  if (i < DEPTH + 1)
+    progress += (DEPTH + 1 - i) * last;
+
+  return progress / DEPTH;
+#undef DEPTH
+}
+
 #if 1
 #define WIDTH 4
 #include "gtktimsort-impl.c"
diff --git a/gtk/gtktimsortprivate.h b/gtk/gtktimsortprivate.h
index a864a9c936..1fcadbd9a6 100644
--- a/gtk/gtktimsortprivate.h
+++ b/gtk/gtktimsortprivate.h
@@ -108,6 +108,8 @@ void            gtk_tim_sort_set_runs                           (GtkTimSort
 void            gtk_tim_sort_set_max_merge_size                 (GtkTimSort             *self,
                                                                  gsize                   max_merge_size);
 
+gsize           gtk_tim_sort_get_progress                       (GtkTimSort             *self);
+
 gboolean        gtk_tim_sort_step                               (GtkTimSort             *self,
                                                                  GtkTimSortRun          *out_change);