impala::StringSearch Class Reference

#include <string-search.h>

Collaboration diagram for impala::StringSearch:

Public Member Functions
	StringSearch ()
	StringSearch (const StringValue *pattern)
	Initialize/Precompute a StringSearch object from the pattern. More...
int	Search (const StringValue *str) const

Private Member Functions
void	BloomAdd (char c)
bool	BloomQuery (char c) const

Private Attributes
const StringValue *	pattern_
int64_t	mask_
int64_t	skip_

Static Private Attributes
static const int	BLOOM_WIDTH = 64

Detailed Description

TODO: This can be sped up with SIDD_CMP_EQUAL_ORDERED or at the very least rewritten from published algorithms. This is taken from the python search string function doing string search (substring) using an optimized boyer-moore-horspool algorithm.

http://hg.python.org/cpython/file/6b6c79eba944/Objects/stringlib/fastsearch.h PYTHON SOFTWARE FOUNDATION LICENSE VERSION 2

1. This LICENSE AGREEMENT is between the Python Software Foundation ("PSF"), and the Individual or Organization ("Licensee") accessing and otherwise using this software ("Python") in source or binary form and its associated documentation. 2. Subject to the terms and conditions of this License Agreement, PSF hereby grants Licensee a nonexclusive, royalty-free, world-wide license to reproduce, analyze, test, perform and/or display publicly, prepare derivative works, distribute, and otherwise use Python alone or in any derivative version, provided, however, that PSF's License Agreement and PSF's notice of copyright, i.e., "Copyright (c) 2001, 2002, 2003, 2004, 2005, 2006 Python Software Foundation; All Rights Reserved" are retained in Python alone or in any derivative version prepared by Licensee. 3. In the event Licensee prepares a derivative work that is based on or incorporates Python or any part thereof, and wants to make the derivative work available to others as provided herein, then Licensee hereby agrees to include in any such work a brief summary of the changes made to Python. 4. PSF is making Python available to Licensee on an "AS IS" basis. PSF MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED. BY WAY OF EXAMPLE, BUT NOT LIMITATION, PSF MAKES NO AND DISCLAIMS ANY REPRESENTATION OR WARRANTY OF MERCHANTABILITY OR FITNESS FOR ANY PARTICULAR PURPOSE OR THAT THE USE OF PYTHON WILL NOT INFRINGE ANY THIRD PARTY RIGHTS. 5. PSF SHALL NOT BE LIABLE TO LICENSEE OR ANY OTHER USERS OF PYTHON FOR ANY INCIDENTAL, SPECIAL, OR CONSEQUENTIAL DAMAGES OR LOSS AS A RESULT OF MODIFYING, DISTRIBUTING, OR OTHERWISE USING PYTHON, OR ANY DERIVATIVE THEREOF, EVEN IF ADVISED OF THE POSSIBILITY THEREOF. 6. This License Agreement will automatically terminate upon a material breach of its terms and conditions. 7. Nothing in this License Agreement shall be deemed to create any relationship of agency, partnership, or joint venture between PSF and Licensee. This License Agreement does not grant permission to use PSF trademarks or trade name in a trademark sense to endorse or promote products or services of Licensee, or any third party. 8. By copying, installing or otherwise using Python, Licensee agrees to be bound by the terms and conditions of this License Agreement.

Definition at line 83 of file string-search.h.

Constructor & Destructor Documentation

impala::StringSearch::StringSearch ( )

inline

Definition at line 86 of file string-search.h.

impala::StringSearch::StringSearch ( const StringValue *  pattern )

inline

Initialize/Precompute a StringSearch object from the pattern.

Definition at line 89 of file string-search.h.

References BloomAdd(), impala::StringValue::len, pattern_, impala::StringValue::ptr, and skip_.

Member Function Documentation

void impala::StringSearch::BloomAdd ( char  c )

inlineprivate

Definition at line 162 of file string-search.h.

References BLOOM_WIDTH, and mask_.

Referenced by StringSearch().

bool impala::StringSearch::BloomQuery ( char  c ) const

inlineprivate

Definition at line 166 of file string-search.h.

References BLOOM_WIDTH, and mask_.

Referenced by Search().

int impala::StringSearch::Search ( const StringValue *  str ) const

inline

Search for this pattern in str. Returns the offset into str if the pattern exists Returns -1 if the pattern is not found

Definition at line 110 of file string-search.h.

References BloomQuery(), impala::StringValue::len, pattern_, impala::StringValue::ptr, and skip_.

Referenced by impala::LikePredicate::ConstantSubstringFn(), impala::BaseSequenceScanner::FindSyncBlock(), impala::StringFunctions::Instr(), impala::StringFunctions::LocatePos(), impala::UrlParser::ParseUrl(), impala::UrlParser::ParseUrlKey(), and TestPython().

Member Data Documentation

const int impala::StringSearch::BLOOM_WIDTH = 64

staticprivate

Definition at line 160 of file string-search.h.

Referenced by BloomAdd(), and BloomQuery().

int64_t impala::StringSearch::mask_

private

Definition at line 171 of file string-search.h.

Referenced by BloomAdd(), and BloomQuery().

const StringValue* impala::StringSearch::pattern_

private

Definition at line 170 of file string-search.h.

Referenced by Search(), and StringSearch().

int64_t impala::StringSearch::skip_

private

Definition at line 172 of file string-search.h.

Referenced by Search(), and StringSearch().

---

The documentation for this class was generated from the following file:

• be/src/runtime/string-search.h