cgul_rolling_hash.h File Reference

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]cexc-style exception
[in]blockblock of binary data
[in]block_lengthlength 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]cexc-style exception
[in]hvold hash value
[in]c_oldold character
[in]c_newnew character
[in]block_lengthlength of the block in bytes
Returns
new hash value
See also
cgul_rolling_hash__hash()

Referenced by cgul_rolling_hash_cxx::roll().