rolling hash function More...

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

Include dependency graph for cgul_rolling_hash.h:

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

Functions
CGUL_BEGIN_C CGUL_EXPORT cgul_uint32_t	cgul_rolling_hash__hash (cgul_exception_t cex, const char block, size_t block_length)

CGUL_EXPORT cgul_uint32_t	cgul_rolling_hash__roll (cgul_exception_t *cex, cgul_uint32_t hv, const char c_old, const char c_new, size_t block_length)

Detailed Description

Rolling hash function. The rolling hash function allows the hash value to change incrementally by quickly removing the oldest byte and adding a new one to take its place. It is used by cgul_substring() to implement the Rabin-Karp substring search, but it can be used generally.

Author: Paul Serice

Function Documentation

§ cgul_rolling_hash__hash()

CGUL_BEGIN_C CGUL_EXPORT cgul_uint32_t cgul_rolling_hash__hash	(	cgul_exception_t *	cex,
		const char *	block,
		size_t	block_length
	)

This function calculates the hash value for length bytes in the block block. The main purpose of this function is to generate the initial hash value that can then be passed into cgul_rolling_hash__roll(), but it can also be used as a stand-alone hash function.

Parameters

[in]	cex	c-style exception
[in]	block	block of binary data
[in]	block_length	length of `block` in bytes

Returns: hash value

See also: cgul_rolling_hash__roll(); cgul_hash__hash_block()

Referenced by cgul_rolling_hash_cxx::hash().

§ cgul_rolling_hash__roll()

CGUL_EXPORT cgul_uint32_t cgul_rolling_hash__roll	(	cgul_exception_t *	cex,
		cgul_uint32_t	hv,
		const char	c_old,
		const char	c_new,
		size_t	block_length
	)

Peform a rolling hash calculation on the hash value hv by surgically removing the part of the hash value associated with the old character c_old that is being removed and adding the part of the hash value associated with the new character c_new that is being added. The initial value for hv should be obtained by calling cgul_rolling_hash__hash(). The value for block_length should be same as what originally was passed into cgul_rolling_hash__hash().

Parameters

[in]	cex	c-style exception
[in]	hv	old hash value
[in]	c_old	old character
[in]	c_new	new character
[in]	block_length	length of the block in bytes

Returns: new hash value

See also: cgul_rolling_hash__hash()

Referenced by cgul_rolling_hash_cxx::roll().

Functions

Detailed Description

Function Documentation

§ cgul_rolling_hash__hash()

§ cgul_rolling_hash__roll()