hashtable: introduce a small and naive hashtable
PATCH v6 1/1 hashtable: introduce a small and naive hashtable
This hashtable implementation is using hlist buckets to provide a simple hashtable to prevent it from getting reimplemented all over the kernel.
---
Changes since v5:
- Fix hash_init.
- Clarify this implementation deals with statically allocated hashtables only.
include/linux/hashtable.h | 190 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 190 insertions(+) create mode 100644 include/linux/hashtable.h
include/linux/hashtable.h new file +190 -0
@@ -0,0 +1,190 @@ +/* +* Statically sized hash table implementation +* (C) 2012 Sasha Levin <[email protected]> +*/ + +#ifndef _LINUX_HASHTABLE_H +#define _LINUX_HASHTABLE_H + +#include <linux/list.h> +#include <linux/types.h> +#include <linux/kernel.h> +#include <linux/hash.h> +#include <linux/rculist.h> + +#define DEFINE_HASHTABLE (name, bits) \ + struct hlist_head name[HASH_SIZE(bits)] = \ + { [0 ... HASH_SIZE(bits) - 1] = HLIST_HEAD_INIT } + +#define DECLARE_HASHTABLE (name, bits) \ + struct hlist_head name[1 << (bits)] + +#define HASH_SIZE (name) (1 << HASH_BITS(name)) +#define HASH_BITS (name) ilog2(ARRAY_SIZE(name)) + +/* Use hash_32 when possible to allow for fast 32bit hashing in 64bit kernels. */ +#define hash_min (val, bits) \ +({ \ + sizeof(val) <= 4 ? \ + hash_32(val, bits) : \ + hash_long(val, bits); \ +}) + +/** +* hash_init - initialize a hash table +* @hashtable: hashtable to be initialized +* +* Calculates the size of the hashtable from the given parameter, otherwise +* same as hash_init_size. +* +* This has to be a macro since HASH_BITS() will not work on pointers since +* it calculates the size during preprocessing. +*/ +#define hash_init (hashtable) \ +({ \ + int __i; \ + \ + for (__i = 0; __i < HASH_SIZE(hashtable); __i++) \ + INIT_HLIST_HEAD(&hashtable[__i]); \ +}) + +/** +* hash_add - add an object to a hashtable +* @hashtable: hashtable to add to +* @node: the &struct hlist_node of the object to be added +* @key: the key of the object to be added +*/ +#define hash_add (hashtable, node, key) \ + hlist_add_head(node, &hashtable[hash_min(key, HASH_BITS(hashtable))]); + +/** +* hash_add_rcu - add an object to a rcu enabled hashtable +* @hashtable: hashtable to add to +* @node: the &struct hlist_node of the object to be added +* @key: the key of the object to be added +*/ +#define hash_add_rcu (hashtable, node, key) \ + hlist_add_head_rcu(node, &hashtable[hash_min(key, HASH_BITS(hashtable))]); + +/** +* hash_hashed - check whether an object is in any hashtable +* @node: the &struct hlist_node of the object to be checked +*/ +#define hash_hashed (node) (!hlist_unhashed(node)) + +/** +* hash_empty - check whether a hashtable is empty +* @hashtable: hashtable to check +* +* This has to be a macro since HASH_BITS() will not work on pointers since +* it calculates the size during preprocessing. +*/ +#define hash_empty (hashtable) \ +({ \ + int __i; \ + bool __ret = true; \ + \ + for (__i = 0; __i < HASH_SIZE(hashtable); __i++) \ + if (!hlist_empty(&hashtable[__i])) \ + __ret = false; \ + \ + __ret; \ +}) + +/** +* hash_del - remove an object from a hashtable +* @node: &struct hlist_node of the object to remove +*/ +static inline void hash_del (struct hlist_node *node) +{ +hlist_del_init (node); +} + +/** +* hash_del_rcu - remove an object from a rcu enabled hashtable +* @node: &struct hlist_node of the object to remove +*/ +static inline void hash_del_rcu (struct hlist_node *node) +{ +hlist_del_init_rcu (node); +} + +/** +* hash_for_each - iterate over a hashtable +* @name: hashtable to iterate +* @bkt: integer to use as bucket loop cursor +* @node: the &struct list_head to use as a loop cursor for each entry +* @obj: the type * to use as a loop cursor for each entry +* @member: the name of the hlist_node within the struct +*/ +#define hash_for_each (name, bkt, node, obj, member) \ + for (bkt = 0, node = NULL; node == NULL && bkt < HASH_SIZE(name); bkt++)\ + hlist_for_each_entry(obj, node, &name[bkt], member) + +/** +* hash_for_each_rcu - iterate over a rcu enabled hashtable +* @name: hashtable to iterate +* @bkt: integer to use as bucket loop cursor +* @node: the &struct list_head to use as a loop cursor for each entry +* @obj: the type * to use as a loop cursor for each entry +* @member: the name of the hlist_node within the struct +*/ +#define hash_for_each_rcu (name, bkt, node, obj, member) \ + for (bkt = 0, node = NULL; node == NULL && bkt < HASH_SIZE(name); bkt++)\ + hlist_for_each_entry_rcu(obj, node, &name[bkt], member) + +/** +* hash_for_each_safe - iterate over a hashtable safe against removal of +* hash entry +* @name: hashtable to iterate +* @bkt: integer to use as bucket loop cursor +* @node: the &struct list_head to use as a loop cursor for each entry +* @tmp: a &struct used for temporary storage +* @obj: the type * to use as a loop cursor for each entry +* @member: the name of the hlist_node within the struct +*/ +#define hash_for_each_safe (name, bkt, node, tmp, obj, member) \ + for (bkt = 0, node = NULL; node == NULL && bkt < HASH_SIZE(name); bkt++)\ + hlist_for_each_entry_safe(obj, node, tmp, &name[bkt], member) + +/** +* hash_for_each_possible - iterate over all possible objects hashing to the +* same bucket +* @name: hashtable to iterate +* @obj: the type * to use as a loop cursor for each entry +* @node: the &struct list_head to use as a loop cursor for each entry +* @member: the name of the hlist_node within the struct +* @key: the key of the objects to iterate over +*/ +#define hash_for_each_possible (name, obj, node, member, key) \ + hlist_for_each_entry(obj, node, &name[hash_min(key, HASH_BITS(name))], member) + +/** +* hash_for_each_possible_rcu - iterate over all possible objects hashing to the +* same bucket in an rcu enabled hashtable +* in a rcu enabled hashtable +* @name: hashtable to iterate +* @obj: the type * to use as a loop cursor for each entry +* @node: the &struct list_head to use as a loop cursor for each entry +* @member: the name of the hlist_node within the struct +* @key: the key of the objects to iterate over +*/ +#define hash_for_each_possible_rcu (name, obj, node, member, key) \ + hlist_for_each_entry_rcu(obj, node, &name[hash_min(key, HASH_BITS(name))], member) + +/** +* hash_for_each_possible_safe - iterate over all possible objects hashing to the +* same bucket safe against removals +* @name: hashtable to iterate +* @obj: the type * to use as a loop cursor for each entry +* @node: the &struct list_head to use as a loop cursor for each entry +* @tmp: a &struct used for temporary storage +* @member: the name of the hlist_node within the struct +* @key: the key of the objects to iterate over +*/ +#define hash_for_each_possible_safe (name, obj, node, tmp, member, key) \ + hlist_for_each_entry_safe(obj, node, tmp, \ + &name[hash_min(key, HASH_BITS(name))], member) + + +#endif
Signature · 1 line
1.7.12
Amazing how something simple gets lots of comments and versions :-)
Quoted 5 lines
...
+ * This has to be a macro sinceHASH_BITS()will not work on pointers since
+ * it calculates the size during preprocessing.
+ */include/linux/hashtable.h new file +1
-0+#define hash_empty (hashtable) \
include/linux/hashtable.h line 92
Quoted 10 lines
include/linux/hashtable.h new file +10
-0+({ \ +int __i; \ +bool __ret = true; \ + \ +for (__i =0 ; __i <HASH_SIZE (hashtable); __i++) \ +if (!hlist_empty (&hashtable[__i])) \ + __ret = false; \ + \ + __ret; \ +})
Actually you could have a #define that calls a function passing in the address and size.
Also, should the loop have a 'break' in it?
David
Quoted 12 lines · David Laight
Amazing how something simple gets lots of comments and versions :-)
Quoted 10 lines
...
+ * This has to be a macro sinceHASH_BITS()will not work on pointers since
+ * it calculates the size during preprocessing.
+ */include/linux/hashtable.h new file +6
-0+#define hash_empty (hashtable) \ +({ \ + int __i; \ + bool __ret = true; \ + \ + for (__i = 0; __i < HASH_SIZE(hashtable); __i++) \
Quoted 8 lines
include/linux/hashtable.h line 92
Quoted 5 lines
include/linux/hashtable.h new file +5
-0+if (!hlist_empty (&hashtable[__i])) \ + __ret = false; \ + \ + __ret; \ +})Actually you could have a #define that calls a function passing in the address and size.
Probably would be cleaner to do so.
Quoted 1 line
Also, should the loop have a 'break' in it?
Yeah it should, and could do:
for (i = 0; i < HASH_SIZE(hashtable); i++) if (!hlist_empty(&hashtable[i])) break; return i < HASH_SIZE(hashtable);
-- Steve
Quoted 22 lines · Steven Rostedt
Quoted 12 lines · David Laight
Amazing how something simple gets lots of comments and versions :-)
Quoted 10 lines
...
+ * This has to be a macro sinceHASH_BITS()will not work on pointers since
+ * it calculates the size during preprocessing.
+ */include/linux/hashtable.h new file +6
-0+#define hash_empty (hashtable) \ +({ \ + int __i; \ + bool __ret = true; \ + \ + for (__i = 0; __i < HASH_SIZE(hashtable); __i++) \Quoted 8 lines
include/linux/hashtable.h line 92
Quoted 5 lines
include/linux/hashtable.h new file +5
-0+if (!hlist_empty (&hashtable[__i])) \ + __ret = false; \ + \ + __ret; \ +})Actually you could have a #define that calls a function passing in the address and size.
Quoted 1 line
Probably would be cleaner to do so.
I think it's worth it if it was more complex than a simple loop. We were doing a similar thing with the _size() functions (see version 4 of this patch), but decided to remove it since it was becoming too complex.
Quoted 11 lines
Quoted 3 lines
Also, should the loop have a 'break' in it?
Yeah it should, and could do:
for (i = 0; i < HASH_SIZE(hashtable); i++) if (!hlist_empty(&hashtable[i])) break; return i < HASH_SIZE(hashtable);
Right.
Thanks,
Sasha
Quoted 23 lines · * Sasha Levin ([email protected]) wrote:
Quoted 22 lines · Steven Rostedt
Quoted 20 lines · David Laight
Amazing how something simple gets lots of comments and versions :-)
Quoted 5 lines
...
+ * This has to be a macro sinceHASH_BITS()will not work on pointers since
+ * it calculates the size during preprocessing.
+ */include/linux/hashtable.h new file +1
-0+#define hash_empty (hashtable) \include/linux/hashtable.h line 92
Quoted 10 lines
include/linux/hashtable.h new file +10
-0+({ \ +int __i; \ +bool __ret = true; \ + \ +for (__i =0 ; __i <HASH_SIZE (hashtable); __i++) \ +if (!hlist_empty (&hashtable[__i])) \ + __ret = false; \ + \ + __ret; \ +})Actually you could have a #define that calls a function passing in the address and size.
Quoted 6 lines
Quoted 1 line
Probably would be cleaner to do so.
I think it's worth it if it was more complex than a simple loop. We were doing a similar thing with the
_size()functions (see version 4 of this patch), but decided to remove it since it was becoming too complex.
Defining local variables within statement-expressions can have some unexpected side-effects if the "caller" which embeds the macro use the same variable name. See rcu_dereference() as an example (Paul uses an awefully large number of underscores). It should be avoided whenever possible.
Quoted 11 lines
Quoted 11 lines
Quoted 3 lines
Also, should the loop have a 'break' in it?
Yeah it should, and could do:
for (i = 0; i < HASH_SIZE(hashtable); i++) if (!hlist_empty(&hashtable[i])) break; return i < HASH_SIZE(hashtable);
Hrm, Steven, did you drink you morning coffee before writing this ? ;-) It looks like you did 2 bugs in 4 LOC.
First, the condition should be reversed, because this function returns whether the hash is empty, not the other way around.
And even then, if we would do:
for (i = 0; i < HASH_SIZE(hashtable); i++)
if (!hlist_empty(&hashtable[i]))
break;
return i >= HASH_SIZE(hashtable);
What happens if the last entry of the table is non-empty ?
So I would advise that Sasha keep his original flag-based implementation, but add the missing break, and move the init and empty define loops into static inlines.
Thanks,
Mathieu
Quoted 6 lines
Right.
Thanks,
Sasha
Signature · 4 lines
Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com
Quoted 47 lines · Mathieu Desnoyers
Quoted 23 lines · * Sasha Levin ([email protected]) wrote:
Quoted 22 lines · Steven Rostedt
Quoted 20 lines · David Laight
Amazing how something simple gets lots of comments and versions :-)
Quoted 5 lines
...
+ * This has to be a macro sinceHASH_BITS()will not work on pointers since
+ * it calculates the size during preprocessing.
+ */include/linux/hashtable.h new file +1
-0+#define hash_empty (hashtable) \include/linux/hashtable.h line 92
Quoted 10 lines
include/linux/hashtable.h new file +10
-0+({ \ +int __i; \ +bool __ret = true; \ + \ +for (__i =0 ; __i <HASH_SIZE (hashtable); __i++) \ +if (!hlist_empty (&hashtable[__i])) \ + __ret = false; \ + \ + __ret; \ +})Actually you could have a #define that calls a function passing in the address and size.
Quoted 6 lines
Quoted 1 line
Probably would be cleaner to do so.
I think it's worth it if it was more complex than a simple loop. We were doing a similar thing with the
_size()functions (see version 4 of this patch), but decided to remove it since it was becoming too complex.Defining local variables within statement-expressions can have some unexpected side-effects if the "caller" which embeds the macro use the same variable name. See
rcu_dereference()as an example (Paul uses an awefully large number of underscores). It should be avoided whenever possible.Quoted 10 lines
Quoted 10 lines
Quoted 3 lines
Also, should the loop have a 'break' in it?
Yeah it should, and could do:
for (i = 0; i < HASH_SIZE(hashtable); i++) if (!hlist_empty(&hashtable[i])) break;
Quoted 5 lines
Quoted 1 line
Quoted 1 line
return i < HASH_SIZE(hashtable);Hrm, Steven, did you drink you morning coffee before writing this ? ;-) It looks like you did 2 bugs in 4 LOC.
Coffee yes, but head cold as well. :-p
Quoted 3 lines
First, the condition should be reversed, because this function returns whether the hash is empty, not the other way around.
Bah, I was looking at the code the code and got the ret confused. I originally had it the opposite, and then reversed it before sending.
Quoted 10 lines
And even then, if we would do:
(quoted diff) +0
-0for (i = 0; i < HASH_SIZE(hashtable); i++) if (!hlist_empty(&hashtable[i])) break; return i >= HASH_SIZE(hashtable);What happens if the last entry of the table is non-empty ?
It still works, as 'i' is not incremented due to the break. And i will still be less than HASH_SIZE(hashtable). Did you have *your* cup of coffee today? ;-)
Quoted 5 lines
So I would advise that Sasha keep his original flag-based implementation, but add the missing break, and move the init and empty define loops into static inlines.
Nah,
-- Steve
Quoted 70 lines · * Steven Rostedt ([email protected]) wrote:
Quoted 47 lines · Mathieu Desnoyers
Quoted 23 lines · * Sasha Levin ([email protected]) wrote:
Quoted 22 lines · Steven Rostedt
Quoted 20 lines · David Laight
Amazing how something simple gets lots of comments and versions :-)
Quoted 5 lines
...
+ * This has to be a macro sinceHASH_BITS()will not work on pointers since
+ * it calculates the size during preprocessing.
+ */include/linux/hashtable.h new file +1
-0+#define hash_empty (hashtable) \include/linux/hashtable.h line 92
Quoted 10 lines
include/linux/hashtable.h new file +10
-0+({ \ +int __i; \ +bool __ret = true; \ + \ +for (__i =0 ; __i <HASH_SIZE (hashtable); __i++) \ +if (!hlist_empty (&hashtable[__i])) \ + __ret = false; \ + \ + __ret; \ +})Actually you could have a #define that calls a function passing in the address and size.
Quoted 6 lines
Quoted 1 line
Probably would be cleaner to do so.
I think it's worth it if it was more complex than a simple loop. We were doing a similar thing with the
_size()functions (see version 4 of this patch), but decided to remove it since it was becoming too complex.Defining local variables within statement-expressions can have some unexpected side-effects if the "caller" which embeds the macro use the same variable name. See
rcu_dereference()as an example (Paul uses an awefully large number of underscores). It should be avoided whenever possible.Quoted 10 lines
Quoted 10 lines
Quoted 3 lines
Also, should the loop have a 'break' in it?
Yeah it should, and could do:
for (i = 0; i < HASH_SIZE(hashtable); i++) if (!hlist_empty(&hashtable[i])) break;Quoted 5 lines
Quoted 1 line
Quoted 1 line
return i < HASH_SIZE(hashtable);Hrm, Steven, did you drink you morning coffee before writing this ? ;-) It looks like you did 2 bugs in 4 LOC.
Coffee yes, but head cold as well. :-p
Quoted 3 lines
First, the condition should be reversed, because this function returns whether the hash is empty, not the other way around.
Bah, I was looking at the code the code and got the ret confused. I originally had it the opposite, and then reversed it before sending.
Quoted 7 lines
And even then, if we would do:
(quoted diff) +0
-0for (i = 0; i < HASH_SIZE(hashtable); i++) if (!hlist_empty(&hashtable[i])) break;
Quoted 7 lines
Quoted 3 lines
return i >=
HASH_SIZE(hashtable);What happens if the last entry of the table is non-empty ?
It still works, as 'i' is not incremented due to the break. And i will still be less than
HASH_SIZE(hashtable). Did you have *your* cup of coffee today? ;-)
Ahh, right! Actually I had it already ;-)
Quoted 9 lines
Quoted 7 lines
So I would advise that Sasha keep his original flag-based implementation, but add the missing break, and move the init and empty define loops into static inlines.
Nah,
Agreed that the flags should be removed. Moving to define + static inline is still important though.
Thanks,
Mathieu
Quoted 4 lines
-- Steve
Signature · 4 lines
Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
And even then, if we would do:
(quoted diff) +0
-0for (i = 0; i < HASH_SIZE(hashtable); i++) if (!hlist_empty(&hashtable[i])) break; return i >= HASH_SIZE(hashtable);
Quoted 7 lines
Quoted 5 lines
Quoted 1 line
What happens if the last entry of the table is non-empty ?
It still works, as 'i' is not incremented due to the break. And i will still be less than
HASH_SIZE(hashtable). Did you have *your* cup of coffee today? ;-)Ahh, right! Actually I had it already ;-)
I tend to dislike the repeated test, gcc might be able to optimise it away, but the code is cleaner written as:
for (i = 0; i < HASH_SIZE(hashtable); i++) if (!hlist_empty(&hashtable[i])) return false; return true;
Quoted 2 lines
Agreed that the flags should be removed. Moving to define + static inline is still important though.
Not sure I'd bother making the function inline.
David
Quoted 16 lines · David Laight
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
And even then, if we would do:
(quoted diff) +0
-0for (i = 0; i < HASH_SIZE(hashtable); i++) if (!hlist_empty(&hashtable[i])) break; return i >= HASH_SIZE(hashtable);Quoted 7 lines
Quoted 5 lines
Quoted 1 line
What happens if the last entry of the table is non-empty ?
It still works, as 'i' is not incremented due to the break. And i will still be less than
HASH_SIZE(hashtable). Did you have *your* cup of coffee today? ;-)Ahh, right! Actually I had it already ;-)
Quoted 7 lines
I tend to dislike the repeated test, gcc might be able to optimise it away, but the code is cleaner written as:
for (i = 0; i < HASH_SIZE(hashtable); i++) if (!hlist_empty(&hashtable[i])) return false; return true;
Right, the flag thing in the macro was there just to make it work properly as a macro.
Quoted 4 lines
Quoted 2 lines
Agreed that the flags should be removed. Moving to define + static inline is still important though.
Not sure I'd bother making the function inline.
I usually never make anything 'inline', I just let gcc do it's own thing when it compiles the code. If there are any objections please let me know before I send the new version.
Thanks,
Sasha
Quoted 9 lines · Sasha Levin
Right, the flag thing in the macro was there just to make it work properly as a macro.
Quoted 4 lines
Quoted 2 lines
Agreed that the flags should be removed. Moving to define + static inline is still important though.
Not sure I'd bother making the function inline.
I usually never make anything 'inline', I just let gcc do it's own thing when it compiles the code. If there are any objections please let me know before I send the new version.
But this is a header file. You guys have no problem with macros, but refuse to use 'inline' for functions defined in header files? That doesn't make sense. A 'static inline' is basically a gcc macro, but without the side-effects.
-- Steve
Quoted 28 lines · * Sasha Levin ([email protected]) wrote:
Quoted 16 lines · David Laight
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
And even then, if we would do:
(quoted diff) +0
-0for (i = 0; i < HASH_SIZE(hashtable); i++) if (!hlist_empty(&hashtable[i])) break; return i >= HASH_SIZE(hashtable);Quoted 7 lines
Quoted 5 lines
Quoted 1 line
What happens if the last entry of the table is non-empty ?
It still works, as 'i' is not incremented due to the break. And i will still be less than
HASH_SIZE(hashtable). Did you have *your* cup of coffee today? ;-)Ahh, right! Actually I had it already ;-)
Quoted 7 lines
I tend to dislike the repeated test, gcc might be able to optimise it away, but the code is cleaner written as:
for (i = 0; i < HASH_SIZE(hashtable); i++) if (!hlist_empty(&hashtable[i])) return false; return true;Right, the flag thing in the macro was there just to make it work properly as a macro.
Quoted 8 lines
Quoted 4 lines
Quoted 2 lines
Agreed that the flags should be removed. Moving to define + static inline is still important though.
Not sure I'd bother making the function inline.
I usually never make anything 'inline', I just let gcc do it's own thing when it compiles the code. If there are any objections please let me know before I send the new version.
AFAIK, gcc nowadays use "inline" only as a hint, because programmers were using it everywhere, even where it should not have been used. This is where the attribute always_inline becomes useful, if you really, really want to inline. However, for kernel coding style consistency, it might be better to use "static inline", because it is used everywhere else in kernel headers. Or maybe are there some headers that do not use "inline" I am not aware of ?
Moreover, if your thinking is that we do not need a static inline function replicated at every caller, maybe we should introduce a lib/hashtable.c that implements those 2 functions.
Thanks,
Mathieu
Quoted 5 lines
Thanks,
Sasha
Signature · 4 lines
Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com
Quoted 1 line · Mathieu Desnoyers
AFAIK, gcc nowadays use "inline" only as a hint
Only if CONFIG_OPTIMIZE_INLINING is set.
Quoted 1 line
From
include/linux/compiler-gcc.h:
#if !defined(CONFIG_ARCH_SUPPORTS_OPTIMIZED_INLINING) || \
!defined(CONFIG_OPTIMIZE_INLINING) || (__GNUC__ < 4)
# define inline inline __attribute__((always_inline)) notrace
# define __inline__ __inline__ __attribute__((always_inline)) notrace
# define __inline __inline __attribute__((always_inline)) notrace
#else
/* A lot of inline functions can cause havoc with function tracing */
# define inline inline notrace
# define __inline__ __inline__ notrace
# define __inline __inline notrace
#endif-- Steve
Quoted 3 lines
Moreover, if your thinking is that we do not need a static inline function replicated at every caller, maybe we should introduce a
lib/hashtable.cthat implements those 2 functions.
That was my thought...
Given their nature, I'd guess they aren't critical path. Probably not worth adding an entire source file though.
With regard to 'inline', when I say it, I really mean it! Unfortunately some people seem to just type it anyway (rather like 'register' used to get used) - so the compilers start ignoring the request.
At least some versions of gcc will usually inline static functions that are only called once - but even then it can change its mind for almost no reason.
David
Quoted 16 lines · * David Laight ([email protected]) wrote:
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
And even then, if we would do:
(quoted diff) +0
-0for (i = 0; i < HASH_SIZE(hashtable); i++) if (!hlist_empty(&hashtable[i])) break; return i >= HASH_SIZE(hashtable);Quoted 7 lines
Quoted 5 lines
Quoted 1 line
What happens if the last entry of the table is non-empty ?
It still works, as 'i' is not incremented due to the break. And i will still be less than
HASH_SIZE(hashtable). Did you have *your* cup of coffee today? ;-)Ahh, right! Actually I had it already ;-)
Quoted 8 lines
I tend to dislike the repeated test, gcc might be able to optimise it away, but the code is cleaner written as:
for (i = 0; i < HASH_SIZE(hashtable); i++) if (!hlist_empty(&hashtable[i])) return false; return true;
Agreed, this looks like a good way to write it.
Quoted 4 lines
Quoted 2 lines
Agreed that the flags should be removed. Moving to define + static inline is still important though.
Not sure I'd bother making the function inline.
Do you mean you prefer to keep it as a macro, or that you don't think the "inline" keyword is relevant anymore, and want to do a "static" only function in the header file ?
In both cases, please explain the reasons for doing things that way.
Thanks,
Mathieu
Quoted 5 lines
David
Signature · 4 lines
Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com
Quoted 13 lines · * David Laight ([email protected]) wrote:
Amazing how something simple gets lots of comments and versions :-)
Quoted 11 lines
...
+ * This has to be a macro sinceHASH_BITS()will not work on pointers since
+ * it calculates the size during preprocessing.
+ */include/linux/hashtable.h new file +7
-0+#define hash_empty (hashtable) \ +({ \ + int __i; \ + bool __ret = true; \ + \ + for (__i = 0; __i < HASH_SIZE(hashtable); __i++) \ + if (!hlist_empty(&hashtable[__i])) \
Quoted 8 lines
include/linux/hashtable.h line 92
Quoted 4 lines
include/linux/hashtable.h new file +4
-0+ __ret = false; \ + \ + __ret; \ +})Actually you could have a #define that calls a function passing in the address and size.
Also, should the loop have a 'break' in it?
+1 Removing unnecessary variables defined within a
statement-expression is indeed something we want, and your suggestion of a macro calling a static inline is, IMHO, spot-on.
The same should be done for hash_init().
And yes, a break would be welcome in that loop: no need to continue if we encounter a non-empty hlist.
Thanks,
Mathieu
Signature · 4 lines
Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com