SkipList C implemenation | Together C & C++ | Page 1

tacit pagodaBOT May 30, 2023, 9:01 AM

#

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question run !howto ask.

slim cradle May 30, 2023, 9:03 AM

#

Obviously I will pass you the text of the exercise with the related structs and the descriptions of their fields to have all the information useful to you
Would be nice if you could follow up on that

gloomy flame May 30, 2023, 9:04 AM

#

this is the text

#

wait a minute

#

This is the text translated

📎 SkipLIst.txt

#

and this is my library

#

sorry again

slim cradle May 30, 2023, 9:10 AM

#

okay, and why do you think it's not working or more specifically, what is not working?

gloomy flame May 30, 2023, 9:11 AM

#

i'm afraid i fail lo implement the new_skiplist, cause everytime i need to use to function pointer compare to insert or search an element i got SEGV_FAULT

slim cradle May 30, 2023, 9:12 AM

#

Can you provide a MRE (minimal reproducible example)?

#

That is a main function with as little going on as possible which still causes your program to crash

#

Also why is your heads and next a double pointer as opposed to a normal pointer in SkipList and Node respectively?

#

ah, cause that was how it was suggested, I see

#

!f

tacit pagodaBOT May 30, 2023, 9:20 AM

#

int compare_int(const void* a, const void* b) {
  const int* num1 = (const int*)a;
  const int* num2 = (const int*)b;

  if (*num1 < *num2)
    return -1;
  else if (*num1 > *num2)
    return 1;
  else
    return 0;
}

int main() {
  struct SkipList* list;
  new_skiplist(&list, 4, compare_int);

  // Insert some elements
  int num1 = 5;
  insert_skiplist(list, &num1);
  int num2 = 3;
  insert_skiplist(list, &num2);
  int num3 = 7;
  insert_skiplist(list, &num3);
  int num4 = 2;
  insert_skiplist(list, &num4);
  int num5 = 9;
  insert_skiplist(list, &num5);

  // Search for an element
  int search_num = 7;
  const void* result = search_skiplist(list, &search_num);
  if (result != NULL) {
    printf("Element found: %d\n", *(int*)result);
  } else {
    printf("Element not found.\n");
  }

  // Cleanup
  clear_skiplist(&list);

  return 0;
}

Raito Yakuzi

slim cradle May 30, 2023, 9:22 AM

#

So, for me this runs without crashing

gloomy flame May 30, 2023, 9:22 AM

#

oh i see

#

can i ask you one more question?

slim cradle May 30, 2023, 9:23 AM

#

sure

gloomy flame May 30, 2023, 9:31 AM

#

maybe i'm paranoid, but i tried this library on another test online of my university on moodle platform: but in that test i always get a SEGV_FAULT. Unfortunately the source code is not avaliable (and another problem is that this test is not written by my professor, they just copy and paste the test on moodle to give us the chance to check the library implementation) cause is a test on the platform so i can't use GDB on that test to check what is wrong. One thing that i omittes is that for this library i must create another moudule for unit test with unity library. I haven't done it yet because I was obsessed with failing the online moodle test. My question is : should i forgot this test on moodle platform and focus to write unit tests to check if my library is working?

slim cradle May 30, 2023, 9:35 AM

#

with unity library
Is that an actual library for unit testing C code?

Anyways, writing tests is always a good idea. Usually you actually want to write tests before you even start implementing anything else.

#

Also does the whole test case get exposed? Cause if so then if you copy it entirely you should get the same behaviour

#

The only possibly scary thing I see with new_skiplist is that you set all heads[i] values to NULL, but that doesn't need to be a problem.

gloomy flame May 30, 2023, 9:41 AM

#

slim cradle The only possibly scary thing I see with `new_skiplist` is that you set all `hea...

i did it cause i was afraid to not inizializate the pointers: cause, if i'm not wrong, they could be a problem for access memory during the execution of program, i mean that : if a pointer variable is uninitialized it has an undefined value;
▪ Using a pointer with arbitrary value at best generates
during the execution of the program an access to a memory area
illegal causing it to be terminated by the Operating System with a
signal which is called Segmentation Fault (SEGV), in the worst case scenario
causes access to a data area of the same program thus going to
subtly modify other variables;
▪ it is good practice to always initialize a pointer to NULL, like this
incorrect use of a NULL pointer during execution causes termination
of the program by the Operating System with the SEGV signal

slim cradle May 30, 2023, 9:43 AM

#

Yeah, the reason why I said it's scary is because it might trick you in some other place where you then forget to actually allocate memory

#

But as I mentioned, doesn't have to be a problem depending on how your other functions are implemented, but can be if the other functions are implemented poorly

#

You could try to compile with sanitizers (-fsanitize=address,undefined)

gloomy flame May 30, 2023, 9:44 AM

#

slim cradle > with unity library Is that an actual library for unit testing C code? Anyways...

yes unity.h is an extern library to help us for unit test

#

cause for unit test in c unfortunately there is no “standard” library
❖ for this reason:
❖ it is permissible to use an ad-hoc program to carry out the test,
as long as you write your test functions paying attention to
As said
❖ it is allowed to use libraries, but it will be the responsibility of the
student/group install and use them correctly
❖ Simple and widely used:
❖ Unity (http://www.throwtheswitch.org/unity/)
❖ you can find Unity in the Resources/C/Unity del folder
Git repositories

Throw The Switch

Unity — Throw The Switch

slim cradle May 30, 2023, 9:46 AM

#

But yeah, you can use sanitizers to maybe figure out some memory leak or other problem regarding access to NULL pointers

gloomy flame May 30, 2023, 9:49 AM

#

slim cradle But yeah, you can use sanitizers to maybe figure out some memory leak or other p...

like that : gcc -fsanitize=address -o program program.c ?

slim cradle May 30, 2023, 9:50 AM

#

*-fsanitize=address
or -fsanitize=address,undefined
but other than that yeah, just put it as a compiler flag.

tacit pagodaBOT May 30, 2023, 9:50 AM

#

How To Use Sanitizers

Sanitizers are tools which generate additional code in your program that can catch many common programming mistakes, such as:

General Advice

Not all sanitizers can be combined, but when they can, use e.g.: -fsanitize=address,undefined to combine them. Always compile with debug info to get line numbers, variable names, etc.

GCC 4.8+

clang 3.1+

MSVC 19.27+ and VS 2019 16.9+

-fsanitize=address
-Zi for debug info

Sample Program

int main(void) {
    int x;
    return x;
} ```

