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 java.nio.ByteBuffer; 18 import java.util.Optional; 19 import java.util.Random; 20 21 /** An array of buckets where each bucket can store a fixed number of fingerprints. */ 22 interface CuckooFilterTable { 23 /** Value of the empty "slot", which is reserved as 0. */ 24 public static long EMPTY_SLOT = 0L; 25 26 /** 27 * Creates an implementation of an empty cuckoo filter based on whether space optimization should 28 * be used. 29 * 30 * <p>Space optimization is best effort, and is not guaranteed. 31 */ create( CuckooFilterConfig.Size size, boolean useSpaceOptimization, Random random)32 public static CuckooFilterTable create( 33 CuckooFilterConfig.Size size, boolean useSpaceOptimization, Random random) { 34 if (useSpaceOptimization && size.bucketCapacity() == 4 && size.fingerprintLength() >= 4) { 35 return new SemiSortedCuckooFilterTable(size, random); 36 } 37 return new UncompressedCuckooFilterTable(size, random); 38 } 39 40 /** Creates an implementation of the cuckoo filter based on the serialization. */ createFromSerialization( SerializedCuckooFilterTable serializedTable, Random random)41 public static CuckooFilterTable createFromSerialization( 42 SerializedCuckooFilterTable serializedTable, Random random) { 43 ByteBuffer buffer = ByteBuffer.wrap(serializedTable.asByteArray()); 44 45 if (buffer.remaining() <= 16) { 46 throw new IllegalArgumentException("Unable to parse the SerializedCuckooFilterTable."); 47 } 48 49 int tableType = buffer.getInt(); 50 int bucketCount = buffer.getInt(); 51 int bucketCapacity = buffer.getInt(); 52 int fingerprintLength = buffer.getInt(); 53 CuckooFilterConfig.Size size = 54 CuckooFilterConfig.Size.newBuilder() 55 .setBucketCount(bucketCount) 56 .setBucketCapacity(bucketCapacity) 57 .setFingerprintLength(fingerprintLength) 58 .build(); 59 60 byte[] bitArray = new byte[buffer.remaining()]; 61 buffer.get(bitArray); 62 63 if (tableType == UncompressedCuckooFilterTable.TABLE_TYPE) { 64 return new UncompressedCuckooFilterTable(size, bitArray, random); 65 } else if (tableType == SemiSortedCuckooFilterTable.TABLE_TYPE) { 66 return new SemiSortedCuckooFilterTable(size, bitArray, random); 67 } else { 68 throw new IllegalArgumentException("Unable to parse the SerializedCuckooFilterTable."); 69 } 70 } 71 72 /** 73 * Inserts given {@code fingerprint} to the {@code bucketIndex}th bucket, replacing an arbitrary 74 * fingerprint if the bucket is full. 75 * 76 * <p>How this arbitrary fingerprint is chosen depends on the implementation. 77 * 78 * @return the value of the replaced fingerprint if the bucket is full, and an empty {@link 79 * Optional} otherwise. 80 */ insertWithReplacement(int bucketIndex, long fingerprint)81 Optional<Long> insertWithReplacement(int bucketIndex, long fingerprint); 82 83 /** Returns whether {@code bucketIndex}th bucket contains {@code fingerprint}. */ contains(int bucketIndex, long fingerprint)84 boolean contains(int bucketIndex, long fingerprint); 85 86 /** 87 * Deletes a {@code fingerprint} from {@code bucketIndex}th bucket. 88 * 89 * <p>If a bucket contains multiple {@code fingerprint} values, this method only deletes one. 90 * 91 * @return {@code true} if {@code fingerprint} is in {@code bucketIndex}th bucket and is deleted, 92 * and {@code false} otherwise. 93 */ delete(int bucketIndex, long fingerprint)94 boolean delete(int bucketIndex, long fingerprint); 95 96 /** Returns whether {@code bucketIndex}th bucket is full. */ isFull(int bucketIndex)97 boolean isFull(int bucketIndex); 98 99 /** Returns the size of {@link CuckooFilterTable}. */ size()100 CuckooFilterConfig.Size size(); 101 102 /** Returns serialization of {@link CuckooFilterTable}. */ serialize()103 SerializedCuckooFilterTable serialize(); 104 105 // TODO: Add more methods as needed. 106 } 107