Skip to main content

rustjava_runtime/classes/java/util/
hash_map.rs

1use alloc::{format, vec, vec::Vec};
2
3use jvm::{Array, ClassInstanceRef, Jvm, Result};
4use jvm_class_proto::{JavaFieldProto, JavaMethodProto};
5use jvm_types::{ClassAccessFlags, FieldAccessFlags, MethodAccessFlags};
6
7use crate::{RuntimeClassProto, RuntimeContext, classes::java::lang::Object};
8
9use super::HashMapEntry;
10
11const DEFAULT_INITIAL_CAPACITY: i32 = 16;
12const DEFAULT_LOAD_FACTOR: f32 = 0.75;
13
14// class java.util.HashMap
15pub struct HashMap;
16
17impl HashMap {
18    pub fn as_proto() -> RuntimeClassProto {
19        RuntimeClassProto {
20            name: "java/util/HashMap",
21            parent_class: Some("java/util/AbstractMap"),
22            interfaces: vec!["java/lang/Cloneable", "java/io/Serializable"],
23            methods: vec![
24                JavaMethodProto::new("<init>", "()V", Self::init, MethodAccessFlags::PUBLIC),
25                JavaMethodProto::new("<init>", "(I)V", Self::init_with_capacity, MethodAccessFlags::PUBLIC),
26                JavaMethodProto::new("<init>", "(IF)V", Self::init_with_capacity_and_load_factor, MethodAccessFlags::PUBLIC),
27                JavaMethodProto::new("<init>", "(Ljava/util/Map;)V", Self::init_from_map, MethodAccessFlags::PUBLIC),
28                JavaMethodProto::new("size", "()I", Self::size, MethodAccessFlags::PUBLIC),
29                JavaMethodProto::new("isEmpty", "()Z", Self::is_empty, MethodAccessFlags::PUBLIC),
30                JavaMethodProto::new("containsKey", "(Ljava/lang/Object;)Z", Self::contains_key, MethodAccessFlags::PUBLIC),
31                JavaMethodProto::new("containsValue", "(Ljava/lang/Object;)Z", Self::contains_value, MethodAccessFlags::PUBLIC),
32                JavaMethodProto::new("get", "(Ljava/lang/Object;)Ljava/lang/Object;", Self::get, MethodAccessFlags::PUBLIC),
33                JavaMethodProto::new(
34                    "put",
35                    "(Ljava/lang/Object;Ljava/lang/Object;)Ljava/lang/Object;",
36                    Self::put,
37                    MethodAccessFlags::PUBLIC,
38                ),
39                JavaMethodProto::new("putAll", "(Ljava/util/Map;)V", Self::put_all, MethodAccessFlags::PUBLIC),
40                JavaMethodProto::new(
41                    "remove",
42                    "(Ljava/lang/Object;)Ljava/lang/Object;",
43                    Self::remove,
44                    MethodAccessFlags::PUBLIC,
45                ),
46                JavaMethodProto::new("clear", "()V", Self::clear, MethodAccessFlags::PUBLIC),
47                JavaMethodProto::new("keySet", "()Ljava/util/Set;", Self::key_set, MethodAccessFlags::PUBLIC),
48                JavaMethodProto::new("values", "()Ljava/util/Collection;", Self::values, MethodAccessFlags::PUBLIC),
49                JavaMethodProto::new("entrySet", "()Ljava/util/Set;", Self::entry_set, MethodAccessFlags::PUBLIC),
50                JavaMethodProto::new("initializeMap", "()V", Self::initialize_map, MethodAccessFlags::empty()),
51                JavaMethodProto::new(
52                    "storeNewEntry",
53                    "(ILjava/lang/Object;Ljava/lang/Object;I)V",
54                    Self::store_new_entry,
55                    MethodAccessFlags::empty(),
56                ),
57                JavaMethodProto::new(
58                    "insertNewEntry",
59                    "(ILjava/lang/Object;Ljava/lang/Object;I)V",
60                    Self::insert_new_entry,
61                    MethodAccessFlags::empty(),
62                ),
63                JavaMethodProto::new("keyIterator", "()Ljava/util/Iterator;", Self::key_iterator, MethodAccessFlags::empty()),
64                JavaMethodProto::new(
65                    "valueIterator",
66                    "()Ljava/util/Iterator;",
67                    Self::value_iterator,
68                    MethodAccessFlags::empty(),
69                ),
70                JavaMethodProto::new(
71                    "entryIterator",
72                    "()Ljava/util/Iterator;",
73                    Self::entry_iterator,
74                    MethodAccessFlags::empty(),
75                ),
76            ],
77            fields: vec![
78                JavaFieldProto::new("table", "[Ljava/util/HashMap$Entry;", FieldAccessFlags::TRANSIENT),
79                JavaFieldProto::new("size", "I", FieldAccessFlags::TRANSIENT),
80                JavaFieldProto::new("threshold", "I", FieldAccessFlags::empty()),
81                JavaFieldProto::new("loadFactor", "F", FieldAccessFlags::FINAL),
82                JavaFieldProto::new("modCount", "I", FieldAccessFlags::TRANSIENT),
83            ],
84            access_flags: ClassAccessFlags::PUBLIC,
85        }
86    }
87
88    async fn init(jvm: &Jvm, _: &mut RuntimeContext, this: ClassInstanceRef<Self>) -> Result<()> {
89        tracing::debug!("java.util.HashMap::<init>({this:?})");
90
91        let _: () = jvm
92            .invoke_special(
93                &this,
94                "java/util/HashMap",
95                "<init>",
96                "(IF)V",
97                (DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR),
98            )
99            .await?;
100
101        Ok(())
102    }
103
104    async fn key_set(jvm: &Jvm, _: &mut RuntimeContext, this: ClassInstanceRef<Self>) -> Result<ClassInstanceRef<Object>> {
105        tracing::debug!("java.util.HashMap::keySet({this:?})");
106
107        let key_set = jvm.new_class("java/util/HashMap$KeySet", "(Ljava/util/HashMap;)V", (this,)).await?;
108
109        Ok(key_set.into())
110    }
111
112    async fn values(jvm: &Jvm, _: &mut RuntimeContext, this: ClassInstanceRef<Self>) -> Result<ClassInstanceRef<Object>> {
113        tracing::debug!("java.util.HashMap::values({this:?})");
114
115        let values = jvm.new_class("java/util/HashMap$Values", "(Ljava/util/HashMap;)V", (this,)).await?;
116
117        Ok(values.into())
118    }
119
120    async fn entry_set(jvm: &Jvm, _: &mut RuntimeContext, this: ClassInstanceRef<Self>) -> Result<ClassInstanceRef<Object>> {
121        tracing::debug!("java.util.HashMap::entrySet({this:?})");
122
123        let entry_set = jvm.new_class("java/util/HashMap$EntrySet", "(Ljava/util/HashMap;)V", (this,)).await?;
124
125        Ok(entry_set.into())
126    }
127
128    async fn keys_snapshot(jvm: &Jvm, this: &ClassInstanceRef<Self>) -> Result<ClassInstanceRef<Array<Object>>> {
129        Self::snapshot_entries(jvm, this, SnapshotKind::Keys).await
130    }
131
132    async fn values_snapshot(jvm: &Jvm, this: &ClassInstanceRef<Self>) -> Result<ClassInstanceRef<Array<Object>>> {
133        Self::snapshot_entries(jvm, this, SnapshotKind::Values).await
134    }
135
136    async fn entries_snapshot(jvm: &Jvm, this: &ClassInstanceRef<Self>) -> Result<ClassInstanceRef<Array<Object>>> {
137        Self::snapshot_entries(jvm, this, SnapshotKind::Entries).await
138    }
139
140    async fn init_with_capacity(jvm: &Jvm, _: &mut RuntimeContext, this: ClassInstanceRef<Self>, capacity: i32) -> Result<()> {
141        tracing::debug!("java.util.HashMap::<init>({this:?}, {capacity:?})");
142
143        jvm.invoke_special(&this, "java/util/HashMap", "<init>", "(IF)V", (capacity, DEFAULT_LOAD_FACTOR))
144            .await
145    }
146
147    async fn init_with_capacity_and_load_factor(
148        jvm: &Jvm,
149        _: &mut RuntimeContext,
150        mut this: ClassInstanceRef<Self>,
151        capacity: i32,
152        load_factor: f32,
153    ) -> Result<()> {
154        tracing::debug!("java.util.HashMap::<init>({this:?}, {capacity:?}, {load_factor:?})");
155
156        if capacity < 0 {
157            return Err(jvm
158                .exception("java/lang/IllegalArgumentException", &format!("Illegal Capacity: {capacity}"))
159                .await);
160        }
161        if load_factor <= 0.0 || load_factor.is_nan() {
162            return Err(jvm
163                .exception("java/lang/IllegalArgumentException", &format!("Illegal Load: {load_factor}"))
164                .await);
165        }
166
167        let _: () = jvm.invoke_special(&this, "java/util/AbstractMap", "<init>", "()V", ()).await?;
168
169        let table: ClassInstanceRef<Array<HashMapEntry>> = jvm.instantiate_array("Ljava/util/HashMap$Entry;", capacity as usize).await?.into();
170        jvm.put_field(&mut this, "java/util/HashMap", "table", "[Ljava/util/HashMap$Entry;", table)
171            .await?;
172        jvm.put_field(&mut this, "java/util/HashMap", "size", "I", 0).await?;
173        jvm.put_field(
174            &mut this,
175            "java/util/HashMap",
176            "threshold",
177            "I",
178            Self::threshold_for_capacity(capacity, load_factor),
179        )
180        .await?;
181        jvm.put_field(&mut this, "java/util/HashMap", "loadFactor", "F", load_factor).await?;
182        jvm.put_field(&mut this, "java/util/HashMap", "modCount", "I", 0).await?;
183        let _: () = jvm.invoke_virtual(&this, "java/util/HashMap", "initializeMap", "()V", ()).await?;
184
185        Ok(())
186    }
187
188    async fn init_from_map(jvm: &Jvm, _: &mut RuntimeContext, mut this: ClassInstanceRef<Self>, map: ClassInstanceRef<Object>) -> Result<()> {
189        tracing::debug!("java.util.HashMap::<init>({this:?}, {map:?})");
190
191        if map.is_null() {
192            return Err(jvm.exception("java/lang/NullPointerException", "map").await);
193        }
194        let size: i32 = jvm.invoke_virtual(&map, &map.class_definition().name(), "size", "()I", ()).await?;
195        let capacity = size.saturating_mul(2).max(DEFAULT_INITIAL_CAPACITY);
196        let _: () = jvm
197            .invoke_special(&this, "java/util/HashMap", "<init>", "(IF)V", (capacity, DEFAULT_LOAD_FACTOR))
198            .await?;
199        let entry_set: ClassInstanceRef<Object> = jvm
200            .invoke_virtual(&map, &map.class_definition().name(), "entrySet", "()Ljava/util/Set;", ())
201            .await?;
202        let entries: ClassInstanceRef<Array<Object>> = jvm
203            .invoke_virtual(&entry_set, &entry_set.class_definition().name(), "toArray", "()[Ljava/lang/Object;", ())
204            .await?;
205        let count = jvm.array_length(&entries).await?;
206        for entry in jvm.load_array::<ClassInstanceRef<Object>>(&entries, 0, count).await? {
207            let key: ClassInstanceRef<Object> = jvm
208                .invoke_virtual(&entry, &entry.class_definition().name(), "getKey", "()Ljava/lang/Object;", ())
209                .await?;
210            let value: ClassInstanceRef<Object> = jvm
211                .invoke_virtual(&entry, &entry.class_definition().name(), "getValue", "()Ljava/lang/Object;", ())
212                .await?;
213            Self::put_for_create(jvm, &mut this, key, value).await?;
214        }
215
216        Ok(())
217    }
218
219    async fn size(jvm: &Jvm, _: &mut RuntimeContext, this: ClassInstanceRef<Self>) -> Result<i32> {
220        tracing::debug!("java.util.HashMap::size({this:?})");
221
222        jvm.get_field(&this, "java/util/HashMap", "size", "I").await
223    }
224
225    async fn is_empty(jvm: &Jvm, _: &mut RuntimeContext, this: ClassInstanceRef<Self>) -> Result<bool> {
226        tracing::debug!("java.util.HashMap::isEmpty({this:?})");
227
228        let size: i32 = jvm.get_field(&this, "java/util/HashMap", "size", "I").await?;
229
230        Ok(size == 0)
231    }
232
233    async fn contains_key(jvm: &Jvm, _: &mut RuntimeContext, this: ClassInstanceRef<Self>, key: ClassInstanceRef<Object>) -> Result<bool> {
234        tracing::debug!("java.util.HashMap::containsKey({this:?}, {key:?})");
235
236        let entry = Self::find_entry(jvm, &this, &key).await?;
237
238        Ok(!entry.is_null())
239    }
240
241    async fn contains_value(jvm: &Jvm, _: &mut RuntimeContext, this: ClassInstanceRef<Self>, value: ClassInstanceRef<Object>) -> Result<bool> {
242        tracing::debug!("java.util.HashMap::containsValue({this:?}, {value:?})");
243
244        let table: ClassInstanceRef<Array<HashMapEntry>> = jvm.get_field(&this, "java/util/HashMap", "table", "[Ljava/util/HashMap$Entry;").await?;
245        let table_len = jvm.array_length(&table).await?;
246        for bucket_index in 0..table_len {
247            let mut entry = Self::load_bucket(jvm, &table, bucket_index).await?;
248            while !entry.is_null() {
249                let entry_value: ClassInstanceRef<Object> = jvm.get_field(&entry, "java/util/HashMap$Entry", "value", "Ljava/lang/Object;").await?;
250                if Self::object_equals(jvm, &value, &entry_value).await? {
251                    return Ok(true);
252                }
253
254                entry = jvm
255                    .get_field(&entry, "java/util/HashMap$Entry", "next", "Ljava/util/HashMap$Entry;")
256                    .await?;
257            }
258        }
259
260        Ok(false)
261    }
262
263    async fn get(jvm: &Jvm, _: &mut RuntimeContext, this: ClassInstanceRef<Self>, key: ClassInstanceRef<Object>) -> Result<ClassInstanceRef<Object>> {
264        tracing::debug!("java.util.HashMap::get({this:?}, {key:?})");
265
266        let entry = Self::find_entry(jvm, &this, &key).await?;
267        if entry.is_null() {
268            return Ok(None.into());
269        }
270
271        jvm.get_field(&entry, "java/util/HashMap$Entry", "value", "Ljava/lang/Object;").await
272    }
273
274    async fn put(
275        jvm: &Jvm,
276        _: &mut RuntimeContext,
277        mut this: ClassInstanceRef<Self>,
278        key: ClassInstanceRef<Object>,
279        value: ClassInstanceRef<Object>,
280    ) -> Result<ClassInstanceRef<Object>> {
281        tracing::debug!("java.util.HashMap::put({this:?}, {key:?}, {value:?})");
282
283        let key_hash = Self::object_hash_or_zero(jvm, &key).await?;
284        Self::ensure_table_for_insert(jvm, &mut this).await?;
285
286        let table: ClassInstanceRef<Array<HashMapEntry>> = jvm.get_field(&this, "java/util/HashMap", "table", "[Ljava/util/HashMap$Entry;").await?;
287        let table_len = jvm.array_length(&table).await?;
288        let bucket_index = Self::bucket_index(key_hash, table_len);
289
290        let mut entry = Self::load_bucket(jvm, &table, bucket_index).await?;
291        while !entry.is_null() {
292            let entry_hash: i32 = jvm.get_field(&entry, "java/util/HashMap$Entry", "hash", "I").await?;
293            if entry_hash == key_hash {
294                let entry_key: ClassInstanceRef<Object> = jvm.get_field(&entry, "java/util/HashMap$Entry", "key", "Ljava/lang/Object;").await?;
295                if Self::keys_equal(jvm, &key, &entry_key).await? {
296                    let old_value: ClassInstanceRef<Object> = jvm.get_field(&entry, "java/util/HashMap$Entry", "value", "Ljava/lang/Object;").await?;
297                    jvm.put_field(&mut entry, "java/util/HashMap$Entry", "value", "Ljava/lang/Object;", value)
298                        .await?;
299                    let _: () = jvm
300                        .invoke_virtual(&entry, "java/util/HashMap$Entry", "onAccess", "(Ljava/util/HashMap;)V", (this.clone(),))
301                        .await?;
302                    return Ok(old_value);
303                }
304            }
305
306            entry = jvm
307                .get_field(&entry, "java/util/HashMap$Entry", "next", "Ljava/util/HashMap$Entry;")
308                .await?;
309        }
310
311        let _: () = jvm
312            .invoke_virtual(
313                &this,
314                "java/util/HashMap",
315                "insertNewEntry",
316                "(ILjava/lang/Object;Ljava/lang/Object;I)V",
317                (key_hash, key, value, bucket_index as i32),
318            )
319            .await?;
320
321        Ok(None.into())
322    }
323
324    async fn put_all(jvm: &Jvm, _: &mut RuntimeContext, this: ClassInstanceRef<Self>, map: ClassInstanceRef<Object>) -> Result<()> {
325        tracing::debug!("java.util.HashMap::putAll({this:?}, {map:?})");
326
327        jvm.invoke_special(&this, "java/util/AbstractMap", "putAll", "(Ljava/util/Map;)V", (map,))
328            .await
329    }
330
331    async fn remove(
332        jvm: &Jvm,
333        _: &mut RuntimeContext,
334        mut this: ClassInstanceRef<Self>,
335        key: ClassInstanceRef<Object>,
336    ) -> Result<ClassInstanceRef<Object>> {
337        tracing::debug!("java.util.HashMap::remove({this:?}, {key:?})");
338
339        let key_hash = Self::object_hash_or_zero(jvm, &key).await?;
340        let mut table: ClassInstanceRef<Array<HashMapEntry>> =
341            jvm.get_field(&this, "java/util/HashMap", "table", "[Ljava/util/HashMap$Entry;").await?;
342        let table_len = jvm.array_length(&table).await?;
343        if table_len == 0 {
344            return Ok(None.into());
345        }
346        let bucket_index = Self::bucket_index(key_hash, table_len);
347
348        let mut previous: ClassInstanceRef<HashMapEntry> = None.into();
349        let mut entry = Self::load_bucket(jvm, &table, bucket_index).await?;
350        while !entry.is_null() {
351            let entry_hash: i32 = jvm.get_field(&entry, "java/util/HashMap$Entry", "hash", "I").await?;
352            if entry_hash == key_hash {
353                let entry_key: ClassInstanceRef<Object> = jvm.get_field(&entry, "java/util/HashMap$Entry", "key", "Ljava/lang/Object;").await?;
354                if Self::keys_equal(jvm, &key, &entry_key).await? {
355                    let next: ClassInstanceRef<HashMapEntry> = jvm
356                        .get_field(&entry, "java/util/HashMap$Entry", "next", "Ljava/util/HashMap$Entry;")
357                        .await?;
358                    if previous.is_null() {
359                        jvm.store_array(&mut table, bucket_index, core::iter::once(next.clone())).await?;
360                    } else {
361                        jvm.put_field(
362                            &mut previous,
363                            "java/util/HashMap$Entry",
364                            "next",
365                            "Ljava/util/HashMap$Entry;",
366                            next.clone(),
367                        )
368                        .await?;
369                    }
370
371                    let old_value: ClassInstanceRef<Object> = jvm.get_field(&entry, "java/util/HashMap$Entry", "value", "Ljava/lang/Object;").await?;
372                    let _: () = jvm
373                        .invoke_virtual(&entry, "java/util/HashMap$Entry", "onRemoval", "(Ljava/util/HashMap;)V", (this.clone(),))
374                        .await?;
375                    let null_entry: ClassInstanceRef<HashMapEntry> = None.into();
376                    jvm.put_field(&mut entry, "java/util/HashMap$Entry", "next", "Ljava/util/HashMap$Entry;", null_entry)
377                        .await?;
378
379                    let size: i32 = jvm.get_field(&this, "java/util/HashMap", "size", "I").await?;
380                    jvm.put_field(&mut this, "java/util/HashMap", "size", "I", size - 1).await?;
381                    let mod_count: i32 = jvm.get_field(&this, "java/util/HashMap", "modCount", "I").await?;
382                    jvm.put_field(&mut this, "java/util/HashMap", "modCount", "I", mod_count.wrapping_add(1))
383                        .await?;
384
385                    return Ok(old_value);
386                }
387            }
388
389            previous = entry;
390            entry = jvm
391                .get_field(&previous, "java/util/HashMap$Entry", "next", "Ljava/util/HashMap$Entry;")
392                .await?;
393        }
394
395        Ok(None.into())
396    }
397
398    async fn clear(jvm: &Jvm, _: &mut RuntimeContext, mut this: ClassInstanceRef<Self>) -> Result<()> {
399        tracing::debug!("java.util.HashMap::clear({this:?})");
400
401        let mut table: ClassInstanceRef<Array<HashMapEntry>> =
402            jvm.get_field(&this, "java/util/HashMap", "table", "[Ljava/util/HashMap$Entry;").await?;
403        let table_len = jvm.array_length(&table).await?;
404        if table_len > 0 {
405            let nulls: Vec<ClassInstanceRef<HashMapEntry>> = (0..table_len).map(|_| None.into()).collect();
406            jvm.store_array(&mut table, 0, nulls).await?;
407        }
408        jvm.put_field(&mut this, "java/util/HashMap", "size", "I", 0).await?;
409        let mod_count: i32 = jvm.get_field(&this, "java/util/HashMap", "modCount", "I").await?;
410        jvm.put_field(&mut this, "java/util/HashMap", "modCount", "I", mod_count.wrapping_add(1))
411            .await?;
412
413        Ok(())
414    }
415
416    async fn initialize_map(_: &Jvm, _: &mut RuntimeContext, _: ClassInstanceRef<Self>) -> Result<()> {
417        Ok(())
418    }
419
420    async fn store_new_entry(
421        jvm: &Jvm,
422        _: &mut RuntimeContext,
423        mut this: ClassInstanceRef<Self>,
424        hash: i32,
425        key: ClassInstanceRef<Object>,
426        value: ClassInstanceRef<Object>,
427        bucket_index: i32,
428    ) -> Result<()> {
429        let mut table: ClassInstanceRef<Array<HashMapEntry>> =
430            jvm.get_field(&this, "java/util/HashMap", "table", "[Ljava/util/HashMap$Entry;").await?;
431        let existing = Self::load_bucket(jvm, &table, bucket_index as usize).await?;
432        let entry: ClassInstanceRef<HashMapEntry> = jvm
433            .new_class(
434                "java/util/HashMap$Entry",
435                "(ILjava/lang/Object;Ljava/lang/Object;Ljava/util/HashMap$Entry;)V",
436                (hash, key, value, existing),
437            )
438            .await?
439            .into();
440        jvm.store_array(&mut table, bucket_index as usize, core::iter::once(entry)).await?;
441        let size: i32 = jvm.get_field(&this, "java/util/HashMap", "size", "I").await?;
442        jvm.put_field(&mut this, "java/util/HashMap", "size", "I", size + 1).await
443    }
444
445    async fn insert_new_entry(
446        jvm: &Jvm,
447        _: &mut RuntimeContext,
448        mut this: ClassInstanceRef<Self>,
449        hash: i32,
450        key: ClassInstanceRef<Object>,
451        value: ClassInstanceRef<Object>,
452        bucket_index: i32,
453    ) -> Result<()> {
454        let size: i32 = jvm.get_field(&this, "java/util/HashMap", "size", "I").await?;
455        let mod_count: i32 = jvm.get_field(&this, "java/util/HashMap", "modCount", "I").await?;
456        jvm.put_field(&mut this, "java/util/HashMap", "modCount", "I", mod_count.wrapping_add(1))
457            .await?;
458        let _: () = jvm
459            .invoke_virtual(
460                &this,
461                "java/util/HashMap",
462                "storeNewEntry",
463                "(ILjava/lang/Object;Ljava/lang/Object;I)V",
464                (hash, key, value, bucket_index),
465            )
466            .await?;
467        let threshold: i32 = jvm.get_field(&this, "java/util/HashMap", "threshold", "I").await?;
468        if size >= threshold {
469            Self::rehash(jvm, &mut this).await?;
470        }
471
472        Ok(())
473    }
474
475    async fn key_iterator(jvm: &Jvm, _: &mut RuntimeContext, this: ClassInstanceRef<Self>) -> Result<ClassInstanceRef<Object>> {
476        let snapshot = Self::keys_snapshot(jvm, &this).await?;
477
478        Ok(jvm
479            .new_class("java/util/HashMap$KeyIterator", "([Ljava/lang/Object;)V", (snapshot,))
480            .await?
481            .into())
482    }
483
484    async fn value_iterator(jvm: &Jvm, _: &mut RuntimeContext, this: ClassInstanceRef<Self>) -> Result<ClassInstanceRef<Object>> {
485        let snapshot = Self::values_snapshot(jvm, &this).await?;
486
487        Ok(jvm
488            .new_class("java/util/HashMap$ValueIterator", "([Ljava/lang/Object;)V", (snapshot,))
489            .await?
490            .into())
491    }
492
493    async fn entry_iterator(jvm: &Jvm, _: &mut RuntimeContext, this: ClassInstanceRef<Self>) -> Result<ClassInstanceRef<Object>> {
494        let snapshot = Self::entries_snapshot(jvm, &this).await?;
495
496        Ok(jvm
497            .new_class("java/util/HashMap$EntryIterator", "([Ljava/lang/Object;)V", (snapshot,))
498            .await?
499            .into())
500    }
501
502    pub(super) async fn find_entry(
503        jvm: &Jvm,
504        this: &ClassInstanceRef<Self>,
505        key: &ClassInstanceRef<Object>,
506    ) -> Result<ClassInstanceRef<HashMapEntry>> {
507        let key_hash = Self::object_hash_or_zero(jvm, key).await?;
508        let table: ClassInstanceRef<Array<HashMapEntry>> = jvm.get_field(this, "java/util/HashMap", "table", "[Ljava/util/HashMap$Entry;").await?;
509        let table_len = jvm.array_length(&table).await?;
510        if table_len == 0 {
511            return Ok(None.into());
512        }
513        let bucket_index = Self::bucket_index(key_hash, table_len);
514
515        let mut entry = Self::load_bucket(jvm, &table, bucket_index).await?;
516        while !entry.is_null() {
517            let entry_hash: i32 = jvm.get_field(&entry, "java/util/HashMap$Entry", "hash", "I").await?;
518            if entry_hash == key_hash {
519                let entry_key: ClassInstanceRef<Object> = jvm.get_field(&entry, "java/util/HashMap$Entry", "key", "Ljava/lang/Object;").await?;
520                if Self::keys_equal(jvm, key, &entry_key).await? {
521                    return Ok(entry);
522                }
523            }
524
525            entry = jvm
526                .get_field(&entry, "java/util/HashMap$Entry", "next", "Ljava/util/HashMap$Entry;")
527                .await?;
528        }
529
530        Ok(None.into())
531    }
532
533    pub(super) async fn put_for_create(
534        jvm: &Jvm,
535        this: &mut ClassInstanceRef<Self>,
536        key: ClassInstanceRef<Object>,
537        value: ClassInstanceRef<Object>,
538    ) -> Result<()> {
539        let hash = Self::object_hash_or_zero(jvm, &key).await?;
540        Self::ensure_table_for_insert(jvm, this).await?;
541        let table: ClassInstanceRef<Array<HashMapEntry>> = jvm.get_field(this, "java/util/HashMap", "table", "[Ljava/util/HashMap$Entry;").await?;
542        let bucket_index = Self::bucket_index(hash, jvm.array_length(&table).await?);
543        jvm.invoke_virtual(
544            this,
545            "java/util/HashMap",
546            "storeNewEntry",
547            "(ILjava/lang/Object;Ljava/lang/Object;I)V",
548            (hash, key, value, bucket_index as i32),
549        )
550        .await
551    }
552
553    async fn ensure_table_for_insert(jvm: &Jvm, this: &mut ClassInstanceRef<Self>) -> Result<()> {
554        let table: ClassInstanceRef<Array<HashMapEntry>> = jvm.get_field(this, "java/util/HashMap", "table", "[Ljava/util/HashMap$Entry;").await?;
555        if jvm.array_length(&table).await? > 0 {
556            return Ok(());
557        }
558
559        let new_capacity = 1;
560        let new_table: ClassInstanceRef<Array<HashMapEntry>> = jvm.instantiate_array("Ljava/util/HashMap$Entry;", new_capacity).await?.into();
561        jvm.put_field(this, "java/util/HashMap", "table", "[Ljava/util/HashMap$Entry;", new_table)
562            .await?;
563        let load_factor: f32 = jvm.get_field(this, "java/util/HashMap", "loadFactor", "F").await?;
564        jvm.put_field(
565            this,
566            "java/util/HashMap",
567            "threshold",
568            "I",
569            Self::threshold_for_capacity(new_capacity as i32, load_factor),
570        )
571        .await?;
572
573        Ok(())
574    }
575
576    pub(super) async fn rehash(jvm: &Jvm, this: &mut ClassInstanceRef<Self>) -> Result<()> {
577        let old_table: ClassInstanceRef<Array<HashMapEntry>> =
578            jvm.get_field(this, "java/util/HashMap", "table", "[Ljava/util/HashMap$Entry;").await?;
579        let old_capacity = jvm.array_length(&old_table).await?;
580        let new_capacity = old_capacity * 2 + 1;
581
582        let mut new_table: ClassInstanceRef<Array<HashMapEntry>> = jvm.instantiate_array("Ljava/util/HashMap$Entry;", new_capacity).await?.into();
583        for bucket_index in 0..old_capacity {
584            let mut entry = Self::load_bucket(jvm, &old_table, bucket_index).await?;
585            while !entry.is_null() {
586                let next: ClassInstanceRef<HashMapEntry> = jvm
587                    .get_field(&entry, "java/util/HashMap$Entry", "next", "Ljava/util/HashMap$Entry;")
588                    .await?;
589                let entry_hash: i32 = jvm.get_field(&entry, "java/util/HashMap$Entry", "hash", "I").await?;
590                let new_index = Self::bucket_index(entry_hash, new_capacity);
591
592                let existing = Self::load_bucket(jvm, &new_table, new_index).await?;
593                jvm.put_field(&mut entry, "java/util/HashMap$Entry", "next", "Ljava/util/HashMap$Entry;", existing)
594                    .await?;
595                jvm.store_array(&mut new_table, new_index, core::iter::once(entry)).await?;
596
597                entry = next;
598            }
599        }
600
601        jvm.put_field(this, "java/util/HashMap", "table", "[Ljava/util/HashMap$Entry;", new_table)
602            .await?;
603        let load_factor: f32 = jvm.get_field(this, "java/util/HashMap", "loadFactor", "F").await?;
604        jvm.put_field(
605            this,
606            "java/util/HashMap",
607            "threshold",
608            "I",
609            Self::threshold_for_capacity(new_capacity as i32, load_factor),
610        )
611        .await?;
612
613        Ok(())
614    }
615
616    async fn load_bucket(jvm: &Jvm, table: &ClassInstanceRef<Array<HashMapEntry>>, bucket_index: usize) -> Result<ClassInstanceRef<HashMapEntry>> {
617        Ok(jvm.load_array(table, bucket_index, 1).await?.remove(0))
618    }
619
620    async fn object_equals(jvm: &Jvm, left: &ClassInstanceRef<Object>, right: &ClassInstanceRef<Object>) -> Result<bool> {
621        if left.is_null() {
622            return Ok(right.is_null());
623        }
624
625        if right.is_null() {
626            return Ok(false);
627        }
628
629        jvm.invoke_virtual(left, "java/lang/Object", "equals", "(Ljava/lang/Object;)Z", (right.clone(),))
630            .await
631    }
632
633    async fn keys_equal(jvm: &Jvm, query_key: &ClassInstanceRef<Object>, stored_key: &ClassInstanceRef<Object>) -> Result<bool> {
634        if query_key.is_null() {
635            return Ok(stored_key.is_null());
636        }
637
638        if stored_key.is_null() {
639            return Ok(false);
640        }
641
642        jvm.invoke_virtual(query_key, "java/lang/Object", "equals", "(Ljava/lang/Object;)Z", (stored_key.clone(),))
643            .await
644    }
645
646    async fn object_hash_or_zero(jvm: &Jvm, value: &ClassInstanceRef<Object>) -> Result<i32> {
647        if value.is_null() {
648            return Ok(0);
649        }
650
651        jvm.invoke_virtual(value, "java/lang/Object", "hashCode", "()I", ()).await
652    }
653
654    fn bucket_index(hash: i32, table_len: usize) -> usize {
655        (hash & 0x7FFFFFFF) as usize % table_len
656    }
657
658    async fn snapshot_entries(jvm: &Jvm, this: &ClassInstanceRef<Self>, kind: SnapshotKind) -> Result<ClassInstanceRef<Array<Object>>> {
659        let table: ClassInstanceRef<Array<HashMapEntry>> = jvm.get_field(this, "java/util/HashMap", "table", "[Ljava/util/HashMap$Entry;").await?;
660        let table_len = jvm.array_length(&table).await?;
661        let size: i32 = jvm.get_field(this, "java/util/HashMap", "size", "I").await?;
662        let mut elements: Vec<ClassInstanceRef<Object>> = Vec::with_capacity(size as usize);
663
664        for bucket_index in 0..table_len {
665            let mut entry = Self::load_bucket(jvm, &table, bucket_index).await?;
666            while !entry.is_null() {
667                let element = match kind {
668                    SnapshotKind::Keys => jvm.get_field(&entry, "java/util/HashMap$Entry", "key", "Ljava/lang/Object;").await?,
669                    SnapshotKind::Values => jvm.get_field(&entry, "java/util/HashMap$Entry", "value", "Ljava/lang/Object;").await?,
670                    SnapshotKind::Entries => ClassInstanceRef::new(entry.clone().instance),
671                };
672                elements.push(element);
673
674                entry = jvm
675                    .get_field(&entry, "java/util/HashMap$Entry", "next", "Ljava/util/HashMap$Entry;")
676                    .await?;
677            }
678        }
679
680        let mut snapshot: ClassInstanceRef<Array<Object>> = jvm.instantiate_array("Ljava/lang/Object;", elements.len()).await?.into();
681        if !elements.is_empty() {
682            jvm.store_array(&mut snapshot, 0, elements).await?;
683        }
684
685        Ok(snapshot)
686    }
687
688    fn threshold_for_capacity(capacity: i32, load_factor: f32) -> i32 {
689        if capacity <= 0 { 0 } else { (capacity as f32 * load_factor) as i32 }
690    }
691}
692
693#[derive(Copy, Clone)]
694enum SnapshotKind {
695    Keys,
696    Values,
697    Entries,
698}