list.go

     1  // Copyright 2025 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 runtime
     6  
     7  import (
     8  	"unsafe"
     9  )
    10  
    11  // listHead points to the head of an intrusive doubly-linked list.
    12  //
    13  // Prior to use, you must call init to store the offset of listNode fields.
    14  //
    15  // Every object in the list should be the same type.
    16  type listHead struct {
    17  	obj unsafe.Pointer
    18  
    19  	initialized bool
    20  	nodeOffset  uintptr
    21  }
    22  
    23  // init initializes the list head. off is the offset (via unsafe.Offsetof) of
    24  // the listNode field in the objects in the list.
    25  func (head *listHead) init(off uintptr) {
    26  	head.initialized = true
    27  	head.nodeOffset = off
    28  }
    29  
    30  // listNode is the linked list node for objects in a listHead list.
    31  //
    32  // listNode must be stored as a field in objects placed in the linked list. The
    33  // offset of the field is registered via listHead.init.
    34  //
    35  // For example:
    36  //
    37  // type foo struct {
    38  // 	val int
    39  //
    40  // 	node listNode
    41  // }
    42  //
    43  // var fooHead listHead
    44  // fooHead.init(unsafe.Offsetof(foo{}.node))
    45  type listNode struct {
    46  	prev unsafe.Pointer
    47  	next unsafe.Pointer
    48  }
    49  
    50  func (head *listHead) getNode(p unsafe.Pointer) *listNode {
    51  	if !head.initialized {
    52  		throw("runtime: uninitialized listHead")
    53  	}
    54  
    55  	if p == nil {
    56  		return nil
    57  	}
    58  	return (*listNode)(unsafe.Add(p, head.nodeOffset))
    59  }
    60  
    61  // Returns true if the list is empty.
    62  func (head *listHead) empty() bool {
    63  	return head.obj == nil
    64  }
    65  
    66  // Returns the head of the list without removing it.
    67  func (head *listHead) head() unsafe.Pointer {
    68  	return head.obj
    69  }
    70  
    71  // Push p onto the front of the list.
    72  func (head *listHead) push(p unsafe.Pointer) {
    73  	// p becomes the head of the list.
    74  
    75  	// ... so p's next is the current head.
    76  	pNode := head.getNode(p)
    77  	pNode.next = head.obj
    78  
    79  	// ... and the current head's prev is p.
    80  	if head.obj != nil {
    81  		headNode := head.getNode(head.obj)
    82  		headNode.prev = p
    83  	}
    84  
    85  	head.obj = p
    86  }
    87  
    88  // Pop removes the head of the list.
    89  func (head *listHead) pop() unsafe.Pointer {
    90  	if head.obj == nil {
    91  		return nil
    92  	}
    93  
    94  	// Return the head of the list.
    95  	p := head.obj
    96  
    97  	// ... so the new head is p's next.
    98  	pNode := head.getNode(p)
    99  	head.obj = pNode.next
   100  	// p is no longer on the list. Clear next to remove unused references.
   101  	// N.B. as the head, prev must already be nil.
   102  	pNode.next = nil
   103  
   104  	// ... and the new head no longer has a prev.
   105  	if head.obj != nil {
   106  		headNode := head.getNode(head.obj)
   107  		headNode.prev = nil
   108  	}
   109  
   110  	return p
   111  }
   112  
   113  // Remove p from the middle of the list.
   114  func (head *listHead) remove(p unsafe.Pointer) {
   115  	if head.obj == p {
   116  		// Use pop to ensure head is updated when removing the head.
   117  		head.pop()
   118  		return
   119  	}
   120  
   121  	pNode := head.getNode(p)
   122  	prevNode := head.getNode(pNode.prev)
   123  	nextNode := head.getNode(pNode.next)
   124  
   125  	// Link prev to next.
   126  	if prevNode != nil {
   127  		prevNode.next = pNode.next
   128  	}
   129  	// Link next to prev.
   130  	if nextNode != nil {
   131  		nextNode.prev = pNode.prev
   132  	}
   133  
   134  	pNode.prev = nil
   135  	pNode.next = nil
   136  }
   137
View as plain text