Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit42d9377

Browse files
committed
MakeHashTable entries useTag instead of a full hash
`VacantEntry` now stores a `Tag` instead of a full `hash: u64`. Thismeans that `OccupiedEntry` doesn't need to store anything, because itcan get that tag from the control byte for `remove -> VacantEntry`.The `get_bucket_entry` method doesn't need a hash argument either.Also, since `OccupiedEntry` is now smaller, `enum Entry` will be thesame size as `VacantEntry` by using a niche for the discriminant.(Although this is not _guaranteed_ by the compiler.)
1 parent5aac3c9 commit42d9377

File tree

2 files changed

+57
-34
lines changed

2 files changed

+57
-34
lines changed

‎src/raw/mod.rs‎

Lines changed: 39 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -838,6 +838,19 @@ impl<T, A: Allocator> RawTable<T, A> {
838838
(item.read(),self.bucket_index(&item))
839839
}
840840

841+
/// Removes an element from the table, returning it.
842+
///
843+
/// This also returns an index to the newly free bucket
844+
/// and the former `Tag` for that bucket.
845+
#[cfg_attr(feature ="inline-more", inline)]
846+
#[allow(clippy::needless_pass_by_value)]
847+
pub(crate)unsafefnremove_tagged(&mutself,item:Bucket<T>) ->(T,usize,Tag){
848+
let index =self.bucket_index(&item);
849+
let tag =*self.table.ctrl(index);
850+
self.table.erase(index);
851+
(item.read(), index, tag)
852+
}
853+
841854
/// Finds and removes an element from the table, returning it.
842855
#[cfg_attr(feature ="inline-more", inline)]
843856
pubfnremove_entry(&mutself,hash:u64,eq:implFnMut(&T) ->bool) ->Option<T>{
@@ -1172,8 +1185,8 @@ impl<T, A: Allocator> RawTable<T, A> {
11721185
}
11731186
}
11741187

