Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Common libraries and data structures for C

github.com

Post reply on HN
Print view View original

1–7 of 7 posts

Re: Common libraries and data structures for C

#2

Post by d26900 »

That's a cool library! Well done!

I made something similar to it being inspired by the C++ standard library. But it is for C89:

https://github.com/d26900/JamaisVu

I use tombstones for my hash table (unordered_map) though.

Another drawback of my lib: for each hash table entry, I allocate an extra byte for the tombstones.

Re: Common libraries and data structures for C

#3

Post by janselman »

d26900 wrote: post #2

That's a cool library! Well done! I made something similar to it being inspired by the C++ standard library. But it is for C89: https://github.com/d26900/JamaisVu I use tombstones for my hash table (unordered_map) though. Another drawback of my lib: for each hash table entry, I allocate an extra byte for the tombstones.

Btw I'm not the author, author posted on reddit : https://www.reddit.com/r/C_Programming/comments/lh9irz/commo...

I don't know much about hashmaps but the disadvantage with tombstones is if you add/remove a lot, then you have to rehash your map at some point right?

I really like tiny libs anyway, yours looks good, very readable :)

Re: Common libraries and data structures for C

#4

Post by d26900 »

janselman wrote: post #3
d26900 wrote: post #2

That's a cool library! Well done! I made something similar to it being inspired by the C++ standard library. But it is for C89: https://github.com/d26900/JamaisVu I use tombstones for my hash table (unordered_map) though. Another drawback of my lib: for each hash table entry, I allocate an extra byte for the tombstones.

Btw I'm not the author, author posted on reddit : https://www.reddit.com/r/C_Programming/comments/lh9irz/commo... I don't know much about hashmaps but the disadvantage with tombstones is if you add/remove a lot, then you have to rehash your map at some point right? I really like tiny libs anyway, yours looks good, very readable :)

I am not an expert either, but I would say that you have to rehash it either way if it grows (or shrinks). Tombstones as I understand it, are a way to "mark" deleted entries off of the hash table. Having these deleted entries marked ensures that your hash table doesn't break its "search chain". This is important so that you still can find entries that are put at another index when one index ("bucket") is already occupied.

However, I also don't shrink my table, once it grows. It stays grown. (Another drawback of my lib I suppose).

Thank you for the feedback, I really appreciate it! :)

Re: Common libraries and data structures for C

#5

Post by janselman »

d26900 wrote: post #4
janselman wrote: post #3

Earlier quoted context omitted.

Btw I'm not the author, author posted on reddit : https://www.reddit.com/r/C_Programming/comments/lh9irz/commo... I don't know much about hashmaps but the disadvantage with tombstones is if you add/remove a lot, then you have to rehash your map at some point right? I really like tiny libs anyway, yours looks good, very readable :)

I am not an expert either, but I would say that you have to rehash it either way if it grows (or shrinks). Tombstones as I understand it, are a way to "mark" deleted entries off of the hash table. Having these deleted entries marked ensures that your hash table doesn't break its "search chain". This is important so that you still can find entries that are put at another index when one index ("bucket") is already occu…

Shrinking is not that necessary I believe. C++ and Java data structures do not shrink automatically either.

Re: Common libraries and data structures for C

#6

Post by Delk »

d26900 wrote: post #2

That's a cool library! Well done! I made something similar to it being inspired by the C++ standard library. But it is for C89: https://github.com/d26900/JamaisVu I use tombstones for my hash table (unordered_map) though. Another drawback of my lib: for each hash table entry, I allocate an extra byte for the tombstones.

I've been making something kind of similar as well, although it's neither that pretty nor as minimal as I may have aimed for. And unlike the library in the post title, I only did container-style data structures, not other common stuff.

https://github.com/mwahlroos/libcoll-c

Post reply on HN