1package descriptor
2
3import (
4 "math/bits"
5 "slices"
6)
7
8// Table is a data structure mapping 32 bit descriptor to items.
9//
10// # Negative keys are invalid.
11//
12// Negative keys (e.g. -1) are invalid inputs and will return a corresponding
13// not-found value. This matches POSIX behavior of file descriptors.
14// See https://pubs.opengroup.org/onlinepubs/9699919799/functions/dirfd.html#tag_16_90
15//
16// # Data structure design
17//
18// The data structure optimizes for memory density and lookup performance,
19// trading off compute at insertion time. This is a useful compromise for the
20// use cases we employ it with: items are usually accessed a lot more often
21// than they are inserted, each operation requires a table lookup, so we are
22// better off spending extra compute to insert items in the table in order to
23// get cheaper lookups. Memory efficiency is also crucial to support scaling
24// with programs that maintain thousands of items: having a high or non-linear
25// memory-to-item ratio could otherwise be used as an attack vector by
26// malicious applications attempting to damage performance of the host.
27type Table[Key ~int32, Item any] struct {
28 masks []uint64
29 items []Item
30}
31
32// Len returns the number of items stored in the table.
33func (t *Table[Key, Item]) Len() (n int) {
34 // We could make this a O(1) operation if we cached the number of items in
35 // the table. More state usually means more problems, so until we have a
36 // clear need for this, the simple implementation may be a better trade off.
37 for _, mask := range t.masks {
38 n += bits.OnesCount64(mask)
39 }
40 return n
41}
42
43// grow grows the table by n * 64 items.
44func (t *Table[Key, Item]) grow(n int) {
45 total := len(t.masks) + n
46 t.masks = slices.Grow(t.masks, n)[:total]
47
48 total = len(t.items) + n*64
49 t.items = slices.Grow(t.items, n*64)[:total]
50}
51
52// Insert inserts the given item to the table, returning the key that it is
53// mapped to or false if the table was full.
54//
55// The method does not perform deduplication, it is possible for the same item
56// to be inserted multiple times, each insertion will return a different key.
57func (t *Table[Key, Item]) Insert(item Item) (key Key, ok bool) {
58 offset := 0
59insert:
60 // Note: this loop could be made a lot more efficient using vectorized
61 // operations: 256 bits vector registers would yield a theoretical 4x
62 // speed up (e.g. using AVX2).
63 for index, mask := range t.masks[offset:] {
64 if ^mask != 0 { // not full?
65 shift := bits.TrailingZeros64(^mask)
66 index += offset
67 key = Key(index)*64 + Key(shift)
68 t.items[key] = item
69 t.masks[index] = mask | uint64(1<<shift)
70 return key, key >= 0
71 }
72 }
73
74 // No free slot found, grow the table and retry.
75 offset = len(t.masks)
76 t.grow(1)
77 goto insert
78}
79
80// Lookup returns the item associated with the given key (may be nil).
81func (t *Table[Key, Item]) Lookup(key Key) (item Item, found bool) {
82 if key < 0 { // invalid key
83 return
84 }
85 if i := int(key); i >= 0 && i < len(t.items) {
86 index := uint(key) / 64
87 shift := uint(key) % 64
88 if (t.masks[index] & (1 << shift)) != 0 {
89 item, found = t.items[i], true
90 }
91 }
92 return
93}
94
95// InsertAt inserts the given `item` at the item descriptor `key`. This returns
96// false if the insert was impossible due to negative key.
97func (t *Table[Key, Item]) InsertAt(item Item, key Key) bool {
98 if key < 0 {
99 return false
100 }
101 index := uint(key) / 64
102 if diff := int(index) - len(t.masks) + 1; diff > 0 {
103 t.grow(diff)
104 }
105 shift := uint(key) % 64
106 t.masks[index] |= 1 << shift
107 t.items[key] = item
108 return true
109}
110
111// Delete deletes the item stored at the given key from the table.
112func (t *Table[Key, Item]) Delete(key Key) {
113 if key < 0 { // invalid key
114 return
115 }
116 if index := uint(key) / 64; int(index) < len(t.masks) {
117 shift := uint(key) % 64
118 mask := t.masks[index]
119 if (mask & (1 << shift)) != 0 {
120 var zero Item
121 t.items[key] = zero
122 t.masks[index] = mask & ^uint64(1<<shift)
123 }
124 }
125}
126
127// Range calls f for each item and its associated key in the table. The function
128// f might return false to interupt the iteration.
129func (t *Table[Key, Item]) Range(f func(Key, Item) bool) {
130 for i, mask := range t.masks {
131 if mask == 0 {
132 continue
133 }
134 for j := Key(0); j < 64; j++ {
135 if (mask & (1 << j)) == 0 {
136 continue
137 }
138 if key := Key(i)*64 + j; !f(key, t.items[key]) {
139 return
140 }
141 }
142 }
143}
144
145// Reset clears the content of the table.
146func (t *Table[Key, Item]) Reset() {
147 clear(t.masks)
148 clear(t.items)
149}