Skip to content

[Core] Add try_link: atomic accept-or-forward slot decision #85

Description

@thep2p

Summary

Add a try_link primitive to LookupTable: a single write-lock critical section that decides, for one (level, direction) slot, whether to accept a candidate node directly or forward to the existing neighbor.

Algorithm detail: docs/protocol/concurrent-insert.md, Section 4.

Scope

  • src/core/lookup/mod.rs — add try_link to the LookupTable trait; add a LinkOutcome enum (LinkedDirectly / Forward(Identity)).
  • src/core/lookup/array_lookup_table.rs — implement try_link for ArrayLookupTable. The compare-then-act decision must execute entirely inside one inner.write() critical section — two separate lock acquisitions are not equivalent (see docs/protocol/concurrent-insert.md, Section 4.2).
  • src/core/lookup/array_lookup_table_test.rs — tests for both outcomes plus the existing out-of-bounds-level error case.

Acceptance criteria

  • try_link never calls get_entry/update_entry as two separate lock acquisitions.
  • Test: empty slot → link.
  • Test: existing neighbor not between self and candidate → link (overwrite).
  • Test: existing neighbor strictly between self and candidate → forward, table left untouched.
  • Test: out-of-range level → error.

Dependencies

None.

Dependency graph (unblocked first):
EPIC #81 -- local search & join protocol
  #67 [DONE] search_by_id            #71 [OPEN] search_by_mem_vec (independent)
  #74 [OPEN] search_by_id timeout fix   #76 [OPEN] delete/leave
  Concurrent join + repair (Algorithm 2 + Algorithm 8; supersedes closed #66, #77):
    L0 (no deps):         #84  #85 <-- YOU ARE HERE  #93  #86  #87
    L1:                   #94  #88  #89
    L2:                   #90  #91  #95  #96
    L3:                   #92
    L4 (acceptance gate): #97

Metadata

Metadata

Labels

No labels
No labels

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions