From e57b26fc1406a2f1e6541558d5ebd35d7ef54b1d Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Wed, 4 Nov 2026 22:58:39 -0300 Subject: Places: one lineOf for the line a byte is on, std.sort.partitionPoint in place of five hand-written binary searches (firstFrom, paint's, tickOf's, and Query's lineOfOffset and writePlacesRows', the latter two the same search as tickOf's) Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_016Y9MNAtZenFv4weoMD3cge --- src/Places.zig | 42 ++++++++++++++++++++---------------------- src/Query.zig | 24 ++---------------------- 2 files changed, 22 insertions(+), 44 deletions(-) diff --git a/src/Places.zig b/src/Places.zig index 30c14b46..d5a4bb4d 100644 --- a/src/Places.zig +++ b/src/Places.zig @@ -165,13 +165,20 @@ pub fn complete(set: *const Places) bool { /// The first hit starting at or after `at`. pub fn firstFrom(hits: []const Hit, at: usize) usize { - var lo: usize = 0; - var hi = hits.len; - while (lo < hi) { - const mid = lo + (hi - lo) / 2; - if (hits[mid].start < at) lo = mid + 1 else hi = mid; - } - return lo; + return std.sort.partitionPoint(Hit, hits, at, struct { + fn before(byte: usize, h: Hit) bool { + return h.start < byte; + } + }.before); +} + +/// The line (0-based) that holds byte `at`, by a file's line index. +pub fn lineOf(index: []const usize, at: usize) usize { + return std.sort.partitionPoint(usize, index, at, struct { + fn before(byte: usize, start: usize) bool { + return start <= byte; + } + }.before) -| 1; } /// Search `pane`'s text for `pattern` from now on, in place of whatever @@ -700,13 +707,11 @@ pub fn paint(set: *Places, p: *Pardes, s: *Surface, pane: *Pane, r: pardes.Rect, const next = File.lineStart(p.gpa, f, @intCast(line + 1)); const le = if (next > ls and next <= f.content.len and f.content[next - 1] == '\n') next - 1 else next; // the first hit ending past the line's start - var lo: usize = 0; - var hi = hits.len; - while (lo < hi) { - const mid = lo + (hi - lo) / 2; - if (hits[mid].end <= ls) lo = mid + 1 else hi = mid; - } - var i = lo; + var i = std.sort.partitionPoint(Hit, hits, ls, struct { + fn before(line_start: usize, h: Hit) bool { + return h.end <= line_start; + } + }.before); while (i < hits.len and hits[i].start <= le) : (i += 1) { const a = @max(hits[i].start, ls) - ls; const b = @min(hits[i].end, le) - ls; @@ -738,14 +743,7 @@ fn buildTicks(set: *Places, p: *Pardes, f: *File.State) void { /// The step of the rail holding place `i`. fn tickOf(set: *Places, p: *Pardes, f: *File.State, i: usize) ?u16 { const index = File.lineIndex(p.gpa, f) catch return null; - const at = set.hits.items[i].start; - var lo: usize = 0; - var hi = index.len; - while (lo < hi) { - const mid = lo + (hi - lo) / 2; - if (index[mid] <= at) lo = mid + 1 else hi = mid; - } - const line = lo -| 1; + const line = lineOf(index, set.hits.items[i].start); return @intCast(@min(tick_scale - 1, line * tick_scale / @max(1, index.len))); } diff --git a/src/Query.zig b/src/Query.zig index e34b1054..5fdfff2a 100644 --- a/src/Query.zig +++ b/src/Query.zig @@ -925,15 +925,7 @@ fn writePlacesRows(p: *Pardes, q: *Query, out: *std.ArrayList(u8), rows: *std.Ar var decl_now: ?usize = null; var i: usize = @min(from, hits.len); // the line of the first, found in the index - var line: usize = if (i < hits.len) blk: { - var lo: usize = 0; - var hi = index.len; - while (lo < hi) { - const mid = lo + (hi - lo) / 2; - if (index[mid] <= hits[i].start) lo = mid + 1 else hi = mid; - } - break :blk lo -| 1; - } else 0; + var line: usize = if (i < hits.len) Places.lineOf(index, hits[i].start) else 0; // a window begins at a line's first place while (i > 0 and hits[i - 1].start >= index[line]) i -= 1; while (i < hits.len) { @@ -1032,7 +1024,7 @@ fn showPlacesCurrent(p: *Pardes, id: usize) void { // By line, not by the rows' place indices: the rows may lag the places // a tick while they are still being found. if (set.current) |c| if (c < set.hits.items.len) { - const at = lineOfOffset(p, &owner.file.?, set.hits.items[c].start) + 1; + const at = Places.lineOf(File.lineIndex(p.gpa, &owner.file.?) catch &.{}, set.hits.items[c].start) + 1; const rows = rp.file.?.location_rows; for (q.items.items, 0..) |it, i| { if (it.kind != .hit or it.serial != owner.serial or i + 1 >= rows.len) continue; @@ -1508,18 +1500,6 @@ fn caretTo(rp: *Pane, i: usize) void { if (r >= off + @as(i32, rp.rows)) rp.scrollBy(r - off - @as(i32, rp.rows) + 1) else if (r < off) rp.scrollBy(r - off); } -/// The line (0-based) of byte `at` of `f`'s text. -fn lineOfOffset(p: *Pardes, f: *File.State, at: usize) usize { - const index = File.lineIndex(p.gpa, f) catch return 0; - var lo: usize = 0; - var hi = index.len; - while (lo < hi) { - const mid = lo + (hi - lo) / 2; - if (index[mid] <= at) lo = mid + 1 else hi = mid; - } - return lo -| 1; -} - /// The first of pane `tp`'s places on line `line` (1-based), if any. fn placeOnLine(p: *Pardes, tp: *Pane, line: usize) ?usize { const f = &tp.file.?; -- cgit v1.3