block_bloom_filter.hh revision 14262
111731Sjason@lowepower.com/* 211731Sjason@lowepower.com * Copyright (c) 2019 Inria 311731Sjason@lowepower.com * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood 411731Sjason@lowepower.com * All rights reserved. 511731Sjason@lowepower.com * 611731Sjason@lowepower.com * Redistribution and use in source and binary forms, with or without 711731Sjason@lowepower.com * modification, are permitted provided that the following conditions are 811731Sjason@lowepower.com * met: redistributions of source code must retain the above copyright 911731Sjason@lowepower.com * notice, this list of conditions and the following disclaimer; 1011731Sjason@lowepower.com * redistributions in binary form must reproduce the above copyright 1111731Sjason@lowepower.com * notice, this list of conditions and the following disclaimer in the 1211731Sjason@lowepower.com * documentation and/or other materials provided with the distribution; 1311731Sjason@lowepower.com * neither the name of the copyright holders nor the names of its 1411731Sjason@lowepower.com * contributors may be used to endorse or promote products derived from 1511731Sjason@lowepower.com * this software without specific prior written permission. 1611731Sjason@lowepower.com * 1711731Sjason@lowepower.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1811731Sjason@lowepower.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1911731Sjason@lowepower.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2011731Sjason@lowepower.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2111731Sjason@lowepower.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2211731Sjason@lowepower.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2311731Sjason@lowepower.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2411731Sjason@lowepower.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2511731Sjason@lowepower.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2611731Sjason@lowepower.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2711731Sjason@lowepower.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2811731Sjason@lowepower.com * 2911731Sjason@lowepower.com * Authors: Daniel Carvalho 3011731Sjason@lowepower.com */ 3111731Sjason@lowepower.com 3211731Sjason@lowepower.com#ifndef __BASE_FILTERS_BLOCK_BLOOM_FILTER_HH__ 3311731Sjason@lowepower.com#define __BASE_FILTERS_BLOCK_BLOOM_FILTER_HH__ 3411731Sjason@lowepower.com 3511731Sjason@lowepower.com#include <vector> 3611731Sjason@lowepower.com 3711731Sjason@lowepower.com#include "base/filters/base.hh" 3811731Sjason@lowepower.com 3911731Sjason@lowepower.comstruct BloomFilterBlockParams; 4011731Sjason@lowepower.com 4111731Sjason@lowepower.comnamespace BloomFilter { 4211731Sjason@lowepower.com 4311731Sjason@lowepower.com/** 4411731Sjason@lowepower.com * Simple deletable (with false negatives) bloom filter that extracts 4511731Sjason@lowepower.com * bitfields of an address to use as indexes of the filter vector. 4611731Sjason@lowepower.com */ 4711731Sjason@lowepower.comclass Block : public Base 4811731Sjason@lowepower.com{ 4911731Sjason@lowepower.com public: 5011731Sjason@lowepower.com Block(const BloomFilterBlockParams* p); 5111731Sjason@lowepower.com ~Block(); 5211731Sjason@lowepower.com 5311731Sjason@lowepower.com void set(Addr addr) override; 5411731Sjason@lowepower.com void unset(Addr addr) override; 5511731Sjason@lowepower.com int getCount(Addr addr) const override; 5611731Sjason@lowepower.com 5711731Sjason@lowepower.com private: 5811731Sjason@lowepower.com /** 5911731Sjason@lowepower.com * XOR hash between bitfields of an address, provided by the mask vector. 6011731Sjason@lowepower.com * 6111731Sjason@lowepower.com * @param addr The address to be hashed. 6211731Sjason@lowepower.com * @return The value of the XOR of the masked bitfields of the address. 6311731Sjason@lowepower.com */ 6411731Sjason@lowepower.com int hash(Addr addr) const; 6511731Sjason@lowepower.com 6611731Sjason@lowepower.com /** Position of the LSB of each mask. */ 6711731Sjason@lowepower.com std::vector<unsigned> masksLSBs; 6811731Sjason@lowepower.com 6911731Sjason@lowepower.com /** Number of bits in each mask. */ 7011731Sjason@lowepower.com std::vector<unsigned> masksSizes; 7111731Sjason@lowepower.com}; 7211731Sjason@lowepower.com 7311731Sjason@lowepower.com} // namespace BloomFilter 7411731Sjason@lowepower.com 7511731Sjason@lowepower.com#endif // __BASE_FILTERS_BLOCK_BLOOM_FILTER_HH__ 7611731Sjason@lowepower.com