4 ms·

> malloc(sizeof(Entry) + strlen(key)); Don't forget +1 for the terminator. I also think a linked list is not a great data structure in practice. Having the bu

> malloc(sizeof(Entry) + strlen(key)); Don't forget +1 for the terminator. I also think a linked list is not a great data structure in practice. Having the buckets be one of those amortized-O(1)-append heap allocations would be kinder on CPU caches. But, if you are making the string part of the entry, that would also require padding the string length to word boundaries so that the struct gets aligned. Note also if you kept the length of the string somewhere (which you would need to for my above paragraph's suggestion), you could avoid strcmp-ing hash collisions where the string has different length. Strcmp is going to add up to an expensive thing in this code. This code also never checks the return value of malloc. Color me unimpressed with this code. (Cue people arguing that checking for malloc failure is a bad idea ... Linux oom killer and high level languages have you spoiled, there i said it! /s)

wahern 3y ago
> > malloc(sizeof(Entry) + strlen(key)); > Don't forget +1 for the terminator. Also should check for arithmetic overflow, or at least static_assert that sizeof(Entry) is "too small" to matter. (Hopefully the process of deciding what "too small" should be results in just adding the overflow check.)
- dahfizz 3y ago
  Not really. We defined Entry, so we know it's only a few bytes. And we know size_t is large enough to iterate over all of main memory. So the only way that statement overflows is if the key is literally larger than main memory. Not a concern.
  - asveikau 3y ago
    I agree with your reasoning, but it's not "literally", it's main memory minus (sizeof(struct Entry) - 1). But it's impossible to find a C string that big. Any point in memory is pretty clearly going to hit a 0 or a page fault before then.
the-smug-one 3y ago
>But, if you are making the string part of the entry, that would also require padding the string length to word boundaries so that the struct gets aligned. It also makes deletion a far more complicated situation. You'd essentially be implementing your own allocator then.
- asveikau 3y ago
  That's true. Maybe you could keep it simpler by making small strings inline with the struct, but larger strings go on the heap. This gives you fixed size records, so removal could be o(1) by swapping with the last one and shortening.
lyu07282 3y ago
Well it's C, it's ought to be broken in some way. Just put it in some sufficiently high value target, a few months to years later the CVE is gonna explain how it was broken exactly.

wahern 3y ago

> > malloc(sizeof(Entry) + strlen(key)); > Don't forget +1 for the terminator. Also should check for arithmetic overflow, or at least static_assert that sizeof(Entry) is "too small" to matter. (Hopefully the process of deciding what "too small" should be results in just adding the overflow check.)

dahfizz 3y ago
Not really. We defined Entry, so we know it's only a few bytes. And we know size_t is large enough to iterate over all of main memory. So the only way that statement overflows is if the key is literally larger than main memory. Not a concern.
- asveikau 3y ago
  I agree with your reasoning, but it's not "literally", it's main memory minus (sizeof(struct Entry) - 1). But it's impossible to find a C string that big. Any point in memory is pretty clearly going to hit a 0 or a page fault before then.

the-smug-one 3y ago

>But, if you are making the string part of the entry, that would also require padding the string length to word boundaries so that the struct gets aligned. It also makes deletion a far more complicated situation. You'd essentially be implementing your own allocator then.

asveikau 3y ago
That's true. Maybe you could keep it simpler by making small strings inline with the struct, but larger strings go on the heap. This gives you fixed size records, so removal could be o(1) by swapping with the last one and shortening.

lyu07282 3y ago

Well it's C, it's ought to be broken in some way. Just put it in some sufficiently high value target, a few months to years later the CVE is gonna explain how it was broken exactly.