revlog: implement fast_rank retrieval in C
authorpacien <pacien.trangirard@pacien.net>
Mon, 21 Feb 2022 18:05:54 +0100
changeset 48852 e633e660158f
parent 48851 d739cd69bb6a
child 48853 4346be456875
revlog: implement fast_rank retrieval in C This will be useful in particular to avoid going through the Python interpreter in native Rust functions. Differential Revision: https://phab.mercurial-scm.org/D12209
mercurial/cext/revlog.c
rust/hg-cpython/src/cindex.rs
--- a/mercurial/cext/revlog.c	Mon Feb 21 15:53:03 2022 +0100
+++ b/mercurial/cext/revlog.c	Mon Feb 21 18:05:54 2022 +0100
@@ -33,6 +33,7 @@
 	int abi_version;
 	Py_ssize_t (*index_length)(const indexObject *);
 	const char *(*index_node)(indexObject *, Py_ssize_t);
+	int (*fast_rank)(indexObject *, Py_ssize_t);
 	int (*index_parents)(PyObject *, int, int *);
 } Revlog_CAPI;
 
@@ -564,6 +565,34 @@
 }
 
 /*
+ * Return the stored rank of a given revision if known, or rank_unknown
+ * otherwise.
+ *
+ * The rank of a revision is the size of the sub-graph it defines as a head.
+ * Equivalently, the rank of a revision `r` is the size of the set
+ * `ancestors(r)`, `r` included.
+ *
+ * This method returns the rank retrieved from the revlog in constant time. It
+ * makes no attempt at computing unknown values for versions of the revlog
+ * which do not persist the rank.
+ */
+static int index_fast_rank(indexObject *self, Py_ssize_t pos)
+{
+	Py_ssize_t length = index_length(self);
+	int rank;
+
+	if (self->format_version != format_cl2 || pos >= length) {
+		return rank_unknown;
+	}
+
+	if (pos == nullrev) {
+		return 0; /* convention */
+	}
+
+	return *(index_deref(self, pos) + entry_cl2_offset_rank);
+}
+
+/*
  * Return the hash of the node corresponding to the given rev. The
  * rev is assumed to be existing. If not, an exception is set.
  */
@@ -3248,10 +3277,7 @@
 static Revlog_CAPI CAPI = {
     /* increment the abi_version field upon each change in the Revlog_CAPI
        struct or in the ABI of the listed functions */
-    2,
-    index_length,
-    index_node,
-    HgRevlogIndex_GetParents,
+    3, index_length, index_node, index_fast_rank, HgRevlogIndex_GetParents,
 };
 
 void revlog_module_init(PyObject *mod)
--- a/rust/hg-cpython/src/cindex.rs	Mon Feb 21 15:53:03 2022 +0100
+++ b/rust/hg-cpython/src/cindex.rs	Mon Feb 21 18:05:54 2022 +0100
@@ -18,7 +18,7 @@
 use hg::{Graph, GraphError, Revision, WORKING_DIRECTORY_REVISION};
 use libc::{c_int, ssize_t};
 
-const REVLOG_CABI_VERSION: c_int = 2;
+const REVLOG_CABI_VERSION: c_int = 3;
 
 #[repr(C)]
 pub struct Revlog_CAPI {
@@ -29,6 +29,10 @@
         index: *mut revlog_capi::RawPyObject,
         rev: ssize_t,
     ) -> *const Node,
+    fast_rank: unsafe extern "C" fn(
+        index: *mut revlog_capi::RawPyObject,
+        rev: ssize_t,
+    ) -> ssize_t,
     index_parents: unsafe extern "C" fn(
         index: *mut revlog_capi::RawPyObject,
         rev: c_int,