1// This file was automatically generated by genny. 2// Any changes will be lost if this file is regenerated. 3// see https://github.com/cheekybits/genny 4 5package ackhandler 6 7// Linked list implementation from the Go standard library. 8 9// PacketElement is an element of a linked list. 10type PacketElement struct { 11 // Next and previous pointers in the doubly-linked list of elements. 12 // To simplify the implementation, internally a list l is implemented 13 // as a ring, such that &l.root is both the next element of the last 14 // list element (l.Back()) and the previous element of the first list 15 // element (l.Front()). 16 next, prev *PacketElement 17 18 // The list to which this element belongs. 19 list *PacketList 20 21 // The value stored with this element. 22 Value Packet 23} 24 25// Next returns the next list element or nil. 26func (e *PacketElement) Next() *PacketElement { 27 if p := e.next; e.list != nil && p != &e.list.root { 28 return p 29 } 30 return nil 31} 32 33// Prev returns the previous list element or nil. 34func (e *PacketElement) Prev() *PacketElement { 35 if p := e.prev; e.list != nil && p != &e.list.root { 36 return p 37 } 38 return nil 39} 40 41// PacketList is a linked list of Packets. 42type PacketList struct { 43 root PacketElement // sentinel list element, only &root, root.prev, and root.next are used 44 len int // current list length excluding (this) sentinel element 45} 46 47// Init initializes or clears list l. 48func (l *PacketList) Init() *PacketList { 49 l.root.next = &l.root 50 l.root.prev = &l.root 51 l.len = 0 52 return l 53} 54 55// NewPacketList returns an initialized list. 56func NewPacketList() *PacketList { return new(PacketList).Init() } 57 58// Len returns the number of elements of list l. 59// The complexity is O(1). 60func (l *PacketList) Len() int { return l.len } 61 62// Front returns the first element of list l or nil if the list is empty. 63func (l *PacketList) Front() *PacketElement { 64 if l.len == 0 { 65 return nil 66 } 67 return l.root.next 68} 69 70// Back returns the last element of list l or nil if the list is empty. 71func (l *PacketList) Back() *PacketElement { 72 if l.len == 0 { 73 return nil 74 } 75 return l.root.prev 76} 77 78// lazyInit lazily initializes a zero List value. 79func (l *PacketList) lazyInit() { 80 if l.root.next == nil { 81 l.Init() 82 } 83} 84 85// insert inserts e after at, increments l.len, and returns e. 86func (l *PacketList) insert(e, at *PacketElement) *PacketElement { 87 n := at.next 88 at.next = e 89 e.prev = at 90 e.next = n 91 n.prev = e 92 e.list = l 93 l.len++ 94 return e 95} 96 97// insertValue is a convenience wrapper for insert(&Element{Value: v}, at). 98func (l *PacketList) insertValue(v Packet, at *PacketElement) *PacketElement { 99 return l.insert(&PacketElement{Value: v}, at) 100} 101 102// remove removes e from its list, decrements l.len, and returns e. 103func (l *PacketList) remove(e *PacketElement) *PacketElement { 104 e.prev.next = e.next 105 e.next.prev = e.prev 106 e.next = nil // avoid memory leaks 107 e.prev = nil // avoid memory leaks 108 e.list = nil 109 l.len-- 110 return e 111} 112 113// Remove removes e from l if e is an element of list l. 114// It returns the element value e.Value. 115// The element must not be nil. 116func (l *PacketList) Remove(e *PacketElement) Packet { 117 if e.list == l { 118 // if e.list == l, l must have been initialized when e was inserted 119 // in l or l == nil (e is a zero Element) and l.remove will crash 120 l.remove(e) 121 } 122 return e.Value 123} 124 125// PushFront inserts a new element e with value v at the front of list l and returns e. 126func (l *PacketList) PushFront(v Packet) *PacketElement { 127 l.lazyInit() 128 return l.insertValue(v, &l.root) 129} 130 131// PushBack inserts a new element e with value v at the back of list l and returns e. 132func (l *PacketList) PushBack(v Packet) *PacketElement { 133 l.lazyInit() 134 return l.insertValue(v, l.root.prev) 135} 136 137// InsertBefore inserts a new element e with value v immediately before mark and returns e. 138// If mark is not an element of l, the list is not modified. 139// The mark must not be nil. 140func (l *PacketList) InsertBefore(v Packet, mark *PacketElement) *PacketElement { 141 if mark.list != l { 142 return nil 143 } 144 // see comment in List.Remove about initialization of l 145 return l.insertValue(v, mark.prev) 146} 147 148// InsertAfter inserts a new element e with value v immediately after mark and returns e. 149// If mark is not an element of l, the list is not modified. 150// The mark must not be nil. 151func (l *PacketList) InsertAfter(v Packet, mark *PacketElement) *PacketElement { 152 if mark.list != l { 153 return nil 154 } 155 // see comment in List.Remove about initialization of l 156 return l.insertValue(v, mark) 157} 158 159// MoveToFront moves element e to the front of list l. 160// If e is not an element of l, the list is not modified. 161// The element must not be nil. 162func (l *PacketList) MoveToFront(e *PacketElement) { 163 if e.list != l || l.root.next == e { 164 return 165 } 166 // see comment in List.Remove about initialization of l 167 l.insert(l.remove(e), &l.root) 168} 169 170// MoveToBack moves element e to the back of list l. 171// If e is not an element of l, the list is not modified. 172// The element must not be nil. 173func (l *PacketList) MoveToBack(e *PacketElement) { 174 if e.list != l || l.root.prev == e { 175 return 176 } 177 // see comment in List.Remove about initialization of l 178 l.insert(l.remove(e), l.root.prev) 179} 180 181// MoveBefore moves element e to its new position before mark. 182// If e or mark is not an element of l, or e == mark, the list is not modified. 183// The element and mark must not be nil. 184func (l *PacketList) MoveBefore(e, mark *PacketElement) { 185 if e.list != l || e == mark || mark.list != l { 186 return 187 } 188 l.insert(l.remove(e), mark.prev) 189} 190 191// MoveAfter moves element e to its new position after mark. 192// If e or mark is not an element of l, or e == mark, the list is not modified. 193// The element and mark must not be nil. 194func (l *PacketList) MoveAfter(e, mark *PacketElement) { 195 if e.list != l || e == mark || mark.list != l { 196 return 197 } 198 l.insert(l.remove(e), mark) 199} 200 201// PushBackList inserts a copy of an other list at the back of list l. 202// The lists l and other may be the same. They must not be nil. 203func (l *PacketList) PushBackList(other *PacketList) { 204 l.lazyInit() 205 for i, e := other.Len(), other.Front(); i > 0; i, e = i-1, e.Next() { 206 l.insertValue(e.Value, l.root.prev) 207 } 208} 209 210// PushFrontList inserts a copy of an other list at the front of list l. 211// The lists l and other may be the same. They must not be nil. 212func (l *PacketList) PushFrontList(other *PacketList) { 213 l.lazyInit() 214 for i, e := other.Len(), other.Back(); i > 0; i, e = i-1, e.Prev() { 215 l.insertValue(e.Value, &l.root) 216 } 217} 218