<html>
<head>
<base href="https://llvm.org/bugs/" />
</head>
<body><table border="1" cellspacing="0" cellpadding="8">
<tr>
<th>Bug ID</th>
<td><a class="bz_bug_link
bz_status_NEW "
title="NEW --- - booyer moore searchers violate algorithmic complexity requirements."
href="https://llvm.org/bugs/show_bug.cgi?id=31462">31462</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>booyer moore searchers violate algorithmic complexity requirements.
</td>
</tr>
<tr>
<th>Product</th>
<td>libc++
</td>
</tr>
<tr>
<th>Version</th>
<td>unspecified
</td>
</tr>
<tr>
<th>Hardware</th>
<td>PC
</td>
</tr>
<tr>
<th>OS</th>
<td>Windows NT
</td>
</tr>
<tr>
<th>Status</th>
<td>NEW
</td>
</tr>
<tr>
<th>Severity</th>
<td>normal
</td>
</tr>
<tr>
<th>Priority</th>
<td>P
</td>
</tr>
<tr>
<th>Component</th>
<td>All Bugs
</td>
</tr>
<tr>
<th>Assignee</th>
<td>unassignedclangbugs@nondot.org
</td>
</tr>
<tr>
<th>Reporter</th>
<td>eric@efcs.ca
</td>
</tr>
<tr>
<th>CC</th>
<td>llvm-bugs@lists.llvm.org, mclow.lists@gmail.com
</td>
</tr>
<tr>
<th>Classification</th>
<td>Unclassified
</td>
</tr></table>
<p>
<div>
<pre>The standard states the required complexity for the boyer_moore and
boyer_moore_horspool searchers as:
<span class="quote">> Complexity: At most (last - first) * (pat_last_ - pat_first_) applications of the predicate</span >
However certain test cases violate this requirement. Specifically when the
input range is smaller than the "pat" range. There are FIXME comments in the
searchers tests which mark these test cases. When this bug gets fixed those
should be fixed as well.
Minimal reproducer:
#include <experimental/algorithm>
#include <experimental/functional>
#include <cassert>
struct count_equal {
static unsigned count;
template <class T>
bool operator()(const T& x, const T& y) const
{++count; return x == y;}
};
unsigned count_equal::count = 0;
int main() {
count_equal::count = 0;
char ia[] = {0, 1, 2, 3, 4, 5};
const unsigned sa = sizeof(ia)/sizeof(ia[0]);
std::experimental::boyer_moore_searcher<char*, std::hash<char>, count_equal>
searcher(ia, ia+sa);
std::experimental::search(ia, ia+1, searcher);
assert(count_equal::count <= sa); // fails
}</pre>
</div>
</p>
<hr>
<span>You are receiving this mail because:</span>
<ul>
<li>You are on the CC list for the bug.</li>
</ul>
</body>
</html>