nodelist — 고정 intrusive 목록
노드가 링크를 자기 안에 든다(intrusive). 목록 쪽에 따로 칸을 잡지 않으므로 넣고 빼는 데 할당이 없다 — Linux 커널의 list_head 가 그 모양이다. 위험한 것은 둘뿐이다 — 링크된 노드를 옮기면 이웃이 가리키던 자리가 썩고, 링크된 채 회수하면 목록이 썩는다.
그 둘을 언어가 막는다. 노드에는 이동권 (site)이 있고, 목록에 넣으면 목록이 그것을 먹는다(held). 링크된 채 옮기려는 프로그램은 건넬 값이 없어 컴파일이 거절한다.
newtype lru u32 .
var s owned nodelist.site lru . be nodelist.nl_open lru 3 .
var h owned nodelist.held lru . be nodelist.nl_link lru s .
rem nodelist.nl_relocate lru s 9 → E-OWN-MOVED (s 는 이미 먹혔다)
var s3 owned nodelist.site lru . be nodelist.nl_unlink lru h .
var s4 owned nodelist.site lru . be nodelist.nl_relocate lru s3 1 .| op | 하는 일 |
|---|---|
site · held | 이동권(링크 안 됨) · 링크된 표 — 브랜드 붙은 타입 |
nl_open · nl_relocate | 자리를 이동권으로 연다 · 링크 안 된 노드를 옮긴다 |
nl_link · nl_unlink | 이동권을 먹고 링크 표를 낸다 · 표를 먹고 이동권을 돌려준다 |
nl_slot_of · nl_held_slot | 이동권 · 링크 표의 자리 번호 |
nl_solo · nl_after · nl_cut | 혼자인 고리로 · at 뒤에 넣기 · 빼기(nx · pv 를 고친다) |
nl_walk_cut | 머리부터 돌면서 한 노드를 뺀다(가변 순회) |
nl_count | 고리의 노드 수 |
표 50.1 — nodelist 의 op
목록은 고리다. 널이 없으므로 끝을 표시할 값이 없다. 대신 머리로 돌아오면 한 바퀴다. 혼자인 노드는 자기 자신을 가리키는 고리 하나다. 처음엔 “자기 자신을 가리키면 끝” 으로 셌다가 틀렸다 — 둘 이상인 고리에서는 아무도 자기를 가리키지 않으므로 그 조건이 영영 오지 않는다.
순회하면서 뺄 때는 다음을 먼저 읽는다. 지금 노드를 빼면 그 next 가 자기 자신이 되므로, 빼기 전에 읽어 두지 않으면 순회가 그 자리에서 멈춘다. nl_walk_cut 이 그렇게 한다.
저장은 호출자 것이다. nx(다음) · pv(이전) 두 슬라이스를 밖에서 받는다. 링크는 인덱스다 — 생 포인터가 없고, 인덱스는 segarena 처럼 움직이지 않는 저장과 맞물린다.
여러 목록에 동시에 드는 노드. LRU 목록과 해시 버킷에 같은 노드가 든다면 이동권이 하나뿐이라 두 번째 링크가 들지 못한다. shard 토큰으로 쪼갠다 — role 마다 조각 하나, 전부 되합쳐야(rejoin) 이동권이 다시 선다. 그것이 곧 “모든 role 에서 빼고 나서 회수” 다. 브랜드 하나는 저장소 하나를 이름하므로, 노드 자리와 role 토큰에 같은 브랜드를 쓰면 E-BRAND-REUSED 가 거절한다 — 이 매뉴얼을 쓰다 실제로 걸렸고 컴파일러가 옳았다.
짓지 않은 것 — 자동 회수(첫 회수 정책은 일괄이다), 순환 검출, 동시 순회, 링크된 노드 재배치(고정이 그 반대다).