substring search More...

#include "cgul_common.h"
#include "cgul_exception.h"

Include dependency graph for cgul_substring.h:

This graph shows which files directly or indirectly include this file:

Typedefs
typedef typedefCGUL_BEGIN_C struct cgul_substring *	cgul_substring_t

Functions
CGUL_EXPORT const char *	cgul_substring__search_ez (cgul_exception_t cex, const char ss, size_t ss_length, const char *block, size_t block_length)

CGUL_EXPORT cgul_substring_t	cgul_substring__new (cgul_exception_t *cex)

CGUL_EXPORT cgul_substring_t	cgul_substring__new_from_cstring (cgul_exception_t cex, const char substring)

CGUL_EXPORT cgul_substring_t	cgul_substring__new_from_bstring (cgul_exception_t cex, const char substring, size_t length)

CGUL_EXPORT void	cgul_substring__delete (cgul_substring_t ss)

CGUL_EXPORT const char *	cgul_substring__get_value (cgul_exception_t *cex, cgul_substring_t ss)

CGUL_EXPORT void	cgul_substring__set_value (cgul_exception_t cex, cgul_substring_t ss, const char substring, size_t length)

CGUL_EXPORT size_t	cgul_substring__get_length (cgul_exception_t *cex, cgul_substring_t ss)

CGUL_EXPORT const char *	cgul_substring__search (cgul_exception_t cex, cgul_substring_t ss, const char block, size_t length)

Detailed Description

Substring search. This class performs a substring search using the Rabin-Karp algorithm which is effectively O(m + n) where m is the length of the substring and n is the length of the string being searched.

Author: Paul Serice

Typedef Documentation

§ cgul_substring_t

typedef typedefCGUL_BEGIN_C struct cgul_substring* cgul_substring_t

Opaque pointer to a cgul_substring instance.

Function Documentation

§ cgul_substring__search_ez()

CGUL_EXPORT const char* cgul_substring__search_ez	(	cgul_exception_t *	cex,
		const char *	ss,
		size_t	ss_length,
		const char *	block,
		size_t	block_length
	)

This function is the easy way to search because it does not require the user to allocate a cgul_substring instance. Instead, just pass in the binary substring ss and its length ss_length in bytes along with the binary block block to search and its length block_length in bytes. If the substring is found, a pointer to the first matching character of the substring in block is returned; otherwise, NULL is returned.

If you are only going to search block once, in addition to being easier to use, this function will be faster than cgul_substring__search() because this function does not copy the substring.

Parameters

[in]	cex	c-style exception
[in]	ss	binary substring
[in]	ss_length	substring length in bytes
[in]	block	block of binary data to search
[in]	block_length	block length in bytes

Returns: pointer to first match or NULL if no match

Referenced by cgul_substring_cxx::search_ez().

§ cgul_substring__new()

CGUL_EXPORT cgul_substring_t cgul_substring__new ( cgul_exception_t * cex )

Create a new cgul_substring instance. The caller is responsible for calling cgul_substring__delete() on the pointer returned. If an error occurs, NULL is returned, and an exception is thrown.

Parameters

[in,out] cex c-style exception

Returns: new cgul_substring instance

Referenced by cgul_substring_cxx::cgul_substring_cxx().

§ cgul_substring__new_from_cstring()

CGUL_EXPORT cgul_substring_t cgul_substring__new_from_cstring	(	cgul_exception_t *	cex,
		const char *	substring
	)

Create a new cgul_substring instance initializing the substring from the C-style string substring. The caller is responsible for calling cgul_substring__delete() on the pointer returned. If an error occurs, NULL is returned, and an exception is thrown.

Parameters

[in,out]	cex	c-style exception
[in]	substring	c-style substring

Returns: new cgul_substring instance

Referenced by cgul_substring_cxx::cgul_substring_cxx().

§ cgul_substring__new_from_bstring()

