NVBIO
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
bloom_filter_inl.h
Go to the documentation of this file.
1 /*
2  * nvbio
3  * Copyright (c) 2011-2014, NVIDIA CORPORATION. All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions are met:
7  * * Redistributions of source code must retain the above copyright
8  * notice, this list of conditions and the following disclaimer.
9  * * Redistributions in binary form must reproduce the above copyright
10  * notice, this list of conditions and the following disclaimer in the
11  * documentation and/or other materials provided with the distribution.
12  * * Neither the name of the NVIDIA CORPORATION nor the
13  * names of its contributors may be used to endorse or promote products
14  * derived from this software without specific prior written permission.
15  *
16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
17  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19  * DISCLAIMED. IN NO EVENT SHALL NVIDIA CORPORATION BE LIABLE FOR ANY
20  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26  */
27 
28 namespace nvbio {
29 
30 template <
31  uint32 K, // number of hash functions { Hash1 + i * Hash2 | i : 0, ..., K-1 }
32  typename Hash1, // first hash generator function
33  typename Hash2, // second hash generator function
34  typename Iterator, // storage iterator - must dereference to uint32
35  typename OrOperator>
36 bloom_filter<K,Hash1,Hash2,Iterator,OrOperator>::bloom_filter(
37  const uint64 size,
38  Iterator storage,
39  const Hash1 hash1,
40  const Hash2 hash2) :
41  m_size( size ),
42  m_storage( storage ),
43  m_hash1( hash1 ),
44  m_hash2( hash2 ) {}
45 
46 template <
47  uint32 K, // number of hash functions { Hash1 + i * Hash2 | i : 0, ..., K-1 }
48  typename Hash1, // first hash generator function
49  typename Hash2, // second hash generator function
50  typename Iterator, // storage iterator - must dereference to uint32
51  typename OrOperator>
52 template <typename Key>
53 void bloom_filter<K,Hash1,Hash2,Iterator,OrOperator>::insert(const Key key, const OrOperator or_op)
54 {
55  const uint64 h0 = m_hash1( key );
56  const uint64 h1 = m_hash2( key );
57 
58  #if defined(__CUDA_ARCH__)
59  #pragma unroll
60  #endif
61  for (uint64 i = 0; i < K; ++i)
62  {
63  const uint64 r = (h0 + i * h1) % m_size;
64 
65  const uint32 word = uint32(r >> 5);
66  const uint32 bit = uint32(r) & 31u;
67 
68  or_op( &m_storage[word], (1u << bit) );
69  }
70 }
71 
72 template <
73  uint32 K, // number of hash functions { Hash1 + i * Hash2 | i : 0, ..., K-1 }
74  typename Hash1, // first hash generator function
75  typename Hash2, // second hash generator function
76  typename Iterator, // storage iterator - must dereference to uint32
77  typename OrOperator>
78 template <typename Key>
79 bool bloom_filter<K,Hash1,Hash2,Iterator,OrOperator>::has(const Key key) const
80 {
81  const uint64 h0 = m_hash1( key );
82  const uint64 h1 = m_hash2( key );
83 
84  #if defined(__CUDA_ARCH__)
85  #pragma unroll
86  #endif
87  for (uint64 i = 0; i < K; ++i)
88  {
89  const uint64 r = (h0 + i * h1) % m_size;
90 
91  const uint32 word = uint32(r >> 5);
92  const uint32 bit = uint32(r) & 31u;
93 
94  if ((m_storage[word] & (1u << bit)) == 0u)
95  return false;
96  }
97  return true;
98 }
99 
100 
101 template <
102  typename Hash1, // first hash generator function
103  typename Hash2, // second hash generator function
104  typename Iterator, // storage iterator - must be one of {uint32|uint2|uint4|uint64|uint64_2|uint64_4}
105  typename OrOperator>
106 blocked_bloom_filter<Hash1,Hash2,Iterator,OrOperator>::blocked_bloom_filter(
107  const uint32 k,
108  const uint64 size,
109  Iterator storage,
110  const Hash1 hash1,
111  const Hash2 hash2) :
112  m_k( k ),
113  m_size( size ),
114  m_storage( storage ),
115  m_hash1( hash1 ),
116  m_hash2( hash2 ) {}
117 
118 template <
119  typename Hash1, // first hash generator function
120  typename Hash2, // second hash generator function
121  typename Iterator, // storage iterator - must be one of {uint32|uint2|uint4|uint64|uint64_2|uint64_4}
122  typename OrOperator>
123 template <typename Key>
124 void blocked_bloom_filter<Hash1,Hash2,Iterator,OrOperator>::insert(const Key key, const OrOperator or_op)
125 {
126  const uint64 h0 = m_hash1( key );
127  const uint64 h1 = m_hash2( key );
128 
129  const uint64 block_idx = (h0 % m_size) / BLOCK_SIZE;
130  block_type block = vector_type( 0u );
131 
132  #if defined(__CUDA_ARCH__)
133  #pragma unroll
134  #endif
135  for (uint64 i = 1; i <= m_k; ++i)
136  {
137  const uint32 r = uint32(h0 + i * h1) % BLOCK_SIZE;
138 
139  const uint32 word = r / WORD_SIZE;
140  const uint32 bit = r & (WORD_SIZE-1);
141 
142  const word_type pattern = (word_type(1u) << bit);
143 
144  or_op( block, word, pattern );
145  }
146  or_op( &m_storage[block_idx], block );
147 }
148 
149 template <
150  typename Hash1, // first hash generator function
151  typename Hash2, // second hash generator function
152  typename Iterator, // storage iterator - must be one of {uint32|uint2|uint4|uint64|uint64_2|uint64_4}
153  typename OrOperator>
154 template <typename Key>
155 bool blocked_bloom_filter<Hash1,Hash2,Iterator,OrOperator>::has(const Key key) const
156 {
157  const uint64 h0 = m_hash1( key );
158  const uint64 h1 = m_hash2( key );
159 
160  const uint64 block_idx = (h0 % m_size) / BLOCK_SIZE;
161  const block_type block = m_storage[block_idx];
162 
163  #if defined(__CUDA_ARCH__)
164  #pragma unroll
165  #endif
166  for (uint64 i = 1; i <= m_k; ++i)
167  {
168  const uint32 r = uint32(h0 + i * h1) % BLOCK_SIZE;
169 
170  const uint32 word = r / WORD_SIZE;
171  const uint32 bit = r & (WORD_SIZE-1);
172 
173  const word_type pattern = (word_type(1u) << bit);
174 
175  if ((comp( block, word ) & pattern) == 0u)
176  return false;
177  }
178  return true;
179 }
180 
181 } // namespace nvbio
Generated on Wed Feb 25 2015 08:41:01 for NVBIO by   doxygen 1.8.4