Repository: maypok86/otter
Pull request #24 (2023-12-15 19:40:12)

[#19] Implement queues based on double-linked lists
## Description

<!--
Describes the nature of your changes. If they are substantial, you should
further subdivide this into a section describing the problem you are solving and
another describing your solution.
-->

Implemented a queue on a double-linked list and transferred the eviction policy to it. Also added tests for this queue.

## Related issue(s)
#19 
<!--
- Short description of how the PR relates to the issue, including an issue link.
For example
- Fixed #100500 by adding lenses to exported items

Write 'None' if there are no related issues (which is discouraged).
-->

## :white_check_mark: Checklist for your Pull Request

<!--
Ideally a PR has all of the checkmarks set.

If something in this list is irrelevant to your PR, you should still set this
checkmark indicating that you are sure it is dealt with (be that by irrelevance).

If you don't set a checkmark (e. g. don't add a test for new functionality),
you must be able to justify that.
-->

#### Related changes (conditional)

- Tests
    - [x] If I added new functionality, I added tests covering it.
    - [x] If I fixed a bug, I added a regression test to prevent the bug from
      silently reappearing again.

- Documentation
    - [x] I checked whether I should update the docs and did so if necessary:
        - [README](../README.md)

- Public contracts
    - [x] My changes doesn't break project license.

#### Stylistic guide (mandatory)

