dangit, my inner data structure has a structural fault because of rust ownership semantics.Conceptually, the inner struct is a binary tree where inner nodes can carry a value, and leaves can carry a value or a child tree. If you need a leaf to hold bot...
-
@danderson
No language change necessary, and I will be darned to Gopher heck for this: https://go.dev/play/p/BirpA56Oi1l -
@danderson Hmm… I think you're right, pointer equality carries important semantics here that `T: Copy+PartialEq` equality doesn't. Maybe this really *does* need to hide internal (unbounded) `T` storage.
-
@dr2chase Huh, how does that not cause the values to get collected? Oh, if we assume sizeof both types is at least a couple bytes, that's still a pointer _into_ the struct, even if not _to_ the struct, and so it works out?...
-
@willglynn Yeah, or the caller must only store unique values, and provide the indirection themselves outside the route table if they want to point several routes at one nexthop struct. But of course that continues to make the API less and less usable...
-
@danderson The stride tables rely on compact, readily-duplicated value references. References need to be unique per insert to provide proper deletion – or at least, unique within the table at that point in time. Given these invariants, I don't think this *can* be a caller-defined type.
Table operations frequently compare and duplicate references, but they only follow the references at the very end, at most once per call. Maybe they're `NonZeroUsize` referring to an internal `Vec<T>`?
-
@willglynn Yeah that was my thinking, although given the maximum number of entries a NonZeroU16 would be even cheaper.
Annoying part with an internal Vec is handling deletes, you end up with holes in your Vec and so have to scan on insert to find a reusable slot.
otoh rust is good at autovectorization and there are tradeoffs w/ branching where you only do the search if the alternative is growing the backing array...
-
@danderson I was thinking a single backing store for all `T` in the table. You could still parameterize the internal reference type (a trait implemented for various numeric types?) but the low level tree code need not ever know a specific `T` value type.
-
@willglynn oh, right, yes if the outer table is storing the Ts then NonZeroUsize is right, and the internal table has an API contract that prefixes are inserted with unique values still - but the outer table enforces that, not the caller.
-
@danderson The Go GC recognizes interior pointers, yes. I'm surprised nobody else has done this, it's horrible, but I've seen much much worse.
-
@dr2chase If we accept that, past a certain level of optimizing, crimes are inevitable... This isn't the worst, imo. You even get to hide all the unsafe twiddling inside a nice friendly type and eat the sin for your callers!