search

attractivechaos / klib

A standalone and lightweight C library
http://attractivechaos.github.io/klib/
MIT License
4.18k stars 556 forks source link

Example on how to use klist.h #134

Open pfeatherstone opened 4 years ago

pfeatherstone commented 4 years ago

Please could you provide an example on how to use klist.h. I'm having to forward declare structures defined by the macro expansion which i'm pretty sure is not the way to do it.

pfeatherstone commented 4 years ago

I think line 100 of klist.h should be removed. Even if you have an empty list, the head and tail pointers are non zero. Therefore when you free the list kmp_free gets called.

@larseggert I know you use klib. Do you agree?

larseggert commented 4 years ago

I'm not using klist though.

pfeatherstone commented 4 years ago

Fair enough. I think way more effort was put into khash.h That is really well documented and works perfectly

selavy commented 4 years ago

Personally I find the usefulness of klist to be minimal at best. First, you almost always would be better with kvec, and second if you really need a linked list, then an intrusive list would be better to avoid the extra allocations.

pfeatherstone commented 4 years ago

Incidentally removing line 100 of klist.h works fine. There doesn’t seem to be any memory leaks. Using it is fairly straight forward actually. My bad

trapexit commented 4 years ago

Linked list like objects (say... ropes) are very useful but per object lists are rarely a good structure to use.

https://www.youtube.com/watch?v=YQs6IC-vgmo

pfeatherstone commented 4 years ago

@trapexit Thanks that's a great video. I love watching Bjarne. Wouldn't you say it's a bit easier to use lists when you want to remove a single element in the middle of the container? With vectors you have to move the remaining elements back into a contiguous space whereas with lists you just have to update the pointer to the "next" or "prev" nodes. So there are no memmove's, just update a single pointer.

trapexit commented 4 years ago

You should always try to pick or design a data structure based on your needs. If order isn't important or removes are rare it'd be just as fast to copy the last element over the one removed or to copy n+1 - m to n - m-1. Updating pointers seems faster but you have to account for the total workflow. Pointers are indirection. That indirection is more costly than direct access in an array. Using pointers means data could be scattered around memory and might not cache well. Arrays can be brought into caches more efficiently.

You have to consider how your data structure will be accessed. What's the cost of those behaviors. How often they are done. Etc.

trapexit commented 4 years ago

If speed isn't a concern use whatever you're comfortable with but generally speaking linked lists should be considered anti-patterns on modern hardware. Data locality is important and linked lists almost couldn't be worse for that.