trace-cmd: remove ununsed knuth_hash*() routines
PATCH 1/1 trace-cmd: remove ununsed knuth_hash*() routines
Neither knuth_hash16() nor knuth_hash() are used.
Delete them.
--- lib/trace-cmd/trace-filter-hash.c | 20 -------------------- 1 file changed, 20 deletions(-)
lib/trace-cmd/trace-filter-hash.c +0 -20
@@ -29,26 +29,6 @@ static inline uint8_t knuth_hash8(uint32_t val)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) -{ -/* -* Multiplicative hashing function. -* Multiplication by the Prime number, closest to the golden -* ratio of 2^32. -*/ -return val *UINT32_C (2654435761 ); -} -struct tracecmd_filter_id_item *tracecmd_filter_id_find (struct tracecmd_filter_id *hash,int id) {
Signature · 1 line
2.22.0.410.gd8fdbe21b5-goog
Quoted 3 lines · On Tue, 25 Jun 2019 23:01:01 -0700 Greg Thelen <[email protected]> wrote:
Neither
knuth_hash16()norknuth_hash()are used.
Delete them.
Yordan,
Do you foresee that we will be using the other two versions of the hash?
-- Steve
Quoted 36 lines
Signed-off-by Greg Thelen <[email protected]>--- lib/trace-cmd/trace-filter-hash.c | 20 -------------------- 1 file changed, 20 deletions(-)lib/trace-cmd/trace-filter-hash.c +0
-20@@ -29,26 +29,6 @@ static inline uint8_t knuth_hash8(uint32_t val)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) -{ -/* -* Multiplicative hashing function. -* Multiplication by the Prime number, closest to the golden -* ratio of 2^32. -*/ -return val *UINT32_C (2654435761 ); -} -struct tracecmd_filter_id_item *tracecmd_filter_id_find (struct tracecmd_filter_id *hash,int id) {
Quoted 7 lines · Steven Rostedt
Quoted 3 lines · On Tue, 25 Jun 2019 23:01:01 -0700 Greg Thelen <[email protected]> wrote:
Neither
knuth_hash16()norknuth_hash()are used.
Delete them.
Quoted 6 lines
Yordan,
Do you foresee that we will be using the other two versions of the hash?
-- Steve
Hi Greg,
Thanks for the fix!
I agree that we have to remove the unused hashing functions, but may I ask you to do a little bit of extra work here. I think that if we are going to keep only one hashing function this function can be called simply knuth_has (not knuth_has8).
Also the comment on top which refers to the TAOCP book must be modified stating that the original idea from the book (32 bit hash) was adapted in order to be used for small tables.
cheers,
Yordan
PS: I just saw couple of new patches coming from you and I want to say that your help is more than welcome.
Quoted 37 lines
Quoted 36 lines
Signed-off-by Greg Thelen <[email protected]>--- lib/trace-cmd/trace-filter-hash.c | 20 -------------------- 1 file changed, 20 deletions(-)lib/trace-cmd/trace-filter-hash.c +0
-20@@ -29,26 +29,6 @@ static inline uint8_t knuth_hash8(uint32_t val)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) -{ -/* -* Multiplicative hashing function. -* Multiplication by the Prime number, closest to the golden -* ratio of 2^32. -*/ -return val *UINT32_C (2654435761 ); -} -struct tracecmd_filter_id_item *tracecmd_filter_id_find (struct tracecmd_filter_id *hash,int id) {
Quoted 8 lines · On Thu, 27 Jun 2019 18:40:27 +0300 "Yordan Karadzhov (VMware)"…
Hi Greg,
Thanks for the fix!
I agree that we have to remove the unused hashing functions, but may I ask you to do a little bit of extra work here.
I think that if we are going to keep only one hashing function this function can be called simplyknuth_has(notknuth_has8).
Hi Yordan,
Small nit. I think you meant "knuth_hash" not "knuth_has", even though I'm sure knuth has a lot ;-)
Quoted 4 lines
Also the comment on top which refers to the TAOCP book must be modified stating that the original idea from the book (32 bit hash) was adapted in order to be used for small tables.
Ack.
-- Steve
Quoted 20 lines · Steven Rostedt
Quoted 8 lines · On Thu, 27 Jun 2019 18:40:27 +0300 "Yordan Karadzhov (VMware)"…
Hi Greg,
Thanks for the fix!
I agree that we have to remove the unused hashing functions, but may I ask you to do a little bit of extra work here.
I think that if we are going to keep only one hashing function this function can be called simplyknuth_has(notknuth_has8).Hi Yordan,
Small nit. I think you meant "
knuth_hash" not "knuth_has", even though I'm sure knuth has a lot ;-)Quoted 1 line
Quoted 7 lines
Quoted 3 lines
Also the comment on top which refers to the TAOCP book must be modified stating that the original idea from the book (32 bit hash) was adapted in order to be used for small tables.
Ack.
-- Steve
Nod. I'll make these changes and post a patch in a day or so.
PATCH v2 1/1 trace-cmd: remove ununsed knuth_hash*() routines
In reply to Steven RostedtNeither 16-bit knuth_hash16() nor the 32-bit knuth_hash() are used. Delete them both.
And rename the remaining function: knuth_hash8() => knuth_hash()
--- kernel-shark/src/libkshark.c | 12 +++++----- lib/trace-cmd/trace-filter-hash.c | 40 +++++++------------------------ 2 files changed, 14 insertions(+), 38 deletions(-)
kernel-shark/src/libkshark.c +6 -6
@@ -252,13 +252,13 @@ void kshark_free(struct kshark_context *kshark_ctx)free (kshark_ctx); } -static inline uint8_t knuth_hash8 (uint32_t val) +static inline uint8_t knuth_hash (uint32_t val) {/* -* Hashing functions, based on Donald E. Knuth's Multiplicative -* hashing. See The Art of Computer Programming (TAOCP). -* Multiplication by the Prime number, closest to the golden -* ratio of 2^8. +* Small table hashing function adapted from Donald E. Knuth's 32 bit +* multiplicative hash. See The Art of Computer Programming (TAOCP). +* Multiplication by the Prime number, closest to the golden ratio of +* 2^8. */ return UINT8_C (val) *UINT8_C (157 ); }
@@ -282,7 +282,7 @@ kshark_add_task(struct kshark_context *kshark_ctx, int pid)struct kshark_task_list *list;uint8_t key; - key =knuth_hash8 (pid); + key =knuth_hash (pid); list =kshark_find_task (kshark_ctx, key, pid);if (list)return list;
lib/trace-cmd/trace-filter-hash.c +8 -32
@@ -14,45 +14,21 @@#define FILTER_HASH_SIZE 256 -/* -* 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) +static inline uint8_t knuth_hash (uint32_t val) {/* -* Multiplicative hashing function. -* Multiplication by the Prime number, closest to the golden -* ratio of 2^8. +* Small table hashing function adapted from Donald E. Knuth's 32 bit +* multiplicative hash. See The Art of Computer Programming (TAOCP). +* 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) -{ -/* -* Multiplicative hashing function. -* Multiplication by the Prime number, closest to the golden -* ratio of 2^32. -*/ -return val *UINT32_C (2654435761 ); -} -struct tracecmd_filter_id_item *tracecmd_filter_id_find (struct tracecmd_filter_id *hash,int id) { -int key =knuth_hash8 (id); +int key =knuth_hash (id);struct tracecmd_filter_id_item *item = hash->hash[key];while (item) {
@@ -66,7 +42,7 @@ tracecmd_filter_id_find(struct tracecmd_filter_id *hash, int id)void tracecmd_filter_id_add (struct tracecmd_filter_id *hash,int id) { -int key =knuth_hash8 (id); +int key =knuth_hash (id);struct tracecmd_filter_id_item *item; item =calloc (1 ,sizeof (*item));
@@ -81,7 +57,7 @@ void tracecmd_filter_id_add(struct tracecmd_filter_id *hash, int id)void tracecmd_filter_id_remove (struct tracecmd_filter_id *hash,int id) { -int key =knuth_hash8 (id); +int key =knuth_hash (id);struct tracecmd_filter_id_item **next = &hash->hash[key];struct tracecmd_filter_id_item *item;
Signature · 1 line
2.22.0.410.gd8fdbe21b5-goog
Quoted 5 lines · Greg Thelen
Neither 16-bit
knuth_hash16()nor the 32-bitknuth_hash()are used. Delete them both.And rename the remaining function:
knuth_hash8()=>knuth_hash()
Thanks!
Quoted 113 lines
Signed-off-by Greg Thelen <[email protected]>--- kernel-shark/src/libkshark.c | 12 +++++----- lib/trace-cmd/trace-filter-hash.c | 40 +++++++------------------------ 2 files changed, 14 insertions(+), 38 deletions(-)kernel-shark/src/libkshark.c +6
-6@@ -252,13 +252,13 @@ void kshark_free(struct kshark_context *kshark_ctx)free (kshark_ctx); } -static inline uint8_t knuth_hash8 (uint32_t val) +static inline uint8_t knuth_hash (uint32_t val) {/* -* Hashing functions, based on Donald E. Knuth's Multiplicative -* hashing. See The Art of Computer Programming (TAOCP). -* Multiplication by the Prime number, closest to the golden -* ratio of 2^8. +* Small table hashing function adapted from Donald E. Knuth's 32 bit +* multiplicative hash. See The Art of Computer Programming (TAOCP). +* Multiplication by the Prime number, closest to the golden ratio of +* 2^8. */ return UINT8_C (val) *UINT8_C (157 ); }@@ -282,7 +282,7 @@ kshark_add_task(struct kshark_context *kshark_ctx, int pid)struct kshark_task_list *list;uint8_t key; - key =knuth_hash8 (pid); + key =knuth_hash (pid); list =kshark_find_task (kshark_ctx, key, pid);if (list)return list;lib/trace-cmd/trace-filter-hash.c +8
-32@@ -14,45 +14,21 @@#define FILTER_HASH_SIZE 256 -/* -* 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) +static inline uint8_t knuth_hash (uint32_t val) {/* -* Multiplicative hashing function. -* Multiplication by the Prime number, closest to the golden -* ratio of 2^8. +* Small table hashing function adapted from Donald E. Knuth's 32 bit +* multiplicative hash. See The Art of Computer Programming (TAOCP). +* 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) -{ -/* -* Multiplicative hashing function. -* Multiplication by the Prime number, closest to the golden -* ratio of 2^32. -*/ -return val *UINT32_C (2654435761 ); -} -struct tracecmd_filter_id_item *tracecmd_filter_id_find (struct tracecmd_filter_id *hash,int id) { -int key =knuth_hash8 (id); +int key =knuth_hash (id);struct tracecmd_filter_id_item *item = hash->hash[key];while (item) {@@ -66,7 +42,7 @@ tracecmd_filter_id_find(struct tracecmd_filter_id *hash, int id)void tracecmd_filter_id_add (struct tracecmd_filter_id *hash,int id) { -int key =knuth_hash8 (id); +int key =knuth_hash (id);struct tracecmd_filter_id_item *item; item =calloc (1 ,sizeof (*item));@@ -81,7 +57,7 @@ void tracecmd_filter_id_add(struct tracecmd_filter_id *hash, int id)void tracecmd_filter_id_remove (struct tracecmd_filter_id *hash,int id) { -int key =knuth_hash8 (id); +int key =knuth_hash (id);struct tracecmd_filter_id_item **next = &hash->hash[key];struct tracecmd_filter_id_item *item;
Quoted 7 lines · On Fri, 28 Jun 2019 23:27:52 -0700 Greg Thelen <[email protected]> wrote:
Neither 16-bit
knuth_hash16()nor the 32-bitknuth_hash()are used. Delete them both.And rename the remaining function:
knuth_hash8()=>knuth_hash()Signed-off-by Greg Thelen <[email protected]>
Thanks Greg, I applied this.
Note, when sending a v2 patch, it is best to start a new thread, as some maintainer's patch maintenance systems (including mine) have trouble dealing with patches within threads. That is, they tend to get lost easier.
Thanks!
-- Steve