The array-map from luro02

Which hashing crate should be used by default?

Currently, aHash is used, but there are other crates available:

Implement `Serialize` and `Deserialize` for `ArrayMapFacade` and `ArraySetFacade`

Add optional logging

This could be either the tracing or log crate.

Cleanup branches in `array_map` macro

The doc shows the @helper cases too, which makes it harder to read. Those should be put in a helper macro?

Rudra in CI

Additionally, to miri one could run this in CI to check for undefined behaviour:
https://github.com/sslab-gatech/Rudra

CI broken

Should be fixed after this PR will be merged:
rust-lang/rust#87468

Add `IndexTable` to have a fixed size `IndexMap`

With the IndexTable one could have an IndexMap:
https://docs.rs/indexmap

Should `ArrayMap::raw_entry` and `ArrayMap::raw_entry_mut` exist?

See tracking issue, which discusses this feature: rust-lang/rust#56167

Implement `TryFrom<[(K, V); N]> for ArrayMap<K, V, M>`

ArrayMapFacade could implement this:

impl<K, V, R, B, const N: usize> TryFrom<[(K, V); N]> for ArrayMapFacade<K, V, R, B>
where
    K: Eq + Hash,
    R: RawTable<(K, V)> + Default,
    B: BuildHasher + Default,
{
    type Error = CapacityError;

    fn try_from(value: [(K, V); N]) -> Result<Self, Self::Error> {
        let mut result = Self::with_build_hasher(B::default());

        for (key, value) in value {
            result.insert(key, value)?;
        }

        Ok(result)
    }
}

but it conflicts with the "specialized" implementation for FixedSizeTables:

array-map/src/array_map.rs

Lines 1064 to 1081 in 4390c72

    
           impl<K, V, R, B, const N: usize> From<[(K, V); N]> for ArrayMapFacade<K, V, R, B> 
        
           where 
        
               K: Eq + Hash, 
        
               R: FixedSizeTable<(K, V), N> + Default, 
        
               B: BuildHasher + Default, 
        
           { 
        
               fn from(value: [(K, V); N]) -> Self { 
        
                   let mut result = Self::with_build_hasher(B::default()); 
        
                   for (key, value) in value { 
        
                       if let Err(error) = result.insert(key, value) { 
        
                           unreachable_unchecked!(error); 
        
                       } 
        
                   } 
        
                   result 
        
               } 
        
           }

Tracking issue of unstable features that have to be stabilized before publishing to crates.io

The implementation uses a number of unstable features, which have to be stabilized, before it can be published to crates.io.

Currently one is not allowed to use const and type parameters with default parameters, because no design decision has been made yet: rust-lang/rust#44580
[(); N].map(|_| None) is used to initialize an array with None: rust-lang/rust#75243
ArrayMap::get_each_key_value_mut requires [T; N]::each_mut: rust-lang/rust#76118
TryFromIterator uses the "never-type" (!) for an implementation, which can be replaced with core::convert::Infallible: rust-lang/lang-team#60
[T; N]::try_map is not implemented in the standard library, so a custom implementation is used, which requires maybe_uninit_uninit_array, maybe_uninit_array_assume_init and try_trait_v2: rust-lang/rust#79711
stmt_expr_attributes required for making ahash optional in the array_map macro: rust-lang/rust#15701

`IndexMap`s with different orders but the same key are equal

This is because IndexMap is an alias of ArrayMapFacade. The indexmap's IndexMap has the same implementation, but this is something that should be documented.

https://github.com/bluss/indexmap/blob/35b36eb83338d7c8d3f2a60013e5f5ac020c2c71/src/map.rs#L1400-L1415

`ArrayMap::remove` should happen in `O(1)`

Currently, each removal causes the entire ArrayMap/ArrayTable to be rebuilt.

This is very inefficient and with linear probing it is possible to remove the entries in O(1), which was done before c8a2e0e, but the implementation did not behave correctly, so it has been replaced with the current implementation, which is inefficient, but correct.

Add `ArraySetFacade`

Functions that should be implemented:

Traits

Migrate to rust 2021 edition

The new edition will be stabilized with rust version 1.56 (October 21st, 2021).

https://blog.rust-lang.org/2021/07/21/Rust-2021-public-testing.html

Functions of `ArrayMapFacade` should return the table's associated error (`R::Error` instead of `CapacityError`)

This is to keep it working with future RawTable that do return a different error type.

Compare to `fixed-map` crate

https://docs.rs/fixed-map

Implement `TryFrom<[(K, V); N]> for ArrayMap<K, V, M>` and `From<[(K, V); N]> for ArrayMap<K, V, N>`

See: rust-lang/rust#84111

The TryFrom implementation is already kind of implemented by TryFromIterator and rust 2021 edition (with the new edition arrays implement IntoIterator trait):

let table = ArrayMap::try_from_iterator([
    (1, 2),
    (3, 4),
    (5, 6)
]).expect("failed to create the hash map");

`Drain` and `DrainFilter` do not behave correctly

The tests for DrainFilter may fail randomly (just execute cargo test multiple times to reproduce).

Missing functionality for `ArrayMap`

Functions that should be implemented:

Nightly only functions:

ArrayMap::get_each_key_value_mut
ArrayMap::get_each_mut

	impl<K, V, R, B, const N: usize> From<[(K, V); N]> for ArrayMapFacade<K, V, R, B>
	where
	K: Eq + Hash,
	R: FixedSizeTable<(K, V), N> + Default,
	B: BuildHasher + Default,
	{
	fn from(value: [(K, V); N]) -> Self {
	let mut result = Self::with_build_hasher(B::default());

	for (key, value) in value {
	if let Err(error) = result.insert(key, value) {
	unreachable_unchecked!(error);
	}
	}

	result
	}
	}

luro02 / array-map Goto Github PK

array-map's Introduction

Hi there 👋

array-map's People

Contributors

Stargazers

Watchers

array-map's Issues

Functions that should be implemented:

Traits

Functions that should be implemented:

Nightly only functions:

Traits:

Auto Traits:

Recommend Projects

Recommend Topics

Recommend Org