mirror of
https://github.com/photoprism/photoprism.git
synced 2026-01-23 10:26:03 +00:00
106 lines
3.1 KiB
Go
106 lines
3.1 KiB
Go
package ordered
|
|
|
|
// Element represents a node in the intrusive doubly linked list that backs
|
|
// Map. Every element knows its key and value so the map can mutate values
|
|
// without rebuilding the list.
|
|
type Element[K comparable, V any] struct {
|
|
// Next and previous pointers in the doubly-linked list of elements.
|
|
// To simplify the implementation, internally a list l is implemented
|
|
// as a ring, such that &l.root is both the next element of the last
|
|
// list element (l.Back()) and the previous element of the first list
|
|
// element (l.Front()).
|
|
next, prev *Element[K, V]
|
|
|
|
// The key that corresponds to this element in the ordered map.
|
|
Key K
|
|
|
|
// The value stored with this element.
|
|
Value V
|
|
}
|
|
|
|
// Next returns the next list element or nil.
|
|
func (e *Element[K, V]) Next() *Element[K, V] {
|
|
return e.next
|
|
}
|
|
|
|
// Prev returns the previous list element or nil.
|
|
func (e *Element[K, V]) Prev() *Element[K, V] {
|
|
return e.prev
|
|
}
|
|
|
|
// list is a minimal intrusive doubly linked list implementation used to keep
|
|
// insertion order for Map. It is intentionally null terminated (non-circular)
|
|
// so checks such as "el == nil" read naturally when iterating, and the zero
|
|
// value is ready for use because the root sentinel starts empty.
|
|
type list[K comparable, V any] struct {
|
|
root Element[K, V] // list head and tail
|
|
}
|
|
|
|
// IsEmpty reports whether the list currently contains no elements.
|
|
func (l *list[K, V]) IsEmpty() bool {
|
|
return l.root.next == nil
|
|
}
|
|
|
|
// Front returns the first element of list l or nil if the list is empty.
|
|
func (l *list[K, V]) Front() *Element[K, V] {
|
|
return l.root.next
|
|
}
|
|
|
|
// Back returns the last element of list l or nil if the list is empty.
|
|
func (l *list[K, V]) Back() *Element[K, V] {
|
|
return l.root.prev
|
|
}
|
|
|
|
// Remove detaches e from the list while keeping the remaining neighbors
|
|
// correctly linked. After removal the element's next/prev references are
|
|
// zeroed so the node can be safely re-used or left for GC without retaining
|
|
// other elements.
|
|
func (l *list[K, V]) Remove(e *Element[K, V]) {
|
|
if e.prev == nil {
|
|
l.root.next = e.next
|
|
} else {
|
|
e.prev.next = e.next
|
|
}
|
|
if e.next == nil {
|
|
l.root.prev = e.prev
|
|
} else {
|
|
e.next.prev = e.prev
|
|
}
|
|
e.next = nil // avoid memory leaks
|
|
e.prev = nil // avoid memory leaks
|
|
}
|
|
|
|
// PushFront inserts a new element with the given key/value at the head of the
|
|
// list and returns the created element. The first insertion also updates the
|
|
// tail pointer because the list was empty before.
|
|
func (l *list[K, V]) PushFront(key K, value V) *Element[K, V] {
|
|
e := &Element[K, V]{Key: key, Value: value}
|
|
if l.root.next == nil {
|
|
// It's the first element
|
|
l.root.next = e
|
|
l.root.prev = e
|
|
return e
|
|
}
|
|
|
|
e.next = l.root.next
|
|
l.root.next.prev = e
|
|
l.root.next = e
|
|
return e
|
|
}
|
|
|
|
// PushBack appends a new element to the tail of the list and returns it. When
|
|
// called on an empty list the element becomes both head and tail.
|
|
func (l *list[K, V]) PushBack(key K, value V) *Element[K, V] {
|
|
e := &Element[K, V]{Key: key, Value: value}
|
|
if l.root.prev == nil {
|
|
// It's the first element
|
|
l.root.next = e
|
|
l.root.prev = e
|
|
return e
|
|
}
|
|
|
|
e.prev = l.root.prev
|
|
l.root.prev.next = e
|
|
l.root.prev = e
|
|
return e
|
|
}
|