add linked list exercise

[sudhackar]

Adding linked list exercise from https://github.com/exercism/problem-specifications/tree/main/exercises/linked-list

Example solution passed the build

$ docker build -t exx86 .
$ docker run -it --rm -v $PWD/exercises/practice/linked-list:/tmp/test  -v /tmp/out:/tmp/out --entrypoint /bin/sh --name temp exx86
/opt/test-runner # /opt/test-runner/bin/run.sh linked-list /tmp/test/ /tmp/out/

[x86-64-assembly] \cat /tmp/out/results.out
linked_list_test.c:232:test_pop_gets_element_from_the_list:PASS
linked_list_test.c:233:test_pushpop_respectively_addremove_at_the_end_of_the_list:PASS
linked_list_test.c:234:test_shift_gets_an_element_from_the_list:PASS
linked_list_test.c:235:test_shift_gets_first_element_from_the_list:PASS
linked_list_test.c:236:test_unshift_adds_element_at_start_of_the_list:PASS
linked_list_test.c:237:test_pop_push_shift_and_unshift_can_be_used_in_any_order:PASS
linked_list_test.c:238:test_count_an_empty_list:PASS
linked_list_test.c:239:test_count_a_list_with_items:PASS
linked_list_test.c:240:test_count_is_correct_after_mutation:PASS
linked_list_test.c:241:test_popping_to_empty_doesnt_break_the_list:PASS
linked_list_test.c:242:test_shifting_to_empty_doesnt_break_the_list:PASS
linked_list_test.c:243:test_deletes_the_only_element:PASS
linked_list_test.c:244:test_deletes_the_element_with_the_specified_value_from_the_list:PASS
linked_list_test.c:245:test_deletes_the_element_with_the_specified_value_from_the_list_reassigns_tail:PASS
linked_list_test.c:246:test_deletes_the_element_with_the_specified_value_from_the_list_reassigns_head:PASS
linked_list_test.c:247:test_deletes_the_first_of_two_elements:PASS
linked_list_test.c:248:test_deletes_the_second_of_two_elements:PASS
linked_list_test.c:249:test_delete_does_not_modify_the_list_if_the_element_is_not_found:PASS
linked_list_test.c:250:test_deletes_only_the_first_occurrence:PASS

-----------------------
19 Tests 0 Failures 0 Ignored
OK

[sudhackar]

hmm. The build fails for macos. I'll test more.

[sudhackar]

So without disabling pie I am not able to get nasm to call libc functions on linux

Symbol `exit' causes overflow in R_X86_64_PC32 relocation

I saw some workarounds like using wrt with ..plt or ..got to call libc functions in presence of pie - but that'd fail on mac. See build

linked_list.asm:12: error: symbol `..plt' undefined

In current state it works fine on my mac - intel, 2019, Big Sur 11.6.3 and ubuntu/alpine docker in this state. Additionally I tested a change with plt too.

[ErikSchierboom]

Thanks for submitting this PR! @bergjohan Could you look at this PR?

[bergjohan]

I'll try to take a look tomorrow

[bergjohan]

Thanks for the PR, nice work! A few thoughts:

When I created this track, I avoided exercises with dynamic allocation, since it's very OS dependent. I'm not sure how I feel about forcing the student to use the C standard library in an assembly track. The student would have to learn how to use the functions malloc and free, which might not be what you want/expect when working through an assembly track. Although, the test cases are written in C, so a basic knowledge of C is pretty much required to get started.

struct list_node and struct list are defined in the .c test file, but never actually used, we could just as well use something like typedef void *ll_handle. I assume you'd like the student to follow the layout of these structs in the exercise. Maybe it would be better to add a struc as a starting point in the .asm file with an example layout: https://www.nasm.us/xdoc/2.15.05/html/nasmdoc5.html#section-5.9

To avoid dynamic memory allocation, maybe we could pre allocate some memory in the .bss section, enough to handle the test cases, i.e have the linked list be fixed size. Something like memory: resb 1024 ; reserve 1024 bytes for the linked list.

This is just some thoughts to get a discussion going on what the best way to implement this exercise would be.

[sudhackar]

Calling malloc and free from the library actually created a couple of problems while testing. So I'd agree about that. Same goes about making syscalls - it makes them limited to a platform.

I'll move the struct defs from c to asm - that makes sense.

[sudhackar]

@bergjohan Did these changes - based on your thoughts

• moved struct definitions from C to asm - use field names and size to use members and allocate in .data
• remove non-pie build
• added a simple struc in the solution template
• removed malloc and free instances

[bergjohan]

Thanks, great work!

Some additional thoughts:

• I think it would make sense to move currm, m, curridx and global to the .bss section, since they're static data and it would make them zero initialized by default.
• Afaict, currm is unused.
• I think it would be good to add the globals to the template file, to give the student a bit more guidance.
• If we add the globals to the template, I think it would be good to use some more descriptive names. Maybe nodes instead of glob, and something like list instead of m. That would probably collide with the STRUC though, maybe capitalize the STRUC names, and call them Node and List to separate them from the variables. Or maybe get rid of the list STRUC and use two separate variables for first and last.
• Since we only support one list at a time, it feels a bit redundant to pass around a list pointer. I think we could get rid of list_create() and list_destroy() to simplify the exercise, and make it clear that the there's only a single list.

[sudhackar]

Since we only support one list at a time, it feels a bit redundant to pass around a list pointer. I think we could get rid of list_create() and list_destroy() to simplify the exercise, and make it clear that the there's only a single list.

The list needs to be a new one for each test. The tests will fail if we don't clear the state from last test - setUp and tearDown are called before and after each test.

[bergjohan]

Yeah, I was thinking we could add a function, list_clear(), that clears the list, which could be called in setUp.

If you think the current way is better, that's fine, I'm just trying to think of ways to simplify the exercise and make it as clear as possible to the student what's expected of them.

[sudhackar]

IMO a tearDown function to clear all pointers would help clear dangling references for the students - I'll add additional documentation to make it clearer

[bergjohan]

My bad, a call to list_clear() would be better in tearDown. My thoughts were, list_clear() would clear all static memory for the list, i.e. all the pointers would be set to zero. Maybe list_reset() would be a better name.

[sudhackar]

I have made changes for the first 4 points. I still feel that keeping the List as a struct with a couple of pointers is OK. For the tearDown change I'll do it in a while

[sudhackar]

Ah Its been a "while". Sorry I totally forgot about this - the current change should do everything you suggested @bergjohan