Peter said:
Hi again,
this time, I want to do some binary searching. Therefore I have declared the
following:
BYTE *buffer; //holds pointer to data to search in
UINT bufferlen; //length in bytes of buffer
BYTE *pattern; //holds pointer to pattern to search for
UINT patternlen; //length of pattern in bytes
Now, I've decided to use _lfind for this searching (I'm not using bsearch,
because AFAIK I'd have to sort the buffer I search in - and as I normally
search in rather small buffers this would decrease my speed significantly -
or am I wrong?).
Binary search requires a sorted array, but _lfind does a linear search, for
which sorting is neither required nor helps. It is indeed true that more
sophisticated algorithms that do well even as input gets large tend to do
worse than straightforward algorithms on small data sets, for varying
definitions of "large" and "small".
But somehow I don't get the correct syntax to call _lfind (perhaps because
I'm a newbie to C). So, could someone show me how to call _lfind with the
parameters from above?
Does the example here help any?
http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vccore98/html/_crt__lfind.asp
However, I don't think you need to use _lfind at all, which viewed as a
drop-in replacement for bsearch, is based on the premise that every element
of the array is a potential match of the search key. (Viewed independently
from bsearch, I'm not sure _lfind has any reason for being.) This is not
really the case for the buffer/pattern data you've presented, for which
every element of the array is a potential match of the start of the search
pattern. Assuming pattern is a literal string, it sounds like you have a
simple string search problem. The length parameters imply the strings aren't
nul-terminated, and if this is the case, you can't use strstr, and you need
to write "memmem" (following the Standard C Library naming conventions),
something like this (untested, and again following C conventions, as you
said you're using C; in C++, you'd want to avoid returning a void* pointer
into a const void* buffer, and you'd use std::search anyway):
void*
memmem(const void* buf, size_t bufLen, const void* pat, size_t patLen)
{
if (patLen != 0 && patLen <= bufLen)
{
const unsigned char* s = (const unsigned char*) buf;
const unsigned char* const sEnd = s+bufLen-patLen;
const unsigned char* const p = (const unsigned char*) pat;
for ( ; s <= sEnd; ++s)
{
if (*s == *p)
{
if (memcmp(s+1, p+1, patLen-1) == 0)
return (void*) s;
}
}
}
return 0;
}
The above is the straightforward linear search, which for small data sets,
is going to be better than more sophisticated approaches like Boyer-Moore,
which require substantial preprocessing. Concerning micro-optimization, it's
a guess whether or not the character-by-character outer loop is better than
memchr and the memcmp call is better than a character-by-character inner
loop. I wouldn't worry about this unless you have profiling data that
suggests it's a genuine issue.
