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

View as plain text