[PATCH 4/5] cyclic: switch to using hlist instead of list

[Stefan Roese]

On 28.10.22 13:50, Rasmus Villemoes wrote:
> A hlist is headed by just a single pointer, so can only be traversed
> forwards, and insertions can only happen at the head (or before/after
> an existing list member). But each list node still consists of two
> pointers, so arbitrary elements can still be removed in O(1).
> 
> This is precisely what we need for the cyclic_list - we never need to
> traverse it backwards, and the order the callbacks appear in the list
> should really not matter.
> 
> One advantage, and the main reason for doing this switch, is that an
> empty list is represented by a NULL head pointer, so unlike a
> list_head, it does not need separate C code to initialize - a
> memset(,0,) of the containing structure is sufficient.
> 
> This is mostly mechanical:
> 
> - The iterators are updated with an h prefix, and the type of the
>    temporary variable changed to struct hlist_node*.
> 
> - Adding/removing is now just hlist_add_head (and not tail) and
>    hlist_del().
> 
> - struct members and function return values updated.
> 
> Signed-off-by: Rasmus Villemoes <rasmus.villemoes at prevas.dk>
> ---
>   cmd/cyclic.c     |  5 +++--
>   common/cyclic.c  | 18 ++++++++++--------
>   include/cyclic.h |  6 +++---
>   3 files changed, 16 insertions(+), 13 deletions(-)
> 
> diff --git a/cmd/cyclic.c b/cmd/cyclic.c
> index c1bc556aad..97324d8240 100644
> --- a/cmd/cyclic.c
> +++ b/cmd/cyclic.c
> @@ -61,10 +61,11 @@ static int do_cyclic_demo(struct cmd_tbl *cmdtp, int flag, int argc,
>   static int do_cyclic_list(struct cmd_tbl *cmdtp, int flag, int argc,
>   			  char *const argv[])
>   {
> -	struct cyclic_info *cyclic, *tmp;
> +	struct cyclic_info *cyclic;
> +	struct hlist_node *tmp;
>   	u64 cnt, freq;
>   
> -	list_for_each_entry_safe(cyclic, tmp, cyclic_get_list(), list) {
> +	hlist_for_each_entry_safe(cyclic, tmp, cyclic_get_list(), list) {
>   		cnt = cyclic->run_cnt * 1000000ULL * 100ULL;
>   		freq = lldiv(cnt, timer_get_us() - cyclic->start_time_us);
>   		printf("function: %s, cpu-time: %lld us, frequency: %lld.%02d times/s\n",
> diff --git a/common/cyclic.c b/common/cyclic.c
> index d6f11b002e..32d9bf0d02 100644
> --- a/common/cyclic.c
> +++ b/common/cyclic.c
> @@ -20,7 +20,7 @@ DECLARE_GLOBAL_DATA_PTR;
>   
>   void hw_watchdog_reset(void);
>   
> -struct list_head *cyclic_get_list(void)
> +struct hlist_head *cyclic_get_list(void)
>   {
>   	return &gd->cyclic->cyclic_list;
>   }
> @@ -47,14 +47,14 @@ struct cyclic_info *cyclic_register(cyclic_func_t func, uint64_t delay_us,
>   	cyclic->name = strdup(name);
>   	cyclic->delay_us = delay_us;
>   	cyclic->start_time_us = timer_get_us();
> -	list_add_tail(&cyclic->list, &gd->cyclic->cyclic_list);
> +	hlist_add_head(&cyclic->list, &gd->cyclic->cyclic_list);
>   
>   	return cyclic;
>   }
>   
>   int cyclic_unregister(struct cyclic_info *cyclic)
>   {
> -	list_del(&cyclic->list);
> +	hlist_del(&cyclic->list);
>   	free(cyclic);
>   
>   	return 0;
> @@ -62,7 +62,8 @@ int cyclic_unregister(struct cyclic_info *cyclic)
>   
>   void cyclic_run(void)
>   {
> -	struct cyclic_info *cyclic, *tmp;
> +	struct cyclic_info *cyclic;
> +	struct hlist_node *tmp;
>   	uint64_t now, cpu_time;
>   
>   	/* Prevent recursion */
> @@ -70,7 +71,7 @@ void cyclic_run(void)
>   		return;
>   
>   	gd->flags |= GD_FLG_CYCLIC_RUNNING;
> -	list_for_each_entry_safe(cyclic, tmp, &gd->cyclic->cyclic_list, list) {
> +	hlist_for_each_entry_safe(cyclic, tmp, &gd->cyclic->cyclic_list, list) {
>   		/*
>   		 * Check if this cyclic function needs to get called, e.g.
>   		 * do not call the cyclic func too often
> @@ -118,9 +119,10 @@ void schedule(void)
>   
>   int cyclic_uninit(void)
>   {
> -	struct cyclic_info *cyclic, *tmp;
> +	struct cyclic_info *cyclic;
> +	struct hlist_node *tmp;
>   
> -	list_for_each_entry_safe(cyclic, tmp, &gd->cyclic->cyclic_list, list)
> +	hlist_for_each_entry_safe(cyclic, tmp, &gd->cyclic->cyclic_list, list)
>   		cyclic_unregister(cyclic);
>   
>   	return 0;
> @@ -135,7 +137,7 @@ int cyclic_init(void)
>   		return -ENOMEM;
>   
>   	memset(gd->cyclic, '\0', size);
> -	INIT_LIST_HEAD(&gd->cyclic->cyclic_list);
> +	INIT_HLIST_HEAD(&gd->cyclic->cyclic_list);
>   
>   	return 0;
>   }
> diff --git a/include/cyclic.h b/include/cyclic.h
> index 263b74d89b..4a11f9b105 100644
> --- a/include/cyclic.h
> +++ b/include/cyclic.h
> @@ -20,7 +20,7 @@
>    * @cyclic_list: Cylic list node
>    */
>   struct cyclic_drv {
> -	struct list_head cyclic_list;
> +	struct hlist_head cyclic_list;
>   };
>   
>   /**
> @@ -46,7 +46,7 @@ struct cyclic_info {
>   	uint64_t cpu_time_us;
>   	uint64_t run_cnt;
>   	uint64_t next_call;
> -	struct list_head list;
> +	struct hlist_node list;
>   	bool already_warned;
>   };
>   
> @@ -95,7 +95,7 @@ int cyclic_uninit(void);
>    *
>    * @return: pointer to cyclic_list
>    */
> -struct list_head *cyclic_get_list(void);
> +struct hlist_head *cyclic_get_list(void);
>   
>   /**
>    * cyclic_run() - Interate over all registered cyclic functions

Reviewed-by: Stefan Roese <sr at denx.de>
Tested-by: Stefan Roese <sr at denx.de>

Thanks,
Stefan