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

I write type-safe generic data structures in C

danielchasehooper.com

Post reply on HN
Print view View original

171–180 of 196 posts

Re: I write type-safe generic data structures in C

#171

Post by MangoToupe »

rangerelf wrote: post #166
MangoToupe wrote: post #158

Earlier quoted context omitted.

Well, I certainly would not interpret the terms that way, but you do you.

lol, it's not a "you do you" thing, that's what they're actually named, "parameters" and "arguments" have distinct objective definitions in this context and those are it. In this specific case it's you who's using made up words for concepts that others already have a specific name for.

> that's what they're actually named

...by what authority? c'mon, communication is important, and insisting on the correctness of definitions tanks that.

EDIT: however, I will concede there's good evidence for widespread usage of this, and I'll adjust my usage accordingly. Insisting on "correctness" is just asinine, though.

Re: I write type-safe generic data structures in C

#172

Post by monkeyelite »

el_pollo_diablo wrote: post #105
monkeyelite wrote: post #92

Earlier quoted context omitted.

And you can write them when you need them. The situation where you need a red black tree with 10 different key/value combos isn’t real.

If, by "situation", you mean the development of a small program with so many constraints that using existing libraries is out if the question, then yes. Otherwise, that seems unwise to me. Not every user of a generic type has to be generic. A major selling point of generic types is that you write a library once, then everyone can instantiate it. Even if that is the only instance they need in their use case, you have…

Ok you’re telling me the upside which we already know. Now what’s the downside?

Re: I write type-safe generic data structures in C

#173

Post by KingLancelot »

o11c wrote: post #12

For your level 2 code, `uint64_t data[];` is wrong for types whose alignment is greater than `uint64_t`, and also wasteful for types whose alignment is smaller (for example, under an ilp32 ABI on 64-bit architectures). For your level 3 code, it should be `int main() { List(Foo) foo_list = {NULL};` Note that working around a lack of `typeof` means you can't return anything. Also, your particular workaround allows `con…

[dead]

Re: I write type-safe generic data structures in C

#174

Post by monkeyelite »

dwattttt wrote: post #121
monkeyelite wrote: post #104

Earlier quoted context omitted.

Except it’s very common for C programs to contain one-off data structures, so it’s not a hypothetical. It’s a concrete programming style.

Do you mean a data structure they only use once? Or one that's never been done elsewhere? If they only use it once, that seems like the worst effort/pay-off ratio you can get writing it yourself. And I don't think there's that many fundamental data structures out there... and even then, why would it be good to be forced to make your bespoke structure out of only arrays, when things like maps exist?

> And I don't think there's that many fundamental data structures out there

No. There are a few fundamental ones which work well in a generic context. When you tailor make it you find simplifying assumptions.

One I am aware of is a hash map that doesn’t need to delete individual keys.

Re: I write type-safe generic data structures in C

#176

Post by cb321 »

monkeyelite wrote: post #174
dwattttt wrote: post #121

Earlier quoted context omitted.

Do you mean a data structure they only use once? Or one that's never been done elsewhere? If they only use it once, that seems like the worst effort/pay-off ratio you can get writing it yourself. And I don't think there's that many fundamental data structures out there... and even then, why would it be good to be forced to make your bespoke structure out of only arrays, when things like maps exist?

> And I don't think there's that many fundamental data structures out there No. There are a few fundamental ones which work well in a generic context. When you tailor make it you find simplifying assumptions. One I am aware of is a hash map that doesn’t need to delete individual keys.

This is true of the common tombstone approach to deletions in hash tables { which also require rehashing (like in resizing) if there are too many tombstones }.

Somehow dissemination of Knuth v3,chapter6.4 Algorithm D has been weak, though it has lately become known as "backshift deletion" - unsure who coined that. It is limited to linear probing (but then these days that also creates the least memory traffic/potential latency). With this approach, there is no real specialized form of "hash tables that can delete". You may already know all of this and not disagreeing with anything. Just a natural follow-up.

Re: I write type-safe generic data structures in C

#177

Post by dfawcus »

WalterBright wrote: post #170
dfawcus wrote: post #167

Earlier quoted context omitted.

Nah - one would simply use a punch with the hammer. So nail the architrave with the hammer until the nail is say 1/8" proud, then punch it home.

There's a reason carpenters use nail guns. Try it and you'll see!

Well, obviously speed when one is on the clock.

All power tools have trade offs vs the manual alternates, often tipping towards their use, but not always.

I have had success on an occasion using a belt fed screw gun when fitting plaster boards, especially for ceiling boards.

However I don't do joinery often enough to justify the use of a nail gun.

Re: I write type-safe generic data structures in C

#178

Post by uecker »

WalterBright wrote: post #160
uecker wrote: post #110

Earlier quoted context omitted.

I could tell a similar story (many, in fact) about C++'s templates. It is not entirely clear to me what exactly makes the preprocessor a bad choice. One could argue that it is too flexible, so it is possible to create a mess with it. But somehow this seems a rather weak argument for inventing another monomorphization layer, which often evolve into their own mess.

You can definitely make an incomprehensible soup out of C++ templates. C++ expression templates are a classic example. But the threshold of this is much higher than with a macro language. Using C++ templates for a linked list type doesn't make a mess.

I am not sure, I quite like the new C macro-templates. I also do not think the implementation is messy. Can you narrow down specific aspects where you think using macros for this is problematic?

Re: I write type-safe generic data structures in C

#179

Post by gnulinux996 »

_proofs wrote: post #77
cherryteastain wrote: post #29

Why would you jump through all these hoops instead of just writing C++ if you want "C with generics"

because i work on a legacy project that is coupled to safety regulations and other quality guarantees, and we cannot just simply roll out a solution ported to c++ on the next release, or even tenth, so perhaps we make it work until we can. however we can set a standard and expectation for new projects to use c++, and we do and set an expectation to target a specific std. i see this sentiment quite a lot on hackernews…

Out of curiosity, what is an example of a regulation that specifies using a specific programming language and/or toolchain out there?

Re: I write type-safe generic data structures in C

#180

Post by monkeyelite »

cb321 wrote: post #176
monkeyelite wrote: post #174

Earlier quoted context omitted.

> And I don't think there's that many fundamental data structures out there No. There are a few fundamental ones which work well in a generic context. When you tailor make it you find simplifying assumptions. One I am aware of is a hash map that doesn’t need to delete individual keys.

This is true of the common tombstone approach to deletions in hash tables { which also require rehashing (like in resizing) if there are too many tombstones }. Somehow dissemination of Knuth v3,chapter6.4 Algorithm D has been weak, though it has lately become known as "backshift deletion" - unsure who coined that. It is limited to linear probing (but then these days that also creates the least memory traffic/potentia…

If we look at the major standard libraries for hash tables, you're telling me there will be no overhead to supporting the ability to delete keys?

Isn't resizing logic already a counterexample?

Post reply on HN