-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathNativeLru.cs
More file actions
122 lines (102 loc) · 4.23 KB
/
NativeLru.cs
File metadata and controls
122 lines (102 loc) · 4.23 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
using Unity.Collections;
using System.Runtime.CompilerServices;
namespace Renderloom
{
public struct NativeLru : System.IDisposable
{
public struct LruNode { public int prev; public int next; }
private NativeArray<LruNode> _nodes; // per-id {prev,next}
private int _head; // oldest id or -1
private int _tail; // newest id or -1
private int _count;
private int _capacity;
private Allocator _alloc;
private const int NULL = -1;
private const int NOTIN = -2; // not in list
public int Count => _count;
public int HeadId => _head;
public int TailId => _tail;
public int Capacity => _capacity;
public NativeLru(int capacity, Allocator alloc)
{
_capacity = capacity;
_alloc = alloc;
_nodes = new NativeArray<LruNode>(capacity, alloc, NativeArrayOptions.UninitializedMemory);
for (int i = 0; i < capacity; i++) _nodes[i] = new LruNode { prev = NOTIN, next = NOTIN };
_head = NULL; _tail = NULL; _count = 0;
}
public void Dispose()
{
if (_nodes.IsCreated) _nodes.Dispose();
_head = _tail = NULL; _count = 0; _capacity = 0;
}
public void Clear()
{
for (int i = 0; i < _capacity; i++) _nodes[i] = new LruNode { prev = NOTIN, next = NOTIN };
_head = _tail = NULL; _count = 0;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public bool Contains(int id)
{
return (uint)id < (uint)_capacity && _nodes[id].prev != NOTIN;
}
/// <summary>
/// If id not present: append to tail. If present and not tail: move to tail. If already tail: no-op.
/// Typical: call when refCount transitions 1->0 (becoming evictable), or when refreshing zero-ref recency.
/// </summary>
public bool AddOrTouch(int id)
{
if ((uint)id >= (uint)_capacity) return false;
if (!Contains(id))
{
var n = _nodes[id];
n.prev = _tail; n.next = NULL; _nodes[id] = n;
if (_tail != NULL) { var t = _nodes[_tail]; t.next = id; _nodes[_tail] = t; }
_tail = id;
if (_head == NULL) _head = id;
_count++;
return true;
}
if (id == _tail) return true;
var node = _nodes[id];
int p = node.prev;
int q = node.next;
if (p != NULL) { var tp = _nodes[p]; tp.next = q; _nodes[p] = tp; } else { _head = q; }
if (q != NULL) { var tq = _nodes[q]; tq.prev = p; _nodes[q] = tq; }
node.prev = _tail; node.next = NULL; _nodes[id] = node;
if (_tail != NULL) { var t = _nodes[_tail]; t.next = id; _nodes[_tail] = t; }
_tail = id;
if (_head == NULL) _head = id;
return true;
}
/// <summary>Remove id if present (O(1)). Call when refCount transitions 0->1.</summary>
public bool Remove(int id)
{
if (!Contains(id)) return false;
var node = _nodes[id];
int p = node.prev;
int q = node.next;
if (p != NULL) { var tp = _nodes[p]; tp.next = q; _nodes[p] = tp; } else { _head = q; }
if (q != NULL) { var tq = _nodes[q]; tq.prev = p; _nodes[q] = tq; } else { _tail = p; }
_nodes[id] = new LruNode { prev = NOTIN, next = NOTIN };
_count--;
if (_count == 0) { _head = _tail = NULL; }
return true;
}
/// <summary>Pop oldest id (head). Returns false if empty.</summary>
public bool PopHead(out int id)
{
id = _head;
if (id == NULL) return false;
var node = _nodes[id];
int q = node.next;
if (q != NULL) { var tq = _nodes[q]; tq.prev = NULL; _nodes[q] = tq; }
_head = q;
if (_tail == id) _tail = q;
_nodes[id] = new LruNode { prev = NOTIN, next = NOTIN };
_count--;
if (_count == 0) { _head = _tail = NULL; }
return true;
}
}
}