`-fsanitize=memory -g` Output

SUMMARY: MemorySanitizer: use-of-uninitialized-value /tmp/test.cpp:3:5 in main > Exiting (3:5 is line and column of return)

slim cradle May 30, 2023, 9:51 AM

#

Oh yeah, and you also need to compile with -g (or -g3) for debug info

gloomy flame May 30, 2023, 9:51 AM

#

ah yeah i forgot

#

thanks for the help

slim cradle May 30, 2023, 9:52 AM

#

And if you ever want to debug yourself with gdb then I also recommend -Og

#

-Og is an optimization like -O3 or -Os but instead of going for performance or size it goes for an easy translation between your C code and the generated assembly, so that debugging is easier

gloomy flame May 30, 2023, 9:53 AM

#

can i leave thi post open for furthe question about the skiplist?

slim cradle May 30, 2023, 9:53 AM

#

yup

gloomy flame May 30, 2023, 9:53 AM

#

slim cradle `-Og` is an optimization like `-O3` or `-Os` but instead of going for performanc...

ok i understand

#

thank you very much

tacit pagodaBOT May 30, 2023, 9:58 AM

#

@gloomy flame Has your question been resolved? If so, run !solved :)

gloomy flame May 30, 2023, 10:45 AM

#

@slim cradle hi i tried to use the flag tha you suggest me and i encouter an error

#

can i share to you the GDB output?

tacit pagodaBOT May 30, 2023, 10:51 AM

#

Monke

Just Post Your Question

Don't ask to ask a question, don't ask if anyone is familiar with XYZ. Just ask your question.
Someone is bound to know the answer and will be happy to help.
Learn why asking to ask is not a good idea

gloomy flame May 30, 2023, 11:09 AM

#

📎 message.txt

slim cradle May 30, 2023, 11:16 AM

#

ooof, no clue. Try to run it the normal way, sanitizers also output all their information when not explicitly debugging

gloomy flame May 30, 2023, 11:41 AM

#

do you mean without the flag -fsanitize=address,undefined?

#

(gdb) run
Starting program: /home/mattiaunito/Scrivania/ex2
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
Level 2:
.
Level 1:
.
Level 0:
3 5 7 .
Element found: 7
[Inferior 1 (process 6664) exited normally]
(gdb)

#

i only used the -g and -Og flags

#

(gdb) run
Starting program: /home/mattiaunito/Scrivania/ex2
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
Level 2:
.
Level 1:
.
Level 0:
3 5 7 .
Element found: 7
==6712==LeakSanitizer has encountered a fatal error.
==6712==HINT: For debugging, try setting environment variable LSAN_OPTIONS=verbosity=1:log_threads=1
==6712==HINT: LeakSanitizer does not work under ptrace (strace, gdb, etc)
[Inferior 1 (process 6712) exited with code 01]
(gdb)

#

this is instead with the flag -fsanitize=address,undefined but without export the environment variable suggested by GDB

slim cradle May 30, 2023, 1:39 PM

#

I mean without using gdb

#

Just run as normal

gloomy flame May 30, 2023, 1:48 PM

#

okok my bad

#

slim cradle May 30, 2023, 1:50 PM

#

weird

#

hmm, no clue.
I mean the code apparently works, so unless you can create a scenario where it crashes there isn't all that much to do for you

#

or does it work?

#

Is that the expected output?

gloomy flame May 30, 2023, 1:52 PM

#

for the main that i passed to you yes

#

about the test on moodle that i told you earlier is little bit complicated cause i can't have access to the source code of the module that test my library

#

but i think i should test it by myself with unit test

#

is the only way

#

anyway thanks a lot for the help. Have a nice day!!

slim cradle May 30, 2023, 2:00 PM

#

u 2

gloomy flame May 30, 2023, 2:02 PM

#

!solved

tacit pagodaBOT May 30, 2023, 2:02 PM

#

Thank you and let us know if you have any more questions!

This thread is now set to auto-hide after an hour of inactivity

#

@gloomy flame

Please Do Not Delete Posts!

Please don't delete forum posts. They can be helpful to refer to later and other members can learn from them. In the future you can use !solved to close a post and mark a post as solved.

#SkipList C implemenation