BDE 4.39.x Production Release
Loading...
Searching...
No Matches
bslstl_boyermoorehorspoolsearcher.h
Go to the documentation of this file.
1/// @file bslstl_boyermoorehorspoolsearcher.h
2///
3/// The content of this file has been pre-processed for Doxygen.
4///
5
6
7// bslstl_boyermoorehorspoolsearcher.h -*-C++-*-
8#ifndef INCLUDED_BSLSTL_BOYERMOOREHORSPOOLSEARCHER
9#define INCLUDED_BSLSTL_BOYERMOOREHORSPOOLSEARCHER
10
11#include <bsls_ident.h>
12BSLS_IDENT("$Id: $")
13
14/// @defgroup bslstl_boyermoorehorspoolsearcher bslstl_boyermoorehorspoolsearcher
15/// @brief Provide an STL-compliant `boyer_moore_horspool_searcher` class.
16/// @addtogroup bsl
17/// @{
18/// @addtogroup bslstl
19/// @{
20/// @addtogroup bslstl_boyermoorehorspoolsearcher
21/// @{
22///
23/// <h1> Outline </h1>
24/// * <a href="#bslstl_boyermoorehorspoolsearcher-purpose"> Purpose</a>
25/// * <a href="#bslstl_boyermoorehorspoolsearcher-classes"> Classes </a>
26/// * <a href="#bslstl_boyermoorehorspoolsearcher-canonical-header"> Canonical Header </a>
27/// * <a href="#bslstl_boyermoorehorspoolsearcher-description"> Description </a>
28/// * <a href="#bslstl_boyermoorehorspoolsearcher-algorithm"> Algorithm </a>
29/// * <a href="#bslstl_boyermoorehorspoolsearcher-iterator-requirements"> Iterator Requirements </a>
30/// * <a href="#bslstl_boyermoorehorspoolsearcher-requirements-for-hash-and-equal"> Requirements for HASH and EQUAL </a>
31/// * <a href="#bslstl_boyermoorehorspoolsearcher-optimizations-for-bslstl-boyermoorehorspoolsearcher"> Optimizations for bslstl::BoyerMooreHorspoolSearcher </a>
32/// * <a href="#bslstl_boyermoorehorspoolsearcher-usage"> Usage </a>
33/// * <a href="#bslstl_boyermoorehorspoolsearcher-example-1-basic-usage"> Example 1: Basic Usage </a>
34/// * <a href="#bslstl_boyermoorehorspoolsearcher-example-2-defining-a-comparator-and-hash"> Example 2: Defining a Comparator and Hash </a>
35/// * <a href="#bslstl_boyermoorehorspoolsearcher-example-3-non-char-searches"> Example 3: Non-char Searches </a>
36/// * <a href="#bslstl_boyermoorehorspoolsearcher-example-4-caching-searcher-objects"> Example 4: Caching Searcher Objects </a>
37/// * <a href="#bslstl_boyermoorehorspoolsearcher-the-problem"> The Problem </a>
38/// * <a href="#bslstl_boyermoorehorspoolsearcher-design-choices"> Design Choices </a>
39/// * <a href="#bslstl_boyermoorehorspoolsearcher-steps"> Steps </a>
40///
41/// # Purpose {#bslstl_boyermoorehorspoolsearcher-purpose}
42/// Provide an STL-compliant @ref boyer_moore_horspool_searcher class.
43///
44/// # Classes {#bslstl_boyermoorehorspoolsearcher-classes}
45///
46/// - bsl::boyer_moore_horspool_searcher: class template to search via BMH
47/// - bslstl::BoyerMooreHorspoolSearcher: class template to search via BMH
48///
49/// # Canonical Header {#bslstl_boyermoorehorspoolsearcher-canonical-header}
50/// bsl_functional.h
51///
52/// @see bslstl_defaultsearcher
53///
54/// # Description {#bslstl_boyermoorehorspoolsearcher-description}
55/// This component defines two class templates,
56/// `bsl::boyer_moore_horspool_searcher` and
57/// `bslstl::BoyerMooreHorspoolSearcher`. Both are compliant with section
58/// `[func.search.bmh]` of the C++ Standard (C++17 and later).
59///
60/// `bsl::boyer_moore_horspool_searcher` is strictly limited to the Standard and
61/// is provided for clients for whom standard compliance is a priority.
62/// `bslslt::BoyerMoreHorspoolSearcher` provides several accessors that are not
63/// mentioned in the Standard. Moreover, `bslslt::BoyerMoreHorspoolSearcher` is
64/// "plumbed" for BDE allocators and can be used with BDE standard containers
65/// whereas the compliant strict class always uses the currently installed
66/// default allocator. See {Example 4} below.
67///
68/// Except where there is a relevant difference, both are described below as if
69/// they were one.
70///
71/// This class has several template parameters:
72///
73/// `RNDACC_ITR_NEEDLE`:
74/// The type used to specify (on construction) the range of values
75/// being sought (the "needle").
76///
77/// `HASH`:
78/// The functor type used to hash metadata for the unique values of
79/// the needle. See {Requirements for `HASH` and `EQUAL`}.
80///
81/// `EQUAL`:
82/// The functor type used to compare values when storing/accessing needle
83/// metadata. See {Requirements for `HASH` and `EQUAL`}.
84///
85/// The class also provides a functor-style interface that accepts two iterators
86/// that define the range of values to be searched (the "haystack"). Once
87/// constructed, a single searcher object can be re-used to search multiple
88/// haystacks (for the same needle value).
89///
90/// The iterators defining the haystack need not be of the same type as those
91/// that define the needle. Moreover, the search method of the searcher can be
92/// overloaded for an arbitrary number of different haystack iterators (subject
93/// to {Iterator Requirements}).
94///
95/// ## Algorithm {#bslstl_boyermoorehorspoolsearcher-algorithm}
96///
97///
98/// The search algorithm used is an implementation of the well-known Boyer,
99/// Moore, Horspool (BMH) Algorithm for string matching (see
100/// https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm).
101/// In the typical case, this algorithm offers complexity of `O(N)` for a
102/// haystack of length `N`.
103///
104/// ## Iterator Requirements {#bslstl_boyermoorehorspoolsearcher-iterator-requirements}
105///
106///
107/// The two independent iterators types associated with this class -- one
108/// defining the needle, the other defining the haystack -- must meet the
109/// requirements of *RandomAccessIterator*.
110///
111/// Additionally:
112/// * The iterators can be constant.
113/// * When dereferenced, both iterator types must refer to the same value type.
114///
115/// The operations of either of the iterator types are allowed to throw
116/// exceptions.
117///
118/// Iterators defining needles are required to remain valid as long as the
119/// searcher object might be used.
120///
121/// ## Requirements for HASH and EQUAL {#bslstl_boyermoorehorspoolsearcher-requirements-for-hash-and-equal}
122///
123///
124/// The comparer class, `EQUAL`, must meet the requirements of
125/// *BinaryPredicate*:
126/// * The class defines an `operator()` method that, given a
127/// *RandomAccessIterator', `iterator`, can be invoked as
128/// `operator()(*iterator, *iterator)`.
129/// * The return value must be contextually convertible to `bool`.
130/// * The supplied iterators can be constant.
131/// * The class must be copyable.
132///
133/// Comparer classes are allowed to throw exceptions.
134///
135/// The behavior is undefined unless two values that are deemed equal by the
136/// `EQUAL` functor generate the same value by the `HASH` functor. That is:
137/// @code
138/// true == searcher.equal()(a, b);
139/// @endcode
140/// implies:
141/// @code
142/// searcher.hash()(a) == searcher.hash()(b);
143/// @endcode
144///
145/// ## Optimizations for bslstl::BoyerMooreHorspoolSearcher {#bslstl_boyermoorehorspoolsearcher-optimizations-for-bslstl-boyermoorehorspoolsearcher}
146///
147///
148/// This implementation handles needle metadata using a fixed size array when
149/// the `value_type` is `char` (either `signed` or `unsigned` flavors). For
150/// needles of typical size, this choice results in somewhat more memory use
151/// than it would have if some dynamically sized container were used; however,
152/// the faster access during searches warrants the tradeoff.
153///
154/// ## Usage {#bslstl_boyermoorehorspoolsearcher-usage}
155///
156///
157/// In this section we show the intended usage of this component.
158///
159/// ### Example 1: Basic Usage {#bslstl_boyermoorehorspoolsearcher-example-1-basic-usage}
160///
161///
162/// The problem of searching a sequence of characters for a particular
163/// sub-sequence arises in many applications. For example, one might need to
164/// know if some document contains a particular word of interest. For example,
165/// suppose we would like to know the first occurrence of the word "United" in
166/// the Declaration of Independence (of the United States):
167///
168/// First, we obtain the text of document and word of interest as sequences of
169/// `char` values.
170/// @code
171/// const char document[] =
172/// " IN CONGRESS, July 4, 1776.\n" // 28
173/// "\n" // 1
174/// " The unanimous Declaration of the thirteen united States of America,\n"
175/// //----^----|----^----|----^----|----^----|---- // 44
176/// // // --
177/// // // 73rd character
178/// //
179/// "\n"
180/// // ...
181/// " declare, That these United Colonies are, and of Right ought to be\n"
182/// // ...
183/// "Honor.";
184///
185/// const char *word = "United";
186/// @endcode
187/// Then, we create a @ref default_searcher object (a functor) using the given
188/// `word`:
189/// @code
190/// bsl::boyer_moore_horspool_searcher<const char *> searchForUnited(
191/// word,
192/// word
193/// + bsl::strlen(word));
194/// @endcode
195/// Notice that no equality comparison functor was specified so
196/// `searchForUnited` will use `bsl::equal_to<char>` by default.
197///
198/// Now, we invoke our functor, specifying the range of the document to be
199/// searched:
200/// @code
201/// bsl::pair<const char *, const char *> result = searchForUnited(
202/// document,
203/// document
204/// + sizeof document);
205///
206/// bsl::size_t offset = result.first - document;
207///
208/// assert(120 == offset);
209/// assert(static_cast<bsl::size_t>(result.second - result.first)
210/// == bsl::strlen(word));
211/// @endcode
212/// Finally, we notice that the search correctly ignored the appearance of the
213/// word "united" (all lower case) in the second sentence.
214///
215/// {@ref bslstl_defaultsearcher |Example 1} shows how the same problem is addressed using
216/// `bsl::default_searcher`.
217///
218/// ### Example 2: Defining a Comparator and Hash {#bslstl_boyermoorehorspoolsearcher-example-2-defining-a-comparator-and-hash}
219///
220///
221/// As seen in {Example 1} above, the default equality comparison functor is
222/// case sensitive. If one needs case *in*-sensitive searches, a non-default
223/// equality comparison class *and* a non-default hash functor must be
224/// specified.
225///
226/// First, define (at file scope if using a pre-C++11 compiler) an equality
227/// comparison class that provides the required functor interface:
228/// @code
229/// struct MyCaseInsensitiveCharComparer {
230/// bool operator()(const char& a, const char& b) const {
231/// return bsl::tolower(a) == bsl::tolower(b);
232/// }
233/// };
234/// @endcode
235/// Then, define (again at file scope, if pre-C++11), a hash functor so that two
236/// values, irrespective of their case, hash to the same value:
237/// @code
238/// struct MyCaseInsensitiveCharHasher {
239/// bool operator()(const char& value) const {
240/// static bsl::hash<char> s_hash;
241/// return s_hash(static_cast<char>(bsl::tolower(value)));
242/// }
243/// };
244/// @endcode
245/// Now, specify `bsl::boyer_moore_horspool_searcher` type for and create a
246/// searcher object to search for `word`:
247/// @code
248/// bsl::boyer_moore_horspool_searcher<const char *,
249/// MyCaseInsensitiveCharHasher,
250/// MyCaseInsensitiveCharComparer>
251/// searchForUnitedInsensitive(
252/// word,
253/// word
254/// + bsl::strlen(word));
255/// @endcode
256/// Note that the new searcher object will use defaulted constructed
257/// `MyCaseInsensitiveCharHasher` and `MyCaseInsensitiveCharComparer` classes.
258/// If stateful functors are required such objects can be passed in the optional
259/// constructor arguments.
260///
261/// Now, we invoke our searcher functor, specifying that the same document
262/// searched in {Example 1}:
263/// @code
264/// bsl::pair<const char *, const char *> resultInsensitive =
265/// searchForUnitedInsensitive(
266/// document,
267/// document
268/// + sizeof document);
269///
270/// bsl::size_t offsetInsensitive = resultInsensitive.first - document;
271///
272/// assert( 72 == offsetInsensitive);
273/// assert(static_cast<bsl::size_t>(resultInsensitive.second
274/// - resultInsensitive.first)
275/// == bsl::strlen(word));
276/// @endcode
277/// Finally, we find the next occurrence of `word` by *reusing* the same
278/// searcher object, this time instructing it to begin its search just after the
279/// previous occurrence of `word` was found:
280/// @code
281/// resultInsensitive = searchForUnitedInsensitive(resultInsensitive.second,
282/// document + sizeof document);
283///
284/// offsetInsensitive = resultInsensitive.first - document;
285///
286/// assert(120 == offsetInsensitive);
287/// assert(static_cast<bsl::size_t>(resultInsensitive.second
288/// - resultInsensitive.first)
289/// == bsl::strlen(word));
290/// @endcode
291///
292/// {@ref bslstl_defaultsearcher |Example 2} shows how the same problem is addressed using
293/// `bsl::default_searcher`.
294///
295/// ### Example 3: Non-char Searches {#bslstl_boyermoorehorspoolsearcher-example-3-non-char-searches}
296///
297///
298/// The BMH searcher class template is not constrained to searching for `char`
299/// values. Searches can be done on other types (see {Iterator Requirements}).
300/// Moreover the container of the sequence being sought (the "needle") need not
301/// the same as the sequence being searched (the "haystack").
302///
303/// Suppose one has data from an instrument that reports `float` values and that
304/// inserts the sequence `{ FLT_MAX, FLT_MIN, FLT_MAX }` as a marker for the
305/// start and end of a test run. We can assume the probably of the instrument
306/// reporting this sequence as readings is negligible and that data reported
307/// outside of the test runs is random noise. Here is how we can search for the
308/// first test run data in the data sequence.
309///
310/// First, we create a representation of the sequence that denotes the limit of
311/// a test run.
312/// @code
313/// const float markerSequence[] = { FLT_MAX , FLT_MIN , FLT_MAX };
314/// const bsl::size_t markerSequenceLength = sizeof markerSequence
315/// / sizeof *markerSequence;
316/// @endcode
317/// Next, we obtain the data to be searched. (In this example, we will use
318/// simulated data.)
319/// @code
320/// bsl::vector<float> data; // Container provides random access iterators.
321/// doTestRun(&data);
322/// @endcode
323/// Then, we define and create our searcher object:
324/// @code
325/// bsl::boyer_moore_horspool_searcher<const float *>
326/// searchForMarker(markerSequence,
327/// markerSequence
328/// + markerSequenceLength);
329/// @endcode
330/// Notice that no equality comparison functor was specified so
331/// `searchForMarker` will use `bsl::equal_to<float>` by default.
332///
333/// Now, we invoke our searcher on the instrument data.
334/// @code
335/// typedef bsl::vector<float>::const_iterator DataConstItr;
336///
337/// const bsl::pair<DataConstItr, DataConstItr> notFound(data.cend(),
338/// data.cend());
339///
340/// bsl::pair<DataConstItr, DataConstItr> markerPosition = searchForMarker(
341/// data.cbegin(),
342/// data.cend());
343///
344/// assert(notFound != markerPosition);
345///
346/// DataConstItr startOfTestRun = markerPosition.second;
347/// @endcode
348/// Finally, we locate the marker of the end of the first test run and pass the
349/// location of the first test run data to some other function for processing.
350/// @code
351/// markerPosition = searchForMarker(markerPosition.second, data.cend());
352///
353/// assert(notFound != markerPosition);
354///
355/// DataConstItr endOfTestRun = markerPosition.first;
356///
357/// processTestRun(startOfTestRun, endOfTestRun);
358/// @endcode
359/// {@ref bslstl_defaultsearcher |Example 3} shows how the same problem is addressed
360/// using `bsl::default_searcher`. Notice that other example uses `data` from a
361/// container that provides bidirectional iterators (and forward iterators would
362/// have sufficed), whereas here random access iterators are required.
363///
364/// ### Example 4: Caching Searcher Objects {#bslstl_boyermoorehorspoolsearcher-example-4-caching-searcher-objects}
365///
366///
367/// The construction of `bsl::boyer_moore_horspool_searcher` objects is small
368/// (the needle must be scanned, meta-data calculated, and results saved) but
369/// can be non-neglibible when one needs a great number of them. When there is
370/// a reasonable chance that one will have to repeat a given search, it can be
371/// worthwhile to cache the searcher objects for reuse.
372///
373/// #### The Problem {#bslstl_boyermoorehorspoolsearcher-the-problem}
374///
375///
376/// Suppose we have a long list of names, each consisting of a given name (first
377/// name) and a surname (last name), and that we wish to identify instances of
378/// reduplication of the given name in the surname. That is, we want to
379/// identify the cases where the given name is a *case-insensitive* substring of
380/// the surname. Examples include "Durand Durand", "James Jameson", "John St.
381/// John", and "Jean Valjean". In this example we will not accept nicknames and
382/// other approximate name forms as matches (e.g., "Joe Joseph", "Jack
383/// Johnson").
384///
385/// Since we want to perform our task as efficiently as possible, and since we
386/// expect many entries to have common given names (e.g., "John"), we decide to
387/// create a cache of searcher objects for those first names so they need not be
388/// reconstructed for each search of a surname.
389///
390/// #### Design Choices {#bslstl_boyermoorehorspoolsearcher-design-choices}
391///
392///
393/// To implement our cache we will use a `bsl::unordered_map` container.
394/// Allocating types must meet certain requirements to work properly with
395/// allocator-enabled containers such as `bsl::unordered_map`.
396/// `bsl::boyer_moore_horspool_searcher` does not, so we will use
397/// `bslstl::BoyerMooreHorspoolSearcher`, which does.
398///
399/// To clarify exposition, our cache will have the simple policy of retaining
400/// searcher objects indefinitely and ignore the real-world concern that our
401/// cache may grow so large that the search time exceeds construction time.
402/// Also, we will forgo techniques that might minimize the number of times data
403/// is copied.
404///
405/// #### Steps {#bslstl_boyermoorehorspoolsearcher-steps}
406///
407///
408/// First, we define our cache class:
409/// @code
410/// // ====================================
411/// // class MyCaseInsensitiveSearcherCache
412/// // ====================================
413///
414/// class MyCaseInsensitiveSearcherCache {
415///
416/// // TYPES
417/// public:
418/// typedef bslstl::BoyerMooreHorspoolSearcher<
419/// bsl::string::const_iterator,
420/// MyCaseInsensitiveCharHasher,
421/// MyCaseInsensitiveCharComparer>
422/// Searcher;
423/// // PRIVATE TYPES
424/// private:
425/// typedef bsl::unordered_map<bsl::string, Searcher> Map;
426///
427/// // DATA
428/// Map d_map;
429///
430/// // PRIVATE MANIPULATORS
431///
432/// /// Insert into this cache a key-value pair where the key is the
433/// /// specified `key` and the value is a `Searcher` object created to
434/// /// seek the needle specified by the key part. Note that this
435/// /// arrangement guarantees that the iterators used by this cached
436/// /// searcher object remain valid for the life of the searcher
437/// /// object.
438/// const Searcher& insertSearcher(const bsl::string& key);
439///
440/// public:
441/// // CREATORS
442///
443/// /// Create an empty `MyCaseInsensitiveSearcherCache` object.
444/// /// Optionally specify a `basicAllocator` used to supply memory. If
445/// /// `basicAllocator` is 0, the currently installed default
446/// /// allocator is used.
447/// explicit MyCaseInsensitiveSearcherCache(bslma::Allocator
448/// *basicAllocator = 0);
449///
450/// // MANIPULATORS
451///
452/// /// Return a `const`-reference to the cached server that can do a
453/// /// case-insensitive search for the specified `needle`. If such a
454/// /// searcher does not exist in the cache on entry, such a searcher
455/// /// is constructed, added to the cache, and returned (by
456/// /// `const`-reference).
457/// const Searcher& getSearcher(const char *needle);
458///
459/// // ACCESSORS
460///
461/// /// Return the number of searcher objects in this cache.
462/// bsl::size_t numSearchers() const;
463/// };
464/// @endcode
465/// Notice (see the `typedef` for `Searcher`) that we reuse the hash functor,
466/// `MyCaseInsensitiveCharHasher`, and equality comparison functor,
467/// `MyCaseInsensitiveCharComparer`, that were defined in {Example 2}.
468///
469/// Note that `MyCaseInsensitiveSearcherCache` itself is an allocating type.
470/// If we needed to make it compatible with BDE containers (e.g., to allow a
471/// cache of caches) a few additional features are needed. As we have no such
472/// need, those features are deferred.
473///
474/// Then, we implement the constructor:
475/// @code
476/// // ------------------------------------
477/// // class MyCaseInsensitiveSearcherCache
478/// // ------------------------------------
479///
480/// // CREATORS
481/// MyCaseInsensitiveSearcherCache::
482/// MyCaseInsensitiveSearcherCache(bslma::Allocator *basicAllocator)
483/// : d_map(basicAllocator)
484/// {
485/// }
486/// @endcode
487///
488/// Notice that `basicAllocator` is simply forwarded to `d_map`.
489///
490/// Next, we implement the public methods:
491/// @code
492/// // MANIPULATORS
493/// const
494/// MyCaseInsensitiveSearcherCache::Searcher&
495/// MyCaseInsensitiveSearcherCache::getSearcher(const char *needle)
496/// {
497/// bsl::string key(needle);
498/// Map::iterator findResult = d_map.find(key);
499///
500/// if (d_map.end() == findResult) {
501/// return insertSearcher(key); // RETURN
502/// } else {
503/// return findResult->second; // RETURN
504/// }
505/// }
506///
507/// // ACCESSORS
508/// bsl::size_t MyCaseInsensitiveSearcherCache::numSearchers() const
509/// {
510/// return d_map.size();
511/// }
512/// @endcode
513/// Then, to complete our class, we implement the cache class private method:
514/// @code
515/// // PRIVATE MANIPULATORS
516/// const
517/// MyCaseInsensitiveSearcherCache::Searcher&
518/// MyCaseInsensitiveSearcherCache::insertSearcher(const bsl::string& key)
519/// {
520/// Searcher dummy(key.begin(), key.begin()); // to be overwritten
521/// Map::value_type value(key, dummy);
522///
523/// bsl::pair<Map::iterator, bool> insertResult = d_map.insert(value);
524/// assert(true == insertResult.second);
525///
526/// Map::iterator iterator = insertResult.first;
527///
528/// iterator->second = Searcher(iterator->first.begin(),
529/// iterator->first.end());
530/// return iterator->second;
531/// }
532/// @endcode
533/// Notice creating our element is a two step process. First, we insert the key
534/// with an arbitrary "dummy" searcher. Once the key (a string) exists in the
535/// map (at an address that is stable for the life of the map) we create a
536/// searcher object that refers to that key string for its search sequence, and
537/// overwrite the "dummy" part of previously inserted element.
538///
539/// Now, we show how the searcher object cache can be used. In this example, a
540/// fixed array represents our source of name entries, in random order:
541/// @code
542/// struct {
543/// const char *d_givenName_p;
544/// const char *d_surname_p;
545/// } DATA[] = {
546/// // GIVEN SURNAME
547/// // -------- ------------
548/// { "Donald" , "McDonald" }
549/// , { "John" , "Johnson" }
550/// , { "John" , "Saint Johns" }
551/// , { "Jon" , "Literjon" }
552/// , { "Jean" , "Valjean" }
553/// , { "James" , "Jameson" }
554/// , { "Will" , "Freewill" }
555/// , { "John" , "Johns" }
556/// , { "John" , "John" }
557/// , { "John" , "Jones" }
558/// , { "J'onn" , "J'onzz" }
559/// , { "Donald" , "Donalds" }
560/// , { "Donald" , "Mac Donald" }
561/// , { "William", "Williams" }
562/// , { "Durand" , "Durand" }
563/// , { "John" , "Johnstown" }
564/// , { "Major" , "Major" }
565/// , { "Donald" , "MacDonald" }
566/// , { "Patrick", "O'Patrick" }
567/// , { "Chris", "Christie" }
568/// , { "Don", "London" }
569/// // ...
570/// , { "Ivan" , "Ivanovich" }
571/// };
572///
573/// bsl::size_t NUM_NAMES = sizeof DATA / sizeof *DATA;
574///
575/// typedef bsl::pair<const char *, const char *> Result;
576///
577/// MyAllocator myAllocator;
578/// MyCaseInsensitiveSearcherCache searcherCache(&myAllocator);
579/// bsl::string output;
580///
581/// for (bsl::size_t ti = 0; ti < NUM_NAMES; ++ti) {
582/// const char * const givenName = DATA[ti].d_givenName_p;
583/// const char * const surname = DATA[ti].d_surname_p;
584///
585/// const MyCaseInsensitiveSearcherCache::Searcher& searcher =
586/// searcherCache.getSearcher(givenName);
587///
588/// assert(&myAllocator == searcher.allocator());
589/// @endcode
590/// Notice that each searcher object in the cache (correctly) uses the same
591/// allocator as we specified for the cache itself.
592///
593/// The rest of the application:
594/// @code
595/// const Result result = searcher(surname,
596/// surname + bsl::strlen(surname));
597///
598/// const Result notFound = bsl::make_pair(surname + bsl::strlen(surname),
599/// surname + bsl::strlen(surname));
600///
601/// char buffer[32];
602///
603/// if (notFound == result) {
604/// sprintf(buffer, "ng: %-10s %-11s\n", givenName, surname);
605/// } else {
606/// sprintf(buffer, "OK: %-10s %-11s\n", givenName, surname);
607/// }
608///
609/// output.append(buffer);
610/// }
611/// @endcode
612/// Finally, we examine the collected `output` and confirm that our code is
613/// properly identifying the names of interest.
614/// @code
615/// assert(0 == bsl::strcmp(output.c_str(),
616/// "OK: Donald McDonald \n"
617/// "OK: John Johnson \n"
618/// "OK: John Saint Johns\n"
619/// "OK: Jon Literjon \n"
620/// "OK: Jean Valjean \n"
621/// "OK: James Jameson \n"
622/// "OK: Will Freewill \n"
623/// "OK: John Johns \n"
624/// "OK: John John \n"
625/// "ng: John Jones \n"
626/// "ng: J'onn J'onzz \n"
627/// "OK: Donald Donalds \n"
628/// "OK: Donald Mac Donald \n"
629/// "OK: William Williams \n"
630/// "OK: Durand Durand \n"
631/// "OK: John Johnstown \n"
632/// "OK: Major Major \n"
633/// "OK: Donald MacDonald \n"
634/// "OK: Patrick O'Patrick \n"
635/// "OK: Chris Christie \n"
636/// "OK: Don London \n"
637/// "OK: Ivan Ivanovich \n"));
638///
639/// assert(searcherCache.numSearchers() < NUM_NAMES);
640/// @endcode
641/// @}
642/** @} */
643/** @} */
644
645/** @addtogroup bsl
646 * @{
647 */
648/** @addtogroup bslstl
649 * @{
650 */
651/** @addtogroup bslstl_boyermoorehorspoolsearcher
652 * @{
653 */
654
655#include <bslscm_version.h>
656
657#include <bslstl_array.h>
658#include <bslstl_equalto.h>
659#include <bslstl_hash.h>
660#include <bslstl_iterator.h>
661#include <bslstl_pair.h>
662#include <bslstl_unorderedmap.h>
663
664#include <bslma_allocator.h>
665#include <bslma_default.h>
666
667#include <bslmf_conditional.h>
668#include <bslmf_isbitwisecopyable.h>
669#include <bslmf_isbitwiseequalitycomparable.h>
670#include <bslmf_issame.h>
671#include <bslmf_movableref.h>
672
673#include <bsls_assert.h>
674#include <bsls_keyword.h>
675#include <bsls_libraryfeatures.h>
676#include <bsls_performancehint.h>
677
678#include <cstring> // 'memcpy'
679
680#include <limits.h> // 'UCHAR_MAX'
681
682
683namespace bslstl {
684
685 // ========================================
686 // class BoyerMooreHorspoolSearcher_CharImp
687 // ========================================
688
689/// This class template implements the same interfaces as the
690/// `BoyerMooreHorspoolSearcher_GeneralImp`; however, the implementation is
691/// specialized for a `value_type` of `char`. Notably, needle metadata is
692/// stored/accessed from a fixed size array, not a dynamically-sized
693/// container.
694///
695/// See @ref bslstl_boyermoorehorspoolsearcher
696template <class RNDACC_ITR_NEEDLE,
697 class HASH,
698 class EQUAL>
699class BoyerMooreHorspoolSearcher_CharImp {
700
701 public:
702 // TYPES
703
704 /// the type of the values that can be obtained by dereferencing a
705 /// `RNDACC_ITR_NEEDLE`
706 typedef typename bsl::iterator_traits<RNDACC_ITR_NEEDLE>::value_type
707 value_type;
708
709 /// a signed type that can describe the distance between
710 /// `RNDACC_ITR_NEEDLE` iterators
711 typedef typename bsl::iterator_traits<RNDACC_ITR_NEEDLE>::difference_type
712 difference_type;
713
714 private:
715 // PRIVATE TYPES
716
717 /// This `typedef` is a convenient alias for the utility associated with
718 /// movable references.
719 typedef BloombergLP::bslmf::MovableRefUtil MoveUtil;
720
721 typedef unsigned char ShortNeedleSkipType;
722 // 'd_needleLength <= UCHAR_MAX'
723
724 typedef difference_type LongNeedleSkipType;
725 // 'UCHAR_MAX < d_needleLength'
726
727 typedef bsl::array<ShortNeedleSkipType, UCHAR_MAX + 1>
728 ShortNeedleSkipArray;
729 typedef bsl::array< LongNeedleSkipType, UCHAR_MAX + 1>
730 LongNeedleSkipArray;
731
732 // PRIVATE MANIPULATORS
733
734 /// Install in this object a table copied from the specified `object`.
735 ///
736 /// \pre The behavior is undefined unless `0 == d_table_p` (on entry) and
737 /// `d_needleLength` has been initialized.
738 void privateInstallNewTable(
739 const BoyerMooreHorspoolSearcher_CharImp& object);
740
741 /// Copy the table of the specified `object` over the table of this object.
742 ///
743 /// \pre The behavior is undefined unless this object has a table
744 /// and `privateUseShortNeedleOptimization()` returns the same value for
745 /// `object` and for this object.
746 void privateInstallTableOverOld(
747 const BoyerMooreHorspoolSearcher_CharImp& object);
748
749 /// Replace in an exception-safe manner this object's table with a copy
750 /// of the table of the specified `object`. This object's table (on
751 /// entry), if any, is deleted.
752 void privateInstallMismatchedTable(
753 const BoyerMooreHorspoolSearcher_CharImp& object);
754
755 /// Destroy and deallocate the `d_table_p` member of this object, and
756 /// set `d_table_p` to 0.
757 void privateDeleteTable();
758
759 // PRIVATE ACCESSORS
760
761 /// Set the specified `object`, the source object of a move operation,
762 /// to a (valid) state that is not specified to users.
763 ///
764 /// \pre The behavior is undefined if `this == object`.
765 void privateSetPostMoveState(BoyerMooreHorspoolSearcher_CharImp *object)
766 const;
767
768 /// Return `true` if this instantiation should used the "short needle
769 /// (space) optimization", and `false` otherwise.
770 ///
771 /// \pre The behavior is undefined unless `d_needleLength` has been initialized.
772 bool privateUseShortNeedleOptimization() const;
773
774 /// Return `true` if the specified `object` has the same value for
775 /// `privateUseShortNeedleOptimization()` as this object, and `false`
776 /// otherwise.
777 bool privateHasSameNeedleOptimization(
778 const BoyerMooreHorspoolSearcher_CharImp& object)
779 const;
780
781 // DATA
782 std::size_t d_needleLength;
783 BloombergLP::bslma::Allocator *d_allocator_p;
784 void *d_table_p;
785
786 public:
787 // CREATORS
788
789 /// Create a `BoyerMooreHorspoolSearcher_CharImp` object for the
790 /// sequence of `char` values in the specified range
791 /// `[needleFirst, needlelast)`. This implementation is invoked when
792 /// the specified `hash` is `bsl::hash<char>` and the specified `equal`
793 /// is `bsl::equal_to<char>`. Neither functor is used because for the
794 /// special case of `char` the needle metadata is maintained in a fixed
795 /// size array (256 elements). As always, the specified
796 /// `basicAllocator` is used to supply memory. If `basicAllocator` is
797 /// 0, the currently installed default allocator is used.
798 ///
799 /// \pre The behavior is undefined unless `needleFirst` can be advanced to `needleLast`.
800 BoyerMooreHorspoolSearcher_CharImp(
801 RNDACC_ITR_NEEDLE needleFirst,
802 RNDACC_ITR_NEEDLE needleLast,
803 HASH hash,
804 EQUAL equal,
805 BloombergLP::bslma::Allocator *basicAllocator);
806
807 /// Create a `BoyerMooreHorspoolSearcher_CharImp` object having same
808 /// state as the specified `original` object. The allocator of
809 /// `original` is propagated to the new object.
810 BoyerMooreHorspoolSearcher_CharImp(
811 const BoyerMooreHorspoolSearcher_CharImp& original);
812
813 /// Create a `BoyerMooreHorspoolSearcher_CharImp` object having same
814 /// state as the specified `original` object by moving (in constant
815 /// time) the state of the original object to the new object. The
816 /// allocator of `original` is propagated to the new object. The
817 /// `original` object is left in an unspecified (valid) state.
818 BoyerMooreHorspoolSearcher_CharImp(
819 BloombergLP::bslmf::MovableRef<BoyerMooreHorspoolSearcher_CharImp>
820 original)
821 BSLS_KEYWORD_NOEXCEPT;
822
823 /// Create a `BoyerMooreHorspoolSearcher_CharImp` object having the same
824 /// state as the specified `original` object and that uses the specified
825 /// `basicAllocator` to supply memory. If `basicAllocator` is 0, the
826 /// currently installed default allocator is used.
827 BoyerMooreHorspoolSearcher_CharImp(
828 const BoyerMooreHorspoolSearcher_CharImp& original,
829 BloombergLP::bslma::Allocator *basicAllocator);
830
831 /// Create a `BoyerMooreHorspoolSearcher_CharImp` object having the same
832 /// state as the specified `original` object and that uses the specified
833 /// `basicAllocator` to supply memory. The state of `original` is moved
834 /// (in constant time) to the new searcher if
835 /// `basicAllocator == original.allocator()`, and is copied using
836 /// `basicAllocator` otherwise. If `basicAllocator` is 0, the currently
837 /// installed default allocator is used. The `original` object is left
838 /// in an unspecified (valid) state.
839 BoyerMooreHorspoolSearcher_CharImp(
840 BloombergLP::bslmf::MovableRef<BoyerMooreHorspoolSearcher_CharImp>
841 original,
842 BloombergLP::bslma::Allocator *basicAllocator);
843
844 /// Destroy this object;
845 ~BoyerMooreHorspoolSearcher_CharImp();
846
847 // MANIPULATORS
848
849 /// Assign to this object the state of the specified `rhs` object, and
850 /// return a non-`const` reference to this searcher object.
851 BoyerMooreHorspoolSearcher_CharImp& operator=(
852 const BoyerMooreHorspoolSearcher_CharImp& rhs);
853
854 /// Assign to this object the state of the specified `rhs` object and
855 /// return a non-`const` reference to this searcher. The `rhs` is left
856 /// in an unspecified (valid) state.
857 BoyerMooreHorspoolSearcher_CharImp& operator=(
858 BloombergLP::bslmf::MovableRef<BoyerMooreHorspoolSearcher_CharImp>
859 rhs);
860
861 // ACCESSORS
862
863 /// Return the number of positions to advance the search in the haystack
864 /// when the specified `value` is found in the rightmost position of the
865 /// current (unsuccessful) match attempt.
866 difference_type badCharacterSkip(const value_type& value) const;
867
868 /// Return the hashing functor supplied on construction.
869 HASH hash() const;
870
871 /// Return the equality comparison functor supplied on construction.
872 EQUAL equal() const;
873
874 /// Return the allocator supplied on construction.
875 BloombergLP::bslma::Allocator *allocator() const;
876};
877
878 // ===========================================
879 // class BoyerMooreHorspoolSearcher_GeneralImp
880 // ===========================================
881
882/// This class template implements the same interfaces as the
883/// `BoyerMooreHorspoolSearcher_CharImp` for arbitrary `value_type`.
884///
885/// See @ref bslstl_boyermoorehorspoolsearcher
886template <class RNDACC_ITR_NEEDLE,
887 class HASH,
888 class EQUAL>
889class BoyerMooreHorspoolSearcher_GeneralImp {
890
891 // PUBLIC TYPES
892 public:
893 typedef typename bsl::iterator_traits<RNDACC_ITR_NEEDLE>::value_type
894 value_type;
895
896 typedef typename bsl::iterator_traits<RNDACC_ITR_NEEDLE>::difference_type
897 difference_type;
898 private:
899 // PRIVATE TYPES
900 typedef bsl::unordered_map<value_type, // key
901 difference_type, // value
902 HASH,
903 EQUAL> Map; // skip-on-mismatch "table"
904
905 /// This `typedef` is a convenient alias for the utility associated with
906 /// movable references.
907 typedef BloombergLP::bslmf::MovableRefUtil MoveUtil;
908
909 // DATA
910 difference_type d_needleLength;
911 Map d_map;
912
913 public:
914 // CREATORS
915
916 /// Create a `BoyerMooreHorspoolSearcher_GeneralImp` object for the
917 /// sequence of `value_type` values in the specified range
918 /// `[needleFirst, needlelast)`. The specified `hash` and `equal`
919 /// functors are used to store/access metadata associated with the
920 /// needle. See {Requirements for `HASH` and `EQUAL`}. Optionally
921 /// specify a `basicAllocator` used to supply memory. If
922 /// `basicAllocator` is 0, the currently installed default allocator is used.
923 ///
924 /// \pre The behavior is undefined unless `needleFirst` can be
925 /// advanced to `needleLast`.
926 BoyerMooreHorspoolSearcher_GeneralImp(
927 RNDACC_ITR_NEEDLE needleFirst,
928 RNDACC_ITR_NEEDLE needleLast,
929 HASH hash,
930 EQUAL equal,
931 BloombergLP::bslma::Allocator *basicAllocator);
932
933 /// Create a `BoyerMooreHorspoolSearcher_GeneralImp` object having same
934 /// state as the specified `original` object. The allocator of
935 /// `original` is propagated to the new object.
936 BoyerMooreHorspoolSearcher_GeneralImp(
937 const BoyerMooreHorspoolSearcher_GeneralImp& original);
938
939 /// Create a `BoyerMooreHorspoolSearcher_GeneralImp` object having same
940 /// state as the specified `original` object by moving (in constant
941 /// time) the state of the original object to the new object. The
942 /// allocator of `original` is propagated to the new object. The
943 /// `original` object is left in an unspecified (valid) state.
944 BoyerMooreHorspoolSearcher_GeneralImp(
945 BloombergLP::bslmf::MovableRef<BoyerMooreHorspoolSearcher_GeneralImp>
946 original)
947 BSLS_KEYWORD_NOEXCEPT;
948
949 /// Create a `BoyerMooreHorspoolSearcher_GeneralImp` object having the
950 /// same state as the specified `original` object. Optionally specify a
951 /// `basicAllocator` used to supply memory. If `basicAllocator` is 0,
952 /// the currently installed default allocator is used.
953 BoyerMooreHorspoolSearcher_GeneralImp(
954 const BoyerMooreHorspoolSearcher_GeneralImp& original,
955 BloombergLP::bslma::Allocator *basicAllocator);
956
957 /// Create a `BoyerMooreHorspoolSearcher_GeneralImp` object having same
958 /// state as the specified `original` object and that uses
959 /// `basicAllocator` to supply memory. The state of `original` is moved
960 /// (in constant time) to the new searcher if
961 /// `basicAllocator == original.allocator()`, and is copied using
962 /// `basicAllocator` otherwise. The `original` object is left in an
963 /// unspecified (valid) state.
964 BoyerMooreHorspoolSearcher_GeneralImp(
965 BloombergLP::bslmf::MovableRef<BoyerMooreHorspoolSearcher_GeneralImp>
966 original,
967 BloombergLP::bslma::Allocator *basicAllocator);
968
969 // MANIPULATORS
970
971 /// Assign to this object the state of the specified `rhs` object, and
972 /// return a non-`const` reference to this searcher object.
973 BoyerMooreHorspoolSearcher_GeneralImp& operator=(
974 const BoyerMooreHorspoolSearcher_GeneralImp& rhs);
975
976 /// Assign to this object the state of the specified `rhs` object and
977 /// return a non-`const` reference to this searcher. The `rhs` is left
978 /// in an unspecified (valid) state.
979 BoyerMooreHorspoolSearcher_GeneralImp& operator=(
980 BloombergLP::bslmf::MovableRef<BoyerMooreHorspoolSearcher_GeneralImp>
981 rhs);
982
983 // ACCESSORS
984
985 /// Return the number of positions to advance the search in the haystack
986 /// when the specified `value` is found in the rightmost position of the
987 /// current (unsuccessful) match attempt.
988 difference_type badCharacterSkip(const value_type& value) const;
989
990 /// Return the hashing functor supplied on construction.
991 HASH hash() const;
992
993 /// Return the equality comparison functor supplied on construction.
994 EQUAL equal() const;
995
996 /// Return the allocator used by this object to supply memory.
997 BloombergLP::bslma::Allocator *allocator() const;
998};
999
1000 // ================================
1001 // class BoyerMooreHorspoolSearcher
1002 // ================================
1003
1004/// This class template implements an STL-compliant searcher object that
1005/// uses the Boyer, Moore, Horspool Algorithm. Several non-standard
1006/// accessors are also provided.
1007///
1008/// See @ref bslstl_boyermoorehorspoolsearcher
1009template <class RNDACC_ITR_NEEDLE,
1010 class HASH = bsl::hash<
1011 typename bsl::iterator_traits<RNDACC_ITR_NEEDLE>::value_type>,
1012 class EQUAL = bsl::equal_to<
1013 typename bsl::iterator_traits<RNDACC_ITR_NEEDLE>::value_type>
1014 >
1015class BoyerMooreHorspoolSearcher {
1016
1017 public:
1018 // TYPES
1019
1020 /// the type of the values that can be obtained by dereferencing a
1021 /// `RNDACC_ITR_NEEDLE`
1022 typedef typename bsl::iterator_traits<RNDACC_ITR_NEEDLE>::value_type
1023 value_type;
1024
1025 /// the default type for the `HASH` optional template parameter
1026 typedef bsl::hash<
1027 typename bsl::iterator_traits<RNDACC_ITR_NEEDLE>::value_type>
1028 DefaultHash;
1029
1030 /// the default type for the `EQUAL` optional template parameter
1031 typedef bsl::equal_to<
1032 typename bsl::iterator_traits<RNDACC_ITR_NEEDLE>::value_type>
1033 DefaultEqual;
1034
1035 private:
1036 // PRIVATE TYPES
1037
1038 /// a signed type that can describe the distance between
1039 /// `RNDACC_ITR_NEEDLE` iterators
1040 typedef typename bsl::iterator_traits<RNDACC_ITR_NEEDLE>::difference_type
1041 difference_type;
1042
1043 /// This `typedef` is a convenient alias for the utility associated with
1044 /// movable references.
1045 typedef BloombergLP::bslmf::MovableRefUtil MoveUtil;
1046
1047 enum { k_CAN_OPTIMIZE_FOR_CHAR = (
1048 1 == sizeof(value_type)
1049 && bslmf::IsBitwiseEqualityComparable<value_type>::value
1050 && bslmf::IsBitwiseCopyable<difference_type>::value
1051 && bsl::is_same<HASH, DefaultHash >::value
1052 && bsl::is_same<EQUAL, DefaultEqual>::value)
1053 };
1054
1055 typedef typename bsl::conditional<
1056 k_CAN_OPTIMIZE_FOR_CHAR,
1057
1058 BloombergLP::bslstl::
1059 BoyerMooreHorspoolSearcher_CharImp<RNDACC_ITR_NEEDLE,
1060 HASH,
1061 EQUAL>,
1062 BloombergLP::bslstl::
1063 BoyerMooreHorspoolSearcher_GeneralImp<RNDACC_ITR_NEEDLE,
1064 HASH,
1065 EQUAL> >::type Imp;
1066
1067 // DATA
1068 RNDACC_ITR_NEEDLE d_needleFirst; // start of needle specified by CTOR
1069 RNDACC_ITR_NEEDLE d_needleLast; // end of needle specified by CTOR
1070 difference_type d_needleLength; // length of needle specified by CTOR
1071
1072 Imp d_imp; // 'char'-optimized or general implementation
1073
1074 // PRIVATE ACCESSORS
1075
1076 /// Set the specified `object`, the source object of a move operation,
1077 /// to a (valid) state that is not specified to users.
1078 ///
1079 /// \pre The behavior is undefined if `this == object`.
1080 void privateSetPostMoveState(BoyerMooreHorspoolSearcher *object) const;
1081
1082 public:
1083 // CREATORS
1084
1085 /// Create a `BoyerMooreHorspoolSearcher` object that can search for the
1086 /// sequence of `value_type` values found in the specified range
1087 /// `[needleFirst, needleLast)`. Generate meta-data and save for use by
1088 /// `operator()`. The complexity of this process is O(M) where M is
1089 /// the length of the "needle". Optionally specify a `hash` functor
1090 /// mapping mis-matched values to the size of the next step in the
1091 /// search -- as large as, `needleLast - needleFirst`. Optionally
1092 /// specify an `equal` functor for use with `hash` and for use by
1093 /// `operator()`. See {Requirements for `HASH` and `EQUAL`}.
1094 /// Optionally specify `basicAllocator` to supply memory. If
1095 /// `basicAllocator` is 0 or not supplied, the currently installed default allocator is used.
1096 ///
1097 /// \pre The behavior is undefined unless
1098 /// `needleFirst` can be advanced to `needleLast`.
1099 BoyerMooreHorspoolSearcher(
1100 RNDACC_ITR_NEEDLE needleFirst,
1101 RNDACC_ITR_NEEDLE needleLast,
1102 HASH hash = HASH(),
1103 EQUAL equal = EQUAL(),
1104 BloombergLP::bslma::Allocator *basicAllocator = 0);
1105
1106 /// Create a `BoyerMooreHorspoolSearcher` object having same state --
1107 /// `needleFirst()`, `needleLast()`, `hash()`, and `equal()` -- as the
1108 /// specified `original` object, and that uses the currently installed
1109 /// default allocator to supply memory.
1110 BoyerMooreHorspoolSearcher(const BoyerMooreHorspoolSearcher& original);
1111
1112 /// Create a `BoyerMooreHorspoolSearcher` object having same state --
1113 /// `needleFirst()`, `needleLast()`, `hash()`, and `equal()` -- as the
1114 /// specified `original` object by moving (in constant time) the state
1115 /// of `original` to the new searcher. The allocator of `original` is
1116 /// propagated for use in the newly created searcher. The `original`
1117 /// object is left in an unspecified (valid) state.
1118 BoyerMooreHorspoolSearcher(
1119 BloombergLP::bslmf::MovableRef<BoyerMooreHorspoolSearcher> original)
1120 BSLS_KEYWORD_NOEXCEPT;
1121
1122 /// Create a `BoyerMooreHorspoolSearcher` object having same state --
1123 /// `needleFirst()`, `needleLast()`, `hash()`, and `equal()` -- as the
1124 /// specified `original` object. Optionally specify a `basicAllocator`
1125 /// used to supply memory. If `basicAllocator` is 0, the currently
1126 /// installed default allocator is used.
1127 BoyerMooreHorspoolSearcher(
1128 const BoyerMooreHorspoolSearcher& original,
1129 BloombergLP::bslma::Allocator *basicAllocator);
1130
1131 /// Create a `BoyerMooreHorspoolSearcher` object having same state --
1132 /// `needleFirst()`, `needleLast()`, `hash()`, and `equal()` -- as the
1133 /// specified `original` object. The specified `basicAllocator` is used
1134 /// to supply memory. If `basicAllocator` is 0, the currently installed
1135 /// default allocator is used. The state of `original` is moved (in
1136 /// constant time) to the new searcher if
1137 /// `basicAllocator == original.allocator()`, and is move-inserted (in
1138 /// linear time) using `basicAllocator` otherwise. The `original`
1139 /// object is left in an unspecified (valid) state.
1140 BoyerMooreHorspoolSearcher(
1141 BloombergLP::bslmf::MovableRef<BoyerMooreHorspoolSearcher>
1142 original,
1143 BloombergLP::bslma::Allocator *basicAllocator);
1144
1145 ~BoyerMooreHorspoolSearcher() = default;
1146 // Destroy this 'BoyerMooreHorspoolSearcher' object.
1147
1148 // MANIPULATORS
1149
1150 /// Assign to this object the state -- `needleFirst()`, `needleLast()`,
1151 /// `hash()`, and `equal()` -- of the specified `rhs` object, and return
1152 /// a non-`const` reference to this searcher.
1153 BoyerMooreHorspoolSearcher& operator=(const BoyerMooreHorspoolSearcher&
1154 rhs);
1155
1156 /// Assign to this object the state of the specified `rhs` object --
1157 /// `needleFirst()`, `needleLast()`, `hash()`, and `equal()` -- and
1158 /// return a non-`const` reference to this searcher. The `rhs` is left
1159 /// in an unspecified (valid) state.
1160 BoyerMooreHorspoolSearcher& operator=(
1161 BloombergLP::bslmf::MovableRef<BoyerMooreHorspoolSearcher> rhs);
1162
1163 // ACCESSORS
1164
1165 /// Search the specified range `[haystackFirst, haystackLast)` for the
1166 /// first sequence of `value_type` values specified on construction.
1167 /// Return the range where those values are found, or the range
1168 /// `[haystackLast, haystackLast)` if that sequence is not found. The
1169 /// search is performed using an implementation of the Boyer Moore
1170 /// Horspool algorithm and has a complexity of O(N) for random text.
1171 /// Values of the "needle" sequence and the "haystack" sequence are
1172 /// compared using the equality comparison functor specified on construction.
1173 ///
1174 /// \pre The behavior is undefined unless `haystackFirst` can
1175 /// be advanced to `haystackLast` and the iterators used to construct
1176 /// this object, `needleFirst()` and `needleLast()`, are still valid.
1177 ///
1178 /// \note Note that if the "needle" sequence is empty, the range
1179 /// `[haystackFirst, haystackFirst)` is returned. Also note that if the
1180 /// "needle" sequence is longer than the "haystack" sequence -- thus,
1181 /// impossible for the "needle" to be found in the "haystack" -- the
1182 /// range `[haystackLast, haystackLast)` is returned.
1183 template<class RNDACC_ITR_HAYSTACK>
1184 bsl::pair<RNDACC_ITR_HAYSTACK, RNDACC_ITR_HAYSTACK> operator()(
1185 RNDACC_ITR_HAYSTACK haystackFirst,
1186 RNDACC_ITR_HAYSTACK haystackLast) const;
1187
1188 // Non-Standard Accessors
1189
1190 /// Return an iterator referring to the first element of the sequence of
1191 /// `value_type` values that can be sought by this searcher object.
1192 RNDACC_ITR_NEEDLE needleFirst() const;
1193
1194 /// Return an iterator referring to one past the last element of the
1195 /// sequence of `value_type` values that can be sought by this searcher
1196 /// object.
1197 RNDACC_ITR_NEEDLE needleLast() const;
1198
1199 /// Return the hashing functor supplied on construction.
1200 HASH hash() const;
1201
1202 /// Return the equality comparison functor supplied on construction.
1203 EQUAL equal() const;
1204
1205 /// Return the allocator used by this object to supply memory.
1206 BloombergLP::bslma::Allocator *allocator() const;
1207};
1208
1209} // close package namespace
1210
1211
1212#ifndef BSLS_LIBRARYFEATURES_HAS_CPP17_SEARCH_FUNCTORS
1213namespace bsl {
1214
1215
1216 // ===================================
1217 // class boyer_moore_horspool_searcher
1218 // ===================================
1219
1220/// This class template implements an STL-compliant searcher object that
1221/// uses the Boyer, Moore, Horspool Algorithm.
1222///
1223/// See @ref bslstl_boyermoorehorspoolsearcher
1224template <class RandomAccessIterator1,
1225 class Hash = hash<
1226 typename iterator_traits<RandomAccessIterator1>::value_type>,
1227 class BinaryPredicate = equal_to<
1228 typename iterator_traits<RandomAccessIterator1>::value_type> >
1229class boyer_moore_horspool_searcher {
1230
1231 private:
1232 // DATA
1233 BloombergLP::bslstl::BoyerMooreHorspoolSearcher<RandomAccessIterator1,
1234 Hash,
1235 BinaryPredicate> d_imp;
1236
1237 public:
1238 // CREATORS
1239
1240 /// Create a @ref boyer_moore_horspool_searcher object that can search for
1241 /// the sequence of `value_type` values found in the specified range
1242 /// `[pat_first, pat_last)`. Generate meta-data and save for use by
1243 /// `operator()`. The complexity of this process is O(M) where M is
1244 /// `pat_last - pat_first`. Optionally specify `hf`, a hash functor,
1245 /// that maps mis-matched values to the size of the next step in the
1246 /// search -- as large as, `pat_Last - pat_First`. Optionally specify
1247 /// `pred`, an equality comparison functor for use with `hash` and for
1248 /// use by `operator()`. See {Requirements for `HASH` and `EQUAL`}.
1249 ///
1250 /// \pre The behavior is undefined unless `pat_First` can be advanced to
1251 /// `pat_Last`.
1252 boyer_moore_horspool_searcher(RandomAccessIterator1 pat_first,
1253 RandomAccessIterator1 pat_last,
1254 Hash hf = Hash(),
1255 BinaryPredicate pred =
1256 BinaryPredicate());
1257
1258 boyer_moore_horspool_searcher(
1259 const boyer_moore_horspool_searcher& original)
1260 = default;
1261 // Create a @ref boyer_moore_horspool_searcher object having same state as
1262 // the specified 'original' object.
1263
1264 boyer_moore_horspool_searcher(
1265 BloombergLP::bslmf::MovableRef<boyer_moore_horspool_searcher>
1266 original) = default;
1267 // Create a @ref boyer_moore_horspool_searcher object having same state as
1268 // the specified 'original' object by moving (in constant time) the
1269 // state of 'original' to the new searcher. The 'original' object is
1270 // left in an unspecified (valid) state.
1271
1272 ~boyer_moore_horspool_searcher() = default;
1273 // Destroy this @ref boyer_moore_horspool_searcher object.
1274
1275 // MANIPULATORS
1276 boyer_moore_horspool_searcher& operator=(
1277 const boyer_moore_horspool_searcher& rhs) = default;
1278 // Assign to this object the state of the specified 'rhs' object, and
1279 // return a non-'const' reference to this searcher.
1280
1281 boyer_moore_horspool_searcher& operator=(
1282 BloombergLP::bslmf::MovableRef<boyer_moore_horspool_searcher>
1283 rhs) = default;
1284 // Assign to this object the state of the specified 'rhs' object and
1285 // return a non-'const' reference to this searcher. The 'rhs' is left
1286 // in an unspecified (valid) state.
1287
1288 // ACCESSORS
1289
1290 /// Search the specified range `[first, last)` for the first sequence of
1291 /// the `value_type` values specified on construction. Return the range
1292 /// where those values are found, or the range `[last, last)` if that
1293 /// sequence is not found. The search is performed using an
1294 /// implementation of the Boyer Moore Horspool algorithm and has a
1295 /// complexity of O(N) for random text.
1296 ///
1297 /// \pre The behavior is undefined unless `first` can be advanced to `last` and the iterators used to construct this object are still valid.
1298 ///
1299 /// \note Note that if the sought
1300 /// sequence is empty, the range `[first, first)` is returned. Also
1301 /// note that if the sought sequence is longer than the searched
1302 /// sequence -- thus, the sought sequence cannot be found -- the range
1303 /// `[last, last)` is returned.
1304 template <class RandomAccessIterator2>
1305 pair<RandomAccessIterator2,
1306 RandomAccessIterator2> operator()(RandomAccessIterator2 first,
1307 RandomAccessIterator2 last) const;
1308};
1309
1310} // close namespace bsl
1311#endif // BSLS_LIBRARYFEATURES_HAS_CPP17_SEARCH_FUNCTORS
1312
1313// ----------------------------------------------------------------------------
1314// INLINE DEFINITIONS
1315// ----------------------------------------------------------------------------
1316
1317
1318namespace bslstl {
1319
1320 // ----------------------------------------
1321 // class BoyerMooreHorspoolSearcher_CharImp
1322 // ----------------------------------------
1323
1324// PRIVATE MANIPULATORS
1325template <class RNDACC_ITR_NEEDLE,
1326 class HASH,
1327 class EQUAL>
1328inline
1329void
1330BoyerMooreHorspoolSearcher_CharImp<RNDACC_ITR_NEEDLE,
1331 HASH,
1332 EQUAL>::privateInstallNewTable(
1333 const BoyerMooreHorspoolSearcher_CharImp&
1334 object)
1335{
1336 BSLS_ASSERT(0 == d_table_p);
1337
1338 if (BSLS_PERFORMANCEHINT_PREDICT_LIKELY(
1339 privateUseShortNeedleOptimization())) {
1340 ShortNeedleSkipArray *arrayPtr = new (*d_allocator_p)
1341 ShortNeedleSkipArray;
1342 std::memcpy(
1343 arrayPtr->data(),
1344 static_cast<ShortNeedleSkipArray *>(object.d_table_p)->data(),
1345 UCHAR_MAX + 1);
1346
1347 d_table_p = arrayPtr;
1348 } else {
1349 LongNeedleSkipArray *arrayPtr = new (*d_allocator_p)
1350 LongNeedleSkipArray;
1351
1352 std::copy(
1353 static_cast<LongNeedleSkipArray *>(object.d_table_p)->cbegin(),
1354 static_cast<LongNeedleSkipArray *>(object.d_table_p)->cend(),
1355 arrayPtr->begin());
1356
1357 d_table_p = arrayPtr;
1358 }
1359}
1360
1361template <class RNDACC_ITR_NEEDLE,
1362 class HASH,
1363 class EQUAL>
1364inline
1365void
1366BoyerMooreHorspoolSearcher_CharImp<RNDACC_ITR_NEEDLE,
1367 HASH,
1368 EQUAL>::privateInstallTableOverOld(
1369 const BoyerMooreHorspoolSearcher_CharImp&
1370 object)
1371{
1372 BSLS_ASSERT(d_table_p);
1373 BSLS_ASSERT(privateHasSameNeedleOptimization(object));
1374
1375 if (BSLS_PERFORMANCEHINT_PREDICT_LIKELY(
1376 privateUseShortNeedleOptimization())) {
1377 ShortNeedleSkipArray *arrayPtr = static_cast<ShortNeedleSkipArray *>(
1378 d_table_p);
1379 std::memcpy(
1380 arrayPtr->data(),
1381 static_cast<ShortNeedleSkipArray *>(object.d_table_p)->data(),
1382 UCHAR_MAX + 1);
1383
1384 } else {
1385 LongNeedleSkipArray *arrayPtr = static_cast< LongNeedleSkipArray *>(
1386 d_table_p);
1387 std::copy(
1388 static_cast<LongNeedleSkipArray *>(object.d_table_p)->cbegin(),
1389 static_cast<LongNeedleSkipArray *>(object.d_table_p)->cend(),
1390 arrayPtr->begin());
1391 }
1392}
1393
1394template <class RNDACC_ITR_NEEDLE,
1395 class HASH,
1396 class EQUAL>
1397inline
1398void
1399BoyerMooreHorspoolSearcher_CharImp<RNDACC_ITR_NEEDLE,
1400 HASH,
1401 EQUAL>::privateInstallMismatchedTable(
1402 const BoyerMooreHorspoolSearcher_CharImp&
1403 object)
1404{
1405 if (BSLS_PERFORMANCEHINT_PREDICT_LIKELY(
1406 object.privateUseShortNeedleOptimization())) {
1407 ShortNeedleSkipArray *arrayPtr = new (*d_allocator_p)
1408 ShortNeedleSkipArray;
1409 std::memcpy(
1410 arrayPtr->data(),
1411 static_cast<ShortNeedleSkipArray *>(object.d_table_p)->data(),
1412 UCHAR_MAX + 1);
1413
1414 privateDeleteTable();
1415
1416 d_table_p = arrayPtr;
1417 } else {
1418 LongNeedleSkipArray *arrayPtr = new (*d_allocator_p)
1419 LongNeedleSkipArray;
1420 std::copy(
1421 static_cast<LongNeedleSkipArray *>(object.d_table_p)->cbegin(),
1422 static_cast<LongNeedleSkipArray *>(object.d_table_p)->cend(),
1423 arrayPtr->begin());
1424 privateDeleteTable();
1425
1426 d_table_p = arrayPtr;
1427 }
1428}
1429
1430template <class RNDACC_ITR_NEEDLE,
1431 class HASH,
1432 class EQUAL>
1433inline
1434void
1435BoyerMooreHorspoolSearcher_CharImp<RNDACC_ITR_NEEDLE,
1436 HASH,
1437 EQUAL>::privateDeleteTable()
1438{
1439 if (BSLS_PERFORMANCEHINT_PREDICT_LIKELY(
1440 privateUseShortNeedleOptimization())) {
1441 d_allocator_p->deleteObjectRaw(static_cast<ShortNeedleSkipArray *>(
1442 d_table_p));
1443 } else {
1444 d_allocator_p->deleteObjectRaw(static_cast< LongNeedleSkipArray *>(
1445 d_table_p));
1446 }
1447 d_table_p = 0;
1448}
1449
1450// PRIVATE ACCESSORS
1451template <class RNDACC_ITR_NEEDLE,
1452 class HASH,
1453 class EQUAL>
1454inline
1455void
1456BoyerMooreHorspoolSearcher_CharImp<RNDACC_ITR_NEEDLE,
1457 HASH,
1458 EQUAL>::privateSetPostMoveState(
1459 BoyerMooreHorspoolSearcher_CharImp *object)
1460 const
1461{
1462 BSLS_ASSERT(0 != object);
1463 BSLS_ASSERT(this != object);
1464
1465 object->d_needleLength = 0;
1466 object->d_table_p = 0;
1467}
1468
1469template <class RNDACC_ITR_NEEDLE,
1470 class HASH,
1471 class EQUAL>
1472inline
1473bool
1474BoyerMooreHorspoolSearcher_CharImp<RNDACC_ITR_NEEDLE,
1475 HASH,
1476 EQUAL>::privateUseShortNeedleOptimization()
1477 const
1478{
1479 return d_needleLength <= UCHAR_MAX;
1480}
1481
1482template <class RNDACC_ITR_NEEDLE,
1483 class HASH,
1484 class EQUAL>
1485inline
1486bool
1487BoyerMooreHorspoolSearcher_CharImp<RNDACC_ITR_NEEDLE,
1488 HASH,
1489 EQUAL>::privateHasSameNeedleOptimization(
1490 const BoyerMooreHorspoolSearcher_CharImp&
1491 object)
1492 const
1493{
1494 return this->privateUseShortNeedleOptimization()
1495 == object.privateUseShortNeedleOptimization();
1496}
1497
1498// CREATORS
1499template <class RNDACC_ITR_NEEDLE,
1500 class HASH,
1501 class EQUAL>
1502inline
1503BoyerMooreHorspoolSearcher_CharImp<RNDACC_ITR_NEEDLE,
1504 HASH,
1505 EQUAL>::
1506BoyerMooreHorspoolSearcher_CharImp(
1507 RNDACC_ITR_NEEDLE needleFirst,
1508 RNDACC_ITR_NEEDLE needleLast,
1509 HASH ,
1510 EQUAL ,
1511 BloombergLP::bslma::Allocator *basicAllocator)
1512: d_needleLength(needleLast - needleFirst)
1513, d_allocator_p(bslma::Default::allocator(basicAllocator))
1514, d_table_p(0)
1515{
1516 BSLS_ASSERT(needleFirst <= needleLast);
1517
1518 if (0 == d_needleLength) {
1519 return; // RETURN
1520 }
1521
1522 if (BSLS_PERFORMANCEHINT_PREDICT_LIKELY(
1523 privateUseShortNeedleOptimization())) {
1524 ShortNeedleSkipArray *arrayPtr = new (*d_allocator_p)
1525 ShortNeedleSkipArray;
1526 std::memset(arrayPtr->data(),
1527 static_cast<ShortNeedleSkipType>(d_needleLength),
1528 UCHAR_MAX + 1);
1529 d_table_p = arrayPtr;
1530 } else {
1531 LongNeedleSkipArray *arrayPtr = new (*d_allocator_p)
1532 LongNeedleSkipArray;
1533
1534 std::fill(arrayPtr->begin(), arrayPtr->end(), d_needleLength);
1535
1536 d_table_p = arrayPtr;
1537 }
1538
1539 for (RNDACC_ITR_NEEDLE current = needleFirst,
1540 last = needleLast - 1;
1541 last != current; ++current) {
1542
1543 const unsigned char index = static_cast<unsigned char>(*current);
1544 std::size_t skipValue = d_needleLength
1545 - 1
1546 - (current - needleFirst);
1547
1548 if (BSLS_PERFORMANCEHINT_PREDICT_LIKELY(
1549 privateUseShortNeedleOptimization())) {
1550 BSLS_ASSERT(skipValue <= UCHAR_MAX);
1551
1552 (*static_cast<ShortNeedleSkipArray *>(d_table_p))[index]
1553 = static_cast<ShortNeedleSkipType>(skipValue);
1554 } else {
1555 (*static_cast< LongNeedleSkipArray *>(d_table_p))[index]
1556 = static_cast< LongNeedleSkipType>(skipValue);
1557 }
1558 }
1559}
1560
1561template <class RNDACC_ITR_NEEDLE,
1562 class HASH,
1563 class EQUAL>
1564inline
1565BoyerMooreHorspoolSearcher_CharImp<RNDACC_ITR_NEEDLE,
1566 HASH,
1567 EQUAL>::
1568BoyerMooreHorspoolSearcher_CharImp(
1569 const BoyerMooreHorspoolSearcher_CharImp& original)
1570: d_needleLength(original.d_needleLength)
1571, d_allocator_p( original.d_allocator_p)
1572, d_table_p(0)
1573{
1574 if (0 < d_needleLength) {
1575 privateInstallNewTable(original);
1576 }
1577}
1578
1579template <class RNDACC_ITR_NEEDLE,
1580 class HASH,
1581 class EQUAL>
1582inline
1583BoyerMooreHorspoolSearcher_CharImp<RNDACC_ITR_NEEDLE,
1584 HASH,
1585 EQUAL>::
1586BoyerMooreHorspoolSearcher_CharImp(
1587 BloombergLP::bslmf::MovableRef<BoyerMooreHorspoolSearcher_CharImp>
1588 original)
1589 BSLS_KEYWORD_NOEXCEPT
1590: d_needleLength(MoveUtil::access(original).d_needleLength)
1591, d_allocator_p( MoveUtil::access(original).d_allocator_p)
1592, d_table_p( MoveUtil::access(original).d_table_p)
1593{
1594 privateSetPostMoveState(&MoveUtil::access(original));
1595}
1596
1597template <class RNDACC_ITR_NEEDLE,
1598 class HASH,
1599 class EQUAL>
1600inline
1601BoyerMooreHorspoolSearcher_CharImp<RNDACC_ITR_NEEDLE,
1602 HASH,
1603 EQUAL>::
1604BoyerMooreHorspoolSearcher_CharImp(
1605 const BoyerMooreHorspoolSearcher_CharImp& original,
1606 BloombergLP::bslma::Allocator *basicAllocator)
1607: d_needleLength(original.d_needleLength)
1608, d_allocator_p(bslma::Default::allocator(basicAllocator))
1609, d_table_p(0)
1610{
1611 if (0 < d_needleLength) {
1612 privateInstallNewTable(original);
1613 }
1614}
1615
1616template <class RNDACC_ITR_NEEDLE,
1617 class HASH,
1618 class EQUAL>
1619inline
1620BoyerMooreHorspoolSearcher_CharImp<RNDACC_ITR_NEEDLE,
1621 HASH,
1622 EQUAL>::
1623BoyerMooreHorspoolSearcher_CharImp(
1624 BloombergLP::bslmf::MovableRef<BoyerMooreHorspoolSearcher_CharImp>
1625 original,
1626 BloombergLP::bslma::Allocator *basicAllocator)
1627: d_needleLength(MoveUtil::access(original).d_needleLength)
1628, d_allocator_p( bslma::Default::allocator(basicAllocator))
1629, d_table_p(0)
1630{
1631 if (d_allocator_p == MoveUtil::access(original).d_allocator_p) {
1632
1633 d_table_p = MoveUtil::access(original).d_table_p;
1634
1635 privateSetPostMoveState(&MoveUtil::access(original));
1636 } else {
1637 if (0 < d_needleLength) {
1638 privateInstallNewTable(MoveUtil::access(original));
1639 }
1640 }
1641}
1642
1643template <class RNDACC_ITR_NEEDLE,
1644 class HASH,
1645 class EQUAL>
1646inline
1647BoyerMooreHorspoolSearcher_CharImp<RNDACC_ITR_NEEDLE,
1648 HASH,
1649 EQUAL>::
1650~BoyerMooreHorspoolSearcher_CharImp()
1651{
1652 privateDeleteTable();
1653}
1654
1655// MANIPULATORS
1656template <class RNDACC_ITR_NEEDLE,
1657 class HASH,
1658 class EQUAL>
1659inline
1660BoyerMooreHorspoolSearcher_CharImp<RNDACC_ITR_NEEDLE,
1661 HASH,
1662 EQUAL>&
1663BoyerMooreHorspoolSearcher_CharImp<RNDACC_ITR_NEEDLE,
1664 HASH,
1665 EQUAL>::operator=(
1666 const BoyerMooreHorspoolSearcher_CharImp&
1667 rhs)
1668{
1669 if (0 < rhs.d_needleLength) {
1670 if (d_table_p && privateHasSameNeedleOptimization(rhs)) {
1671 privateInstallTableOverOld(rhs);
1672 } else {
1673 privateInstallMismatchedTable(rhs);
1674 }
1675 } else {
1676 privateDeleteTable();
1677 }
1678
1679 d_needleLength = rhs.d_needleLength;
1680
1681 return *this;
1682}
1683
1684template <class RNDACC_ITR_NEEDLE,
1685 class HASH,
1686 class EQUAL>
1687inline
1688BoyerMooreHorspoolSearcher_CharImp<RNDACC_ITR_NEEDLE,
1689 HASH,
1690 EQUAL>&
1691BoyerMooreHorspoolSearcher_CharImp<RNDACC_ITR_NEEDLE,
1692 HASH,
1693 EQUAL>::operator=(
1694 BloombergLP::bslmf::MovableRef<BoyerMooreHorspoolSearcher_CharImp>
1695 rhs)
1696{
1697 if (d_allocator_p == MoveUtil::access(rhs).d_allocator_p) {
1698 d_allocator_p->deallocate(d_table_p);
1699 d_table_p = MoveUtil::access(rhs).d_table_p;
1700 MoveUtil::access(rhs).d_table_p = 0;
1701 } else {
1702 if (0 < MoveUtil::access(rhs).d_needleLength) {
1703 if (d_table_p && privateHasSameNeedleOptimization(
1704 MoveUtil::access(rhs))) {
1705 privateInstallTableOverOld(rhs);
1706 } else {
1707 privateInstallMismatchedTable(MoveUtil::access(rhs));
1708 }
1709 } else {
1710 privateDeleteTable();
1711 }
1712 }
1713
1714 d_needleLength = MoveUtil::access(rhs).d_needleLength;
1715
1716 return *this;
1717}
1718
1719// ACCESSORS
1720template <class RNDACC_ITR_NEEDLE,
1721 class HASH,
1722 class EQUAL>
1723inline
1724typename
1725BoyerMooreHorspoolSearcher_CharImp<RNDACC_ITR_NEEDLE,
1726 HASH,
1727 EQUAL>::difference_type
1728BoyerMooreHorspoolSearcher_CharImp<RNDACC_ITR_NEEDLE,
1729 HASH,
1730 EQUAL>::badCharacterSkip(
1731 const value_type& value)
1732 const
1733{
1734 unsigned char index = static_cast<unsigned char>(value);
1735
1736 if (BSLS_PERFORMANCEHINT_PREDICT_LIKELY(
1737 privateUseShortNeedleOptimization())) {
1738 return (*static_cast<ShortNeedleSkipArray *>(d_table_p))[index];
1739 // RETURN
1740 } else {
1741 return (*static_cast< LongNeedleSkipArray *>(d_table_p))[index];
1742 // RETURN
1743 }
1744}
1745
1746template <class RNDACC_ITR_NEEDLE,
1747 class HASH,
1748 class EQUAL>
1749inline
1750HASH BoyerMooreHorspoolSearcher_CharImp<RNDACC_ITR_NEEDLE,
1751 HASH,
1752 EQUAL>::hash() const
1753{
1754 return HASH();
1755}
1756
1757template <class RNDACC_ITR_NEEDLE,
1758 class HASH,
1759 class EQUAL>
1760inline
1761EQUAL BoyerMooreHorspoolSearcher_CharImp<RNDACC_ITR_NEEDLE,
1762 HASH,
1763 EQUAL>::equal() const
1764{
1765 return EQUAL();
1766}
1767
1768template <class RNDACC_ITR_NEEDLE,
1769 class HASH,
1770 class EQUAL>
1771inline
1772BloombergLP::bslma::Allocator *BoyerMooreHorspoolSearcher_CharImp<
1773 RNDACC_ITR_NEEDLE,
1774 HASH,
1775 EQUAL>::allocator() const
1776{
1777 return d_allocator_p;
1778}
1779
1780 // -------------------------------------------
1781 // class BoyerMooreHorspoolSearcher_GeneralImp
1782 // -------------------------------------------
1783
1784// CREATORS
1785template <class RNDACC_ITR_NEEDLE,
1786 class HASH,
1787 class EQUAL>
1788inline
1789BoyerMooreHorspoolSearcher_GeneralImp<RNDACC_ITR_NEEDLE,
1790 HASH,
1791 EQUAL>::
1792BoyerMooreHorspoolSearcher_GeneralImp(
1793 RNDACC_ITR_NEEDLE needleFirst,
1794 RNDACC_ITR_NEEDLE needleLast,
1795 HASH hash,
1796 EQUAL equal,
1797 BloombergLP::bslma::Allocator *basicAllocator)
1798: d_needleLength(needleLast - needleFirst)
1799, d_map(0, hash, equal, basicAllocator)
1800{
1801 BSLS_ASSERT(needleFirst <= needleLast);
1802
1803 if (0 < d_needleLength) {
1804 for (RNDACC_ITR_NEEDLE current = needleFirst,
1805 last = needleLast - 1;
1806 last != current; ++current) {
1807 d_map.insert(std::make_pair(*current,
1808 d_needleLength
1809 - 1
1810 - (current - needleFirst)));
1811 }
1812 }
1813}
1814
1815template <class RNDACC_ITR_NEEDLE,
1816 class HASH,
1817 class EQUAL>
1818inline
1819BoyerMooreHorspoolSearcher_GeneralImp<RNDACC_ITR_NEEDLE,
1820 HASH,
1821 EQUAL>::
1822BoyerMooreHorspoolSearcher_GeneralImp(
1823 const BoyerMooreHorspoolSearcher_GeneralImp& original)
1824: d_needleLength(original.d_needleLength)
1825, d_map(original, original.allocator())
1826{
1827}
1828
1829template <class RNDACC_ITR_NEEDLE,
1830 class HASH,
1831 class EQUAL>
1832inline
1833BoyerMooreHorspoolSearcher_GeneralImp<RNDACC_ITR_NEEDLE,
1834 HASH,
1835 EQUAL>::
1836BoyerMooreHorspoolSearcher_GeneralImp(
1837 BloombergLP::bslmf::MovableRef<BoyerMooreHorspoolSearcher_GeneralImp>
1838 original)
1839 BSLS_KEYWORD_NOEXCEPT
1840: d_needleLength(MoveUtil::move(MoveUtil::access(original).d_needleLength))
1841, d_map( MoveUtil::move(MoveUtil::access(original).d_map))
1842{
1843}
1844
1845template <class RNDACC_ITR_NEEDLE,
1846 class HASH,
1847 class EQUAL>
1848inline
1849BoyerMooreHorspoolSearcher_GeneralImp<RNDACC_ITR_NEEDLE,
1850 HASH,
1851 EQUAL>::
1852BoyerMooreHorspoolSearcher_GeneralImp(
1853 const BoyerMooreHorspoolSearcher_GeneralImp& original,
1854 BloombergLP::bslma::Allocator *basicAllocator)
1855: d_needleLength(original.d_needleLength)
1856, d_map(original.d_map, basicAllocator)
1857{
1858}
1859
1860template <class RNDACC_ITR_NEEDLE,
1861 class HASH,
1862 class EQUAL>
1863inline
1864BoyerMooreHorspoolSearcher_GeneralImp<RNDACC_ITR_NEEDLE,
1865 HASH,
1866 EQUAL>::
1867BoyerMooreHorspoolSearcher_GeneralImp(
1868 BloombergLP::bslmf::MovableRef<BoyerMooreHorspoolSearcher_GeneralImp>
1869 original,
1870 BloombergLP::bslma::Allocator *basicAllocator)
1871: d_needleLength(MoveUtil::move(MoveUtil::access(original).d_needleLength))
1872, d_map( MoveUtil::move(MoveUtil::access(original).d_map),
1873 basicAllocator)
1874{
1875}
1876
1877// MANIPULATORS
1878template <class RNDACC_ITR_NEEDLE,
1879 class HASH,
1880 class EQUAL>
1881inline
1882BoyerMooreHorspoolSearcher_GeneralImp<RNDACC_ITR_NEEDLE,
1883 HASH,
1884 EQUAL>&
1885BoyerMooreHorspoolSearcher_GeneralImp<RNDACC_ITR_NEEDLE,
1886 HASH,
1887 EQUAL>::operator=(
1888 const BoyerMooreHorspoolSearcher_GeneralImp& rhs)
1889{
1890 d_needleLength = rhs.d_needleLength;
1891 d_map = rhs.d_map;
1892
1893 return *this;
1894}
1895
1896template <class RNDACC_ITR_NEEDLE,
1897 class HASH,
1898 class EQUAL>
1899inline
1900BoyerMooreHorspoolSearcher_GeneralImp<RNDACC_ITR_NEEDLE,
1901 HASH,
1902 EQUAL>&
1903BoyerMooreHorspoolSearcher_GeneralImp<RNDACC_ITR_NEEDLE,
1904 HASH,
1905 EQUAL>::operator=(
1906 BloombergLP::bslmf::MovableRef<BoyerMooreHorspoolSearcher_GeneralImp>
1907 rhs)
1908{
1909 d_needleLength = MoveUtil::move(MoveUtil::access(rhs).d_needleLength);
1910 d_map = MoveUtil::move(MoveUtil::access(rhs).d_map);
1911
1912 return *this;
1913}
1914
1915// ACCESSORS
1916template <class RNDACC_ITR_NEEDLE,
1917 class HASH,
1918 class EQUAL>
1919inline
1920typename
1921BoyerMooreHorspoolSearcher_GeneralImp<RNDACC_ITR_NEEDLE,
1922 HASH,
1923 EQUAL>::difference_type
1924BoyerMooreHorspoolSearcher_GeneralImp<RNDACC_ITR_NEEDLE,
1925 HASH,
1926 EQUAL>::badCharacterSkip(
1927 const value_type& value) const
1928{
1929 typename Map::const_iterator result = d_map.find(value);
1930
1931 return d_map.cend() == result ? d_needleLength : result->second;
1932}
1933
1934template <class RNDACC_ITR_NEEDLE,
1935 class HASH,
1936 class EQUAL>
1937inline
1938HASH BoyerMooreHorspoolSearcher_GeneralImp<RNDACC_ITR_NEEDLE,
1939 HASH,
1940 EQUAL>::hash() const
1941{
1942 return d_map.hash_function();
1943}
1944
1945template <class RNDACC_ITR_NEEDLE,
1946 class HASH,
1947 class EQUAL>
1948inline
1949EQUAL BoyerMooreHorspoolSearcher_GeneralImp<RNDACC_ITR_NEEDLE,
1950 HASH,
1951 EQUAL>::equal() const
1952{
1953 return d_map.key_eq();
1954}
1955
1956template <class RNDACC_ITR_NEEDLE,
1957 class HASH,
1958 class EQUAL>
1959inline
1960BloombergLP::bslma::Allocator *BoyerMooreHorspoolSearcher_GeneralImp<
1961 RNDACC_ITR_NEEDLE,
1962 HASH,
1963 EQUAL>::allocator() const
1964{
1965 return d_map.get_allocator().mechanism();
1966}
1967
1968 // --------------------------------
1969 // class BoyerMooreHorspoolSearcher
1970 // --------------------------------
1971
1972// PRIVATE ACCESSORS
1973template <class RNDACC_ITR_NEEDLE,
1974 class HASH,
1975 class EQUAL>
1976inline
1977void
1978BoyerMooreHorspoolSearcher<RNDACC_ITR_NEEDLE,
1979 HASH,
1980 EQUAL>::privateSetPostMoveState(
1981 BoyerMooreHorspoolSearcher *object) const
1982{
1983 BSLS_ASSERT(0 != object);
1984 BSLS_ASSERT(this != object);
1985
1986 object->d_needleFirst = d_needleFirst;
1987 object->d_needleLast = d_needleFirst;
1988 object->d_needleLength = 0;
1989}
1990
1991// CREATORS
1992template <class RNDACC_ITR_NEEDLE,
1993 class HASH,
1994 class EQUAL>
1995BoyerMooreHorspoolSearcher<RNDACC_ITR_NEEDLE,
1996 HASH,
1997 EQUAL>::
1998BoyerMooreHorspoolSearcher(RNDACC_ITR_NEEDLE needleFirst,
1999 RNDACC_ITR_NEEDLE needleLast,
2000 HASH hash,
2001 EQUAL equal,
2002 BloombergLP::bslma::Allocator *basicAllocator)
2003: d_needleFirst( needleFirst)
2004, d_needleLast( needleLast)
2005, d_needleLength(bsl::distance(needleFirst, needleLast))
2006, d_imp(needleFirst, needleLast, hash, equal, basicAllocator)
2007{
2008 BSLS_ASSERT(needleFirst <= needleLast);
2009}
2010
2011template <class RNDACC_ITR_NEEDLE,
2012 class HASH,
2013 class EQUAL>
2014BoyerMooreHorspoolSearcher<RNDACC_ITR_NEEDLE,
2015 HASH,
2016 EQUAL>::
2017BoyerMooreHorspoolSearcher(const BoyerMooreHorspoolSearcher& original)
2018: d_needleFirst( original.d_needleFirst)
2019, d_needleLast( original.d_needleLast)
2020, d_needleLength(original.d_needleLength)
2021, d_imp( original.d_imp,
2022 BloombergLP::bslma::Default::defaultAllocator())
2023{
2024}
2025
2026template <class RNDACC_ITR_NEEDLE,
2027 class HASH,
2028 class EQUAL>
2029BoyerMooreHorspoolSearcher<RNDACC_ITR_NEEDLE,
2030 HASH,
2031 EQUAL>::
2032BoyerMooreHorspoolSearcher(
2033 BloombergLP::bslmf::MovableRef<BoyerMooreHorspoolSearcher> original)
2034 BSLS_KEYWORD_NOEXCEPT
2035: d_needleFirst( MoveUtil::move(MoveUtil::access(original).d_needleFirst))
2036, d_needleLast( MoveUtil::move(MoveUtil::access(original).d_needleLast))
2037, d_needleLength(MoveUtil::move(MoveUtil::access(original).d_needleLength))
2038, d_imp( MoveUtil::move(MoveUtil::access(original).d_imp))
2039{
2040 privateSetPostMoveState(&MoveUtil::access(original));
2041}
2042
2043template <class RNDACC_ITR_NEEDLE,
2044 class HASH,
2045 class EQUAL>
2046BoyerMooreHorspoolSearcher<RNDACC_ITR_NEEDLE,
2047 HASH,
2048 EQUAL>::
2049BoyerMooreHorspoolSearcher(const BoyerMooreHorspoolSearcher& original,
2050 BloombergLP::bslma::Allocator *basicAllocator)
2051: d_needleFirst( original.d_needleFirst)
2052, d_needleLast( original.d_needleLast)
2053, d_needleLength(original.d_needleLength)
2054, d_imp( original.d_imp, basicAllocator)
2055{
2056}
2057
2058template <class RNDACC_ITR_NEEDLE,
2059 class HASH,
2060 class EQUAL>
2061BoyerMooreHorspoolSearcher<RNDACC_ITR_NEEDLE,
2062 HASH,
2063 EQUAL>::
2064BoyerMooreHorspoolSearcher(
2065 BloombergLP::bslmf::MovableRef<BoyerMooreHorspoolSearcher> original,
2066 BloombergLP::bslma::Allocator *basicAllocator)
2067: d_needleFirst( MoveUtil::move(MoveUtil::access(original).d_needleFirst))
2068, d_needleLast( MoveUtil::move(MoveUtil::access(original).d_needleLast))
2069, d_needleLength(MoveUtil::move(MoveUtil::access(original).d_needleLength))
2070, d_imp( MoveUtil::move(MoveUtil::access(original).d_imp),
2071 basicAllocator)
2072{
2073 privateSetPostMoveState(&MoveUtil::access(original));
2074}
2075
2076// MANIPULATORS
2077template <class RNDACC_ITR_NEEDLE,
2078 class HASH,
2079 class EQUAL>
2080inline
2081BoyerMooreHorspoolSearcher<RNDACC_ITR_NEEDLE,
2082 HASH,
2083 EQUAL>&
2084BoyerMooreHorspoolSearcher<RNDACC_ITR_NEEDLE,
2085 HASH,
2086 EQUAL>::operator=(
2087 const BoyerMooreHorspoolSearcher& rhs)
2088{
2089 d_needleFirst = rhs.d_needleFirst;
2090 d_needleLast = rhs.d_needleLast;
2091 d_needleLength = rhs.d_needleLength;
2092 d_imp = rhs.d_imp;
2093
2094 return *this;
2095}
2096
2097template <class RNDACC_ITR_NEEDLE,
2098 class HASH,
2099 class EQUAL>
2100inline
2101BoyerMooreHorspoolSearcher<RNDACC_ITR_NEEDLE,
2102 HASH,
2103 EQUAL>&
2104BoyerMooreHorspoolSearcher<RNDACC_ITR_NEEDLE,
2105 HASH,
2106 EQUAL>::operator=(
2107 BloombergLP::bslmf::MovableRef<BoyerMooreHorspoolSearcher> rhs)
2108{
2109 if (BSLS_PERFORMANCEHINT_PREDICT_LIKELY(this != &MoveUtil::access(rhs))) {
2110
2111 d_needleFirst = MoveUtil::move(MoveUtil::access(rhs).d_needleFirst);
2112 d_needleLast = MoveUtil::move(MoveUtil::access(rhs).d_needleLast);
2113 d_needleLength = MoveUtil::move(MoveUtil::access(rhs).d_needleLength);
2114 d_imp = MoveUtil::move(MoveUtil::access(rhs).d_imp);
2115
2116 privateSetPostMoveState(&MoveUtil::access(rhs));
2117 }
2118
2119 return *this;
2120}
2121
2122// ACCESSORS
2123template <class RNDACC_ITR_NEEDLE,
2124 class HASH,
2125 class EQUAL>
2126template <class RNDACC_ITR_HAYSTACK>
2127bsl::pair<RNDACC_ITR_HAYSTACK, RNDACC_ITR_HAYSTACK>
2128BoyerMooreHorspoolSearcher<RNDACC_ITR_NEEDLE,
2129 HASH,
2130 EQUAL>::operator()(
2131 RNDACC_ITR_HAYSTACK haystackFirst,
2132 RNDACC_ITR_HAYSTACK haystackLast) const
2133{
2134 BSLS_ASSERT(0 <= haystackLast - haystackFirst);
2135
2136 if (0 == d_needleLength) {
2137 return std::make_pair(haystackFirst, haystackFirst); // RETURN
2138 }
2139
2140 std::size_t haystackLength = haystackLast - haystackFirst;
2141
2142 for (std::size_t possibleMatch = 0;
2143 d_needleLength + possibleMatch <= haystackLength;
2144 possibleMatch += d_imp.badCharacterSkip(haystackFirst[possibleMatch
2145 + d_needleLength
2146 - 1])) {
2147
2148 // Check in reverse order for match.
2149
2150 const EQUAL comparator(equal());
2151
2152 for (std::size_t idx = d_needleLength - 1;
2153 comparator(haystackFirst[possibleMatch + idx],
2154 d_needleFirst[idx]);
2155 --idx) {
2156
2157 if (0 == idx) { // No difference found
2158 return std::make_pair(haystackFirst + possibleMatch,
2159 haystackFirst + possibleMatch
2160 + d_needleLength);
2161 // RETURN
2162 }
2163 }
2164 }
2165
2166 return std::make_pair(haystackLast, haystackLast);
2167}
2168
2169template <class RNDACC_ITR_NEEDLE,
2170 class HASH,
2171 class EQUAL>
2172inline
2173RNDACC_ITR_NEEDLE BoyerMooreHorspoolSearcher<RNDACC_ITR_NEEDLE,
2174 HASH,
2175 EQUAL>::needleFirst() const
2176{
2177 return d_needleFirst;
2178}
2179
2180template <class RNDACC_ITR_NEEDLE,
2181 class HASH,
2182 class EQUAL>
2183inline
2184RNDACC_ITR_NEEDLE BoyerMooreHorspoolSearcher<RNDACC_ITR_NEEDLE,
2185 HASH,
2186 EQUAL>::needleLast() const
2187{
2188 return d_needleLast;
2189}
2190
2191template <class RNDACC_ITR_NEEDLE,
2192 class HASH,
2193 class EQUAL>
2194inline
2195HASH BoyerMooreHorspoolSearcher<RNDACC_ITR_NEEDLE,
2196 HASH,
2197 EQUAL>::hash() const
2198{
2199 return d_imp.hash();
2200}
2201
2202template <class RNDACC_ITR_NEEDLE,
2203 class HASH,
2204 class EQUAL>
2205inline
2206EQUAL BoyerMooreHorspoolSearcher<RNDACC_ITR_NEEDLE,
2207 HASH,
2208 EQUAL>::equal() const
2209{
2210 return d_imp.equal();
2211}
2212
2213template <class RNDACC_ITR_NEEDLE,
2214 class HASH,
2215 class EQUAL>
2216inline
2217BloombergLP::bslma::Allocator *BoyerMooreHorspoolSearcher<
2218 RNDACC_ITR_NEEDLE,
2219 HASH,
2220 EQUAL>::allocator() const
2221{
2222 return d_imp.allocator();
2223}
2224
2225} // close package namespace
2226
2227
2228#ifndef BSLS_LIBRARYFEATURES_HAS_CPP17_SEARCH_FUNCTORS
2229namespace bsl {
2230
2231 // -----------------------------------
2232 // class boyer_moore_horspool_searcher
2233 // -----------------------------------
2234
2235// CREATORS
2236template <class RandomAccessIterator1,
2237 class Hash,
2238 class BinaryPredicate>
2239inline
2240boyer_moore_horspool_searcher<RandomAccessIterator1,
2241 Hash,
2242 BinaryPredicate>::boyer_moore_horspool_searcher(
2243 RandomAccessIterator1 pat_first,
2244 RandomAccessIterator1 pat_last,
2245 Hash hf,
2246 BinaryPredicate pred)
2247: d_imp(pat_first, pat_last, hf, pred)
2248{
2249 BSLS_ASSERT(pat_first <= pat_last);
2250}
2251
2252// ACCESSORS
2253template <class RandomAccessIterator1,
2254 class Hash,
2255 class BinaryPredicate>
2256template <class RandomAccessIterator2>
2257inline
2258pair<RandomAccessIterator2,
2259 RandomAccessIterator2> boyer_moore_horspool_searcher<
2260 RandomAccessIterator1,
2261 Hash,
2262 BinaryPredicate>::operator()(
2263 RandomAccessIterator2 first,
2264 RandomAccessIterator2 last)
2265 const
2266{
2267 BSLS_ASSERT(first <= last);
2268
2269 return d_imp(first, last);
2270}
2271
2272} // close namespace bsl
2273#endif // BSLS_LIBRARYFEATURES_HAS_CPP17_SEARCH_FUNCTORS
2274
2275// ============================================================================
2276// TYPE TRAITS
2277// ============================================================================
2278
2279
2280namespace bslma {
2281
2282template <class RNDACC_ITR_NEEDLE,
2283 class HASH,
2284 class EQUAL>
2285struct UsesBslmaAllocator<
2286 BloombergLP::bslstl::BoyerMooreHorspoolSearcher<RNDACC_ITR_NEEDLE,
2287 HASH,
2288 EQUAL>
2289 > : bsl::true_type
2290{};
2291
2292template <class RNDACC_ITR_NEEDLE,
2293 class HASH,
2294 class EQUAL>
2295struct UsesBslmaAllocator<
2296 BloombergLP::bslstl::BoyerMooreHorspoolSearcher_GeneralImp<
2297 RNDACC_ITR_NEEDLE,
2298 HASH,
2299 EQUAL>
2300 > : bsl::true_type
2301{};
2302
2303template <class RNDACC_ITR_NEEDLE,
2304 class HASH,
2305 class EQUAL>
2306struct UsesBslmaAllocator<
2307 BloombergLP::bslstl::BoyerMooreHorspoolSearcher_CharImp<RNDACC_ITR_NEEDLE,
2308 HASH,
2309 EQUAL>
2310 > : bsl::true_type
2311{};
2312
2313} // close namespace bslma
2314
2315
2316#endif
2317
2318// ----------------------------------------------------------------------------
2319// Copyright 2019 Bloomberg Finance L.P.
2320//
2321// Licensed under the Apache License, Version 2.0 (the "License");
2322// you may not use this file except in compliance with the License.
2323// You may obtain a copy of the License at
2324//
2325// http://www.apache.org/licenses/LICENSE-2.0
2326//
2327// Unless required by applicable law or agreed to in writing, software
2328// distributed under the License is distributed on an "AS IS" BASIS,
2329// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
2330// See the License for the specific language governing permissions and
2331// limitations under the License.
2332// ----------------------------- END-OF-FILE ----------------------------------
2333
2334/** @} */
2335/** @} */
2336/** @} */
bslma_allocator.h
bslma_default.h
bslmf_conditional.h
bslmf_isbitwisecopyable.h
bslmf_isbitwiseequalitycomparable.h
bslmf_issame.h
bslmf_movableref.h
bsls_assert.h
bsls_ident.h
bsls_keyword.h
bsls_libraryfeatures.h
bsls_performancehint.h
bslstl_array.h
bslstl_equalto.h
bslstl_hash.h
bslstl_iterator.h
bslstl_pair.h
bslstl_unorderedmap.h
bsl::pair
Definition bslstl_pair.h:1280
bsl::unordered_map
Definition bslstl_unorderedmap.h:1123
bsl::unordered_map::insert
pair< iterator, bool > insert(const value_type &value)
Definition bslstl_unorderedmap.h:3543
bsl::unordered_map< value_type, difference_type, HASH, EQUAL >::const_iterator
BloombergLP::bslstl::HashTableIterator< const value_type, difference_type > const_iterator
Definition bslstl_unorderedmap.h:1235
bslstl::BoyerMooreHorspoolSearcher_CharImp
Definition bslstl_boyermoorehorspoolsearcher.h:699
bslstl::BoyerMooreHorspoolSearcher_CharImp::equal
EQUAL equal() const
Return the equality comparison functor supplied on construction.
Definition bslstl_boyermoorehorspoolsearcher.h:1763
bslstl::BoyerMooreHorspoolSearcher_CharImp::~BoyerMooreHorspoolSearcher_CharImp
~BoyerMooreHorspoolSearcher_CharImp()
Destroy this object;.
Definition bslstl_boyermoorehorspoolsearcher.h:1650
bslstl::BoyerMooreHorspoolSearcher_CharImp::allocator
BloombergLP::bslma::Allocator * allocator() const
Return the allocator supplied on construction.
Definition bslstl_boyermoorehorspoolsearcher.h:1775
bslstl::BoyerMooreHorspoolSearcher_CharImp::badCharacterSkip
difference_type badCharacterSkip(const value_type &value) const
Definition bslstl_boyermoorehorspoolsearcher.h:1730
bslstl::BoyerMooreHorspoolSearcher_CharImp::operator=
BoyerMooreHorspoolSearcher_CharImp & operator=(const BoyerMooreHorspoolSearcher_CharImp &rhs)
Definition bslstl_boyermoorehorspoolsearcher.h:1665
bslstl::BoyerMooreHorspoolSearcher_CharImp::difference_type
bsl::iterator_traits< RNDACC_ITR_NEEDLE >::difference_type difference_type
Definition bslstl_boyermoorehorspoolsearcher.h:712
bslstl::BoyerMooreHorspoolSearcher_CharImp::value_type
bsl::iterator_traits< RNDACC_ITR_NEEDLE >::value_type value_type
Definition bslstl_boyermoorehorspoolsearcher.h:707
bslstl::BoyerMooreHorspoolSearcher_CharImp::hash
HASH hash() const
Return the hashing functor supplied on construction.
Definition bslstl_boyermoorehorspoolsearcher.h:1752
bslstl::BoyerMooreHorspoolSearcher_GeneralImp
Definition bslstl_boyermoorehorspoolsearcher.h:889
bslstl::BoyerMooreHorspoolSearcher_GeneralImp::badCharacterSkip
difference_type badCharacterSkip(const value_type &value) const
Definition bslstl_boyermoorehorspoolsearcher.h:1926
bslstl::BoyerMooreHorspoolSearcher_GeneralImp::equal
EQUAL equal() const
Return the equality comparison functor supplied on construction.
Definition bslstl_boyermoorehorspoolsearcher.h:1951
bslstl::BoyerMooreHorspoolSearcher_GeneralImp::value_type
bsl::iterator_traits< RNDACC_ITR_NEEDLE >::value_type value_type
Definition bslstl_boyermoorehorspoolsearcher.h:894
bslstl::BoyerMooreHorspoolSearcher_GeneralImp::operator=
BoyerMooreHorspoolSearcher_GeneralImp & operator=(const BoyerMooreHorspoolSearcher_GeneralImp &rhs)
Definition bslstl_boyermoorehorspoolsearcher.h:1887
bslstl::BoyerMooreHorspoolSearcher_GeneralImp::difference_type
bsl::iterator_traits< RNDACC_ITR_NEEDLE >::difference_type difference_type
Definition bslstl_boyermoorehorspoolsearcher.h:897
bslstl::BoyerMooreHorspoolSearcher_GeneralImp::allocator
BloombergLP::bslma::Allocator * allocator() const
Return the allocator used by this object to supply memory.
Definition bslstl_boyermoorehorspoolsearcher.h:1963
bslstl::BoyerMooreHorspoolSearcher_GeneralImp::hash
HASH hash() const
Return the hashing functor supplied on construction.
Definition bslstl_boyermoorehorspoolsearcher.h:1940
bslstl::BoyerMooreHorspoolSearcher
Definition bslstl_boyermoorehorspoolsearcher.h:1015
bslstl::BoyerMooreHorspoolSearcher::operator()
bsl::pair< RNDACC_ITR_HAYSTACK, RNDACC_ITR_HAYSTACK > operator()(RNDACC_ITR_HAYSTACK haystackFirst, RNDACC_ITR_HAYSTACK haystackLast) const
Definition bslstl_boyermoorehorspoolsearcher.h:2130
bslstl::BoyerMooreHorspoolSearcher::allocator
BloombergLP::bslma::Allocator * allocator() const
Return the allocator used by this object to supply memory.
Definition bslstl_boyermoorehorspoolsearcher.h:2220
bslstl::BoyerMooreHorspoolSearcher::equal
EQUAL equal() const
Return the equality comparison functor supplied on construction.
Definition bslstl_boyermoorehorspoolsearcher.h:2208
bslstl::BoyerMooreHorspoolSearcher::value_type
bsl::iterator_traits< RNDACC_ITR_NEEDLE >::value_type value_type
Definition bslstl_boyermoorehorspoolsearcher.h:1023
bslstl::BoyerMooreHorspoolSearcher::operator=
BoyerMooreHorspoolSearcher & operator=(const BoyerMooreHorspoolSearcher &rhs)
Definition bslstl_boyermoorehorspoolsearcher.h:2086
bslstl::BoyerMooreHorspoolSearcher::hash
HASH hash() const
Return the hashing functor supplied on construction.
Definition bslstl_boyermoorehorspoolsearcher.h:2197
bslstl::BoyerMooreHorspoolSearcher::DefaultEqual
bsl::equal_to< typename bsl::iterator_traits< RNDACC_ITR_NEEDLE >::value_type > DefaultEqual
the default type for the EQUAL optional template parameter
Definition bslstl_boyermoorehorspoolsearcher.h:1033
bslstl::BoyerMooreHorspoolSearcher::needleLast
RNDACC_ITR_NEEDLE needleLast() const
Definition bslstl_boyermoorehorspoolsearcher.h:2186
bslstl::BoyerMooreHorspoolSearcher::DefaultHash
bsl::hash< typename bsl::iterator_traits< RNDACC_ITR_NEEDLE >::value_type > DefaultHash
the default type for the HASH optional template parameter
Definition bslstl_boyermoorehorspoolsearcher.h:1028
bslstl::BoyerMooreHorspoolSearcher::needleFirst
RNDACC_ITR_NEEDLE needleFirst() const
Definition bslstl_boyermoorehorspoolsearcher.h:2175
BSLS_ASSERT
#define BSLS_ASSERT(X)
Definition bsls_assert.h:1976
BSLS_IDENT
#define BSLS_IDENT(str)
BSLS_IDENT() - insert string into .comment binary segment (if supported)
Definition bsls_ident.h:238
BSLS_KEYWORD_NOEXCEPT
#define BSLS_KEYWORD_NOEXCEPT
Definition bsls_keyword.h:674
BSLS_PERFORMANCEHINT_PREDICT_LIKELY
#define BSLS_PERFORMANCEHINT_PREDICT_LIKELY(expr)
Definition bsls_performancehint.h:451
bsl
Definition bdlat_valuetypefunctions.h:939
bsl::cend
T::const_iterator cend(const T &container)
Definition bslstl_iterator.h:1709
bsl::rhs
ALLOCATOR const STRING_VIEW_LIKE_TYPE & rhs
Definition bslstl_string.h:3918
bsl::cbegin
T::const_iterator cbegin(const T &container)
Definition bslstl_iterator.h:1651
bslma
Definition baljsn_encoder_testtypes.h:76
bslstl
Definition bslstl_algorithm.h:84
bsl::array
Definition bslstl_array.h:293
bsl::conditional
Definition bslmf_conditional.h:123
bsl::equal_to
Definition bslstl_equalto.h:316
bsl::hash
Definition bslstl_hash.h:495
bsl::integral_constant< bool, true >
bsl::is_same
Definition bslmf_issame.h:146
bslma::UsesBslmaAllocator
Definition bslma_usesbslmaallocator.h:344
bslmf::IsBitwiseCopyable
Definition bslmf_isbitwisecopyable.h:298
bslmf::IsBitwiseEqualityComparable
Definition bslmf_isbitwiseequalitycomparable.h:500