0xMiden / 0xMiden/protocol

Add `LinkMap` APIs for single and double values

Ouverte
#1,515 2 commentaires 0 réactions 0 personnes assignées Voir sur GitHub
kernels
Langage dominant
Rust
Étoiles
132
Forks
167
Merge moyen
1 j 23 h
PR mergées (30 j)
110

Description

A link map entry currently has the following layout: `[KEY, VALUE0, VALUE1]` (ignoring metadata). Not all use cases need `VALUE1`, they just need a simple key-value pair. We should come up with APIs for the link map for such use cases.

The current link map API looks like this:

```
set(map_ptr, KEY, VALUE0, VALUE1) -> (is_new_key)
get(map_ptr, KEY) -> (contains_key, VALUE0, VALUE1)
is_empty(map_ptr) -> (is_empty)
iter(map_ptr) -> (has_next, iter)
next_key_double_value(iter) -> (KEY, VALUE0, VALUE1, has_next, next_iter)
next_key_value(iter) -> (KEY, VALUE0, has_next, next_iter)
next_key(iter) -> (KEY, has_next, next_iter)
```

## Small Link Map

One way is to have a separate structure that builds on top of the current link map, perhaps called `SmallLinkMap` which is a thin wrapper around a link map but does not use `VALUE1`.

For `link_map` this could become:

```
set(map_ptr, KEY, VALUE0, VALUE1) -> (is_new_key)
get(map_ptr, KEY) -> (contains_key, VALUE0, VALUE1)
is_empty(map_ptr) -> (is_empty)
iter(map_ptr) -> (has_next, iter)
next(iter) -> (KEY, VALUE0, VALUE1, has_next, next_iter)
next_key(iter) -> (KEY, has_next, next_iter)
```

Separately, the `small_link_map` would have this API:

```
set(map_ptr, KEY, VALUE0) -> (is_new_key)
get(map_ptr, KEY) -> (contains_key, VALUE0)
is_empty(map_ptr) -> (is_empty)
iter(map_ptr) -> (has_next, iter)
next(iter) -> (KEY, VALUE0, has_next, next_iter)
next_key(iter) -> (KEY, has_next, next_iter)
```

## Single link map

Keeping just a single link map that has various APIs for setting single and double values, could look something like this:

```
set_double_value(map_ptr, KEY, VALUE0, VALUE1) -> (is_new_key)
set_value(map_ptr, KEY, VALUE0) -> (is_new_key)
get_double_value(map_ptr, KEY) -> (contains_key, VALUE0, VALUE1)
get_value(map_ptr, KEY) -> (contains_key, VALUE0)
is_empty(map_ptr) -> (is_empty)
iter(map_ptr) -> (has_next, iter)
next_key_double_value(iter) -> (KEY, VALUE0, VALUE1, has_next, next_iter)
next_key_value(iter) -> (KEY, VALUE0, has_next, next_iter)
next_key(iter) -> (KEY, has_next, next_iter)
```

## Conclusion

Having a dedicated small link map seems cleaner. Ignoring `VALUE1` would be slightly less efficient than the dedicated procedures on link map itself, but only roughly by the additional invocation of `get_value1` (should be 8 cycles) and a `dropw` (4 cycles).

I think to keep the APIs clean, I would lean towards introducing the small link map.

Guide de contribution

Ouvrir le guide de contribution

Évaluation

Cette issue n'a pas encore été évaluée.

Recevez les nouvelles issues par e-mail

Un résumé court des issues GitHub adaptées aux débutants.