[PATCH] libdl: Sort object file symbols and use a binary search to find

[chrisj at rtems.org]

From: Chris Johns <chrisj at rtems.org>

- Replace the linear object file symbol search with a binary search.
- Sort the object file symbols after loading.

Closes #3748
---
 cpukit/include/rtems/rtl/rtl-sym.h |  9 ++++++
 cpukit/libdl/rtl-obj.c             |  6 +++-
 cpukit/libdl/rtl-sym.c             | 49 +++++++++++++++++++++++++-----
 3 files changed, 55 insertions(+), 9 deletions(-)

diff --git a/cpukit/include/rtems/rtl/rtl-sym.h b/cpukit/include/rtems/rtl/rtl-sym.h
index aff9339ea1..07cad4cab6 100644
--- a/cpukit/include/rtems/rtl/rtl-sym.h
+++ b/cpukit/include/rtems/rtl/rtl-sym.h
@@ -96,6 +96,15 @@ bool rtems_rtl_symbol_global_add (rtems_rtl_obj*       obj,
  */
 rtems_rtl_obj_sym* rtems_rtl_symbol_global_find (const char* name);
 
+/**
+ * Sort an object file's local and global symbol table. This needs to
+ * be done before calling @ref rtems_rtl_symbol_obj_find as it
+ * performs a binary search on the tables.
+ *
+ * @param obj The object file to sort.
+ */
+void rtems_rtl_symbol_obj_sort (rtems_rtl_obj* obj);
+
 /**
  * Find a symbol given the symbol label in the local object file.
  *
diff --git a/cpukit/libdl/rtl-obj.c b/cpukit/libdl/rtl-obj.c
index 9acb6f3943..1683ec1c6d 100644
--- a/cpukit/libdl/rtl-obj.c
+++ b/cpukit/libdl/rtl-obj.c
@@ -914,7 +914,11 @@ rtems_rtl_obj_load_symbols (rtems_rtl_obj*             obj,
                             void*                      data)
 {
   uint32_t mask = RTEMS_RTL_OBJ_SECT_SYM;
-  return rtems_rtl_obj_section_handler (mask, obj, fd, handler, data);
+  bool     ok;
+  ok = rtems_rtl_obj_section_handler (mask, obj, fd, handler, data);
+  if (ok)
+    rtems_rtl_symbol_obj_sort (obj);
+  return ok;
 }
 
 static int
diff --git a/cpukit/libdl/rtl-sym.c b/cpukit/libdl/rtl-sym.c
index c27f2ee676..9dd891525b 100644
--- a/cpukit/libdl/rtl-sym.c
+++ b/cpukit/libdl/rtl-sym.c
@@ -200,26 +200,59 @@ rtems_rtl_symbol_global_find (const char* name)
   return NULL;
 }
 
+static int
+rtems_rtl_symbol_obj_compare (const void* a, const void* b)
+{
+  const rtems_rtl_obj_sym* sa;
+  const rtems_rtl_obj_sym* sb;
+  sa = (const rtems_rtl_obj_sym*) a;
+  sb = (const rtems_rtl_obj_sym*) b;
+  return strcmp (sa->name, sb->name);
+}
+
+void
+rtems_rtl_symbol_obj_sort (rtems_rtl_obj* obj)
+{
+  qsort (obj->local_table,
+         obj->local_syms,
+         sizeof (rtems_rtl_obj_sym),
+         rtems_rtl_symbol_obj_compare);
+  qsort (obj->global_table,
+         obj->global_syms,
+         sizeof (rtems_rtl_obj_sym),
+         rtems_rtl_symbol_obj_compare);
+}
+
 rtems_rtl_obj_sym*
 rtems_rtl_symbol_obj_find (rtems_rtl_obj* obj, const char* name)
 {
-  rtems_rtl_obj_sym* sym;
-  size_t             s;
   /*
    * Check the object file's symbols first. If not found search the
    * global symbol table.
    */
   if (obj->local_syms)
   {
-    for (s = 0, sym = obj->local_table; s < obj->local_syms; ++s, ++sym)
-      if (strcmp (name, sym->name) == 0)
-        return sym;
+    rtems_rtl_obj_sym* match;
+    rtems_rtl_obj_sym  key = { 0 };
+    key.name = name;
+    match = bsearch (&key, obj->local_table,
+                     obj->local_syms,
+                     sizeof (rtems_rtl_obj_sym),
+                     rtems_rtl_symbol_obj_compare);
+    if (match != NULL)
+      return match;
   }
   if (obj->global_syms)
   {
-    for (s = 0, sym = obj->global_table; s < obj->global_syms; ++s, ++sym)
-      if (strcmp (name, sym->name) == 0)
-        return sym;
+    rtems_rtl_obj_sym* match;
+    rtems_rtl_obj_sym  key = { 0 };
+    key.name = name;
+    match = bsearch (&key, obj->global_table,
+                     obj->global_syms,
+                     sizeof (rtems_rtl_obj_sym),
+                     rtems_rtl_symbol_obj_compare);
+    if (match != NULL)
+      return match;
   }
   return rtems_rtl_symbol_global_find (name);
 }
-- 
2.19.1