1 // Copyright 2022 Google LLC
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 //    https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 
15 package com.google.setfilters.cuckoofilter;
16 
17 import static com.google.common.truth.Truth.assertThat;
18 import static org.junit.Assert.assertThrows;
19 import static org.mockito.Mockito.mock;
20 import static org.mockito.Mockito.when;
21 
22 import java.util.Arrays;
23 import java.util.List;
24 import java.util.Optional;
25 import java.util.Random;
26 import org.junit.Before;
27 import org.junit.Test;
28 import org.junit.runner.RunWith;
29 import org.junit.runners.Parameterized;
30 import org.junit.runners.Parameterized.Parameter;
31 import org.junit.runners.Parameterized.Parameters;
32 
33 @RunWith(Parameterized.class)
34 public final class CuckooFilterTableTest {
35   private static final int BUCKET_COUNT = 10000;
36   private static final int BUCKET_CAPACITY = 4;
37   private static final int FINGERPRINT_LENGTH = 16;
38 
39   private Random random;
40   private CuckooFilterTable table;
41 
42   private interface CuckooFilterTableFactory {
create(CuckooFilterConfig.Size size, Random random)43     public CuckooFilterTable create(CuckooFilterConfig.Size size, Random random);
44 
createExisting( SerializedCuckooFilterTable serializedTable, Random random)45     public default CuckooFilterTable createExisting(
46         SerializedCuckooFilterTable serializedTable, Random random) {
47       return CuckooFilterTable.createFromSerialization(serializedTable, random);
48     }
49   }
50 
51   private static class SemiSortedCuckooFilterTableFactory implements CuckooFilterTableFactory {
52     @Override
create(CuckooFilterConfig.Size size, Random random)53     public CuckooFilterTable create(CuckooFilterConfig.Size size, Random random) {
54       return new SemiSortedCuckooFilterTable(size, random);
55     }
56   }
57 
58   private static class UncompressedCuckooFilterTableFactory implements CuckooFilterTableFactory {
59     @Override
create(CuckooFilterConfig.Size size, Random random)60     public CuckooFilterTable create(CuckooFilterConfig.Size size, Random random) {
61       return new UncompressedCuckooFilterTable(size, random);
62     }
63   }
64 
65   @Parameters
data()66   public static List<? extends Object> data() {
67     return Arrays.asList(
68         new SemiSortedCuckooFilterTableFactory(), new UncompressedCuckooFilterTableFactory());
69   }
70 
71   @Parameter public CuckooFilterTableFactory tableFactory;
72 
73   @Before
setUp()74   public void setUp() {
75     random = mock(Random.class);
76     table =
77         tableFactory.create(
78             CuckooFilterConfig.Size.newBuilder()
79                 .setBucketCount(BUCKET_COUNT)
80                 .setBucketCapacity(BUCKET_CAPACITY)
81                 .setFingerprintLength(FINGERPRINT_LENGTH)
82                 .build(),
83             random);
84   }
85 
86   @Test
insertWithReplacement()87   public void insertWithReplacement() {
88     for (int i = 0; i < BUCKET_COUNT; i++) {
89       long offset = (long) i * BUCKET_CAPACITY;
90       for (int j = 0; j < BUCKET_CAPACITY; j++) {
91         assertThat(table.insertWithReplacement(i, offset + j + 1)).isEmpty();
92       }
93       when(random.nextInt(BUCKET_CAPACITY)).thenReturn(0);
94 
95       Optional<Long> replaced = table.insertWithReplacement(i, offset + BUCKET_CAPACITY + 1);
96 
97       boolean anyOf = false;
98       for (int j = 0; j < BUCKET_CAPACITY; j++) {
99         anyOf = anyOf || (replaced.get() == offset + j + 1);
100       }
101       assertThat(anyOf).isTrue();
102       assertThat(table.contains(i, replaced.get())).isFalse();
103       for (long fingerprint = offset + 1;
104           fingerprint < offset + BUCKET_CAPACITY + 2;
105           fingerprint++) {
106         if (fingerprint != replaced.get()) {
107           assertThat(table.contains(i, fingerprint)).isTrue();
108         }
109       }
110     }
111   }
112 
113   @Test
contains_containsFingerprint()114   public void contains_containsFingerprint() {
115     assertThat(table.insertWithReplacement(0, 1L)).isEmpty();
116 
117     assertThat(table.contains(0, 1L)).isTrue();
118   }
119 
120   @Test
contains_doesNotContainFingerprint()121   public void contains_doesNotContainFingerprint() {
122     assertThat(table.contains(0, 1L)).isFalse();
123   }
124 
125   @Test
delete_deletesExistingFingerprint()126   public void delete_deletesExistingFingerprint() {
127     assertThat(table.insertWithReplacement(0, 1L)).isEmpty();
128     assertThat(table.contains(0, 1L)).isTrue();
129 
130     assertThat(table.delete(0, 1L)).isTrue();
131     assertThat(table.contains(0, 1L)).isFalse();
132   }
133 
134   @Test
delete_deletesOneFingerprintAtATime()135   public void delete_deletesOneFingerprintAtATime() {
136     assertThat(table.insertWithReplacement(0, 1L)).isEmpty();
137     assertThat(table.insertWithReplacement(0, 1L)).isEmpty();
138     assertThat(table.contains(0, 1L)).isTrue();
139 
140     assertThat(table.delete(0, 1L)).isTrue();
141     assertThat(table.contains(0, 1L)).isTrue();
142     assertThat(table.delete(0, 1L)).isTrue();
143     assertThat(table.contains(0, 1L)).isFalse();
144   }
145 
146   @Test
delete_deletesNonExistingFingerprint()147   public void delete_deletesNonExistingFingerprint() {
148     assertThat(table.delete(0, 1L)).isFalse();
149   }
150 
151   @Test
isFull()152   public void isFull() {
153     for (int j = 0; j < BUCKET_CAPACITY; j++) {
154       assertThat(table.isFull(0)).isFalse();
155       assertThat(table.insertWithReplacement(0, j + 1)).isEmpty();
156     }
157     assertThat(table.isFull(0)).isTrue();
158   }
159 
160   @Test
size()161   public void size() {
162     CuckooFilterConfig.Size size = table.size();
163 
164     assertThat(size.bucketCount()).isEqualTo(BUCKET_COUNT);
165     assertThat(size.bucketCapacity()).isEqualTo(BUCKET_CAPACITY);
166     assertThat(size.fingerprintLength()).isEqualTo(FINGERPRINT_LENGTH);
167   }
168 
169   @Test
serializeAndDeserialize()170   public void serializeAndDeserialize() {
171     for (int i = 0; i < BUCKET_CAPACITY; i++) {
172       long offset = (long) i * BUCKET_CAPACITY;
173       for (int j = 0; j < BUCKET_CAPACITY; j++) {
174         assertThat(table.insertWithReplacement(i, offset + j + 1)).isEmpty();
175       }
176     }
177 
178     SerializedCuckooFilterTable serializedTable = table.serialize();
179     CuckooFilterTable existingTable = tableFactory.createExisting(serializedTable, new Random());
180 
181     for (int i = 0; i < BUCKET_CAPACITY; i++) {
182       long offset = (long) i * BUCKET_CAPACITY;
183       for (int j = 0; j < BUCKET_CAPACITY; j++) {
184         assertThat(existingTable.contains(i, offset + j + 1)).isTrue();
185       }
186     }
187   }
188 
189   @Test
deserialize_failsWithInvalidSerialization()190   public void deserialize_failsWithInvalidSerialization() {
191     SerializedCuckooFilterTable serializedTable =
192         SerializedCuckooFilterTable.createFromByteArray(new byte[12]);
193 
194     String message =
195         assertThrows(
196                 IllegalArgumentException.class,
197                 () -> tableFactory.createExisting(serializedTable, new Random()))
198             .getMessage();
199     assertThat(message).isEqualTo("Unable to parse the SerializedCuckooFilterTable.");
200   }
201 }
202