- [x] My code complies with the [styles guide](https://github.com/uber-go/guide/blob/master/style.md).
- [x] My commit history is clean (only contains changes relating to my
  issue/pull request and no reverted-my-earlier-commit changes) and commit
  messages start with identifiers of related issues in square brackets.

  **Example:** `[#42] Short commit description`

  If necessary both of these can be achieved even after the commits have been
  made/pushed using [rebase and squash](https://git-scm.com/docs/git-rebase).

#### Before merging (mandatory)
- [x] Check __target__  branch of PR is set correctly



Patch:
diff --git a/cache.go b/cache.go
index c0ffa5d..1feb5cb 100644
--- a/cache.go
+++ b/cache.go
@@ -94,7 +94,7 @@ func (c *Cache[K, V]) Get(key K) (V, bool) {
 	}
 
 	if got.IsExpired() {
-		c.writeBuffer.Insert(node.NewEvictTask(got))
+		c.writeBuffer.Insert(node.NewDeleteTask(got))
 		c.stats.IncMisses()
 		return zeroValue[V](), false
 	}
@@ -110,16 +110,9 @@ func (c *Cache[K, V]) afterGet(got *node.Node[K, V]) {
 	pb := c.readBuffers[idx].Add(got)
 	if pb != nil {
 		c.evictionMutex.Lock()
-		deleted := c.policy.Read(pb.Deleted, pb.Returned)
-		for _, n := range deleted {
-			c.expirePolicy.Delete(n)
-		}
+		c.policy.Read(pb.Returned)
 		c.evictionMutex.Unlock()
 
-		for _, n := range deleted {
-			c.hashmap.EvictNode(n)
-		}
-
 		c.readBuffers[idx].Free()
 	}
 }
@@ -153,7 +146,7 @@ func (c *Cache[K, V]) set(key K, value V, expiration uint64) {
 			return
 		}
 
-		c.writeBuffer.Insert(node.NewEvictTask(got))
+		c.writeBuffer.Insert(node.NewDeleteTask(got))
 	}
 
 	n := node.New(key, value, expiration, cost)
@@ -161,7 +154,7 @@ func (c *Cache[K, V]) set(key K, value V, expiration uint64) {
 	// TODO: try insert?
 	c.writeBuffer.Insert(node.NewAddTask(n))
 	if evicted != nil {
-		c.writeBuffer.Insert(node.NewEvictTask(evicted))
+		c.writeBuffer.Insert(node.NewDeleteTask(evicted))
 	}
 }
 
@@ -229,7 +222,7 @@ func (c *Cache[K, V]) process() {
 			c.evictionMutex.Lock()
 
 			for _, t := range buffer {
-				if t.IsDelete() || t.IsEvict() {
+				if t.IsDelete() {
 					c.expirePolicy.Delete(t.GetNode())
 				} else if t.IsAdd() {
 					c.expirePolicy.Add(t.GetNode())
diff --git a/go.mod b/go.mod
index 5a4628d..0c1551d 100644
--- a/go.mod
+++ b/go.mod
@@ -7,5 +7,3 @@ require (
 	github.com/dolthub/swiss v0.2.1
 	github.com/gammazero/deque v0.2.1
 )
-
-require github.com/stretchr/testify v1.8.2 // indirect
diff --git a/go.sum b/go.sum
index 5bde0df..80d8326 100644
--- a/go.sum
+++ b/go.sum
@@ -1,6 +1,4 @@
-github.com/davecgh/go-spew v1.1.0/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38=
 github.com/davecgh/go-spew v1.1.1 h1:vj9j/u1bqnvCEfJOwUhtlOARqs3+rkHYY13jYWTU97c=
-github.com/davecgh/go-spew v1.1.1/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38=
 github.com/dolthub/maphash v0.1.0 h1:bsQ7JsF4FkkWyrP3oCnFJgrCUAFbFf3kOl4L/QxPDyQ=
 github.com/dolthub/maphash v0.1.0/go.mod h1:gkg4Ch4CdCDu5h6PMriVLawB7koZ+5ijb9puGMV50a4=
 github.com/dolthub/swiss v0.2.1 h1:gs2osYs5SJkAaH5/ggVJqXQxRXtWshF6uE0lgR/Y3Gw=
@@ -8,15 +6,5 @@ github.com/dolthub/swiss v0.2.1/go.mod h1:8AhKZZ1HK7g18j7v7k6c5cYIGEZJcPn0ARsai8
 github.com/gammazero/deque v0.2.1 h1:qSdsbG6pgp6nL7A0+K/B7s12mcCY/5l5SIUpMOl+dC0=
 github.com/gammazero/deque v0.2.1/go.mod h1:LFroj8x4cMYCukHJDbxFCkT+r9AndaJnFMuZDV34tuU=
 github.com/pmezard/go-difflib v1.0.0 h1:4DBwDE0NGyQoBHbLQYPwSUPoCMWR5BEzIk/f1lZbAQM=
-github.com/pmezard/go-difflib v1.0.0/go.mod h1:iKH77koFhYxTK1pcRnkKkqfTogsbg7gZNVY4sRDYZ/4=
-github.com/stretchr/objx v0.1.0/go.mod h1:HFkY916IF+rwdDfMAkV7OtwuqBVzrE8GR6GFx+wExME=
-github.com/stretchr/objx v0.4.0/go.mod h1:YvHI0jy2hoMjB+UWwv71VJQ9isScKT/TqJzVSSt89Yw=
-github.com/stretchr/objx v0.5.0/go.mod h1:Yh+to48EsGEfYuaHDzXPcE3xhTkx73EhmCGUpEOglKo=
-github.com/stretchr/testify v1.7.1/go.mod h1:6Fq8oRcR53rry900zMqJjRRixrwX3KX962/h/Wwjteg=
-github.com/stretchr/testify v1.8.0/go.mod h1:yNjHg4UonilssWZ8iaSj1OCr/vHnekPRkoO+kdMU+MU=
-github.com/stretchr/testify v1.8.2 h1:+h33VjcLVPDHtOdpUCuF+7gSuG3yGIftsP1YvFihtJ8=
-github.com/stretchr/testify v1.8.2/go.mod h1:w2LPCIKwWwSfY2zedu0+kehJoqGctiVI29o6fzry7u4=
-gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0=
-gopkg.in/yaml.v3 v3.0.0-20200313102051-9f266ea9e77c/go.mod h1:K4uyk7z7BCEPqu6E+C64Yfv1cQ7kz7rIZviUmN+EgEM=
+github.com/stretchr/testify v1.8.1 h1:w7B6lhMri9wdJUVmEZPGGhZzrYTPvgJArz7wNPgYKsk=
 gopkg.in/yaml.v3 v3.0.1 h1:fxVm/GzAzEWqLHuvctI91KS9hhNmmWOoWu0XTYJS7CA=
-gopkg.in/yaml.v3 v3.0.1/go.mod h1:K4uyk7z7BCEPqu6E+C64Yfv1cQ7kz7rIZviUmN+EgEM=
diff --git a/internal/lossy/buffer.go b/internal/lossy/buffer.go
index 6ea3bed..36bfa2f 100644
--- a/internal/lossy/buffer.go
+++ b/internal/lossy/buffer.go
@@ -15,7 +15,6 @@ const (
 
 type PolicyBuffers[T any] struct {
 	Returned []*T
-	Deleted  []*T
 }
 
 type Buffer[T any] struct {
@@ -33,7 +32,6 @@ type Buffer[T any] struct {
 func New[T any]() *Buffer[T] {
 	pb := &PolicyBuffers[T]{
 		Returned: make([]*T, 0, capacity),
-		Deleted:  make([]*T, 0, capacity),
 	}
 	b := &Buffer[T]{
 		policyBuffers: unsafe.Pointer(pb),
@@ -83,7 +81,6 @@ func (b *Buffer[T]) Add(item *T) *PolicyBuffers[T] {
 func (b *Buffer[T]) Free() {
 	pb := (*PolicyBuffers[T])(b.policyBuffers)
 	pb.Returned = pb.Returned[:0]
-	pb.Deleted = pb.Deleted[:0]
 	atomic.StorePointer(&b.returned, b.policyBuffers)
 }
 
diff --git a/internal/node/meta.go b/internal/node/meta.go
deleted file mode 100644
index fdec434..0000000
--- a/internal/node/meta.go
+++ /dev/null
@@ -1,75 +0,0 @@
-package node
-
-const (
-	deletedMask   = uint32(1 << 31)
-	mainMask      = uint32(1 << 30)
-	smallMask     = uint32(1 << 29)
-	frequencyMask = uint32(4 - 1)
-)
-
-type Meta uint32
-
-func DefaultMeta() Meta {
-	return Meta(0)
-}
-
-func (m Meta) IsDeleted() bool {
-	return uint32(m)&deletedMask == deletedMask
-}
-
-func (m Meta) MarkDeleted() Meta {
-	return Meta(uint32(m) | deletedMask)
-}
-
-func (m Meta) IsMain() bool {
-	return uint32(m)&mainMask == mainMask
-}
-
-func (m Meta) MarkMain() Meta {
-	return Meta(uint32(m) | mainMask)
-}
-
-func (m Meta) UnmarkMain() Meta {
-	return Meta(uint32(m) &^ mainMask)
-}
-
-func (m Meta) IsSmall() bool {
-	return uint32(m)&smallMask == smallMask
-}
-
-func (m Meta) MarkSmall() Meta {
-	return Meta(uint32(m) | smallMask)
-}
-
-func (m Meta) UnmarkSmall() Meta {
-	return Meta(uint32(m) &^ smallMask)
-}
-
-func (m Meta) IncrementFrequency() Meta {
-	// TODO: speed up
-	frequency := uint32(m) & frequencyMask
-	frequency = minUint32(frequency+1, frequencyMask)
-	return Meta((uint32(m) >> 2 << 2) | frequency)
-}
-
-func (m Meta) DecrementFrequency() Meta {
-	frequency := uint32(m) & frequencyMask
-	frequency--
-	return Meta((uint32(m) >> 2 << 2) | frequency)
-}
-
-func (m Meta) ResetFrequency() Meta {
-	return m >> 2 << 2
-}
-
-func (m Meta) GetFrequency() uint32 {
-	return uint32(m) & frequencyMask
-}
-
-func minUint32(a, b uint32) uint32 {
-	if a < b {
-		return a
-	}
-
-	return b
-}
diff --git a/internal/node/node.go b/internal/node/node.go
index 800e559..39b74e4 100644
--- a/internal/node/node.go
+++ b/internal/node/node.go
@@ -7,14 +7,25 @@ import (
 	"github.com/maypok86/otter/internal/unixtime"
 )
 
+const (
+	unknownQueueType uint8 = iota
+	smallQueueType
+	mainQueueType
+
+	maxFrequency uint8 = 3
+)
+
 type Node[K comparable, V any] struct {
 	key        K
 	value      V
+	prev       *Node[K, V]
+	next       *Node[K, V]
 	mutex      sync.Mutex
 	hash       uint64
 	expiration uint64
-	Meta       Meta
 	cost       uint32
+	frequency  uint8
+	queueType  uint8
 }
 
 func New[K comparable, V any](key K, value V, expiration uint64, cost uint32) *Node[K, V] {
@@ -22,7 +33,6 @@ func New[K comparable, V any](key K, value V, expiration uint64, cost uint32) *N
 		key:        key,
 		value:      value,
 		expiration: expiration,
-		Meta:       DefaultMeta(),
 		cost:       cost,
 	}
 }
@@ -67,3 +77,47 @@ func (n *Node[K, V]) Cost() uint32 {
 func (n *Node[K, V]) SwapCost(cost uint32) (old uint32) {
 	return atomic.SwapUint32(&n.cost, cost)
 }
+
+func (n *Node[K, V]) GetFrequency() uint8 {
+	return n.frequency
+}
+
+func (n *Node[K, V]) IncrementFrequency() {
+	n.frequency = minUint8(n.frequency+1, maxFrequency)
+}
+
+func (n *Node[K, V]) DecrementFrequency() {
+	n.frequency--
+}
+
+func (n *Node[K, V]) ResetFrequency() {
+	n.frequency = 0
+}
+
+func (n *Node[K, V]) MarkSmall() {
+	n.queueType = smallQueueType
+}
+
+func (n *Node[K, V]) IsSmall() bool {
+	return n.queueType == smallQueueType
+}
+
+func (n *Node[K, V]) MarkMain() {
+	n.queueType = mainQueueType
+}
+
+func (n *Node[K, V]) IsMain() bool {
+	return n.queueType == mainQueueType
+}
+
+func (n *Node[K, V]) Unmark() {
+	n.queueType = unknownQueueType
+}
+
+func minUint8(a, b uint8) uint8 {
+	if a < b {
+		return a
+	}
+
+	return b
+}
diff --git a/internal/node/queue.go b/internal/node/queue.go
new file mode 100644
index 0000000..8d42a71
--- /dev/null
+++ b/internal/node/queue.go
@@ -0,0 +1,73 @@
+package node
+
+type Queue[K comparable, V any] struct {
+	head *Node[K, V]
+	tail *Node[K, V]
+	len  int
+}
+
+func NewQueue[K comparable, V any]() *Queue[K, V] {
+	return &Queue[K, V]{}
+}
+
+func (q *Queue[K, V]) Len() int {
+	return q.len
+}
+
+func (q *Queue[K, V]) IsEmpty() bool {
+	return q.Len() == 0
+}
+
+func (q *Queue[K, V]) Push(n *Node[K, V]) {
+	if q.IsEmpty() {
+		q.head = n
+		q.tail = n
+	} else {
+		n.prev = q.tail
+		q.tail.next = n
+		q.tail = n
+	}
+
+	q.len++
+}
+
+func (q *Queue[K, V]) Pop() *Node[K, V] {
+	if q.IsEmpty() {
+		return nil
+	}
+
+	result := q.head
+	q.Remove(result)
+	return result
+}
+
+func (q *Queue[K, V]) Remove(n *Node[K, V]) {
+	next := n.next
+	prev := n.prev
+
+	if prev == nil {
+		if next == nil && q.head != n {
+			return
+		}
+
+		q.head = next
+	} else {
+		prev.next = next
+		n.prev = nil
+	}
+
+	if next == nil {
+		q.tail = prev
+	} else {
+		next.prev = prev
+		n.next = nil
+	}
+
+	q.len--
+}
+
+func (q *Queue[K, V]) Clear() {
+	for !q.IsEmpty() {
+		q.Pop()
+	}
+}
diff --git a/internal/node/task.go b/internal/node/task.go
index 60a2337..7fae4ce 100644
--- a/internal/node/task.go
+++ b/internal/node/task.go
@@ -4,7 +4,6 @@ type reason uint8
 
 const (
 	addReason reason = iota + 1
-	evictReason
 	deleteReason
 	updateReason
 	clearReason
@@ -24,13 +23,6 @@ func NewAddTask[K comparable, V any](n *Node[K, V]) WriteTask[K, V] {
 	}
 }
 
-func NewEvictTask[K comparable, V any](n *Node[K, V]) WriteTask[K, V] {
-	return WriteTask[K, V]{
-		n:           n,
-		writeReason: evictReason,
-	}
-}
-
 func NewDeleteTask[K comparable, V any](n *Node[K, V]) WriteTask[K, V] {
 	return WriteTask[K, V]{
 		n:           n,
@@ -70,10 +62,6 @@ func (t *WriteTask[K, V]) IsAdd() bool {
 	return t.writeReason == addReason
 }
 
-func (t *WriteTask[K, V]) IsEvict() bool {
-	return t.writeReason == evictReason
-}
-
 func (t *WriteTask[K, V]) IsDelete() bool {
 	return t.writeReason == deleteReason
 }
diff --git a/internal/s3fifo/ghost.go b/internal/s3fifo/ghost.go
index 2cf5d32..7b947a2 100644
--- a/internal/s3fifo/ghost.go
+++ b/internal/s3fifo/ghost.go
@@ -16,8 +16,8 @@ type ghost[K comparable, V any] struct {
 
 func newGhost[K comparable, V any](main *main[K, V]) *ghost[K, V] {
 	return &ghost[K, V]{
-		q:    deque.New[uint64](main.q.Cap()),
-		m:    swiss.NewMap[uint64, struct{}](uint32(main.q.Cap())),
+		q:    deque.New[uint64](),
+		m:    swiss.NewMap[uint64, struct{}](64),
 		main: main,
 	}
 }
@@ -28,7 +28,6 @@ func (g *ghost[K, V]) isGhost(n *node.Node[K, V]) bool {
 }
 
 func (g *ghost[K, V]) insert(deleted []*node.Node[K, V], n *node.Node[K, V]) []*node.Node[K, V] {
-	n.Meta = n.Meta.MarkDeleted()
 	deleted = append(deleted, n)
 
 	h := n.Hash()
diff --git a/internal/s3fifo/main.go b/internal/s3fifo/main.go
index 50484a6..1e21c06 100644
--- a/internal/s3fifo/main.go
+++ b/internal/s3fifo/main.go
@@ -1,64 +1,61 @@
 package s3fifo
 
 import (
-	"github.com/gammazero/deque"
-
 	"github.com/maypok86/otter/internal/node"
 )
 
 const maxReinsertions = 20
 
 type main[K comparable, V any] struct {
-	q       *deque.Deque[*node.Node[K, V]]
+	q       *node.Queue[K, V]
 	cost    uint32
 	maxCost uint32
 }
 
 func newMain[K comparable, V any](maxCost uint32) *main[K, V] {
 	return &main[K, V]{
-		q:       deque.New[*node.Node[K, V]](),
+		q:       node.NewQueue[K, V](),
 		maxCost: maxCost,
 	}
 }
 
 func (m *main[K, V]) insert(n *node.Node[K, V]) {
-	m.q.PushBack(n)
-	n.Meta = n.Meta.MarkMain()
+	m.q.Push(n)
+	n.MarkMain()
 	m.cost += n.Cost()
 }
 
 func (m *main[K, V]) evict(deleted []*node.Node[K, V]) []*node.Node[K, V] {
 	reinsertions := 0
 	for m.cost > 0 {
-		n := m.q.PopFront()
-		if n.Meta.IsDeleted() {
-			n.Meta = n.Meta.UnmarkMain()
-			m.cost -= n.Cost()
-			return deleted
-		}
+		n := m.q.Pop()
 
-		if n.IsExpired() || n.Meta.GetFrequency() == 0 {
-			n.Meta = n.Meta.UnmarkMain().MarkDeleted()
+		if n.IsExpired() || n.GetFrequency() == 0 {
+			n.Unmark()
 			m.cost -= n.Cost()
-			// can remove
 			return append(deleted, n)
 		}
 
 		// to avoid the worst case O(n), we remove the 20th reinserted consecutive element.
 		reinsertions++
 		if reinsertions >= maxReinsertions {
-			n.Meta = n.Meta.UnmarkMain().MarkDeleted()
+			n.Unmark()
 			m.cost -= n.Cost()
-			// can remove
 			return append(deleted, n)
 		}
 
-		m.q.PushBack(n)
-		n.Meta = n.Meta.DecrementFrequency()
+		m.q.Push(n)
+		n.DecrementFrequency()
 	}
 	return deleted
 }
 
+func (m *main[K, V]) remove(n *node.Node[K, V]) {
+	m.cost -= n.Cost()
+	n.Unmark()
+	m.q.Remove(n)
+}
+
 func (m *main[K, V]) length() int {
 	return m.q.Len()
 }
diff --git a/internal/s3fifo/policy.go b/internal/s3fifo/policy.go
index 74530e6..71c06fe 100644
--- a/internal/s3fifo/policy.go
+++ b/internal/s3fifo/policy.go
@@ -30,34 +30,16 @@ func NewPolicy[K comparable, V any](maxCost uint32) *Policy[K, V] {
 	}
 }
 
-func (p *Policy[K, V]) Read(deleted, nodes []*node.Node[K, V]) []*node.Node[K, V] {
+func (p *Policy[K, V]) Read(nodes []*node.Node[K, V]) {
 	for _, n := range nodes {
-		deleted = p.read(deleted, n)
+		n.IncrementFrequency()
 	}
-	return deleted
-}
-
-func (p *Policy[K, V]) read(deleted []*node.Node[K, V], n *node.Node[K, V]) []*node.Node[K, V] {
-	if n.Meta.IsDeleted() {
-		return deleted
-	}
-
-	if n.Meta.IsSmall() || n.Meta.IsMain() {
-		n.Meta = n.Meta.IncrementFrequency()
-	} else if p.ghost.isGhost(n) {
-		deleted = p.insert(deleted, n)
-		n.Meta = n.Meta.ResetFrequency()
-	}
-	return deleted
 }
 
 func (p *Policy[K, V]) insert(deleted []*node.Node[K, V], n *node.Node[K, V]) []*node.Node[K, V] {
-	if n.Meta.IsDeleted() {
-		return deleted
-	}
-
 	if p.ghost.isGhost(n) {
 		p.main.insert(n)
+		n.ResetFrequency()
 	} else {
 		p.small.insert(n)
 	}
@@ -70,13 +52,9 @@ func (p *Policy[K, V]) insert(deleted []*node.Node[K, V], n *node.Node[K, V]) []
 }
 
 func (p *Policy[K, V]) update(deleted []*node.Node[K, V], n *node.Node[K, V], costDiff uint32) []*node.Node[K, V] {
-	if n.Meta.IsDeleted() {
-		return deleted
-	}
-
-	if n.Meta.IsSmall() {
+	if n.IsSmall() {
 		p.small.cost += costDiff
-	} else if n.Meta.IsMain() {
+	} else if n.IsMain() {
 		p.main.cost += costDiff
 	}
 
@@ -107,8 +85,8 @@ func (p *Policy[K, V]) Write(
 		n := task.GetNode()
 
 		// already deleted in map
-		if task.IsEvict() || task.IsDelete() {
-			n.Meta = n.Meta.MarkDeleted()
+		if task.IsDelete() {
+			p.delete(task.GetNode())
 			continue
 		}
 
@@ -125,7 +103,18 @@ func (p *Policy[K, V]) Write(
 
 func (p *Policy[K, V]) Delete(buffer []*node.Node[K, V]) {
 	for _, n := range buffer {
-		n.Meta = n.Meta.MarkDeleted()
+		p.delete(n)
+	}
+}
+
+func (p *Policy[K, V]) delete(n *node.Node[K, V]) {
+	if n.IsSmall() {
+		p.small.remove(n)
+		return
+	}
+
+	if n.IsMain() {
+		p.main.remove(n)
 	}
 }
 
diff --git a/internal/s3fifo/small.go b/internal/s3fifo/small.go
index 91578dd..95ca5cc 100644
--- a/internal/s3fifo/small.go
+++ b/internal/s3fifo/small.go
@@ -1,13 +1,11 @@
 package s3fifo
 
 import (
-	"github.com/gammazero/deque"
-
 	"github.com/maypok86/otter/internal/node"
 )
 
 type small[K comparable, V any] struct {
-	q       *deque.Deque[*node.Node[K, V]]
+	q       *node.Queue[K, V]
 	main    *main[K, V]
 	ghost   *ghost[K, V]
 	cost    uint32
@@ -20,7 +18,7 @@ func newSmall[K comparable, V any](
 	ghost *ghost[K, V],
 ) *small[K, V] {
 	return &small[K, V]{
-		q:       deque.New[*node.Node[K, V]](),
+		q:       node.NewQueue[K, V](),
 		main:    main,
 		ghost:   ghost,
 		maxCost: maxCost,
@@ -28,8 +26,8 @@ func newSmall[K comparable, V any](
 }
 
 func (s *small[K, V]) insert(n *node.Node[K, V]) {
-	s.q.PushBack(n)
-	n.Meta = n.Meta.MarkSmall()
+	s.q.Push(n)
+	n.MarkSmall()
 	s.cost += n.Cost()
 }
 
@@ -38,30 +36,31 @@ func (s *small[K, V]) evict(deleted []*node.Node[K, V]) []*node.Node[K, V] {
 		return deleted
 	}
 
-	n := s.q.PopFront()
+	n := s.q.Pop()
 	s.cost -= n.Cost()
-	n.Meta = n.Meta.UnmarkSmall()
-	if n.Meta.IsDeleted() {
-		return deleted
-	}
+	n.Unmark()
 	if n.IsExpired() {
-		n.Meta = n.Meta.MarkDeleted()
-		// can remove
 		return append(deleted, n)
 	}
 
-	if n.Meta.GetFrequency() > 1 {
+	if n.GetFrequency() > 1 {
 		s.main.insert(n)
 		for s.main.isFull() {
 			deleted = s.main.evict(deleted)
 		}
-		n.Meta = n.Meta.ResetFrequency()
+		n.ResetFrequency()
 		return deleted
 	}
 
 	return s.ghost.insert(deleted, n)
 }
 
+func (s *small[K, V]) remove(n *node.Node[K, V]) {
+	s.cost -= n.Cost()
+	n.Unmark()
+	s.q.Remove(n)
+}
+
 func (s *small[K, V]) length() int {
 	return s.q.Len()
 }


Test patch:
diff --git a/internal/node/queue_test.go b/internal/node/queue_test.go
new file mode 100644
index 0000000..b7f1fdd
--- /dev/null
+++ b/internal/node/queue_test.go
@@ -0,0 +1,139 @@
+// Copyright notice. Initial version of the following tests was based on
+// the following file from the Go Programming Language core repo:
+// https://cs.opensource.google/go/go/+/refs/tags/go1.21.5:src/container/list/list_test.go
+package node
+
+import (
+	"strconv"
+	"testing"
+)
+
+func checkQueueLen[K comparable, V any](t *testing.T, q *Queue[K, V], length int) bool {
+	t.Helper()
+
+	if n := q.Len(); n != length {
+		t.Errorf("q.Len() = %d, want %d", n, length)
+		return false
+	}
+	return true
+}
+
+func checkQueuePointers[K comparable, V any](t *testing.T, q *Queue[K, V], nodes []*Node[K, V]) {
+	t.Helper()
+
+	if !checkQueueLen(t, q, len(nodes)) {
+		return
+	}
+
+	// zero length queues must be the zero value
+	if len(nodes) == 0 {
+		if !(q.head == nil && q.tail == nil) {
+			t.Errorf("q.head = %p, q.tail = %p; both should be nil", q.head, q.tail)
+		}
+		return
+	}
+
+	// check internal and external prev/next connections
+	for i, n := range nodes {
+		prev := (*Node[K, V])(nil)
+		if i > 0 {
+			prev = nodes[i-1]
+		}
+		if p := n.prev; p != prev {
+			t.Errorf("elt[%d](%p).prev = %p, want %p", i, n, p, prev)
+		}
+
+		next := (*Node[K, V])(nil)
+		if i < len(nodes)-1 {
+			next = nodes[i+1]
+		}
+		if nn := n.next; nn != next {
+			t.Errorf("nodes[%d](%p).next = %p, want %p", i, n, nn, next)
+		}
+	}
+}
+
+func newFakeNode[K comparable](e K) *Node[K, K] {
+	return New(e, e, 0, 0)
+}
+
+func TestQueue(t *testing.T) {
+	q := NewQueue[string, string]()
+	checkQueuePointers(t, q, []*Node[string, string]{})
+
+	// Single element queue
+	e := newFakeNode("a")
+	q.Push(e)
+	checkQueuePointers(t, q, []*Node[string, string]{e})
+	q.Remove(e)
+	q.Push(e)
+	checkQueuePointers(t, q, []*Node[string, string]{e})
+	q.Remove(e)
+	checkQueuePointers(t, q, []*Node[string, string]{})
+
+	// Bigger queue
+	e2 := newFakeNode("2")
+	e1 := newFakeNode("1")
+	e3 := newFakeNode("3")
+	e4 := newFakeNode("4")
+	q.Push(e1)
+	q.Push(e2)
+	q.Push(e3)
+	q.Push(e4)
+	checkQueuePointers(t, q, []*Node[string, string]{e1, e2, e3, e4})
+
+	q.Remove(e2)
+	checkQueuePointers(t, q, []*Node[string, string]{e1, e3, e4})
+
+	// move from middle
+	q.Remove(e3)
+	q.Push(e3)
+	checkQueuePointers(t, q, []*Node[string, string]{e1, e4, e3})
+
+	q.Clear()
+	q.Push(e3)
+	q.Push(e1)
+	q.Push(e4)
+	checkQueuePointers(t, q, []*Node[string, string]{e3, e1, e4})
+
+	// should be no-op
+	q.Remove(e3)
+	q.Push(e3)
+	checkQueuePointers(t, q, []*Node[string, string]{e1, e4, e3})
+
+	// Check standard iteration.
+	sum := 0
+	for e := q.head; e != nil; e = e.next {
+		i, err := strconv.Atoi(e.value)
+		if err != nil {
+			continue
+		}
+		sum += i
+	}
+	if sum != 8 {
+		t.Errorf("sum over l = %d, want 8", sum)
+	}
+
+	// Clear all elements by iterating
+	var next *Node[string, string]
+	for e := q.head; e != nil; e = next {
+		next = e.next
+		q.Remove(e)
+	}
+	checkQueuePointers(t, q, []*Node[string, string]{})
+}
+
+func TestQueue_Remove(t *testing.T) {
+	q := NewQueue[int, int]()
+
+	e1 := newFakeNode(1)
+	e2 := newFakeNode(2)
+	q.Push(e1)
+	q.Push(e2)
+	checkQueuePointers(t, q, []*Node[int, int]{e1, e2})
+	e := q.head
+	q.Remove(e)
+	checkQueuePointers(t, q, []*Node[int, int]{e2})
+	q.Remove(e)
+	checkQueuePointers(t, q, []*Node[int, int]{e2})
+}