D12209: revlog: implement fast_rank retrieval in C

[pacien (Pacien)]

pacien created this revision.
Herald added a reviewer: hg-reviewers.
Herald added a subscriber: mercurial-patches.

REVISION SUMMARY
  This will be useful in particular to avoid going through the Python interpreter
  in native Rust functions.

REPOSITORY
  rHG Mercurial

BRANCH
  default

REVISION DETAIL
  https://phab.mercurial-scm.org/D12209

AFFECTED FILES
  mercurial/cext/revlog.c
  rust/hg-cpython/src/cindex.rs

CHANGE DETAILS

diff --git a/rust/hg-cpython/src/cindex.rs b/rust/hg-cpython/src/cindex.rs
--- a/rust/hg-cpython/src/cindex.rs
+++ b/rust/hg-cpython/src/cindex.rs
@@ -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,
diff --git a/mercurial/cext/revlog.c b/mercurial/cext/revlog.c
--- a/mercurial/cext/revlog.c
+++ b/mercurial/cext/revlog.c
@@ -43,6 +43,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;
 
@@ -576,6 +577,32 @@
 }
 
 /*
+ * 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.
  */
@@ -3266,10 +3293,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,
+    2, index_length, index_node, index_fast_rank, HgRevlogIndex_GetParents,
 };
 
 void revlog_module_init(PyObject *mod)



To: pacien, #hg-reviewers
Cc: mercurial-patches, mercurial-devel