Faster ndxes_of_sym_name

ndxes_of_sym_name used to have an O(s^2) complexity where s was the number
of symbols in the ELF file. It has now been reduced to an O(s*ln(s)) by
pre-computing the sets of symbols corresponding to each normalized symbol
name.

git-svn-id: https://yquem.inria.fr/compcert/svn/compcert/trunk@1875 fca1b0fc-160b-0410-b1d3-a4f43f01ea2e

1 files changed, 9 insertions, 12 deletions

diff --git a/checklink/ELF_utils.ml b/checklink/ELF_utils.ml
index d5c205a..5244dc8 100644
--- a/checklink/ELF_utils.ml
+++ b/checklink/ELF_utils.ml
@@ -65,19 +65,16 @@ let strip_mangling (s: string): string =
   with Not_found -> s
 
 (**
-   Returns the index of the first symbol matching the specified name, if it
-   exists.
+   Returns the list of all symbols matching the specified name.
 *)
-let ndx_of_sym_name (e: elf) (name: string): int option =
-  array_exists
-    (fun x -> strip_versioning x.st_name = strip_mangling name)
-    e.e_symtab
+let ndxes_of_sym_name (e: elf) (name: string): int list =
+  try StringMap.find (strip_mangling name) e.e_syms_by_name with Not_found -> []
 
 (**
-   Returns the list of all symbols matching the specified name.
+   Returns the index of the first symbol matching the specified name, if it
+   exists.
 *)
-let ndxes_of_sym_name (e: elf) (name: string): int list =
-  List.map fst
-    (List.filter
-       (fun (_, x) -> strip_versioning x.st_name = strip_mangling name)
-       (Array.to_list (Array.mapi (fun a b -> (a, b)) e.e_symtab)))
+let ndx_of_sym_name (e: elf) (name: string): int option =
+  match ndxes_of_sym_name e name with
+  | [] -> None
+  | h::_ -> Some(h)