-
Notifications
You must be signed in to change notification settings - Fork 3
/
table_cb.go
139 lines (115 loc) · 2.96 KB
/
table_cb.go
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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
// Copyright (c) 2024 Karl Gaissmaier
// SPDX-License-Identifier: MIT
package bart
import (
"net/netip"
)
// EachLookupPrefix calls yield() for each CIDR covering pfx
// in reverse CIDR sort order, from longest-prefix-match to
// shortest-prefix-match.
//
// If the yield function returns false, the iteration ends prematurely.
//
// Deprecated: EachLookupPrefix is deprecated. Use [Table.Supernets] instead.
func (t *Table[V]) EachLookupPrefix(pfx netip.Prefix, yield func(pfx netip.Prefix, val V) bool) {
if !pfx.IsValid() || !t.isInit() {
return
}
// values derived from pfx
ip := pfx.Addr()
is4 := ip.Is4()
bits := pfx.Bits()
n := t.rootNodeByVersion(is4)
// do not allocate
path := ip.As16()
octets := path[:]
if is4 {
octets = octets[12:]
}
copy(path[:], octets)
// see comment in Insert()
lastOctetIdx := (bits - 1) / strideLen
lastOctet := octets[lastOctetIdx]
lastOctetBits := bits - (lastOctetIdx * strideLen)
// mask the prefix
lastOctet &= netMask[lastOctetBits]
octets[lastOctetIdx] = lastOctet
// stack of the traversed nodes for reverse ordering of supernets
stack := [maxTreeDepth]*node[V]{}
// run variable, used after for loop
var i int
var octet byte
// find last node
for i, octet = range octets[:lastOctetIdx+1] {
// push current node on stack
stack[i] = n
// go down in tight loop
c := n.getChild(octet)
if c == nil {
break
}
n = c
}
// start backtracking, unwind the stack
for depth := i; depth >= 0; depth-- {
n = stack[depth]
// microbenchmarking
if len(n.prefixes) == 0 {
continue
}
// only the lastOctet may have a different prefix len
if depth == lastOctetIdx {
if !n.eachLookupPrefix(path, depth, is4, lastOctet, lastOctetBits, yield) {
// early exit
return
}
continue
}
// all others are just host routes
if !n.eachLookupPrefix(path, depth, is4, octets[depth], strideLen, yield) {
// early exit
return
}
}
}
// EachSubnet iterates over all CIDRs covered by pfx in natural CIDR sort order.
//
// If the yield function returns false, the iteration ends prematurely.
//
// Deprecated: EachSubnet is deprecated. Use [Table.Subnets] instead.
func (t *Table[V]) EachSubnet(pfx netip.Prefix, yield func(pfx netip.Prefix, val V) bool) {
if !pfx.IsValid() || !t.isInit() {
return
}
// values derived from pfx
ip := pfx.Addr()
is4 := ip.Is4()
bits := pfx.Bits()
n := t.rootNodeByVersion(is4)
// do not allocate
path := ip.As16()
octets := path[:]
if is4 {
octets = octets[12:]
}
copy(path[:], octets)
// see comment in Insert()
lastOctetIdx := (bits - 1) / strideLen
lastOctet := octets[lastOctetIdx]
lastOctetBits := bits - (lastOctetIdx * strideLen)
// mask the prefix
lastOctet &= netMask[lastOctetBits]
octets[lastOctetIdx] = lastOctet
// find the trie node
for i, octet := range octets {
if i == lastOctetIdx {
_ = n.eachSubnet(path, i, is4, lastOctet, lastOctetBits, yield)
return
}
c := n.getChild(octet)
if c == nil {
break
}
n = c
}
}