contributed by < lineagech
>
typeof
typeof is a compiler extension
offsetof
Using 0 address and cast it into type pointer, and then points to member to get the offset from 0 address, and finally cast to size_t.
Suffix rules are rules of the form .c.o. They are a way of telling make that any time you see, say, a .f file (the source file), you can make a .o file (the target file) from it by following that rule, where $< indicates the source file and $@ represents the target file.
Static pattern rules are rules which specify multiple targets and construct the prerequisite names for each target based on the target name. They are more general than ordinary rules with multiple targets because the targets do not have to have identical prerequisites. Their prerequisites must be analogous, but not necessarily identical.
$(objects): %.o: %.c
$(CC) -c $(CFLAGS) $< -o $@
ๅๅบ Linux ๆ ธๅฟ็จๅผ็ขผๆ๏ผ้่ฆๆจๆณจ็ๆฌ่ณ่จ๏ผ้ฟๅ
่ณ่จ้ๆ
jserv
list_head
in task_struct in include/linux/sched.h
, and there is a run_list
, and its operation like real-time scheduling: push a list of entities to a priority queue according to the entity's prioritypage
according to its list_head lru
. Here I guess it sorts pages according to lru policy and then can find relative struct ebased on the list_head noe:arch/arm/mm/mmu.c
, linux memory management maintains a static virtual memory which may be used by ioremap/vmalloc(?) list. The follwoing code fill dummy vm entries by traversing the list.GNU extension ็ typeof ๆไฝไฝ็จ๏ผๅจ็จๅผ็ขผไธญๆฎๆผไป้บผ่ง่ฒ๏ผ
It can refer to type of an expression.
e.g.
#define pointer(T) typeof(T *)
#define array(T, N) typeof(T [N])
In pratice we can just get the type we wanted dynamically and like use it in macro.
่งฃ้ไปฅไธๅทจ้็ๅ็
__extension__: GCC uses the extension attribute when using the -ansi/-pedantic flag to avoid warnings in headers with GCC extensions, such as ({โฆ}).
we can get the pointer __pmember
type of type->member
in struct by using typeof so that we dont need to know what type it is explicitly.
And subtract the offset, from starting address to address of member
by offsetof
.
Finally it gets the address of object containing member whose address is ptr
.
้คไบไฝ ็ๆ็ add ๅ delete ๆไฝ๏ผlist.h
้ๅฎ็พฉไธ็ณปๅๆไฝ๏ผ็บไป้บผๅข๏ผ้ไบๆไป้บผ็่๏ผ
Ans.ใIn addition to add and delete, there are other operations like:
I think kernel maintains lots of lists which is sorted based on some criterions. Due to those macro operations, it can add or remove a node even a list to or from another more efficiently.
LIST_POISONING
้ๆจฃ็่จญ่จๆไฝๆ็พฉ๏ผ
It is defined in linux/position.h
. And comment is
Linux purposely let head point to specific addresses and page faults will happen. The design can make kernel know someone has accessed empty list, easy to debug(?), not very sure.
linked list ๆก็จ็ฐ็ๆฏๅบๆผๅชไบ่้๏ผ
I think it is a performance issue. Based on the operations defined in linux.h
, sometimes it needs to add/delete a list at the head of tail. So circular list will make operations easier.
ไป้บผๆ
ๅขๆ้่ฆๅฐ linked list ๅๆๅบๅข๏ผ่ๅบ็ๅฏฆไธ็็ๆ็จ๏ผๆๅฅฝๅจไฝๆฅญ็ณป็ตฑๆ ธๅฟๅบ็พ
Like priority-based scheduling, kernel will schedule process according to its priority value, and also the number of process is not fixed. So better using list and sort it.
ไป้บผๆ
ๅขๆ้่ฆ้่ฆๆพๅฐ ็ฌฌ k ๅคง/ๅฐๅ
็ด ๅข๏ผๅ๏ผไฝ ๆ็ฎๅฆไฝๅฏฆไฝ๏ผ
*
list_for_each_safe
ๅ list_for_each
็ๅทฎ็ฐๅจๅช๏ผ"safe" ๅจๅท่กๆๆ็ๅฝฑ้ฟ็บไฝ๏ผ
list_for_each_safe additionaly memorize next pointer so that it allows users to delete node after getting it and will not affect traversing.
for_each ้ขจๆ ผ็้็ผๆนๅผๅฐ็จๅผ้็ผ่
็ๅฝฑ้ฟ็บไฝ๏ผ
for_each is more like python as:
It hide for-loop details and need simple one line. I think it is a more concise way for programmer.
็จๅผ่จป่งฃ่ฃก้ ญๅคง้ๅญๅจ @
็ฌฆ่๏ผ้ๆไฝๆ็พฉ๏ผไฝ ่ฝๅฆๆ็จๅจๅพ็บ็็จๅผ้็ผๅข๏ผ
It is specified by Doxygen rules:
Like function parameters, we can just specify @param etc. It is a clearer way for others tracing code afterwards
tests/
็ฎ้ๅบไธ็ unit test ็ไฝ็จ็บไฝ๏ผๅฐฑ่ป้ซๅทฅ็จไพ่ชช็็ฒพ็ฅ็บไฝ๏ผ
Unit test means that testing every single function you have and write some test programs or scripts to test it. Like those *.c
files in the tests/
, every *.c
is just a prgram to verify each list operation using assert
tests/
็ฎ้็ unit test ๅฏๅฆไฝๆ็บ็ฒพ้ฒๅๆนๅๅข๏ผ
Under example/
folder, I just modify the source c file to get user input indicating unsorted array size and Makefile to do multiple unit tests automatically, the same as applying to tests/
:
ไธ้่ฆๅผต่ฒผๅฎๆด็จๅผ็ขผ (็ฝฎๆผ GitHub ๅณๅฏ)๏ผ็ธๅ็๏ผไฝ ๆ่ฉฒ้ก่ฟฐๅฏฆไฝ่ๅพ็ๆ็ถญๅ่้้ป๏ผ็นๅฅ่ฆ่ซๅฆไฝ้ฉ่ญๅ่ฝ
jserv
merge-sort.c
:
list_mergesort
list_split
list_merge
.c
files. Type make
to compile all source files and type make test
to do unit test automatically: