Avoid to re-generate string table from ufdt to fdt

String table contains the strings of all property name in a fdt.

The ufdt_apply_overlay() converts two dtbs from fdt to ufdt,
overlays, and converts merged ufdt to fdt. These operations
shouldn't create new peroperty names, so we can just re-use the
string tables in original dtbs, and just copy them into merged
fdt. This solution can enhance a lot of performance for device
tree overlaying.

To avoid the error that some users could use string offset in
string table, the solution also give a same string offset for
the name properties by ufdt_prop_dict;

Futher, the patch also removed unused header files after
changing algorithm.

Bug: 35255584
Test: ./tests/run_tests.sh
Change-Id: Id422730115531bd20d21117285291bdd860915ff
(cherry picked from commit 1be68ae53e645de1b2ec26140b302fbfcbbb919f)

1 files changed, 131 insertions, 0 deletions

diff --git a/ufdt_prop_dict.c b/ufdt_prop_dict.c
new file mode 100644
index 0000000..93bdfb3
--- /dev/null
+++ b/ufdt_prop_dict.c
@@ -0,0 +1,131 @@
+#include "ufdt_prop_dict.h"
+
+#include "libfdt.h"
+
+#include "libufdt_sysdeps.h"
+
+#define UFDT_PROP_DICT_INIT_SZ 4
+
+/* Empirical values for hash functions. */
+#define HASH_BASE 13131
+
+#define DICT_LIMIT_NUM 2
+#define DICT_LIMIT_DEN 3
+
+static int _ufdt_prop_dict_str_hash(const char *str) {
+  int res = 0;
+
+  for (; *str != '\0'; str++) {
+    res *= HASH_BASE;
+    res += *str;
+  }
+
+  return res;
+}
+
+static const struct fdt_property **_ufdt_prop_dict_find_index_by_name(
+    const struct ufdt_prop_dict *dict, const char *name) {
+  /* size should be 2^k for some k */
+  int hash = _ufdt_prop_dict_str_hash(name);
+  int size = dict->mem_size;
+  int idx = hash & (size - 1);
+  /* If collision, use linear probing to find idx in the hash table */
+  for (int i = 0; i < size; i++) {
+    const struct fdt_property **prop_ptr = &dict->props[idx];
+    const struct fdt_property *prop = *prop_ptr;
+    if (prop == NULL) return prop_ptr;
+
+    const char *prop_name = fdt_string(dict->fdtp, fdt32_to_cpu(prop->nameoff));
+    if (dto_strcmp(prop_name, name) == 0) return prop_ptr;
+
+    idx = (idx + 1) & (size - 1);
+  }
+  return NULL;
+}
+
+static const struct fdt_property **_ufdt_prop_dict_find_index(
+    struct ufdt_prop_dict *dict, const struct fdt_property *prop) {
+  const char *name = fdt_string(dict->fdtp, fdt32_to_cpu(prop->nameoff));
+
+  return _ufdt_prop_dict_find_index_by_name(dict, name);
+}
+
+int _ufdt_prop_dict_construct_int(struct ufdt_prop_dict *dict, void *fdtp,
+                                  int size) {
+  const size_t entry_size = sizeof(const struct fdt_property *);
+  const struct fdt_property **props =
+      (const struct fdt_property **)dto_malloc(size * entry_size);
+  if (props == NULL) return -1;
+  dto_memset(props, 0, size * entry_size);
+
+  dict->mem_size = size;
+  dict->num_used = 0;
+  dict->fdtp = fdtp;
+  dict->props = props;
+
+  return 0;
+}
+
+int ufdt_prop_dict_construct(struct ufdt_prop_dict *dict, void *fdtp) {
+  return _ufdt_prop_dict_construct_int(dict, fdtp, UFDT_PROP_DICT_INIT_SZ);
+}
+
+void ufdt_prop_dict_destruct(struct ufdt_prop_dict *dict) {
+  if (dict == NULL) return;
+
+  dto_free(dict->props);
+}
+
+static int _ufdt_prop_dict_enlarge_if_needed(struct ufdt_prop_dict *dict) {
+  if (dict == NULL) return -1;
+
+  /* Enlarge if the used number over than DICT_LIMIT_NUM / DICT_LIMIT_DEN */
+  if (dict->num_used * DICT_LIMIT_DEN <= dict->mem_size * DICT_LIMIT_NUM) {
+    return 0;
+  }
+
+  int new_size = dict->mem_size * 2;
+  struct ufdt_prop_dict temp_dict;
+  _ufdt_prop_dict_construct_int(&temp_dict, dict->fdtp, new_size);
+
+  for (int i = 0; i < dict->mem_size; i++) {
+    const struct fdt_property *prop = dict->props[i];
+    if (prop == NULL) continue;
+    const struct fdt_property **new_prop_ptr =
+        _ufdt_prop_dict_find_index(&temp_dict, prop);
+    if (new_prop_ptr == NULL) {
+      dto_error("ufdt_prop_dict: failed to find new index when enlarging.\n");
+      ufdt_prop_dict_destruct(&temp_dict);
+      return -1;
+    }
+    *new_prop_ptr = prop;
+  }
+
+  dto_free(dict->props);
+
+  dict->mem_size = new_size;
+  dict->props = temp_dict.props;
+
+  return 0;
+}
+
+int ufdt_prop_dict_add(struct ufdt_prop_dict *dict,
+                       const struct fdt_property *prop) {
+  const struct fdt_property **prop_ptr = _ufdt_prop_dict_find_index(dict, prop);
+  if (prop_ptr == NULL) {
+    dto_error("ufdt_prop_dict: failed to find new index when adding.\n");
+    return -1;
+  }
+
+  if (*prop_ptr == NULL) dict->num_used++;
+  *prop_ptr = prop;
+
+  return _ufdt_prop_dict_enlarge_if_needed(dict);
+}
+
+const struct fdt_property *ufdt_prop_dict_find(const struct ufdt_prop_dict *dict,
+                                               const char *name) {
+  const struct fdt_property **prop_ptr =
+      _ufdt_prop_dict_find_index_by_name(dict, name);
+  return prop_ptr ? *prop_ptr : NULL;
+}