139 lines
4 KiB
Odin
139 lines
4 KiB
Odin
package list
|
|
|
|
IntrusiveList :: struct {
|
|
head: ^IntrusiveListNode
|
|
}
|
|
|
|
IntrusiveListNode :: struct {
|
|
prev, next: ^IntrusiveListNode
|
|
}
|
|
|
|
IntrusiveListIterator :: struct($T: typeid) {
|
|
curr: ^IntrusiveListNode,
|
|
offset: uintptr,
|
|
}
|
|
|
|
intrusive_list_push_front :: proc "contextless" (list: ^IntrusiveList, node: ^IntrusiveListNode) {
|
|
if list.head == nil {
|
|
list.head = node
|
|
node.next, node.prev = node, node
|
|
} else {
|
|
tail := list.head.prev
|
|
list.head.prev = node
|
|
tail.next = node
|
|
node.next, node.prev = list.head, tail
|
|
list.head = node
|
|
}
|
|
}
|
|
|
|
intrusive_list_push_back :: proc (list: ^IntrusiveList, node: ^IntrusiveListNode) {
|
|
if list.head == nil {
|
|
list.head = node
|
|
node.next, node.prev = node, node
|
|
} else {
|
|
node.next, node.prev = list.head, list.head.prev
|
|
list.head.prev.next = node
|
|
list.head.prev = node
|
|
}
|
|
}
|
|
|
|
intrusive_list_pop_front :: proc "contextless" (list: ^IntrusiveList) -> ^IntrusiveListNode {
|
|
head := list.head
|
|
if head == nil {
|
|
return head
|
|
} else if intrusive_list_node_is_only(list^, head) {
|
|
list.head = nil
|
|
return head
|
|
}
|
|
head.prev.next = head.next
|
|
head.next.prev = head.prev
|
|
list.head = head.next
|
|
return head
|
|
}
|
|
|
|
intrusive_list_pop_back :: proc "contextless" (list: ^IntrusiveList) -> ^IntrusiveListNode {
|
|
head := list.head
|
|
if head == nil {
|
|
return nil
|
|
}
|
|
if intrusive_list_node_is_only(list^, head) {
|
|
list.head = nil
|
|
return head
|
|
}
|
|
tail := list.head.prev
|
|
tail.prev.next = tail.next
|
|
tail.next.prev = tail.prev
|
|
return tail
|
|
}
|
|
|
|
intrusive_list_node_is_only :: proc "contextless" (list: IntrusiveList, node: ^IntrusiveListNode) -> bool {
|
|
return node == list.head && node == node.next && node == node.prev
|
|
}
|
|
|
|
intrusive_list_remove :: proc "contextless" (list: ^IntrusiveList, node: ^IntrusiveListNode) {
|
|
if intrusive_list_node_is_only(list^, node) {
|
|
list.head = nil
|
|
} else {
|
|
prev := node.prev
|
|
next := node.next
|
|
prev.next = next
|
|
next.prev = prev
|
|
}
|
|
}
|
|
|
|
intrusive_list_get_next :: proc "contextless" (node: ^IntrusiveListNode, $T: typeid, $field_name: string) -> ^T
|
|
where intrinsics.type_has_field(T, field_name),
|
|
intrinsics.type_field_type(T, field_name) == IntrusiveListNode {
|
|
return (^T)(uintptr(node.next) - offset_of_by_string(T, field_name))
|
|
}
|
|
|
|
intrusive_list_get_previous :: proc "contextless" (node: ^IntrusiveListNode, $T: typeid, $field_name: string) -> ^T
|
|
where intrinsics.type_has_field(T, field_name),
|
|
intrinsics.type_field_type(T, field_name) == IntrusiveListNode {
|
|
return (^T)(uintptr(node.prev) - offset_of_by_string(T, field_name))
|
|
}
|
|
|
|
intrusive_list_get_relative :: proc "contextless" (node: ^IntrusiveListNode, $T: typeid, $field_name: string, pos: int) -> ^T {
|
|
it := intrusive_list_iterator_from_node(node, T, field_name)
|
|
switch math.sign(pos) {
|
|
case 0:
|
|
return (^T)(uintptr(it.curr) - it.offset)
|
|
case 1:
|
|
node: ^T
|
|
for i in 0..<pos {
|
|
node = intrusive_list_iterate_next(&it)
|
|
}
|
|
return node
|
|
}
|
|
node: ^T
|
|
for i in 0..<abs(pos) {
|
|
node = intrusive_list_iterate_prev(&it)
|
|
}
|
|
return node
|
|
}
|
|
|
|
intrusive_list_is_empty :: proc "contextless" (list: IntrusiveList) -> bool {
|
|
return list.head == nil
|
|
}
|
|
|
|
intrusive_list_iterator_head :: proc "contextless" (list: IntrusiveList, $T: typeid, $field_name: string) -> IntrusiveListIterator(T)
|
|
where intrinsics.type_has_field(T, field_name),
|
|
intrinsics.type_field_type(T, field_name) == IntrusiveListNode {
|
|
return {list.head, offset_of_by_string(T, field_name)}
|
|
}
|
|
|
|
intrusive_list_iterator_from_node :: proc "contextless" (node: ^IntrusiveListNode, $T: typeid, $field_name: string) -> IntrusiveListIterator(T)
|
|
where intrinsics.type_has_field(T, field_name),
|
|
intrinsics.type_field_type(T, field_name) == IntrusiveListNode {
|
|
return {node, offset_of_by_string(T, field_name)}
|
|
}
|
|
|
|
intrusive_list_iterate_next :: proc "contextless" (it: ^IntrusiveListIterator($T)) -> ^T {
|
|
it.curr = it.curr.next
|
|
return (^T)(uintptr(it.curr) - it.offset)
|
|
}
|
|
|
|
intrusive_list_iterate_prev :: proc "contextless" (it: ^IntrusiveListIterator($T)) -> ^T {
|
|
it.curr = it.curr.prev
|
|
return (^T)(uintptr(it.curr) - it.offset)
|
|
}
|