commit 3a95372c35fe36f940942dedc85937db4c444caa
author Felipe de A. Mello Pereira <felipeamp@google.com> Thu Mar 02 05:37:36 2023 -0800
committer Copybara-Service <copybara-worker@google.com> Thu Mar 02 05:38:13 2023 -0800
tree 56d1b26c4876960ebdc6e370b1860b41c8e3cdaa
parent 6ed0f6080068adb8bd213b17a56ec5699e5bafa2

Make search for function with given name O(1).

This operation is done in multiple places and currently it is O(N), where N is the total number of items in the IR.

PiperOrigin-RevId: 513510823

rs_bindings_from_cc/ir.rs

diff --git a/rs_bindings_from_cc/ir.rs b/rs_bindings_from_cc/ir.rs
index 859b644..e7fd18e 100644
--- a/rs_bindings_from_cc/ir.rs
+++ b/rs_bindings_from_cc/ir.rs
@@ -106,12 +106,25 @@
             namespace_id_to_number_of_reopened_namespaces.insert(canonical_id, current_count + 1);
         });
 
+    let mut function_name_to_functions = HashMap::<UnqualifiedIdentifier, Vec<Rc<Func>>>::new();
+    flat_ir
+        .items
+        .iter()
+        .filter_map(|item| match item {
+            Item::Func(func) => Some(func),
+            _ => None,
+        })
+        .for_each(|f| {
+            function_name_to_functions.entry(f.name.clone()).or_default().push(f.clone());
+        });
+
     Ok(IR {
         flat_ir,
         item_id_to_item_idx,
         lifetimes,
         namespace_id_to_number_of_reopened_namespaces,
         reopened_namespace_id_to_idx,
+        function_name_to_functions,
     })
 }
 
@@ -769,6 +782,7 @@
     lifetimes: HashMap<LifetimeId, LifetimeName>,
     namespace_id_to_number_of_reopened_namespaces: HashMap<ItemId, usize>,
     reopened_namespace_id_to_idx: HashMap<ItemId, usize>,
+    function_name_to_functions: HashMap<UnqualifiedIdentifier, Vec<Rc<Func>>>,
 }
 
 impl IR {
@@ -924,6 +938,13 @@
     pub fn crate_root_path(&self) -> Option<Rc<str>> {
         self.flat_ir.crate_root_path.clone()
     }
+
+    pub fn get_functions_by_name(
+        &self,
+        function_name: &UnqualifiedIdentifier,
+    ) -> impl Iterator<Item = &Rc<Func>> {
+        self.function_name_to_functions.get(function_name).map_or([].iter(), |v| v.iter())
+    }
 }
 
 #[cfg(test)]

rs_bindings_from_cc/src_code_gen.rs

diff --git a/rs_bindings_from_cc/src_code_gen.rs b/rs_bindings_from_cc/src_code_gen.rs
index ebe975d..6831f19 100644
--- a/rs_bindings_from_cc/src_code_gen.rs
+++ b/rs_bindings_from_cc/src_code_gen.rs
@@ -1160,12 +1160,8 @@
     expected_param_types: Vec<RsTypeKind>,
 ) -> Option<(Ident, ImplKind)> {
     db.ir()
-        // TODO(jeanpierreda): make this O(1) using a hash table lookup.
-        .functions()
-        .filter(|function| {
-            function.name == expected_function_name
-                && generate_func(db, (*function).clone()).ok().flatten().is_some()
-        })
+        .get_functions_by_name(&expected_function_name)
+        .filter(|function| generate_func(db, (*function).clone()).ok().flatten().is_some())
         .find_map(|function| {
             let mut function_param_types = function
                 .params
@@ -1189,12 +1185,10 @@
     should_derive_clone(&record)
         || db
             .ir()
-            // TODO(jeanpierreda): make this O(1) using a hash table lookup.
-            .functions()
+            .get_functions_by_name(&UnqualifiedIdentifier::Constructor)
             .filter(|function| {
-                function.name == UnqualifiedIdentifier::Constructor
                 // __this is always the first parameter of constructors
-                && function.params.len() == 2
+                function.params.len() == 2
             })
             .any(|function| {
                 let mut function_param_types = function
@@ -7041,12 +7035,12 @@
         let ir = ir_from_cc("struct Class {};").unwrap();
 
         let destructor =
-            ir.functions().find(|f| f.name == UnqualifiedIdentifier::Destructor).unwrap();
+            ir.get_functions_by_name(&UnqualifiedIdentifier::Destructor).next().unwrap();
         assert_eq!(thunk_ident(destructor), make_rs_ident("__rust_thunk___ZN5ClassD1Ev"));
 
         let default_constructor = ir
-            .functions()
-            .find(|f| f.name == UnqualifiedIdentifier::Constructor && f.params.len() == 1)
+            .get_functions_by_name(&UnqualifiedIdentifier::Constructor)
+            .find(|f| f.params.len() == 1)
             .unwrap();
         assert_eq!(thunk_ident(default_constructor), make_rs_ident("__rust_thunk___ZN5ClassC1Ev"));
     }