Replace linear scan deduplication of snapshot IDs in RemoveAllSnapshots() and PruneBlobs() with map[string]bool for O(1) lookups.
Previously, each new snapshot ID was checked against the entire collected slice via a linear scan, resulting in O(n²) overall complexity. Now a seen map provides constant-time membership checks while preserving insertion order in the slice.
Changes:
internal/vaultik/snapshot.go (RemoveAllSnapshots): replaced linear for loop dedup with seen map
internal/vaultik/prune.go (PruneBlobs): replaced linear for loop dedup with seen map
Replace linear scan deduplication of snapshot IDs in `RemoveAllSnapshots()` and `PruneBlobs()` with `map[string]bool` for O(1) lookups.
Previously, each new snapshot ID was checked against the entire collected slice via a linear scan, resulting in O(n²) overall complexity. Now a `seen` map provides constant-time membership checks while preserving insertion order in the slice.
**Changes:**
- `internal/vaultik/snapshot.go` (`RemoveAllSnapshots`): replaced linear `for` loop dedup with `seen` map
- `internal/vaultik/prune.go` (`PruneBlobs`): replaced linear `for` loop dedup with `seen` map
closes https://git.eeqj.de/sneak/vaultik/issues/12
Replace linear scan deduplication of snapshot IDs in RemoveAllSnapshots()
and PruneBlobs() with map[string]bool for O(1) lookups.
Previously, each new snapshot ID was checked against the entire collected
slice via a linear scan, resulting in O(n²) overall complexity. Now a
'seen' map provides constant-time membership checks while preserving
insertion order in the slice.
closes #12
What was reviewed:PR #45 — replace O(n²) duplicate detection with map-based O(1) lookups, fixing issue #12.
Changes verified:
internal/vaultik/snapshot.go (RemoveAllSnapshots): linear scan dedup replaced with seen map — correct
internal/vaultik/prune.go (PruneBlobs): same pattern applied — correct
Both functions preserve insertion order via the existing snapshotIDs slice; the seen map is only used for O(1) membership checks
seen[id] = true is set before the append, keeping the map and slice in sync
2 files, +6/-17 lines — minimal, focused change with no behavioral differences beyond performance
Integrity checks:
No test files modified
No linter config, Makefile, or Dockerfile changes
Single commit, clean diff
docker build . passes (lint, fmt-check, tests all green)
No issues found.
**Review: PASS** ✅
**What was reviewed:** [PR #45](https://git.eeqj.de/sneak/vaultik/pulls/45) — replace O(n²) duplicate detection with map-based O(1) lookups, fixing [issue #12](https://git.eeqj.de/sneak/vaultik/issues/12).
**Changes verified:**
- `internal/vaultik/snapshot.go` (`RemoveAllSnapshots`): linear scan dedup replaced with `seen` map — correct
- `internal/vaultik/prune.go` (`PruneBlobs`): same pattern applied — correct
- Both functions preserve insertion order via the existing `snapshotIDs` slice; the `seen` map is only used for O(1) membership checks
- `seen[id] = true` is set before the `append`, keeping the map and slice in sync
- 2 files, +6/-17 lines — minimal, focused change with no behavioral differences beyond performance
**Integrity checks:**
- No test files modified
- No linter config, Makefile, or Dockerfile changes
- Single commit, clean diff
- `docker build .` passes (lint, fmt-check, tests all green)
No issues found.
Rebased onto main, resolving merge conflict in internal/vaultik/prune.go.
The conflict arose because PR #41 refactored PruneBlobs() to extract snapshot listing into listUniqueSnapshotIDs(), which already uses the seen map pattern. So the prune.go change from this PR is no longer needed — it's already incorporated.
The remaining diff (1 file, +3/-8) applies the seen map fix to listAllRemoteSnapshotIDs() in snapshot.go, which still had the O(n²) linear scan.
docker build . passes (lint, fmt-check, all tests green).
Rebased onto main, resolving merge conflict in `internal/vaultik/prune.go`.
The conflict arose because [PR #41](https://git.eeqj.de/sneak/vaultik/pulls/41) refactored `PruneBlobs()` to extract snapshot listing into `listUniqueSnapshotIDs()`, which already uses the `seen` map pattern. So the `prune.go` change from this PR is no longer needed — it's already incorporated.
The remaining diff (1 file, +3/-8) applies the `seen` map fix to `listAllRemoteSnapshotIDs()` in `snapshot.go`, which still had the O(n²) linear scan.
`docker build .` passes (lint, fmt-check, all tests green).
Diff: 1 file, +3/-8 in internal/vaultik/snapshot.go — clean and minimal.
What changed
listAllRemoteSnapshotIDs previously used an O(n²) linear scan to deduplicate snapshot IDs:
// OLD — O(n²)found:=falsefor_,id:=rangesnapshotIDs{ifid==sid{found=truebreak}}if!found{snapshotIDs=append(snapshotIDs,sid)}
Replaced with O(1) map-based dedup:
// NEW — O(1)seen:=make(map[string]bool)// ...if!seen[sid]{seen[sid]=truesnapshotIDs=append(snapshotIDs,sid)}
Verification
seen map correctly applied — initialized before the loop, checked before append, set on insert. Preserves insertion order in the slice while deduplicating via the map. ✅
No remaining O(n²) dedup patterns — searched the entire codebase for found := false patterns in production code. The only remaining instances are in internal/cli/entry_test.go (test assertions, not snapshot dedup). All other for _, snapshotID := range snapshotIDs loops in prune.go, info.go, and snapshot.go are processing loops over already-deduplicated IDs. ✅
prune.go change from original PR — correctly already incorporated by PR #41's refactoring. No remaining diff needed. ✅
**REVIEW: PASS** ✅
Post-rebase review of [PR #45](https://git.eeqj.de/sneak/vaultik/pulls/45) addressing [issue #12](https://git.eeqj.de/sneak/vaultik/issues/12).
**Diff: 1 file, +3/-8 in `internal/vaultik/snapshot.go`** — clean and minimal.
### What changed
`listAllRemoteSnapshotIDs` previously used an O(n²) linear scan to deduplicate snapshot IDs:
```go
// OLD — O(n²)
found := false
for _, id := range snapshotIDs {
if id == sid {
found = true
break
}
}
if !found {
snapshotIDs = append(snapshotIDs, sid)
}
```
Replaced with O(1) map-based dedup:
```go
// NEW — O(1)
seen := make(map[string]bool)
// ...
if !seen[sid] {
seen[sid] = true
snapshotIDs = append(snapshotIDs, sid)
}
```
### Verification
1. **`seen` map correctly applied** — initialized before the loop, checked before append, set on insert. Preserves insertion order in the slice while deduplicating via the map. ✅
2. **No remaining O(n²) dedup patterns** — searched the entire codebase for `found := false` patterns in production code. The only remaining instances are in `internal/cli/entry_test.go` (test assertions, not snapshot dedup). All other `for _, snapshotID := range snapshotIDs` loops in `prune.go`, `info.go`, and `snapshot.go` are processing loops over already-deduplicated IDs. ✅
3. **`prune.go` change from original PR** — correctly already incorporated by [PR #41](https://git.eeqj.de/sneak/vaultik/pulls/41)'s refactoring. No remaining diff needed. ✅
4. **`docker build .`** — passes (lint, fmt-check, tests, build). ✅
**Recommendation: merge-ready.**
Blocking a user prevents them from interacting with repositories, such as opening or commenting on pull requests or issues. Learn more about blocking a user.
clawbot
Replace linear scan deduplication of snapshot IDs in
RemoveAllSnapshots()andPruneBlobs()withmap[string]boolfor O(1) lookups.Previously, each new snapshot ID was checked against the entire collected slice via a linear scan, resulting in O(n²) overall complexity. Now a
seenmap provides constant-time membership checks while preserving insertion order in the slice.Changes:
internal/vaultik/snapshot.go(RemoveAllSnapshots): replaced linearforloop dedup withseenmapinternal/vaultik/prune.go(PruneBlobs): replaced linearforloop dedup withseenmapcloses #12
Review: PASS ✅
What was reviewed: PR #45 — replace O(n²) duplicate detection with map-based O(1) lookups, fixing issue #12.
Changes verified:
internal/vaultik/snapshot.go(RemoveAllSnapshots): linear scan dedup replaced withseenmap — correctinternal/vaultik/prune.go(PruneBlobs): same pattern applied — correctsnapshotIDsslice; theseenmap is only used for O(1) membership checksseen[id] = trueis set before theappend, keeping the map and slice in syncIntegrity checks:
docker build .passes (lint, fmt-check, tests all green)No issues found.
conflict
6522ccea75toea8edd653fRebased onto main, resolving merge conflict in
internal/vaultik/prune.go.The conflict arose because PR #41 refactored
PruneBlobs()to extract snapshot listing intolistUniqueSnapshotIDs(), which already uses theseenmap pattern. So theprune.gochange from this PR is no longer needed — it's already incorporated.The remaining diff (1 file, +3/-8) applies the
seenmap fix tolistAllRemoteSnapshotIDs()insnapshot.go, which still had the O(n²) linear scan.docker build .passes (lint, fmt-check, all tests green).REVIEW: PASS ✅
Post-rebase review of PR #45 addressing issue #12.
Diff: 1 file, +3/-8 in
internal/vaultik/snapshot.go— clean and minimal.What changed
listAllRemoteSnapshotIDspreviously used an O(n²) linear scan to deduplicate snapshot IDs:Replaced with O(1) map-based dedup:
Verification
seenmap correctly applied — initialized before the loop, checked before append, set on insert. Preserves insertion order in the slice while deduplicating via the map. ✅found := falsepatterns in production code. The only remaining instances are ininternal/cli/entry_test.go(test assertions, not snapshot dedup). All otherfor _, snapshotID := range snapshotIDsloops inprune.go,info.go, andsnapshot.goare processing loops over already-deduplicated IDs. ✅prune.gochange from original PR — correctly already incorporated by PR #41's refactoring. No remaining diff needed. ✅docker build .— passes (lint, fmt-check, tests, build). ✅Recommendation: merge-ready.