1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
// Copyright (C) 2023 Luke Shumaker <lukeshu@lukeshu.com>
//
// SPDX-License-Identifier: GPL-2.0-or-later
package caching
import (
"fmt"
)
// LinkedListEntry [T] is an entry in a LinkedList [T].
type LinkedListEntry[T any] struct {
list *LinkedList[T]
older, newer *LinkedListEntry[T]
Value T
}
func (entry *LinkedListEntry[T]) Older() *LinkedListEntry[T] { return entry.older }
func (entry *LinkedListEntry[T]) Newer() *LinkedListEntry[T] { return entry.newer }
// LinkedList is a doubly-linked list.
//
// Rather than "head/tail", "front/back", or "next/prev", it has
// "oldest" and "newest". This is for to make code using it clearer;
// as the motivation for the LinkedList is as an implementation detail
// in LRU caches and FIFO queues, where this temporal naming is
// meaningful. Similarly, it does not implement many common features
// of a linked-list, because these applications do not need such
// features.
//
// Compared to `containers/list.List`, LinkedList has the
// disadvantages that it has fewer safety checks and fewer features in
// general.
type LinkedList[T any] struct {
oldest, newest *LinkedListEntry[T]
}
// IsEmpty returns whether the list empty or not.
func (l *LinkedList[T]) IsEmpty() bool {
return l.oldest == nil
}
// Delete removes an entry from the list. The entry is invalid once
// Delete returns, and should not be reused or have its .Value
// accessed.
//
// It is invalid (runtime-panic) to call Delete on a nil entry.
//
// It is invalid (runtime-panic) to call Delete on an entry that
// isn't in the list.
func (l *LinkedList[T]) Delete(entry *LinkedListEntry[T]) {
if entry.list != l {
panic(fmt.Errorf("LinkedList.Delete: entry %p not in list", entry))
}
if entry.newer == nil {
l.newest = entry.older
} else {
entry.newer.older = entry.older
}
if entry.older == nil {
l.oldest = entry.newer
} else {
entry.older.newer = entry.newer
}
// no memory leaks
entry.list = nil
entry.older = nil
entry.newer = nil
}
// Store appends a value to the "newest" end of the list, returning
// the created entry.
//
// It is invalid (runtime-panic) to call Store on a nil entry.
//
// It is invalid (runtime-panic) to call Store on an entry that is
// already in a list.
func (l *LinkedList[T]) Store(entry *LinkedListEntry[T]) {
if entry.list != nil {
panic(fmt.Errorf("LinkedList.Store: entry %p is already in a list", entry))
}
entry.list = l
entry.older = l.newest
l.newest = entry
if entry.older == nil {
l.oldest = entry
} else {
entry.older.newer = entry
}
}
// MoveToNewest moves an entry fron any position in the list to the
// "newest" end of the list. If the entry is already in the "newest"
// position, then MoveToNewest is a no-op.
//
// It is invalid (runtime-panic) to call MoveToNewest on a nil entry.
//
// It is invalid (runtime-panic) to call MoveToNewest on an entry that
// isn't in the list.
func (l *LinkedList[T]) MoveToNewest(entry *LinkedListEntry[T]) {
if entry.list != l {
panic(fmt.Errorf("LinkedList.MoveToNewest: entry %p not in list", entry))
}
if entry.newer == nil {
// Already newest.
return
}
entry.newer.older = entry.older
if entry.older == nil {
l.oldest = entry.newer
} else {
entry.older.newer = entry.newer
}
entry.older = l.newest
l.newest.newer = entry
entry.newer = nil
l.newest = entry
}
// Oldest returns the entry at the "oldest" end of the list, or nil if
// the list is empty.
func (l *LinkedList[T]) Oldest() *LinkedListEntry[T] {
return l.oldest
}
|
