| 99 | } |
| 100 | |
| 101 | func (trie parentIndirection) insert(ip []byte, cidr uint8, peer *Peer) { |
| 102 | if *trie.parentBit == nil { |
| 103 | node := &trieEntry{ |
| 104 | peer: peer, |
| 105 | parent: trie, |
| 106 | bits: ip, |
| 107 | cidr: cidr, |
| 108 | bitAtByte: cidr / 8, |
| 109 | bitAtShift: 7 - (cidr % 8), |
| 110 | } |
| 111 | node.maskSelf() |
| 112 | node.addToPeerEntries() |
| 113 | *trie.parentBit = node |
| 114 | return |
| 115 | } |
| 116 | node, exact := (*trie.parentBit).nodePlacement(ip, cidr) |
| 117 | if exact { |
| 118 | node.removeFromPeerEntries() |
| 119 | node.peer = peer |
| 120 | node.addToPeerEntries() |
| 121 | return |
| 122 | } |
| 123 | |
| 124 | newNode := &trieEntry{ |
| 125 | peer: peer, |
| 126 | bits: ip, |
| 127 | cidr: cidr, |
| 128 | bitAtByte: cidr / 8, |
| 129 | bitAtShift: 7 - (cidr % 8), |
| 130 | } |
| 131 | newNode.maskSelf() |
| 132 | newNode.addToPeerEntries() |
| 133 | |
| 134 | var down *trieEntry |
| 135 | if node == nil { |
| 136 | down = *trie.parentBit |
| 137 | } else { |
| 138 | bit := node.choose(ip) |
| 139 | down = node.child[bit] |
| 140 | if down == nil { |
| 141 | newNode.parent = parentIndirection{&node.child[bit], bit} |
| 142 | node.child[bit] = newNode |
| 143 | return |
| 144 | } |
| 145 | } |
| 146 | common := commonBits(down.bits, ip) |
| 147 | if common < cidr { |
| 148 | cidr = common |
| 149 | } |
| 150 | parent := node |
| 151 | |
| 152 | if newNode.cidr == cidr { |
| 153 | bit := newNode.choose(down.bits) |
| 154 | down.parent = parentIndirection{&newNode.child[bit], bit} |
| 155 | newNode.child[bit] = down |
| 156 | if parent == nil { |
| 157 | newNode.parent = trie |
| 158 | *trie.parentBit = newNode |