pkg/list/ordered/list.go - develop - githubmirror/photoprism

pkg/list/ordered/list.go
106 строк3 KB
Michael Mayer
CI: Apply Go linter recommendations to remaining "pkg/..." code #5330
22 ноя 2025, 18:14
22 ноя 2025, 18:14149f5e5
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
}