## Appendix A Algorithms for Sections 3.1 and 3.2  
```
Input: element \(x\) to be inserted, which belongs to Level \(n\) Output: element \(x\) has been inserted into the CBHF
1\(L_{\text{P}}\) is a set of popular levels;
2 if\(n\
otin L_{\text{P}}\)then // x will be inserted into a Bloom filter
3 for\((i=1\) to \(k)\)do
4\(\text{BF}_{n}\{\text{Bit Array}[h_{i}(x)]\}\gets 1\);
5\(\text{BF}_{n}\{\text{Counter}[h_{i}(x)]\}++\);
6
7 end for
8
9 else // x will be inserted into a cuckoo filter
10 compute \(\text{CF}_{n}[f(x)]\), \(\text{CF}_{n}[h_{1}(x)]\), \(\text{CF}_{n}[h_{2}(x)]\);
11 if\(\text{CF}_{n}\{\text{Bucket}[h_{1}(x)]\}\) or \(\text{CF}_{n}[\text{Bucket}[h_{2}(x)]]\) has an empty cell then
12 add \(\text{CF}_{n}[f(x)]\) into the cell of that bucket;
13
14 else
15\(B_{n}=\text{randomly pick a bucket from }\{\text{CF}_{n}\{\text{Bucket}[h_{1}(x)]\},\text{CF}_{n}\{\text{Bucket}[h_ {2}(x)]\}\}\);
16\(F=\text{CF}_{n}[f(x)]\);
17 while\(\alpha\leq 0.95\)do // hash table is not considered full
18\(C_{n}=\text{randomly pick a cell in }\text{CF}_{n}[\text{Bucket}(B_{n})]\);
19\(F_{n}=\text{the fingerprint stored in }C_{n}\);
20\(\text{swap}(F,F_{n})\);
21\(B_{n}=B_{n}\oplus h_{1}(F)\);
22 if\(\text{CF}_{n}[\text{Bucket}(B_{n})]\) has an empty cell then
23 add \(F\) into \(\text{CF}_{n}[\text{Bucket}(B_{n})]\);
24 break;
25
26 end if
27
28 end for
29
30 end for
```  
**Algorithm A1**CBHF Inserting  
```
Input: element \(x\) belonging to Level \(n\) Output: membership query result in the CBHF
1\(L_{\text{P}}\) is a set of popular levels;
2 if\(n\
otin L_{\text{P}}\)then // membership query in a Bloom filter
3 for\((i=1\) to \(k)\)do
4 if\(\text{BF}_{n}\{\text{Bit Array}[h_{i}(x)]\}=0\)then
5 return false; // negative
6
7 else
8 return true; // positive
9
10 end if
11
12 end for
13
14 end for
```  
**Algorithm A2**CBHF Querying  
```
Input: element \(x\) belonging to Level \(n\) Output: membership query result in the CBHF
1\(L_{\text{P}}\) is a set of popular levels;
2 if\(n\
otin L_{\text{P}}\)then // membership query in a Bloom filter
3 for\((i=1\) to \(k)\)do
4 if\(\text{BF}_{n}\{\text{Bit Array}[h_{i}(x)]\}=0\)then
5 return false; // negative
6
7 else
8 return true; // positive
9
10 end if
11
12 end for // membership query in a cuckoo filter
13 compute \(\text{CF}_{n}[f(x)]\), \(\text{CF}_{n}[h_{1}(x)]\), \(\text{CF}_{n}[h_{2}(x)]\);
14 if\(\text{CF}_{n}[\text{Bucket}[h_{1}(x)]]\) or \(\text{CF}_{n}[\text{Bucket}[h_{2}(x)]]\) has \(\text{CF}_{n}[f(x)]\)then
15 return true; // positive
16
17 else
18 return false; // negative
19
20 end if
21
22 end for
```  
**Algorithm A3**CBHF Querying
```
Input: element \(x\) to be deleted, which belongs to Level \(n\) Output: element \(x\) has been deleted from the CBHF
1\(L_{\text{P}}\) is a set of popular levels;
2 if\(n\
otin L_{\text{P}}\)then// \(x\) will be removed from a Bloom filter
3 for(\(i=1\) to \(k\))do
4\(\text{BF}_{n}\{\text{Counter}[h_{i}(x)]\}-\text{;}\)
5 if\(\text{BF}_{n}\{\text{Counter}[h_{i}(x)]\}=0\)\"then
6\(\text{BF}_{n}\{\text{Bit Array}[h_{i}(x)]\}\gets 0\);
7
8 end if
9
10 end for
11
12 else // \(x\) will be removed from a cuckoo filter
13 compute \(\text{CF}_{n}[f(x)]\), \(\text{CF}_{n}[h_{1}(x)]\), \(\text{CF}_{n}[h_{2}(x)]\);
14 randomly remove a copy of \(\text{CF}_{n}[f(x)]\) from \(\{\text{CF}_{n}\{\text{Bucket}[h_{1}(x)]\},\text{CF}_{n}\{\text{Bucket}[h_{2}( x)]\}\}\);
15
16 end for
```  
**Algorithm A3**CBHF Deleting  
``` Input: IP address Output: next-hop information (NHI) in the routing table
1 FunctionLPM(\(x\)):// longest prefix matching lookup for an input IP address x
2 for(\(i=1\) to MaxNumLevel)do
3 hash lookup \(\xrightarrow{H_{i}(x)}\) Bitmap[P-\(\text{Trie}_{i}(x)\)];
4 direct lookup \(\xrightarrow{X_{i}(x)}\) Bitmap[R-\(\text{Trie}_{i}(x)\)];
5 Bitmap[OHT\({}_{i}(x)\)] = Bitmap[P-\(\text{Trie}_{i}(x)\)] && Bitmap[R-\(\text{Trie}_{i}(x)\)];
6 ifBitmap[OHT\({}_{i}(x)\)] \(\
eq\) 0 then// Level\({}_{i}(x)\) has at least a matching prefix
7 Offset\({}_{i}(x)=\) bit number of the rightmost \"11\" in Bitmap[OHT\({}_{i}(x)\)];
8 Base Address\({}_{i}(x)=H_{i}[H_{i}(x)]\);// off-chip hash table address information
9[Base Address\({}_{i}(x)+\text{Offset}_{i}(x)]\rightarrow\mathcal{N}\);// add into candidate set
10
11 end for
12 LPM(\(x\)) = [Base Address\({}_{i_{\text{max}}}(x)+\text{Offset}_{i_{\text{max}}}(x)\)] in \(\mathcal{N}\);// off-chip address of the longest matching prefix
13

## References

* (1) Space Exploration Holdings, LLC.