Re: [PATCH v2 2/2] trace-filter: Change the hashing function used when filtering

[Steven Rostedt <rostedt@goodmis.org>]

On Tue, 19 Jun 2018 16:22:59 +0300
"Yordan Karadzhov (VMware)" <y.karadz@gmail.com> wrote:

> diff --git a/kernel-shark/include/trace-filter-hash.h b/kernel-shark/include/trace-filter-hash.h
> index 5cc39dc..98c9ab3 100644
> --- a/kernel-shark/include/trace-filter-hash.h
> +++ b/kernel-shark/include/trace-filter-hash.h
> @@ -20,7 +20,7 @@
>  #ifndef _TRACE_FILTER_HASH_H
>  #define _TRACE_FILTER_HASH_H
>  
> -#include "trace-hash-local.h"
> +#include <stdint.h>
>  
>  struct filter_id_item {
>  	struct filter_id_item	*next;
> @@ -47,4 +47,39 @@ static inline int filter_task_count(struct filter_id *hash)
>  	return hash->count;
>  }
>  
> +/*
> + * Hashing functions, based on Donald E. Knuth's Multiplicative hashing.
> + * See The Art of Computer Programming (TAOCP).
> + */
> +
> +static inline uint8_t knuth_hash8(uint32_t val)
> +{
> +	/*
> +	 * Multiplicative hashing function.
> +	 * Multiplication by the Prime number, closest to the golden
> +	 * ratio of 2^8.
> +	 */
> +	return UINT8_C(val) * UINT8_C(157);
> +}
> +
> +static inline uint16_t knuth_hash16(uint32_t val)
> +{
> +	/*
> +	 * Multiplicative hashing function.
> +	 * Multiplication by the Prime number, closest to the golden
> +	 * ratio of 2^16.
> +	 */
> +	return UINT16_C(val) * UINT16_C(40507);
> +}
> +
> +static inline uint32_t knuth_hash(uint32_t val)

BTW, is there any reason to have these in the header file? Shouldn't
they be in a C file?

The reason I ask is because this is going to be in a more public file,
and I need to rename the functions for namespace reasons. These are
someone out of place for a library header.

-- Steve


> +{
> +	/*
> +	 * Multiplicative hashing function.
> +	 * Multiplication by the Prime number, closest to the golden
> +	 * ratio of 2^32.
> +	 */
> +	return val * UINT32_C(2654435761);
> +}
> +