orlp / slotmap

Slotmap data structure for Rust
zlib License
1.13k stars 70 forks source link

Use map-like (de)serialization #7

Closed TimDiekmann closed 6 years ago

TimDiekmann commented 6 years ago

SlotMap is an unordered map. It would be neat to have a map-like serialization instead of the vector. This has some advantages:

Since both, index and version are u32, the key of the map could be u64, which contains both.

Let me give an example:

slotmap.insert(10);
let key = slotmap.insert(20);
slotmap.insert(30);
slotmap.insert(40);
slotmap.remove(key);

With the current implementation, this would result in

[
  {
    "value": 10,
    "version": 1
  },
  {
    "value": null,
    "version": 2
  },
  {
    "value": 30,
    "version": 1
  },
  {
    "value": 40,
    "version": 1
  }
]

With a map-like serialization, it would look like

{
  "1":           10,
  "4294967298":  null,
  "8589934593":  30,
  "12884901889": 40
}

or

{
  "4294967296": 10,
  "8589934593": null,
  "4294967298": 30,
  "4294967299": 40
}

depending on how to construct the key. I'd prefere the former because the keys will still be ordered by index.

orlp commented 6 years ago

I really don't really like this. My current serialization format is meaningful to anyone familiar with the implementation details, while yours is obscured. I strongly disagree that yours is "more intuitive". Furthermore, what if a malicious actor edits the representation as such:

{
    "1": 10,
    "2": null,
}

This is harder to detect than what we have now, because the current serialization format inherently allows only one entry per slot.

TimDiekmann commented 6 years ago

It's more intuitive in the sense, that we have a key somewhere in the code which is mapped to a value.