The array-map from luro02

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

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.

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

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

Add optional logging

This could be either the tracing or log crate.

`Drain` and `DrainFilter` do not behave correctly

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

Should `ArrayMap::insert` return an error or panic?

Depends on how likely it is that one runs out of capacity? I think it would be good to provide both a panicking and non-panicking method.

The problem is that try_insert seems to be used differently in std/hashbrown, so a different name is needed.

`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.

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

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

Rudra in CI

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

Missing functionality for `ArrayMap`

Functions that should be implemented:

Nightly only functions:

ArrayMap::get_each_key_value_mut
ArrayMap::get_each_mut

Traits:

Auto Traits:

Compare to `fixed-map` crate

https://docs.rs/fixed-map

CI broken

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

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");

Test no features and serde in ci

Which hashing crate should be used by default?

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

Add `ArraySetFacade`

Functions that should be implemented:

Traits

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

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 
        
               } 
        
           }

	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:

Nightly only functions:

Traits:

Auto Traits:

Functions that should be implemented:

Traits

Recommend Projects

Recommend Topics

Recommend Org