merge from upstream and convert to ^File types

3 files changed, 197 insertions, 15 deletions

diff --git a/core/container/intrusive/list/intrusive_list.odin b/core/container/intrusive/list/intrusive_list.odin
new file mode 100644
index 000000000..88e21edc5
--- /dev/null
+++ b/core/container/intrusive/list/intrusive_list.odin
@@ -0,0 +1,173 @@
+package container_intrusive_list
+
+import "core:intrinsics"
+
+// An intrusive doubly-linked list
+//
+// As this is an intrusive container, a `Node` must be embedded in your own
+// structure which is conventionally called a "link". The use of `push_front`
+// and `push_back` take the address of this node. Retrieving the data
+// associated with the node requires finding the relative offset of the node
+// of the parent structure. The parent type and field name are given to
+// `iterator_*` procedures, or to the built-in `container_of` procedure.
+//
+// This data structure is two-pointers in size:
+// 	8 bytes on 32-bit platforms and 16 bytes on 64-bit platforms
+List :: struct {
+	head: ^Node,
+	tail: ^Node,
+}
+
+
+Node :: struct {
+	next, prev: ^Node,
+}
+
+push_front :: proc(list: ^List, node: ^Node) {
+	if list.head != nil {
+		list.head.prev = node
+		node.prev, node.next = nil, list.head
+		list.head = node
+	} else {
+		list.head, list.tail = node, node
+		node.prev, node.next = nil, nil
+	}
+}
+
+push_back :: proc(list: ^List, node: ^Node) {
+	if list.tail != nil {
+		list.tail.next = node
+		node.prev, node.next = list.tail, nil
+		list.tail = node
+	} else {
+		list.head, list.tail = node, node
+		node.prev, node.next = nil, nil
+	}
+}
+
+remove :: proc(list: ^List, node: ^Node) {
+	if node != nil {
+		if node.next != nil {
+			node.next.prev = node.prev
+		}
+		if node.prev != nil {
+			node.prev.next = node.next
+		}
+		if list.head == node {
+			list.head = node.next
+		}
+		if list.tail == node {
+			list.tail = node.prev
+		}
+	}
+}
+
+remove_by_proc :: proc(list: ^List, to_erase: proc(^Node) -> bool) {
+	for node := list.head; node != nil; {
+		next := node.next
+		if to_erase(node) {
+			if node.next != nil {
+				node.next.prev = node.prev
+			}
+			if node.prev != nil {
+				node.prev.next = node.next
+			}
+			if list.head == node {
+				list.head = node.next
+			}
+			if list.tail == node {
+				list.tail = node.prev
+			}
+		}
+		node = next
+	}
+}
+
+
+is_empty :: proc(list: ^List) -> bool {
+	return list.head == nil
+}
+
+pop_front :: proc(list: ^List) -> ^Node {
+	link := list.head
+	if link == nil {
+		return nil
+	}
+	if link.next != nil {
+		link.next.prev = link.prev
+	}
+	if link.prev != nil {
+		link.prev.next = link.next
+	}
+	if link == list.head {
+		list.head = link.next
+	}
+	if link == list.tail {
+		list.tail = link.prev
+	}
+	return link
+
+}
+pop_back :: proc(list: ^List) -> ^Node {
+	link := list.tail
+	if link == nil {
+		return nil
+	}
+	if link.next != nil {
+		link.next.prev = link.prev
+	}
+	if link.prev != nil {
+		link.prev.next = link.next
+	}
+	if link == list.head {
+		list.head = link.next
+	}
+	if link == list.tail {
+		list.tail = link.prev
+	}
+	return link
+}
+
+
+Iterator :: struct($T: typeid) {
+	curr:   ^Node,
+	offset: uintptr,
+}
+
+iterator_head :: proc(list: List, $T: typeid, $field_name: string) -> Iterator(T)
+	where intrinsics.type_has_field(T, field_name),
+	      intrinsics.type_field_type(T, field_name) == Node {
+	return {list.head, offset_of_by_string(T, field_name)}
+}
+
+iterator_tail :: proc(list: List, $T: typeid, $field_name: string) -> Iterator(T)
+	where intrinsics.type_has_field(T, field_name),
+	      intrinsics.type_field_type(T, field_name) == Node {
+	return {list.tail, offset_of_by_string(T, field_name)}
+}
+
+iterator_from_node :: proc(node: ^Node, $T: typeid, $field_name: string) -> Iterator(T)
+	where intrinsics.type_has_field(T, field_name),
+	      intrinsics.type_field_type(T, field_name) == Node {
+	return {node, offset_of_by_string(T, field_name)}
+}
+
+iterate_next :: proc(it: ^Iterator($T)) -> (ptr: ^T, ok: bool) {
+	node := it.curr
+	if node == nil {
+		return nil, false
+	}
+	it.curr = node.next
+
+	return (^T)(uintptr(node) - it.offset), true
+}
+
+iterate_prev :: proc(it: ^Iterator($T)) -> (ptr: ^T, ok: bool) {
+	node := it.curr
+	if node == nil {
+		return nil, false
+	}
+	it.curr = node.prev
+
+	return (^T)(uintptr(node) - it.offset), true
+}
\ No newline at end of file
diff --git a/core/container/lru/lru_cache.odin b/core/container/lru/lru_cache.odin
index f8e6f7b46..b59f29f0c 100644
--- a/core/container/lru/lru_cache.odin
+++ b/core/container/lru/lru_cache.odin
@@ -60,19 +60,27 @@ clear :: proc(c: ^$C/Cache($Key, $Value), call_on_remove: bool) {
 set :: proc(c: ^$C/Cache($Key, $Value), key: Key, value: Value) -> runtime.Allocator_Error {
 	if e, ok := c.entries[key]; ok {
 		e.value = value
+		_pop_node(c, e)
+		_push_front_node(c, e)
 		return nil
 	}
 
-	e := new(Node(Key, Value), c.node_allocator) or_return
+	e : ^Node(Key, Value) = nil
+	assert(c.count <= c.capacity)
+	if c.count == c.capacity {
+		e = c.tail
+		_remove_node(c, e)
+	}
+	else {
+		c.count += 1
+		e = new(Node(Key, Value), c.node_allocator) or_return
+	}
+
 	e.key = key
 	e.value = value
-
 	_push_front_node(c, e)
-	if c.count > c.capacity {
-		_remove_node(c, c.tail)
-	}
-
 	c.entries[key] = e
+
 	return nil
 }
 
@@ -122,6 +130,8 @@ remove :: proc(c: ^$C/Cache($Key, $Value), key: Key) -> bool {
 		return false
 	}
 	_remove_node(c, e)
+	free(node, c.node_allocator)
+	c.count -= 1
 	return true
 }
 
@@ -143,14 +153,9 @@ _remove_node :: proc(c: ^$C/Cache($Key, $Value), node: ^Node(Key, Value)) {
 	node.prev = nil
 	node.next = nil
 
-	c.count -= 1
-
 	delete_key(&c.entries, node.key)
 
 	_call_on_remove(c, node)
-
-	free(node, c.node_allocator)
-
 }
 
 @(private)
@@ -171,8 +176,6 @@ _push_front_node :: proc(c: ^$C/Cache($Key, $Value), e: ^Node(Key, Value)) {
 		c.tail = e
 	}
 	e.prev = nil
-
-	c.count += 1
 }
 
 @(private)
@@ -180,6 +183,12 @@ _pop_node :: proc(c: ^$C/Cache($Key, $Value), e: ^Node(Key, Value)) {
 	if e == nil {
 		return
 	}
+	if c.head == e {
+		c.head = e.next
+	}
+	if c.tail == e {
+		c.tail = e.prev
+	}
 	if e.prev != nil {
 		e.prev.next = e.next
 	}
diff --git a/core/container/small_array/small_array.odin b/core/container/small_array/small_array.odin
index 5cd421c84..4dd16f30c 100644
--- a/core/container/small_array/small_array.odin
+++ b/core/container/small_array/small_array.odin
@@ -86,7 +86,7 @@ pop_back_safe :: proc(a: ^$A/Small_Array($N, $T)) -> (item: T, ok: bool) {
 	return
 }
 
-pop_front_safe :: proc(a: ^$A/Small_Array($N, $T)) -> (T, bool) {
+pop_front_safe :: proc(a: ^$A/Small_Array($N, $T)) -> (item: T, ok: bool) {
 	if N > 0 && a.len > 0 {
 		item = a.data[0]
 		s := slice(a)
@@ -114,4 +114,4 @@ push_back_elems :: proc(a: ^$A/Small_Array($N, $T), items: ..T) {
 append_elem  :: push_back
 append_elems :: push_back_elems
 push   :: proc{push_back, push_back_elems}
-append :: proc{push_back, push_back_elems}
\ No newline at end of file
+append :: proc{push_back, push_back_elems}