Skip to content

revision.c: implement --reverse=before for walks

Mirko Faina git 4 versions – In review

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v4 Latest2 patches 8 repliesIn review
  2. v32 patches 1 replySuperseded
  3. v22 patches 3 repliesSuperseded
Earlier versions · 1
VersionPostedPatchesRepliesStatus
v11 patch18 repliesSuperseded

Patches in v4 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/2revision.c: implement --reverse=before for walksDocumentation/rev-list-options.adoc revision.c revision.h +1 more+113 -87 replies
2/2revision.c: reduce memory usage on reverse beforerevision.c+40 -21 reply

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v4 yet.

Read the v4 thread

Cover letter [PATCH v4 0/2] revision.c: implement --reverse=before for walks

v4 aligns the behaviour for --reverse=before and --reverse=after on negative numbers that are less than -1 to treat them the same as -1, which is current behaviour (before this series).

[1/2] revision.c: implement --reverse=before for walks (Mirko Faina) [2/2] revision.c: reduce memory usage on reverse before (Mirko Faina)

 Documentation/rev-list-options.adoc | 16 +++++--
 revision.c                          | 73 +++++++++++++++++++++++++++--
 revision.h                          |  8 +++-
 t/t4202-log.sh                      | 66 ++++++++++++++++++++++++++
 4 files changed, 153 insertions(+), 10 deletions(-)

Range-diff against v3:

1:  4864ac46dd = 1:  4864ac46dd revision.c: implement --reverse=before for walks
2:  00489b0e52 ! 2:  7c0bab5d14 revision.c: reduce memory usage on reverse before

@@ Commit message
revision with --reverse=before and --max-count=<k>. We do this through a simple queue. With N nodes and K as the --max-count argument, assuming K < N, we go from a space complexity of O(N) to O(K). When it comes down
- to time complexity, the queue has an ammortized time of O(1) for pops,
- so the complexity remains O(N).
+ to time complexity, the queue has an amortized time of O(1) for pops, so
+ the complexity remains O(N).

@@ revision.c: struct commit *get_revision(struct rev_info *revs)
reversed = NULL;
- while ((c = get_revision_internal(revs)))
- commit_list_insert(c, &reversed);
-+ if (revs->reverse == REVERSE_BEFORE && max_count != -1) {
++ if (revs->reverse == REVERSE_BEFORE && max_count >= 0) {
+ retrieve_with_window(revs, max_count, &reversed);
+ } else {
+ while ((c = get_revision_internal(revs)))

base-commit: e8955061076952cc5eab0300424fc48b601fe12d

Signature · 1 line
2.54.0