1175-
/// Inserts a new element into the table at the given index, and returns its
1176-
/// raw bucket.
1188+
/// Inserts a new element into the table at the given index with the given hash,
1189+
///and returns itsraw bucket.
11771190
///
11781191
/// # Safety
11791192
///
@@ -1182,8 +1195,26 @@ impl<T, A: Allocator> RawTable<T, A> {
11821195
/// occurred since that call.
11831196
#[inline]
11841197
pubunsafefninsert_at_index(&mutself,hash:u64,index:usize,value:T) ->Bucket<T>{
1198+
self.insert_tagged_at_index(Tag::full(hash), index, value)
1199+
}
1200+
1201+
/// Inserts a new element into the table at the given index with the given tag,
1202+
/// and returns its raw bucket.
1203+
///
1204+
/// # Safety
1205+
///
1206+
/// `index` must point to a slot previously returned by
1207+
/// `find_or_find_insert_index`, and no mutation of the table must have
1208+
/// occurred since that call.
1209+
#[inline]
1210+
pub(crate)unsafefninsert_tagged_at_index(
1211+
&mutself,
1212+
tag:Tag,
1213+
index:usize,
1214+
value:T,
1215+
) ->Bucket<T>{
11851216
let old_ctrl =*self.table.ctrl(index);
1186-
self.table.record_item_insert_at(index, old_ctrl,hash);
1217+
self.table.record_item_insert_at(index, old_ctrl,tag);
11871218

11881219
let bucket =self.bucket(index);
11891220
bucket.write(value);
@@ -1258,11 +1289,11 @@ impl<T, A: Allocator> RawTable<T, A> {
12581289
}
12591290

12601291
/// Returns a pointer to an element in the table, but only after verifying that
1261-
/// the index is in-bounds andthat its control byte matchesthegiven hash.
1292+
/// the index is in-bounds and thebucket is occupied.
12621293
#[inline]
1263-
pubfnchecked_bucket(&self,hash:u64,index:usize) ->Option<Bucket<T>>{
1294+
pubfnchecked_bucket(&self,index:usize) ->Option<Bucket<T>>{
12641295
unsafe{
1265-
if index <self.buckets() &&*self.table.ctrl(index) ==Tag::full(hash){
1296+
if index <self.buckets() &&self.is_bucket_full(index){
12661297
Some(self.bucket(index))
12671298
}else{
12681299
None
@@ -2442,9 +2473,9 @@ impl RawTableInner {
24422473
}
24432474

24442475
#[inline]
2445-
unsafefnrecord_item_insert_at(&mutself,index:usize,old_ctrl:Tag,hash:u64){
2476+
unsafefnrecord_item_insert_at(&mutself,index:usize,old_ctrl:Tag,new_ctrl:Tag){
24462477
self.growth_left -= usize::from(old_ctrl.special_is_empty());
2447-
self.set_ctrl_hash(index,hash);
2478+
self.set_ctrl(index,new_ctrl);
24482479
self.items +=1;
24492480
}
24502481

‎src/table.rs‎

Lines changed: 18 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,7 @@
11
use core::{fmt, iter::FusedIterator, marker::PhantomData};
22

33
usecrate::{
4+
control::Tag,
45
raw::{
56
Allocator,Bucket,Global,RawDrain,RawExtractIf,RawIntoIter,RawIter,RawIterHash,
67
RawTable,
@@ -303,7 +304,6 @@ where
303304
) ->Result<OccupiedEntry<'_,T,A>,AbsentEntry<'_,T,A>>{
304305
matchself.raw.find(hash, eq){
305306
Some(bucket) =>Ok(OccupiedEntry{
306-
hash,
307307
bucket,
308308
table:self,
309309
}),
@@ -413,24 +413,19 @@ where
413413
) ->Entry<'_,T,A>{
414414
matchself.raw.find_or_find_insert_index(hash, eq, hasher){
415415
Ok(bucket) =>Entry::Occupied(OccupiedEntry{
416-
hash,
417416
bucket,
418417
table:self,
419418
}),
420419
Err(insert_index) =>Entry::Vacant(VacantEntry{
421-
hash,
420+
tag:Tag::full(hash),
422421
index: insert_index,
423422
table:self,
424423
}),
425424
}
426425
}
427426

428-
/// Returns an `OccupiedEntry` for a bucket index in the table with the given hash,
429-
/// or `None` if the index is out of bounds or if its hash doesn't match.
430-
///
431-
/// However, note that the hash is only compared for the few bits that are directly stored in
432-
/// the table, and even in full this could not guarantee equality. Use [`OccupiedEntry::get`]
433-
/// if you need to further validate a match.
427+
/// Returns an `OccupiedEntry` for the given bucket index in the table,
428+
/// or `None` if it is unoccupied or out of bounds.
434429
///
435430
/// # Examples
436431
///
@@ -447,29 +442,25 @@ where
447442
/// table.insert_unique(hasher(&2), (2, 'b'), |val| hasher(&val.0));
448443
/// table.insert_unique(hasher(&3), (3, 'c'), |val| hasher(&val.0));
449444
///
450-
/// let hash = hasher(&2);
451-
/// let index = table.find_bucket_index(hash, |val| val.0 == 2).unwrap();
445+
/// let index = table.find_bucket_index(hasher(&2), |val| val.0 == 2).unwrap();
452446
///
453-
/// let bad_hash = !hash;
454-
/// assert!(table.get_bucket_entry(bad_hash, index).is_none());
455-
/// assert!(table.get_bucket_entry(hash, usize::MAX).is_none());
447+
/// assert!(table.get_bucket_entry(usize::MAX).is_none());
456448
///
457-
/// let occupied_entry = table.get_bucket_entry(hash,index).unwrap();
449+
/// let occupied_entry = table.get_bucket_entry(index).unwrap();
458450
/// assert_eq!(occupied_entry.get(), &(2, 'b'));
459451
/// assert_eq!(occupied_entry.remove().0, (2, 'b'));
460452
///
461-
/// assert!(table.find(hash, |val| val.0 == 2).is_none());
453+
/// assert!(table.find(hasher(&2), |val| val.0 == 2).is_none());
462454
/// # }
463455
/// # fn main() {
464456
/// # #[cfg(feature = "nightly")]
465457
/// # test()
466458
/// # }
467459
/// ```
468460
#[inline]
469-
pubfnget_bucket_entry(&mutself,hash:u64,index:usize) ->Option<OccupiedEntry<'_,T,A>>{
461+
pubfnget_bucket_entry(&mutself,index:usize) ->Option<OccupiedEntry<'_,T,A>>{
470462
Some(OccupiedEntry{
471-
hash,
472-
bucket:self.raw.checked_bucket(hash, index)?,
463+
bucket:self.raw.checked_bucket(index)?,
473464
table:self,
474465
})
475466
}
@@ -573,7 +564,6 @@ where
573564
) ->OccupiedEntry<'_,T,A>{
574565
let bucket =self.raw.insert(hash, value, hasher);
575566
OccupiedEntry{
576-
hash,
577567
bucket,
578568
table:self,
579569
}
@@ -1771,7 +1761,6 @@ pub struct OccupiedEntry<'a, T, A = Global>
17711761
where
17721762
A:Allocator,
17731763
{
1774-
hash:u64,
17751764
bucket:Bucket<T>,
17761765
table:&'amutHashTable<T,A>,
17771766
}
@@ -1840,11 +1829,11 @@ where
18401829
/// ```
18411830
#[cfg_attr(feature ="inline-more", inline)]
18421831
pubfnremove(self) ->(T,VacantEntry<'a,T,A>){
1843-
let(val, index) =unsafe{self.table.raw.remove(self.bucket)};
1832+
let(val, index, tag) =unsafe{self.table.raw.remove_tagged(self.bucket)};
18441833
(
18451834
val,
18461835
VacantEntry{
1847-
hash:self.hash,
1836+
tag,
18481837
index,
18491838
table:self.table,
18501839
},
@@ -2083,7 +2072,7 @@ pub struct VacantEntry<'a, T, A = Global>
20832072
where
20842073
A:Allocator,
20852074
{
2086-
hash:u64,
2075+
tag:Tag,
20872076
index:usize,
20882077
table:&'amutHashTable<T,A>,
20892078
}
@@ -2131,9 +2120,12 @@ where
21312120
/// ```
21322121
#[inline]
21332122
pubfninsert(self,value:T) ->OccupiedEntry<'a,T,A>{
2134-
let bucket =unsafe{self.table.raw.insert_at_index(self.hash,self.index, value)};
2123+
let bucket =unsafe{
2124+
self.table
2125+
.raw
2126+
.insert_tagged_at_index(self.tag,self.index, value)
2127+
};
21352128
OccupiedEntry{
2136-
hash:self.hash,
21372129
bucket,
21382130
table:self.table,
21392131
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp