bulk_bloom_filter.hh revision 14263
114262Sodanrc@yahoo.com.br/* 214262Sodanrc@yahoo.com.br * Copyright (c) 2019 Inria 314262Sodanrc@yahoo.com.br * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood 414262Sodanrc@yahoo.com.br * All rights reserved. 514262Sodanrc@yahoo.com.br * 614262Sodanrc@yahoo.com.br * Redistribution and use in source and binary forms, with or without 714262Sodanrc@yahoo.com.br * modification, are permitted provided that the following conditions are 814262Sodanrc@yahoo.com.br * met: redistributions of source code must retain the above copyright 914262Sodanrc@yahoo.com.br * notice, this list of conditions and the following disclaimer; 1014262Sodanrc@yahoo.com.br * redistributions in binary form must reproduce the above copyright 1114262Sodanrc@yahoo.com.br * notice, this list of conditions and the following disclaimer in the 1214262Sodanrc@yahoo.com.br * documentation and/or other materials provided with the distribution; 1314262Sodanrc@yahoo.com.br * neither the name of the copyright holders nor the names of its 1414262Sodanrc@yahoo.com.br * contributors may be used to endorse or promote products derived from 1514262Sodanrc@yahoo.com.br * this software without specific prior written permission. 1614262Sodanrc@yahoo.com.br * 1714262Sodanrc@yahoo.com.br * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1814262Sodanrc@yahoo.com.br * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1914262Sodanrc@yahoo.com.br * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2014262Sodanrc@yahoo.com.br * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2114262Sodanrc@yahoo.com.br * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2214262Sodanrc@yahoo.com.br * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2314262Sodanrc@yahoo.com.br * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2414262Sodanrc@yahoo.com.br * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2514262Sodanrc@yahoo.com.br * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2614262Sodanrc@yahoo.com.br * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2714262Sodanrc@yahoo.com.br * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2814262Sodanrc@yahoo.com.br * 2914262Sodanrc@yahoo.com.br * Authors: Daniel Carvalho 3014262Sodanrc@yahoo.com.br */ 3114262Sodanrc@yahoo.com.br 3214262Sodanrc@yahoo.com.br#ifndef __BASE_FILTERS_BULK_BLOOM_FILTER_HH__ 3314262Sodanrc@yahoo.com.br#define __BASE_FILTERS_BULK_BLOOM_FILTER_HH__ 3414262Sodanrc@yahoo.com.br 3514263Sodanrc@yahoo.com.br#include "base/filters/multi_bit_sel_bloom_filter.hh" 3614262Sodanrc@yahoo.com.br 3714262Sodanrc@yahoo.com.brstruct BloomFilterBulkParams; 3814262Sodanrc@yahoo.com.br 3914262Sodanrc@yahoo.com.brnamespace BloomFilter { 4014262Sodanrc@yahoo.com.br 4114262Sodanrc@yahoo.com.br/** 4214262Sodanrc@yahoo.com.br * Implementation of the bloom filter, as described in "Bulk Disambiguation of 4314262Sodanrc@yahoo.com.br * Speculative Threads in Multiprocessors", by Ceze, Luis, et al. 4414263Sodanrc@yahoo.com.br * The number of hashes indicates the number of c bitfields. 4514262Sodanrc@yahoo.com.br */ 4614263Sodanrc@yahoo.com.brclass Bulk : public MultiBitSel 4714262Sodanrc@yahoo.com.br{ 4814262Sodanrc@yahoo.com.br public: 4914262Sodanrc@yahoo.com.br Bulk(const BloomFilterBulkParams* p); 5014262Sodanrc@yahoo.com.br ~Bulk(); 5114262Sodanrc@yahoo.com.br 5214263Sodanrc@yahoo.com.br protected: 5314263Sodanrc@yahoo.com.br int hash(Addr addr, int hash_number) const override; 5414262Sodanrc@yahoo.com.br 5514262Sodanrc@yahoo.com.br private: 5614262Sodanrc@yahoo.com.br /** Permutes the address to generate its signature. */ 5714263Sodanrc@yahoo.com.br Addr permute(Addr addr) const; 5814262Sodanrc@yahoo.com.br 5914263Sodanrc@yahoo.com.br /** 6014263Sodanrc@yahoo.com.br * Number of bits used per sector. The filter is split into sectors, 6114263Sodanrc@yahoo.com.br * each of which with its own hash function. When an address is hashed 6214263Sodanrc@yahoo.com.br * all sectors are parsed to generate c indexes. These indexes are then 6314263Sodanrc@yahoo.com.br * used to find the respective v indexes in the main filter. 6414263Sodanrc@yahoo.com.br */ 6514262Sodanrc@yahoo.com.br const int sectorBits; 6614262Sodanrc@yahoo.com.br}; 6714262Sodanrc@yahoo.com.br 6814262Sodanrc@yahoo.com.br} // namespace BloomFilter 6914262Sodanrc@yahoo.com.br 7014262Sodanrc@yahoo.com.br#endif // __BASE_FILTERS_BULK_BLOOM_FILTER_HH__ 71