optimize: added a tail pointer in mntinfo_add_list #2593
Conversation
| @@ -90,6 +90,7 @@ struct mount_info { | |||
| int deleted_level; | |||
| struct list_head deleted_list; | |||
| struct mount_info *next; | |||
| struct mount_info *tail; | |||
There was a problem hiding this comment.
I think it is better to user the list_head structure here.
There was a problem hiding this comment.
You mean instead of mount_info *tail should I make it list_head tail
There was a problem hiding this comment.
I mean we can use the standard list here instead of reinventing a bicycle.
There was a problem hiding this comment.
I'm sorry if this conversation is taking long.. the thing is the list_head is of different type in order to store the tail of a struct mount_info* shouldn't we use the struct mount_info* type?? because in the code mount.c (where I have changed code) the struct mount_info *mntinfo was the single linked list as it was told in the comment (file : mount.c, line : 110) and the struct mount_info *new has to traverse the struct mount_info *mntinfo (file : mount.c, line : 122) in order to find the tail of it ( if the *mntinfo wasn't empty) thats why I created a struct mount_info* tail in order to hold the pointer to tail. Any node of type struct mount_info* can have its tail stored in it so that it can fetch in O(1) time. I know its reinventing a bicycle but the thing is I can't understand how can I use the struct list_head cause there is a mismatch in type in order to hold the tail of anything of type struct mount_info*. Maybe I can wrong here by misunderstanding what you tried to say you can rectify me I am a beginner currently learning things.
|
@avagin What changes should I make to the code overall? |
|
Here is just one logical change, so it should be just one patch. The subject line starts with the subsystem prefix. In this case, it is |
The mntinfo_add_list function previously traversed the entire linked list to find the tail node, resulting in a time complexity of O(n). This commit introduces a mntinfo_tail pointer to track the last node of the list, reducing the time complexity of insertion to O(1).