intrusive_list.go

     1  // Copyright 2026 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package http
     6  
     7  import "iter"
     8  
     9  // intrusiveList is an intrusive doubly-linked list.
    10  //
    11  // The list is circular: head.prev is the tail of the list.
    12  //
    13  // The list's link function must be initialized to a function which returns the
    14  // intrusiveLink structure for a list element. Elements may be a part of any number
    15  // of lists at the same time, so long as they use separate links for each list.
    16  type intrusiveList[T any] struct {
    17  	head *T
    18  	size int
    19  	link func(*T) *intrusiveLink[T]
    20  }
    21  
    22  type intrusiveLink[T any] struct {
    23  	prev, next *T
    24  }
    25  
    26  func (list *intrusiveList[T]) pushBack(e *T) {
    27  	el := list.link(e)
    28  	if el.next != nil {
    29  		panic("element already in list")
    30  	}
    31  	list.size++
    32  	if list.head == nil {
    33  		list.head = e
    34  		el.next = e
    35  		el.prev = e
    36  		return
    37  	}
    38  	headl := list.link(list.head)
    39  	tail := headl.prev
    40  	el.next = list.head
    41  	el.prev = tail
    42  	list.link(tail).next = e
    43  	headl.prev = e
    44  }
    45  
    46  func (list *intrusiveList[T]) remove(e *T) {
    47  	el := list.link(e)
    48  	if el.next == nil {
    49  		return // not in the list
    50  	}
    51  	if el.next == e {
    52  		list.head = nil // only element in the list
    53  	} else {
    54  		if list.head == e {
    55  			list.head = el.next
    56  		}
    57  		list.link(el.prev).next = el.next
    58  		list.link(el.next).prev = el.prev
    59  	}
    60  	el.next = nil
    61  	el.prev = nil
    62  	list.size--
    63  }
    64  
    65  func (list *intrusiveList[T]) all() iter.Seq[*T] {
    66  	return func(yield func(*T) bool) {
    67  		e := list.head
    68  		if e == nil {
    69  			return
    70  		}
    71  		for {
    72  			next := list.link(e).next
    73  			last := next == list.head
    74  			if !yield(e) || last {
    75  				return
    76  			}
    77  			e = next
    78  		}
    79  	}
    80  }
    81  
    82  func (list *intrusiveList[T]) contains(e *T) bool {
    83  	return list.link(e).next != nil
    84  }
    85
View as plain text