base.hh revision 14262
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_BASE_HH__ 3314262Sodanrc@yahoo.com.br#define __BASE_FILTERS_BASE_HH__ 3414262Sodanrc@yahoo.com.br 3514262Sodanrc@yahoo.com.br#include <vector> 3614262Sodanrc@yahoo.com.br 3714262Sodanrc@yahoo.com.br#include "base/intmath.hh" 3814262Sodanrc@yahoo.com.br#include "base/types.hh" 3914262Sodanrc@yahoo.com.br#include "params/BloomFilterBase.hh" 4014262Sodanrc@yahoo.com.br#include "sim/sim_object.hh" 4114262Sodanrc@yahoo.com.br 4214262Sodanrc@yahoo.com.brnamespace BloomFilter { 4314262Sodanrc@yahoo.com.br 4414262Sodanrc@yahoo.com.brclass Base : public SimObject 4514262Sodanrc@yahoo.com.br{ 4614262Sodanrc@yahoo.com.br protected: 4714262Sodanrc@yahoo.com.br /** Number of LSB bits to ignore from the the addresses. */ 4814262Sodanrc@yahoo.com.br const unsigned offsetBits; 4914262Sodanrc@yahoo.com.br 5014262Sodanrc@yahoo.com.br /** The filter itself. */ 5114262Sodanrc@yahoo.com.br std::vector<int> filter; 5214262Sodanrc@yahoo.com.br 5314262Sodanrc@yahoo.com.br /** Number of bits needed to represent the size of the filter. */ 5414262Sodanrc@yahoo.com.br const int sizeBits; 5514262Sodanrc@yahoo.com.br 5614262Sodanrc@yahoo.com.br /** Threshold at which a filter entry starts being considered as set. */ 5714262Sodanrc@yahoo.com.br const int setThreshold; 5814262Sodanrc@yahoo.com.br 5914262Sodanrc@yahoo.com.br public: 6014262Sodanrc@yahoo.com.br /** 6114262Sodanrc@yahoo.com.br * Create and clear the filter. 6214262Sodanrc@yahoo.com.br */ 6314262Sodanrc@yahoo.com.br Base(const BloomFilterBaseParams* p) 6414262Sodanrc@yahoo.com.br : SimObject(p), offsetBits(p->offset_bits), filter(p->size), 6514262Sodanrc@yahoo.com.br sizeBits(floorLog2(p->size)), setThreshold(p->threshold) 6614262Sodanrc@yahoo.com.br { 6714262Sodanrc@yahoo.com.br clear(); 6814262Sodanrc@yahoo.com.br } 6914262Sodanrc@yahoo.com.br virtual ~Base() {}; 7014262Sodanrc@yahoo.com.br 7114262Sodanrc@yahoo.com.br /** 7214262Sodanrc@yahoo.com.br * Clear the filter by resetting all values. 7314262Sodanrc@yahoo.com.br */ 7414262Sodanrc@yahoo.com.br virtual void clear() 7514262Sodanrc@yahoo.com.br { 7614262Sodanrc@yahoo.com.br for (auto& entry : filter) { 7714262Sodanrc@yahoo.com.br entry = 0; 7814262Sodanrc@yahoo.com.br } 7914262Sodanrc@yahoo.com.br } 8014262Sodanrc@yahoo.com.br 8114262Sodanrc@yahoo.com.br /** 8214262Sodanrc@yahoo.com.br * Merges the contents of both filters into this' (Bloom Filter union). 8314262Sodanrc@yahoo.com.br * Both must have the same number of entries. 8414262Sodanrc@yahoo.com.br * 8514262Sodanrc@yahoo.com.br * @param other The other bloom filter to merge with. 8614262Sodanrc@yahoo.com.br */ 8714262Sodanrc@yahoo.com.br virtual void 8814262Sodanrc@yahoo.com.br merge(const Base* other) 8914262Sodanrc@yahoo.com.br { 9014262Sodanrc@yahoo.com.br assert(filter.size() == other->filter.size()); 9114262Sodanrc@yahoo.com.br for (int i = 0; i < filter.size(); ++i){ 9214262Sodanrc@yahoo.com.br filter[i] |= other->filter[i]; 9314262Sodanrc@yahoo.com.br } 9414262Sodanrc@yahoo.com.br } 9514262Sodanrc@yahoo.com.br 9614262Sodanrc@yahoo.com.br /** 9714262Sodanrc@yahoo.com.br * Perform the filter specific function to set the corresponding 9814262Sodanrc@yahoo.com.br * entries (can be multiple) of an address. 9914262Sodanrc@yahoo.com.br * 10014262Sodanrc@yahoo.com.br * @param addr The address being parsed. 10114262Sodanrc@yahoo.com.br */ 10214262Sodanrc@yahoo.com.br virtual void set(Addr addr) = 0; 10314262Sodanrc@yahoo.com.br 10414262Sodanrc@yahoo.com.br /** 10514262Sodanrc@yahoo.com.br * Perform the filter specific function to clear the corresponding 10614262Sodanrc@yahoo.com.br * entries (can be multiple) of an address. By default a bloom 10714262Sodanrc@yahoo.com.br * filter does not support element deletion. 10814262Sodanrc@yahoo.com.br * 10914262Sodanrc@yahoo.com.br * @param addr The address being parsed. 11014262Sodanrc@yahoo.com.br */ 11114262Sodanrc@yahoo.com.br virtual void unset(Addr addr) {}; 11214262Sodanrc@yahoo.com.br 11314262Sodanrc@yahoo.com.br /** 11414262Sodanrc@yahoo.com.br * Check if the corresponding filter entries of an address should be 11514262Sodanrc@yahoo.com.br * considered as set. 11614262Sodanrc@yahoo.com.br * 11714262Sodanrc@yahoo.com.br * @param addr The address being parsed. 11814262Sodanrc@yahoo.com.br * @return Whether the respective filter entry is set. 11914262Sodanrc@yahoo.com.br */ 12014262Sodanrc@yahoo.com.br virtual bool 12114262Sodanrc@yahoo.com.br isSet(Addr addr) const 12214262Sodanrc@yahoo.com.br { 12314262Sodanrc@yahoo.com.br return getCount(addr) >= setThreshold; 12414262Sodanrc@yahoo.com.br } 12514262Sodanrc@yahoo.com.br 12614262Sodanrc@yahoo.com.br /** 12714262Sodanrc@yahoo.com.br * Get the value stored in the corresponding filter entry of an address. 12814262Sodanrc@yahoo.com.br * 12914262Sodanrc@yahoo.com.br * @param addr The address being parsed. 13014262Sodanrc@yahoo.com.br * @param Get the value stored in the respective filter entry. 13114262Sodanrc@yahoo.com.br */ 13214262Sodanrc@yahoo.com.br virtual int getCount(Addr addr) const { return 0; } 13314262Sodanrc@yahoo.com.br 13414262Sodanrc@yahoo.com.br /** 13514262Sodanrc@yahoo.com.br * Get the total value stored in the filter entries. 13614262Sodanrc@yahoo.com.br * 13714262Sodanrc@yahoo.com.br * @return The sum of all filter entries. 13814262Sodanrc@yahoo.com.br */ 13914262Sodanrc@yahoo.com.br virtual int getTotalCount() const 14014262Sodanrc@yahoo.com.br { 14114262Sodanrc@yahoo.com.br int count = 0; 14214262Sodanrc@yahoo.com.br for (const auto& entry : filter) { 14314262Sodanrc@yahoo.com.br count += entry; 14414262Sodanrc@yahoo.com.br } 14514262Sodanrc@yahoo.com.br return count; 14614262Sodanrc@yahoo.com.br } 14714262Sodanrc@yahoo.com.br}; 14814262Sodanrc@yahoo.com.br 14914262Sodanrc@yahoo.com.br} // namespace BloomFilter 15014262Sodanrc@yahoo.com.br 15114262Sodanrc@yahoo.com.br#endif // __BASE_FILTERS_BASE_HH__ 152