CGUL_EXPORT cgul_substring_t cgul_substring__new_from_bstring	(	cgul_exception_t *	cex,
		const char *	substring,
		size_t	length
	)

Create a new cgul_substring instance initializing the substring from the binary string substring extending for length bytes. The caller is responsible for calling cgul_substring__delete() on the pointer returned. If an error occurs, NULL is returned, and an exception is thrown.

Parameters

[in,out]	cex	c-style exception
[in]	substring	binary substring
[in]	length	length of `substring`

Returns: new cgul_substring instance

Referenced by cgul_substring_cxx::cgul_substring_cxx().

§ cgul_substring__delete()

CGUL_EXPORT void cgul_substring__delete ( cgul_substring_t ss )

Delete the cgul_substring instance ss freeing all internally allocated resources. The caller must not attempt to dereference ss after calling this function.

Parameters

[in] ss cgul_substring instance

Referenced by cgul_substring_cxx::~cgul_substring_cxx().

§ cgul_substring__get_value()

CGUL_EXPORT const char* cgul_substring__get_value	(	cgul_exception_t *	cex,
		cgul_substring_t	ss
	)

Get the value used as the substring in subsequent searches. The value can be set by calling cgul_substring__set_value(). If the value is not set, NULL is returned.

Parameters

[in]	cex	c-style exception
[in]	ss	`cgul_substring` instance

Returns: value used as the substring in subsequent searches

Referenced by cgul_substring_cxx::get_value().

§ cgul_substring__set_value()

CGUL_EXPORT void cgul_substring__set_value	(	cgul_exception_t *	cex,
		cgul_substring_t	ss,
		const char *	substring,
		size_t	length
	)

Set the value to use as the substring in subsequent searches. This function must be called before calling cgul_substring__search(). It caches the pre-computations based on the substring so that subsequent searches for the same substring will not have to recompute the same values. If an error occurs, an exception is thrown.

In addition to caching the pre-computed values, this function also caches a copy of substring for use with cgul_substring__search(). Because cgul_substring__search_ez() does not copy the substring, it is not always clear whether cgul_substring__search() or cgul_substring__search_ez() will run faster.

Parameters

[in,out]	cex	c-style exception
[in]	ss	`cgul_substring` instance
[in]	substring	binary substring
[in]	length	length of `substring`

Referenced by cgul_substring_cxx::operator=(), and cgul_substring_cxx::set_value().

§ cgul_substring__get_length()

CGUL_EXPORT size_t cgul_substring__get_length	(	cgul_exception_t *	cex,
		cgul_substring_t	ss
	)

Get the length of the substring that will be used in subsequent searches. The substring can be set by calling cgul_substring__set_value(). If the substring is not set, 0 is returned.

Parameters

[in]	cex	c-style exception
[in]	ss	`cgul_substring` instance

Returns: length of the substring that will be used in subsequent searches

Referenced by cgul_substring_cxx::get_length().

§ cgul_substring__search()

CGUL_EXPORT const char* cgul_substring__search	(	cgul_exception_t *	cex,
		cgul_substring_t	ss,
		const char *	block,
		size_t	length
	)

Search the first length bytes of block block for the substring set by the most recent call to cgul_substring__set_value(). If the substring is found, a pointer to the first matching character in block is returned; otherwise, NULL is returned.

Parameters

[in]	cex	c-style exception
[in]	ss	`cgul_substring` instance
[in]	block	block of binary data to search
[in]	length	block length in bytes

Returns: pointer to first match or NULL if no match

Referenced by cgul_substring_cxx::search().

Typedefs

Functions

Detailed Description

Typedef Documentation

§ cgul_substring_t

Function Documentation

§ cgul_substring__search_ez()

§ cgul_substring__new()

§ cgul_substring__new_from_cstring()

§ cgul_substring__new_from_bstring()

§ cgul_substring__delete()

§ cgul_substring__get_value()

§ cgul_substring__set_value()

§ cgul_substring__get_length()

§ cgul_substring__search()