diff --git a/nearby/presence/handle_map/Cargo.toml b/nearby/presence/handle_map/Cargo.toml
new file mode 100644
index 0000000..8f00bf7
--- /dev/null
+++ b/nearby/presence/handle_map/Cargo.toml
@@ -0,0 +1,19 @@
+[package]
+name = "handle_map"
+version.workspace = true
+edition.workspace = true
+publish.workspace = true
+
+[dependencies]
+hashbrown.workspace = true
+lock_api.workspace = true
+portable-atomic.workspace = true
+spin.workspace = true
+crypto_provider.workspace = true
+
+[dev-dependencies]
+criterion.workspace = true
+
+[[bench]]
+name = "benches"
+harness = false
diff --git a/nearby/presence/handle_map/benches/benches.rs b/nearby/presence/handle_map/benches/benches.rs
new file mode 100644
index 0000000..f1ee427
--- /dev/null
+++ b/nearby/presence/handle_map/benches/benches.rs
@@ -0,0 +1,330 @@
+// Copyright 2023 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+use criterion::{black_box, criterion_group, criterion_main, Criterion};
+use handle_map::*;
+use std::sync::Arc;
+use std::thread;
+use std::time::{Duration, Instant};
+
+// For the sake of these benchmarks, we just want
+// to be able to allocate an almost-arbitrary number of handles
+// if needed by the particular benchmark.
+const MAX_ACTIVE_HANDLES: u32 = u32::MAX - 1;
+
+// The default number of threads+shards to use
+// in multi-threaded benchmarks, chosen
+// to represent a typical multi-threaded use-case.
+const DEFAULT_SHARDS_AND_THREADS: u8 = 8;
+
+/// We're using u8's for the wrapped object type to deliberately ignore
+/// costs related to accessing the underlying data - we just care about
+/// benchmarking handle-map operations.
+type BenchHandleMap = HandleMap<u8>;
+
+fn build_handle_map(num_shards: u8) -> BenchHandleMap {
+    let dimensions = HandleMapDimensions { num_shards, max_active_handles: MAX_ACTIVE_HANDLES };
+    HandleMap::with_dimensions(dimensions)
+}
+
+/// Benchmark for repeated reads on a single thread
+fn single_threaded_read_benchmark(c: &mut Criterion) {
+    // The number of shards should not matter much here.
+    let handle_map = build_handle_map(8);
+    // Pre-populate the map with a single handle.
+    let handle = handle_map.allocate(|| 0xFF).unwrap();
+    let handle_map_ref = &handle_map;
+    // Perform repeated reads
+    c.bench_function("single-threaded reads", |b| {
+        b.iter(|| {
+            let guard = handle_map_ref.get(black_box(handle)).unwrap();
+            black_box(*guard)
+        })
+    });
+}
+
+/// Benchmark for repeated writes on a single thread
+fn single_threaded_write_benchmark(c: &mut Criterion) {
+    // The number of shards should not matter much here.
+    let handle_map = build_handle_map(8);
+    // Pre-populate the map with a single handle.
+    let handle = handle_map.allocate(|| 0xFF).unwrap();
+    let handle_map_ref = &handle_map;
+    // Perform repeated writes
+    c.bench_function("single-threaded writes", |b| {
+        b.iter(|| {
+            let mut guard = handle_map_ref.get_mut(black_box(handle)).unwrap();
+            *guard *= black_box(0);
+        })
+    });
+}
+
+/// Benchmark for repeated allocations on a single thread
+#[allow(unused_must_use)]
+fn single_threaded_allocate_benchmark(c: &mut Criterion) {
+    // The number of shards here is chosen to be quasi-reasonable.
+    // Realistically, performance will fluctuate somewhat with this
+    // due to the difference in the number of internal hash-map collisions,
+    // but ultimately we only care about the asymptotic behavior.
+    let handle_map = build_handle_map(8);
+    let handle_map_ref = &handle_map;
+    // Perform repeated allocations
+    c.bench_function("single-threaded allocations", |b| {
+        b.iter(|| {
+            handle_map_ref.allocate(|| black_box(0xEE));
+        })
+    });
+}
+
+/// Benchmark for repeated allocation->deallocation on a single thread
+/// starting from an empty map.
+#[allow(unused_must_use)]
+fn single_threaded_allocate_deallocate_near_empty_benchmark(c: &mut Criterion) {
+    // The number of shards should not matter much here.
+    let handle_map = build_handle_map(8);
+    let handle_map_ref = &handle_map;
+    // Perform repeated allocation/deallocation pairs
+    c.bench_function("single-threaded allocate/deallocate pairs (empty init state)", |b| {
+        b.iter(|| {
+            let handle = handle_map_ref.allocate(|| black_box(0xDD)).unwrap();
+            handle_map_ref.deallocate(handle);
+        })
+    });
+}
+
+/// Benchmark for repeated allocation->deallocation starting
+/// from a map with a thousand elements per shard.
+#[allow(unused_must_use)]
+fn single_threaded_allocate_deallocate_one_thousand_benchmark(c: &mut Criterion) {
+    let handle_map = build_handle_map(8);
+    for _ in 0..(8 * 1000) {
+        handle_map.allocate(|| black_box(0xFF)).unwrap();
+    }
+    let handle_map_ref = &handle_map;
+
+    // Perform repeated allocation/deallocation pairs
+    c.bench_function(
+        "single-threaded allocate/deallocate pairs (init one thousand elements per shard)",
+        |b| {
+            b.iter(|| {
+                let handle = handle_map_ref.allocate(|| black_box(0xDD)).unwrap();
+                handle_map_ref.deallocate(handle);
+            })
+        },
+    );
+}
+
+/// Benchmark for repeated allocation->deallocation starting
+/// from a map with a million elements per shard.
+#[allow(unused_must_use)]
+fn single_threaded_allocate_deallocate_one_million_benchmark(c: &mut Criterion) {
+    let handle_map = build_handle_map(8);
+    for _ in 0..(8 * 1000000) {
+        handle_map.allocate(|| black_box(0xFF)).unwrap();
+    }
+    let handle_map_ref = &handle_map;
+
+    // Perform repeated allocation/deallocation pairs
+    c.bench_function(
+        "single-threaded allocate/deallocate pairs (init one million elements per shard)",
+        |b| {
+            b.iter(|| {
+                let handle = handle_map_ref.allocate(|| black_box(0xDD)).unwrap();
+                handle_map_ref.deallocate(handle);
+            })
+        },
+    );
+}
+
+/// Helper function for creating a multi-threaded benchmark
+/// with the set number of threads. Untimed Initialization of state
+/// should occur prior to this call. This method will repeatedly
+/// execute the benchmark code on all threads
+fn bench_multithreaded<F>(name: &str, num_threads: u8, benchable_fn_ref: Arc<F>, c: &mut Criterion)
+where
+    F: Fn() + Send + Sync + 'static,
+{
+    c.bench_function(name, move |b| {
+        b.iter_custom(|iters| {
+            // The returned results from the threads will be their timings
+            let mut join_handles = Vec::new();
+            for _ in 0..num_threads {
+                let benchable_fn_ref_clone = benchable_fn_ref.clone();
+                let join_handle = thread::spawn(move || {
+                    let start = Instant::now();
+                    for _ in 0..iters {
+                        benchable_fn_ref_clone();
+                    }
+                    start.elapsed()
+                });
+                join_handles.push(join_handle);
+            }
+            //Threads spawned, now collect the results
+            let mut total_duration = Duration::from_nanos(0);
+            for join_handle in join_handles {
+                let thread_duration = join_handle.join().unwrap();
+                total_duration += thread_duration;
+            }
+            total_duration /= num_threads as u32;
+            total_duration
+        })
+    });
+}
+
+/// Defines a number of reads/writes to perform [relative
+/// to other operations performed in a given test]
+#[derive(Debug, Clone, Copy)]
+struct ReadWriteCount {
+    num_reads: usize,
+    num_writes: usize,
+}
+
+const READS_ONLY: ReadWriteCount = ReadWriteCount { num_reads: 4, num_writes: 0 };
+
+const READ_LEANING: ReadWriteCount = ReadWriteCount { num_reads: 3, num_writes: 1 };
+
+const BALANCED: ReadWriteCount = ReadWriteCount { num_reads: 2, num_writes: 2 };
+
+const WRITE_LEANING: ReadWriteCount = ReadWriteCount { num_reads: 1, num_writes: 3 };
+
+const WRITES_ONLY: ReadWriteCount = ReadWriteCount { num_reads: 0, num_writes: 4 };
+
+const READ_WRITE_COUNTS: [ReadWriteCount; 5] =
+    [READS_ONLY, READ_LEANING, BALANCED, WRITE_LEANING, WRITES_ONLY];
+
+/// Benchmarks a repeated allocate/[X writes]/[Y reads]/deallocate workflow across
+/// the default number of threads and shards.
+fn lifecycle_read_and_write_multithreaded(per_object_rw_count: ReadWriteCount, c: &mut Criterion) {
+    let name = format!(
+        "lifecycle_read_and_write_multithreaded(reads/object: {}, writes/object:{})",
+        per_object_rw_count.num_reads, per_object_rw_count.num_writes
+    );
+    // We need an Arc to be able to pass this off to `bench_multithreaded`.
+    let handle_map = Arc::new(build_handle_map(DEFAULT_SHARDS_AND_THREADS));
+    bench_multithreaded(
+        &name,
+        DEFAULT_SHARDS_AND_THREADS,
+        Arc::new(move || {
+            let handle = handle_map.allocate(|| black_box(0xFF)).unwrap();
+            for _ in 0..per_object_rw_count.num_writes {
+                let mut write_guard = handle_map.get_mut(handle).unwrap();
+                *write_guard *= black_box(1);
+            }
+            for _ in 0..per_object_rw_count.num_reads {
+                let read_guard = handle_map.get_mut(handle).unwrap();
+                black_box(*read_guard);
+            }
+            handle_map.deallocate(handle).unwrap();
+        }),
+        c,
+    );
+}
+
+fn lifecycle_benchmarks(c: &mut Criterion) {
+    for read_write_count in READ_WRITE_COUNTS {
+        // Using 8 separate shards to roughly match the number of active threads.
+        lifecycle_read_and_write_multithreaded(read_write_count, c);
+    }
+}
+
+/// Benchmarks repeated cycles of accessing the given number of distinct objects, each
+/// with the given number of reads and writes across the given number of threads.
+fn read_and_write_contention_multithreaded(
+    num_threads: u8,
+    num_distinct_objects: u32,
+    per_object_rw_count: ReadWriteCount,
+    c: &mut Criterion,
+) {
+    let name = format!("read_and_write_contention_multithreaded(threads: {}, objects: {}, reads/object: {}, writes/object:{})",
+                       num_threads, num_distinct_objects, per_object_rw_count.num_reads, per_object_rw_count.num_writes);
+    // Default to 8 shards, ultimately doesn't matter much since we only ever access a few shards.
+    // This needs to be `'static` in order to pass a ref off to `bench_multithreaded`.
+    let handle_map = Arc::new(build_handle_map(8));
+    let mut handles = Vec::new();
+    for i in 0..num_distinct_objects {
+        let handle = handle_map.allocate(|| i as u8).unwrap();
+        handles.push(handle);
+    }
+
+    bench_multithreaded(
+        &name,
+        num_threads,
+        Arc::new(move || {
+            // Deliberately performing all writes first, with
+            // the goal of getting staggered timings from
+            // all of the threads for subsequent iterations.
+            // We also perform reads and writes across all objects
+            // in batches to get something resembling uniform access.
+            for _ in 0..per_object_rw_count.num_writes {
+                for handle in handles.iter() {
+                    let mut write_guard = handle_map.get_mut(*handle).unwrap();
+                    *write_guard *= black_box(1);
+                }
+            }
+            for _ in 0..per_object_rw_count.num_reads {
+                for handle in handles.iter() {
+                    let read_guard = handle_map.get(*handle).unwrap();
+                    black_box(*read_guard);
+                }
+            }
+        }),
+        c,
+    );
+}
+
+fn read_write_contention_benchmarks(c: &mut Criterion) {
+    for num_threads in [2, 4, 8].iter() {
+        for num_distinct_objects in [1u32, 2u32, 4u32].iter() {
+            if num_distinct_objects >= &(*num_threads as u32) {
+                continue;
+            }
+            for read_write_count in READ_WRITE_COUNTS {
+                read_and_write_contention_multithreaded(
+                    *num_threads,
+                    *num_distinct_objects,
+                    read_write_count,
+                    c,
+                );
+            }
+        }
+    }
+}
+
+/// Benchmarks allocation (starting from empty) for the default number of shards and threads
+fn allocator_contention_benchmark(c: &mut Criterion) {
+    let name = "allocator_contention_multithreaded";
+    // We need an Arc to pass this off to `bench_multithreaded`
+    let handle_map = Arc::new(build_handle_map(DEFAULT_SHARDS_AND_THREADS));
+    bench_multithreaded(
+        name,
+        DEFAULT_SHARDS_AND_THREADS,
+        Arc::new(move || {
+            handle_map.allocate(|| black_box(0xFF)).unwrap();
+        }),
+        c,
+    );
+}
+
+criterion_group!(
+    benches,
+    single_threaded_read_benchmark,
+    single_threaded_write_benchmark,
+    single_threaded_allocate_benchmark,
+    single_threaded_allocate_deallocate_near_empty_benchmark,
+    single_threaded_allocate_deallocate_one_thousand_benchmark,
+    single_threaded_allocate_deallocate_one_million_benchmark,
+    lifecycle_benchmarks,
+    read_write_contention_benchmarks,
+    allocator_contention_benchmark,
+);
+criterion_main!(benches);
diff --git a/nearby/presence/handle_map/src/lib.rs b/nearby/presence/handle_map/src/lib.rs
new file mode 100644
index 0000000..745aec4
--- /dev/null
+++ b/nearby/presence/handle_map/src/lib.rs
@@ -0,0 +1,608 @@
+// Copyright 2023 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//! A thread-safe implementation of a map for managing object handles,
+//! a safer alternative to raw pointers for FFI interop.
+#![cfg_attr(not(test), no_std)]
+#![forbid(unsafe_code)]
+#![deny(missing_docs)]
+extern crate alloc;
+extern crate core;
+
+use alloc::boxed::Box;
+use alloc::vec::Vec;
+use core::ops::{Deref, DerefMut};
+use core::sync::atomic::Ordering;
+use hashbrown::hash_map::EntryRef;
+use portable_atomic::{AtomicU32, AtomicU64};
+use spin::lock_api::*;
+
+#[cfg(test)]
+mod tests;
+
+/// A RAII read lock guard for an object in a [`HandleMap`]
+/// pointed-to by a given [`Handle`]. When this struct is
+/// dropped, the underlying read lock on the associated
+/// shard will be dropped.
+pub struct ObjectReadGuard<'a, T> {
+    guard: lock_api::MappedRwLockReadGuard<'a, spin::RwLock<()>, T>,
+}
+
+impl<'a, T> Deref for ObjectReadGuard<'a, T> {
+    type Target = T;
+
+    fn deref(&self) -> &Self::Target {
+        self.guard.deref()
+    }
+}
+
+/// A RAII read-write lock guard for an object in a [`HandleMap`]
+/// pointed-to by a given [`Handle`]. When this struct is
+/// dropped, the underlying read-write lock on the associated
+/// shard will be dropped.
+pub struct ObjectReadWriteGuard<'a, T> {
+    guard: lock_api::MappedRwLockWriteGuard<'a, spin::RwLock<()>, T>,
+}
+
+impl<'a, T> Deref for ObjectReadWriteGuard<'a, T> {
+    type Target = T;
+
+    fn deref(&self) -> &Self::Target {
+        self.guard.deref()
+    }
+}
+
+impl<'a, T> DerefMut for ObjectReadWriteGuard<'a, T> {
+    fn deref_mut(&mut self) -> &mut Self::Target {
+        self.guard.deref_mut()
+    }
+}
+
+/// FFI-transmissible structure expressing the dimensions
+/// (max # of allocatable slots, number of shards) of a handle-map
+/// to be used upon initialization.
+#[repr(C)]
+#[derive(Clone, Copy)]
+pub struct HandleMapDimensions {
+    /// The number of shards which are employed
+    /// by the associated handle-map.
+    pub num_shards: u8,
+    /// The maximum number of active handles which may be
+    /// stored within the associated handle-map.
+    pub max_active_handles: u32,
+}
+
+/// Trait for marker structs containing information about a
+/// given [`SingletonHandleMap`], including the underlying
+/// object type and the dimensions of the map.
+/// Used primarily to enforce type-level constraints
+/// on `SingletoneHandleMap`s, including
+/// ensuring that they are truly singletons.
+pub trait SingletonHandleMapInfo {
+    /// The underlying kind of object pointed-to by handles
+    /// derived from the associated handle-map.
+    type Object: Send + Sync;
+
+    /// Gets the dimensions of the corresponding handle-map.
+    fn dimensions(&self) -> HandleMapDimensions;
+
+    /// Gets a static reference to the global handle-map
+    fn get_handle_map() -> &'static HandleMap<Self::Object>;
+}
+
+/// An individual handle to be given out by a [`HandleMap`].
+/// This representation is untyped, and just a wrapper
+/// around a handle-id, in contrast to implementors of `HandleLike`.
+#[derive(Clone, Copy, PartialEq, Eq, Hash)]
+pub struct Handle {
+    handle_id: u64,
+}
+
+impl From<&Handle> for Handle {
+    fn from(handle: &Handle) -> Self {
+        *handle
+    }
+}
+
+impl Handle {
+    /// Constructs a handle wrapping the given ID.
+    ///
+    /// No validity checks are done on the wrapped ID
+    /// to ensure that the given ID is active in
+    /// any specific handle-map, and the type
+    /// of the handle is not represented.
+    ///
+    /// As a result, this method is only useful for
+    /// allowing access to handles from an FFI layer.
+    pub fn from_id(handle_id: u64) -> Self {
+        Self { handle_id }
+    }
+    /// Gets the ID for this handle.
+    ///
+    /// Since the underlying handle is un-typed,`
+    /// this method is only suitable for
+    /// transmitting handles across an FFI layer.
+    pub fn get_id(&self) -> u64 {
+        self.handle_id
+    }
+    /// Derives the shard index from the handle id
+    fn get_shard_index(&self, num_shards: u8) -> usize {
+        (self.handle_id % (num_shards as u64)) as usize
+    }
+}
+
+/// Error raised when attempting to allocate into a full handle-map.
+#[derive(Debug)]
+pub struct HandleMapFullError;
+
+/// Internal error enum for failed allocations into a given shard.
+enum ShardAllocationError<T, F: FnOnce() -> T> {
+    /// Error for when the entry for the handle is occupied,
+    /// in which case we spit out the object-provider to try again
+    /// with a new handle-id.
+    EntryOccupied(F),
+    /// Error for when we would exceed the maximum number of allocations.
+    ExceedsAllocationLimit,
+}
+
+/// Error raised when the entry for a given [`Handle`] doesn't exist.
+#[derive(Debug)]
+pub struct HandleNotPresentError;
+
+/// Wrapper around a `HandleMap` which is specifically tailored for maintaining
+/// a global singleton `'static` reference to a handle-map.
+/// The wrapper handles initialization of the singleton in a const-context
+/// and subsequent accesses to ensure that the underlying map is always
+/// initialized upon attempts to access it.
+pub struct SingletonHandleMap<I: SingletonHandleMapInfo> {
+    info: I,
+    wrapped: spin::once::Once<HandleMap<I::Object>, spin::relax::Spin>,
+}
+
+impl<I: SingletonHandleMapInfo> SingletonHandleMap<I> {
+    /// Constructs a new global handle-map using the given
+    /// singleton handle-map info. This method is callable
+    /// from a `const`-context to allow it to be used to initialize
+    /// `static` variables.
+    pub const fn with_info(info: I) -> Self {
+        Self { info, wrapped: spin::once::Once::new() }
+    }
+    /// Initialize the handle-map if it's not already initialized,
+    /// and return a reference to the result.
+    pub fn get(&self) -> &HandleMap<I::Object> {
+        self.wrapped.call_once(|| {
+            let dimensions = self.info.dimensions();
+            HandleMap::with_dimensions(dimensions)
+        })
+    }
+}
+
+/// A thread-safe mapping from "handle"s [like pointers, but safer]
+/// to underlying structures, supporting allocations, reads, writes,
+/// and deallocations of objects behind handles.
+pub struct HandleMap<T: Send + Sync> {
+    /// The dimensions of this handle-map
+    dimensions: HandleMapDimensions,
+
+    /// The individually-lockable "shards" of the handle-map,
+    /// among which the keys will be roughly uniformly-distributed.
+    handle_map_shards: Box<[HandleMapShard<T>]>,
+
+    /// An atomically-incrementing counter which tracks the
+    /// next handle ID which allocations will attempt to use.
+    new_handle_id_counter: AtomicU64,
+
+    /// An atomic integer roughly tracking the number of
+    /// currently-outstanding allocated entries in this
+    /// handle-map among all [`HandleMapShard`]s.
+    outstanding_allocations_counter: AtomicU32,
+}
+
+impl<T: Send + Sync> HandleMap<T> {
+    /// Creates a new handle-map with the given `HandleMapDimensions`.
+    pub fn with_dimensions(dimensions: HandleMapDimensions) -> Self {
+        let mut handle_map_shards = Vec::with_capacity(dimensions.num_shards as usize);
+        for _ in 0..dimensions.num_shards {
+            handle_map_shards.push(HandleMapShard::default());
+        }
+        let handle_map_shards = handle_map_shards.into_boxed_slice();
+        Self {
+            dimensions,
+            handle_map_shards,
+            new_handle_id_counter: AtomicU64::new(0),
+            outstanding_allocations_counter: AtomicU32::new(0),
+        }
+    }
+}
+
+impl<T: Send + Sync> HandleMap<T> {
+    /// Allocates a new object within the given handle-map, returning
+    /// a handle to the location it was stored at. This operation
+    /// may fail if attempting to allocate over the `dimensions.max_active_handles`
+    /// limit imposed on the handle-map, in which case this method
+    /// will return a `HandleMapFullError`.
+    pub fn allocate(
+        &self,
+        initial_value_provider: impl FnOnce() -> T,
+    ) -> Result<Handle, HandleMapFullError> {
+        let mut initial_value_provider = initial_value_provider;
+        loop {
+            // Increment the new-handle-ID counter using relaxed memory ordering,
+            // since the only invariant that we want to enforce is that concurrently-running
+            // threads always get distinct new handle-ids.
+            let new_handle_id = self.new_handle_id_counter.fetch_add(1, Ordering::Relaxed);
+            let new_handle = Handle::from_id(new_handle_id);
+            let shard_index = new_handle.get_shard_index(self.dimensions.num_shards);
+
+            // Now, check the shard to see if we can actually allocate into it.
+            let shard_allocate_result = self.handle_map_shards[shard_index].try_allocate(
+                new_handle,
+                initial_value_provider,
+                &self.outstanding_allocations_counter,
+                self.dimensions.max_active_handles,
+            );
+            match shard_allocate_result {
+                Ok(_) => {
+                    return Ok(new_handle);
+                }
+                Err(ShardAllocationError::ExceedsAllocationLimit) => {
+                    return Err(HandleMapFullError);
+                }
+                Err(ShardAllocationError::EntryOccupied(thrown_back_provider)) => {
+                    // We need to do the whole thing again with a new ID
+                    initial_value_provider = thrown_back_provider;
+                }
+            }
+        }
+    }
+
+    /// Gets a read-only reference to an object within the given handle-map,
+    /// if the given handle is present. Otherwise, returns [`HandleNotPresentError`].
+    pub fn get(&self, handle: Handle) -> Result<ObjectReadGuard<T>, HandleNotPresentError> {
+        let shard_index = handle.get_shard_index(self.dimensions.num_shards);
+        self.handle_map_shards[shard_index].get(handle)
+    }
+
+    /// Gets a read+write reference to an object within the given handle-map,
+    /// if the given handle is present. Otherwise, returns [`HandleNotPresentError`].
+    pub fn get_mut(
+        &self,
+        handle: Handle,
+    ) -> Result<ObjectReadWriteGuard<T>, HandleNotPresentError> {
+        let shard_index = handle.get_shard_index(self.dimensions.num_shards);
+        self.handle_map_shards[shard_index].get_mut(handle)
+    }
+
+    /// Removes the object pointed to by the given handle in
+    /// the handle-map, returning the removed object if it
+    /// exists. Otherwise, returns [`HandleNotPresentError`].
+    pub fn deallocate(&self, handle: Handle) -> Result<T, HandleNotPresentError> {
+        let shard_index = handle.get_shard_index(self.dimensions.num_shards);
+        self.handle_map_shards[shard_index]
+            .deallocate(handle, &self.outstanding_allocations_counter)
+    }
+
+    /// Gets the actual number of elements stored in the entire map.
+    /// Only suitable for single-threaded sections of tests.
+    #[cfg(test)]
+    pub(crate) fn len(&self) -> usize {
+        self.handle_map_shards.iter().map(|s| s.len()).sum()
+    }
+
+    /// Sets the new-handle-id counter to the given value.
+    /// Only suitable for tests.
+    #[cfg(test)]
+    pub(crate) fn set_new_handle_id_counter(&mut self, value: u64) {
+        self.new_handle_id_counter = AtomicU64::new(value);
+    }
+}
+
+// Bunch o' type aliases to make talking about them much easier in the shard code.
+type ShardMapType<T> = hashbrown::HashMap<Handle, T>;
+type ShardReadWriteLock<T> = RwLock<ShardMapType<T>>;
+type ShardReadGuard<'a, T> = RwLockReadGuard<'a, ShardMapType<T>>;
+type ShardUpgradableReadGuard<'a, T> = RwLockUpgradableReadGuard<'a, ShardMapType<T>>;
+type ShardReadWriteGuard<'a, T> = RwLockWriteGuard<'a, ShardMapType<T>>;
+
+/// An individual handle-map shard, which is ultimately
+/// just a hash-map behind a lock.
+pub(crate) struct HandleMapShard<T: Send + Sync> {
+    data: RwLock<ShardMapType<T>>,
+}
+
+impl<T: Send + Sync> Default for HandleMapShard<T> {
+    fn default() -> Self {
+        Self { data: RwLock::new(hashbrown::HashMap::new()) }
+    }
+}
+
+impl<T: Send + Sync> HandleMapShard<T> {
+    fn get(&self, handle: Handle) -> Result<ObjectReadGuard<T>, HandleNotPresentError> {
+        let map_read_guard = ShardReadWriteLock::<T>::read(&self.data);
+        let read_only_map_ref = map_read_guard.deref();
+        if read_only_map_ref.contains_key(&handle) {
+            let object_read_guard = ShardReadGuard::<T>::map(map_read_guard, move |map_ref| {
+                // We know that the entry exists, since we've locked the
+                // shard and already checked that it exists prior to
+                // handing out this new, mapped read-lock.
+                map_ref.get(&handle).unwrap()
+            });
+            Ok(ObjectReadGuard { guard: object_read_guard })
+        } else {
+            // Auto-drop the read guard, and return an error
+            Err(HandleNotPresentError)
+        }
+    }
+    /// Gets a read-write guard on the entire shard map if an entry for the given
+    /// handle exists, but if not, yield [`HandleNotPresentError`].
+    fn get_read_write_guard_if_entry_exists(
+        &self,
+        handle: Handle,
+    ) -> Result<ShardReadWriteGuard<T>, HandleNotPresentError> {
+        // Start with an upgradable read lock and then upgrade to a write lock.
+        // By doing this, we prevent new readers from entering (see `spin` documentation)
+        let map_upgradable_read_guard = ShardReadWriteLock::<T>::upgradable_read(&self.data);
+        let read_only_map_ref = map_upgradable_read_guard.deref();
+        if read_only_map_ref.contains_key(&handle) {
+            // If we know that the entry exists, and we're currently
+            // holding a read-lock, we know that we're safe to request
+            // an upgrade to a write lock, since only one write or
+            // upgradable read lock can be outstanding at any one time.
+            let map_read_write_guard =
+                ShardUpgradableReadGuard::<T>::upgrade(map_upgradable_read_guard);
+            Ok(map_read_write_guard)
+        } else {
+            // Auto-drop the read guard, we don't need to allow a write.
+            Err(HandleNotPresentError)
+        }
+    }
+
+    fn get_mut(&self, handle: Handle) -> Result<ObjectReadWriteGuard<T>, HandleNotPresentError> {
+        let map_read_write_guard = self.get_read_write_guard_if_entry_exists(handle)?;
+        // Expose only the pointed-to object with a mapped read-write guard
+        let object_read_write_guard =
+            ShardReadWriteGuard::<T>::map(map_read_write_guard, move |map_ref| {
+                // Already checked that the entry exists while holding the lock
+                map_ref.get_mut(&handle).unwrap()
+            });
+        Ok(ObjectReadWriteGuard { guard: object_read_write_guard })
+    }
+    fn deallocate(
+        &self,
+        handle: Handle,
+        outstanding_allocations_counter: &AtomicU32,
+    ) -> Result<T, HandleNotPresentError> {
+        let mut map_read_write_guard = self.get_read_write_guard_if_entry_exists(handle)?;
+        // We don't need to worry about double-decrements, since the above call
+        // got us an upgradable read guard for our read, which means it's the only
+        // outstanding upgradeable guard on the shard. See `spin` documentation.
+        // Remove the pointed-to object from the map, and return it,
+        // releasing the lock when the guard goes out of scope.
+        let removed_object = map_read_write_guard.deref_mut().remove(&handle).unwrap();
+        // Decrement the allocations counter. Release ordering because we want
+        // to ensure that clearing the map entry never gets re-ordered to after when
+        // this counter gets decremented.
+        outstanding_allocations_counter.sub(1, Ordering::Release);
+        Ok(removed_object)
+    }
+
+    fn try_allocate<F>(
+        &self,
+        handle: Handle,
+        object_provider: F,
+        outstanding_allocations_counter: &AtomicU32,
+        max_active_handles: u32,
+    ) -> Result<(), ShardAllocationError<T, F>>
+    where
+        F: FnOnce() -> T,
+    {
+        // Use an upgradeable read guard -> write guard to provide greater fairness
+        // toward writers (see `spin` documentation)
+        let map_upgradable_read_guard = ShardReadWriteLock::<T>::upgradable_read(&self.data);
+        let mut map_read_write_guard =
+            ShardUpgradableReadGuard::<T>::upgrade(map_upgradable_read_guard);
+        match map_read_write_guard.entry_ref(&handle) {
+            EntryRef::Occupied(_) => {
+                // We've already allocated for that handle-id, so yield
+                // the object provider back to the caller.
+                Err(ShardAllocationError::EntryOccupied(object_provider))
+            }
+            EntryRef::Vacant(vacant_entry) => {
+                // An entry is open, but we haven't yet checked the allocations count.
+                // Try to increment the total allocations count atomically.
+                // Use acquire ordering on a successful bump, because we don't want
+                // to invoke the allocation closure before we have a guaranteed slot.
+                // On the other hand, upon failure, we don't care about ordering
+                // of surrounding operations, and so we use a relaxed ordering there.
+                let allocation_count_bump_result = outstanding_allocations_counter.fetch_update(
+                    Ordering::Acquire,
+                    Ordering::Relaxed,
+                    |old_total_allocations| {
+                        if old_total_allocations >= max_active_handles {
+                            None
+                        } else {
+                            Some(old_total_allocations + 1)
+                        }
+                    },
+                );
+                match allocation_count_bump_result {
+                    Ok(_) => {
+                        // We're good to actually allocate
+                        let object = object_provider();
+                        vacant_entry.insert(object);
+                        Ok(())
+                    }
+                    Err(_) => {
+                        // The allocation would cause us to exceed the allowed allocations,
+                        // so release all locks and error.
+                        Err(ShardAllocationError::ExceedsAllocationLimit)
+                    }
+                }
+            }
+        }
+    }
+    /// Gets the actual number of elements stored in this shard.
+    /// Only suitable for single-threaded sections of tests.
+    #[cfg(test)]
+    fn len(&self) -> usize {
+        let guard = ShardReadWriteLock::<T>::read(&self.data);
+        guard.deref().len()
+    }
+}
+
+/// Externally-facing trait for things which behave like handle-map handles
+/// with a globally-defined handle-map for the type.
+pub trait HandleLike: Sized {
+    /// The underlying object type pointed-to by this handle
+    type Object: Send + Sync;
+
+    /// Tries to allocate a new handle using the given provider
+    /// to construct the underlying stored object as a new
+    /// entry into the global handle table for this type.
+    fn allocate(
+        initial_value_provider: impl FnOnce() -> Self::Object,
+    ) -> Result<Self, HandleMapFullError>;
+
+    /// Gets a RAII read-guard on the contents behind this handle.
+    fn get(&self) -> Result<ObjectReadGuard<Self::Object>, HandleNotPresentError>;
+
+    /// Gets a RAII read-write guard on the contents behind this handle.
+    fn get_mut(&self) -> Result<ObjectReadWriteGuard<Self::Object>, HandleNotPresentError>;
+
+    /// Deallocates the contents behind this handle.
+    fn deallocate(self) -> Result<Self::Object, HandleNotPresentError>;
+}
+
+#[macro_export]
+/// `declare_handle_map! { handle_module_name, handle_type_name, wrapped_type,
+/// map_dimension_provider }`
+///
+/// Declares a new public module with name `handle_module_name` which includes a new type
+/// `handle_type_name` which is `#[repr(C)]` and represents FFI-accessible handles
+/// to values of type `wrapped_type`.
+///
+/// Internal to the generated module, a new static `SingletonHandleMap` is created, where the
+/// maximum number of active handles and the number of shards are given by
+/// the dimensions returned by evaluation of the `map_dimension_provider` expression.
+///
+/// Note: `map_dimension_provider` will be evaluated within the defined module's scope,
+/// so you will likely need to use `super` to refer to definitions in the enclosing scope.
+///
+/// # Example
+/// The following code defines an FFI-safe type `StringHandle` which references
+/// the `String` data-type, and uses it to define a (contrived)
+/// function `sample` which will print "Hello World".
+///
+/// ```
+/// mod sample {
+///     use core::ops::Deref;
+///     use handle_map::{declare_handle_map, HandleMapDimensions, HandleLike};
+///
+///     fn get_string_handle_map_dimensions() -> HandleMapDimensions {
+///         HandleMapDimensions {
+///             num_shards: 8,
+///             max_active_handles: 100,
+///         }
+///     }
+///
+///     declare_handle_map! { string_handle, StringHandle, String,
+///                           super::get_string_handle_map_dimensions() }
+///
+///     use string_handle::StringHandle;
+///
+///     fn sample() {
+///         // Note: this method could panic if there are
+///         // more than 99 outstanding handles.
+///
+///         // Allocate a new string-handle pointing to the string "Hello"
+///         let handle = StringHandle::allocate(|| { "Hello".to_string() }).unwrap();
+///         {
+///             // Obtain a write-guard on the contents of our handle
+///             let mut handle_write_guard = handle.get_mut().unwrap();
+///             handle_write_guard.push_str(" World");
+///             // Write guard is auto-dropped at the end of this block.
+///         }
+///         {
+///             // Obtain a read-guard on the contents of our handle.
+///             // Note that we had to ensure that the write-guard was
+///             // dropped prior to doing this, or else execution
+///             // could potentially hang.
+///             let handle_read_guard = handle.get().unwrap();
+///             println!("{}", handle_read_guard.deref());
+///         }
+///         // Clean up the data behind the created handle
+///         handle.deallocate().unwrap();
+///     }
+/// }
+/// ```
+macro_rules! declare_handle_map {
+    ($handle_module_name:ident, $handle_type_name:ident, $wrapped_type:ty,
+     $map_dimension_provider:expr) => {
+        #[doc = concat!("Macro-generated (via `handle_map::declare_handle_map!`) module",
+                        " which defines the `", stringify!($handle_module_name), "::",
+                        stringify!($handle_type_name), "` FFI-transmissible handle type ",
+                        " which references values of type `", stringify!($wrapped_type), "`.")]
+        pub mod $handle_module_name {
+            use $crate::SingletonHandleMapInfo;
+
+            struct SingletonInfo;
+
+            static GLOBAL_HANDLE_MAP: $crate::SingletonHandleMap<SingletonInfo> =
+                $crate::SingletonHandleMap::with_info(SingletonInfo);
+
+            impl $crate::SingletonHandleMapInfo for SingletonInfo {
+                type Object = $wrapped_type;
+
+                fn dimensions(&self) -> $crate::HandleMapDimensions {
+                    $map_dimension_provider
+                }
+                fn get_handle_map() -> &'static $crate::HandleMap<$wrapped_type> {
+                    GLOBAL_HANDLE_MAP.get()
+                }
+            }
+
+            #[doc = concat!("A `#[repr(C)]` handle to a value of type `",
+                            stringify!($wrapped_type), "`.")]
+            #[repr(C)]
+            #[derive(Clone, Copy, PartialEq, Eq)]
+            pub struct $handle_type_name {
+                handle_id: u64,
+            }
+
+            impl $handle_type_name {
+                fn get_as_handle(&self) -> $crate::Handle {
+                    $crate::Handle::from_id(self.handle_id)
+                }
+            }
+            impl $crate::HandleLike for $handle_type_name {
+                type Object = $wrapped_type;
+                fn allocate(initial_value_provider: impl FnOnce() -> $wrapped_type,
+                ) -> Result<Self, $crate::HandleMapFullError> {
+                    SingletonInfo::get_handle_map().allocate(initial_value_provider)
+                        .map(|derived_handle| Self {
+                            handle_id: derived_handle.get_id(),
+                        })
+                }
+                fn get(&self) -> Result<$crate::ObjectReadGuard<$wrapped_type>, $crate::HandleNotPresentError> {
+                    SingletonInfo::get_handle_map().get(self.get_as_handle())
+                }
+                fn get_mut(&self) -> Result<$crate::ObjectReadWriteGuard<$wrapped_type>, $crate::HandleNotPresentError> {
+                    SingletonInfo::get_handle_map().get_mut(self.get_as_handle())
+                }
+                fn deallocate(self) -> Result<$wrapped_type, $crate::HandleNotPresentError> {
+                    SingletonInfo::get_handle_map().deallocate(self.get_as_handle())
+                }
+            }
+        }
+    }
+}
diff --git a/nearby/presence/handle_map/src/tests.rs b/nearby/presence/handle_map/src/tests.rs
new file mode 100644
index 0000000..d97657f
--- /dev/null
+++ b/nearby/presence/handle_map/src/tests.rs
@@ -0,0 +1,288 @@
+// Copyright 2023 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+use crate::*;
+
+use hashbrown::HashSet;
+use std::sync::Arc;
+use std::thread;
+
+// Maximum number of active handles used across all tests
+// Chosen to be divisible by the number of active threads
+const MAX_ACTIVE_HANDLES: u32 = NUM_ACTIVE_THREADS * MAX_ACTIVE_HANDLES_PER_THREAD;
+
+const MAX_ACTIVE_HANDLES_PER_THREAD: u32 = 16384;
+
+// Deliberately picking a low number of shards so that we
+// are more likely to discover conflicts between threads.
+const NUM_SHARDS: u8 = 4;
+
+// Deliberately picking a higher number of threads.
+const NUM_ACTIVE_THREADS: u32 = 8;
+
+const DEFAULT_DIMENSIONS: HandleMapDimensions =
+    HandleMapDimensions { num_shards: NUM_SHARDS, max_active_handles: MAX_ACTIVE_HANDLES };
+
+fn build_handle_map<T: Send + Sync>() -> HandleMap<T> {
+    HandleMap::with_dimensions(DEFAULT_DIMENSIONS)
+}
+
+/// Performs the same testing function for each thread
+fn test_for_each_thread<F>(test_function_ref: Arc<F>, num_repetitions_per_thread: usize)
+where
+    F: Fn() + Send + Sync + 'static,
+{
+    let mut join_handles = Vec::new();
+    for _ in 0..NUM_ACTIVE_THREADS {
+        let test_function_clone = test_function_ref.clone();
+        let join_handle = thread::spawn(move || {
+            for _ in 0..num_repetitions_per_thread {
+                test_function_clone();
+            }
+        });
+        join_handles.push(join_handle);
+    }
+    for join_handle in join_handles {
+        join_handle.join().unwrap()
+    }
+}
+
+/// Tests the consistency of reads from the same handle across
+/// multiple threads.
+#[test]
+fn test_read_consistency_same_address() {
+    let num_repetitions_per_thread = 10000;
+    let handle_map = build_handle_map::<String>();
+    let handle = handle_map.allocate(|| "hello".to_string()).expect("Allocation shouldn't fail");
+    let test_fn = Arc::new(move || {
+        let value_ref = handle_map.get(handle).expect("Getting shouldn't fail");
+        assert_eq!("hello", value_ref.deref());
+    });
+    test_for_each_thread(test_fn, num_repetitions_per_thread);
+}
+
+/// Tests overloading the table with allocations to ensure
+/// that when all is said and done, we still haven't exceeded
+/// the allocations limit.
+#[test]
+#[allow(unused_must_use)]
+fn test_overload_with_allocations() {
+    let num_repetitions_per_thread = 2 * MAX_ACTIVE_HANDLES_PER_THREAD as usize;
+    let handle_map = build_handle_map::<u8>();
+
+    let handle_map_function_ref = Arc::new(handle_map);
+    let handle_map_post_function_ref = handle_map_function_ref.clone();
+
+    let test_fn = Arc::new(move || {
+        handle_map_function_ref.allocate(|| 0xFF);
+    });
+    test_for_each_thread(test_fn, num_repetitions_per_thread);
+
+    let actual_num_active_handles = handle_map_post_function_ref.len();
+    assert_eq!(MAX_ACTIVE_HANDLES as usize, actual_num_active_handles);
+}
+
+/// Tests deallocations and allocations near the allocation limit.
+#[test]
+#[allow(unused_must_use)]
+fn test_overload_allocations_deallocations() {
+    let num_repetitions_per_thread = 10000;
+
+    //Pre-fill the map so that there's only one available entry.
+    let handle_map = build_handle_map::<u8>();
+    for i in 0..(MAX_ACTIVE_HANDLES - 1) {
+        handle_map.allocate(|| (i % 256) as u8);
+    }
+
+    let handle_map_function_ref = Arc::new(handle_map);
+    let handle_map_post_function_ref = handle_map_function_ref.clone();
+
+    let test_fn = Arc::new(move || {
+        let allocation_result = handle_map_function_ref.allocate(|| 0xFF);
+        if let Ok(handle) = allocation_result {
+            handle_map_function_ref.deallocate(handle).unwrap();
+        }
+    });
+    test_for_each_thread(test_fn, num_repetitions_per_thread);
+
+    // No matter what happened above, we should have the same number
+    // of handles as when we started, because every successful allocation
+    // should have been paired with a successful deallocation.
+    let actual_num_active_handles = handle_map_post_function_ref.len();
+    assert_eq!((MAX_ACTIVE_HANDLES - 1) as usize, actual_num_active_handles);
+
+    //Verify that we still have space for one more entry after all that.
+    handle_map_post_function_ref.allocate(|| 0xEE).unwrap();
+}
+
+/// Tests the progress of allocate/read/write/read/deallocate
+/// to independent handles across multiple threads.
+#[test]
+fn test_full_lifecycle_independent_handles() {
+    let num_repetitions_per_thread = 10000;
+    let handle_map = build_handle_map::<String>();
+    let test_fn = Arc::new(move || {
+        let handle =
+            handle_map.allocate(|| "Hello".to_string()).expect("Allocation shouldn't fail");
+        {
+            let value_ref = handle_map.get(handle).expect("Getting the value shouldn't fail");
+            assert_eq!("Hello", &*value_ref);
+        };
+        {
+            let mut value_mut_ref =
+                handle_map.get_mut(handle).expect("Mutating the value shouldn't fail");
+            value_mut_ref.deref_mut().push_str(" World!");
+        };
+        {
+            let value_ref = handle_map
+                .get(handle)
+                .expect("Getting the value after modification shouldn't fail");
+            assert_eq!("Hello World!", &*value_ref);
+        };
+        let removed = handle_map.deallocate(handle).expect("Deallocation shouldn't fail");
+        assert_eq!("Hello World!", removed);
+    });
+    test_for_each_thread(test_fn, num_repetitions_per_thread);
+}
+
+/// Tests the consistency of reads+writes to the same handle,
+/// where threads modify and read different parts of an
+/// underlying structure.
+#[test]
+fn test_consistency_of_same_handle_multithreaded_modifications() {
+    let num_repetitions_per_thread = 10000;
+    let handle_map = Arc::new(build_handle_map::<(String, String)>());
+    let handle = handle_map
+        .allocate(|| ("A".to_string(), "B".to_string()))
+        .expect("Allocation shouldn't fail");
+
+    let handle_map_second_ref = handle_map.clone();
+
+    let join_handle_a = thread::spawn(move || {
+        for i in 1..num_repetitions_per_thread {
+            {
+                let value_ref =
+                    handle_map.get(handle).expect("Getting the value from thread A shouldn't fail");
+                let value = &value_ref.0;
+                assert_eq!(i, value.len());
+            }
+            {
+                let mut value_mut_ref = handle_map
+                    .get_mut(handle)
+                    .expect("Mutating the value from thread A shouldn't fail");
+                value_mut_ref.0.push('A');
+            }
+        }
+    });
+
+    let join_handle_b = thread::spawn(move || {
+        for i in 1..num_repetitions_per_thread {
+            {
+                let value_ref = handle_map_second_ref
+                    .get(handle)
+                    .expect("Getting the value from thread B shouldn't fail");
+                let value = &value_ref.1;
+                assert_eq!(i, value.len());
+            }
+            {
+                let mut value_mut_ref = handle_map_second_ref
+                    .get_mut(handle)
+                    .expect("Mutating the value from thread B shouldn't fail");
+                value_mut_ref.1.push('B');
+            }
+        }
+    });
+
+    join_handle_a.join().unwrap();
+    join_handle_b.join().unwrap();
+}
+
+/// Multi-threaded test to ensure that when attempting
+/// to allocate over handle IDs which are already allocated,
+/// all threads eventually get distinct, unused handle IDs
+/// for their own allocations.
+#[test]
+fn test_non_overwriting_old_handles() {
+    let mut all_handles: HashSet<Handle> = HashSet::new();
+    let num_repetitions_per_thread = 100;
+    let mut handle_map = build_handle_map::<u8>();
+    for _ in 0..(num_repetitions_per_thread * NUM_ACTIVE_THREADS) {
+        let handle = handle_map.allocate(|| 0xFF).expect("Initial allocations shouldn't fail");
+        all_handles.insert(handle);
+    }
+    // Reset the new-handle-id counter
+    handle_map.set_new_handle_id_counter(0);
+
+    let handle_map = Arc::new(handle_map);
+
+    let mut thread_handles: Vec<thread::JoinHandle<Vec<Handle>>> = Vec::new();
+    for _ in 0..NUM_ACTIVE_THREADS {
+        let handle_map_reference = handle_map.clone();
+        let thread_handle = thread::spawn(move || {
+            let mut handles = Vec::new();
+            for i in 0..num_repetitions_per_thread {
+                let handle = handle_map_reference
+                    .allocate(move || (i % 256) as u8)
+                    .expect("No allocation should fail");
+                handles.push(handle);
+            }
+            handles
+        });
+        thread_handles.push(thread_handle);
+    }
+    for thread_handle in thread_handles {
+        let handles: Vec<Handle> = thread_handle.join().expect("Individual threads shouldn't fail");
+        for handle in handles {
+            let was_distinct = all_handles.insert(handle);
+            assert!(was_distinct);
+        }
+    }
+}
+
+#[test]
+fn test_id_wraparound() {
+    let mut handle_map = build_handle_map::<u8>();
+    handle_map.set_new_handle_id_counter(u64::MAX);
+    handle_map.allocate(|| 0xAB).expect("Counter wrap-around allocation should not fail");
+    handle_map.allocate(|| 0xCD).expect("Post-counter-wrap-around allocation should not fail");
+}
+
+#[test]
+fn test_deallocate_unallocated_handle() {
+    let handle_map = build_handle_map::<usize>();
+    let handle = handle_map.allocate(|| 2).expect("Allocation shouldn't fail");
+    let deallocated = handle_map.deallocate(handle).expect("Deallocation shouldn't fail");
+    assert_eq!(2, deallocated);
+    let double_deallocate_result = handle_map.deallocate(handle);
+    assert!(double_deallocate_result.is_err());
+}
+
+#[test]
+fn test_get_unallocated_handle() {
+    let handle_map = build_handle_map::<u8>();
+    let handle = handle_map.allocate(|| 0xFE).expect("Allocation shouldn't fail");
+    let deallocated = handle_map.deallocate(handle).expect("Deallocation shouldn't fail");
+    assert_eq!(0xFE, deallocated);
+    let read_result = handle_map.get(handle);
+    assert!(read_result.is_err());
+}
+
+#[test]
+fn test_get_mut_unallocated_handle() {
+    let handle_map = build_handle_map::<(usize, usize, usize)>();
+    let handle = handle_map.allocate(|| (1, 2, 3)).expect("Allocation shouldn't fail");
+    let deallocated = handle_map.deallocate(handle).expect("Deallocation shouldn't fail");
+    assert_eq!((1, 2, 3), deallocated);
+    let get_mut_result = handle_map.get_mut(handle);
+    assert!(get_mut_result.is_err());
+}