1 /*
2  * Copyright (C) 2016 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #include "ufdt_prop_dict.h"
18 
19 #include "libfdt.h"
20 
21 #include "libufdt_sysdeps.h"
22 
23 #define UFDT_PROP_DICT_INIT_SZ 4
24 
25 /* Empirical values for hash functions. */
26 #define HASH_BASE 13131
27 
28 #define DICT_LIMIT_NUM 2
29 #define DICT_LIMIT_DEN 3
30 
_ufdt_prop_dict_str_hash(const char * str)31 static int _ufdt_prop_dict_str_hash(const char *str) {
32   int res = 0;
33 
34   for (; *str != '\0'; str++) {
35     res *= HASH_BASE;
36     res += *str;
37   }
38 
39   return res;
40 }
41 
_ufdt_prop_dict_find_index_by_name(const struct ufdt_prop_dict * dict,const char * name)42 static const struct fdt_property **_ufdt_prop_dict_find_index_by_name(
43     const struct ufdt_prop_dict *dict, const char *name) {
44   /* size should be 2^k for some k */
45   int hash = _ufdt_prop_dict_str_hash(name);
46   int size = dict->mem_size;
47   int idx = hash & (size - 1);
48   /* If collision, use linear probing to find idx in the hash table */
49   for (int i = 0; i < size; i++) {
50     const struct fdt_property **prop_ptr = &dict->props[idx];
51     const struct fdt_property *prop = *prop_ptr;
52     if (prop == NULL) return prop_ptr;
53 
54     const char *prop_name = fdt_string(dict->fdtp, fdt32_to_cpu(prop->nameoff));
55     if (dto_strcmp(prop_name, name) == 0) return prop_ptr;
56 
57     idx = (idx + 1) & (size - 1);
58   }
59   return NULL;
60 }
61 
_ufdt_prop_dict_find_index(struct ufdt_prop_dict * dict,const struct fdt_property * prop)62 static const struct fdt_property **_ufdt_prop_dict_find_index(
63     struct ufdt_prop_dict *dict, const struct fdt_property *prop) {
64   const char *name = fdt_string(dict->fdtp, fdt32_to_cpu(prop->nameoff));
65 
66   return _ufdt_prop_dict_find_index_by_name(dict, name);
67 }
68 
_ufdt_prop_dict_construct_int(struct ufdt_prop_dict * dict,void * fdtp,int size)69 int _ufdt_prop_dict_construct_int(struct ufdt_prop_dict *dict, void *fdtp,
70                                   int size) {
71   const size_t entry_size = sizeof(const struct fdt_property *);
72   const struct fdt_property **props =
73       (const struct fdt_property **)dto_malloc(size * entry_size);
74   if (props == NULL) return -1;
75   dto_memset(props, 0, size * entry_size);
76 
77   dict->mem_size = size;
78   dict->num_used = 0;
79   dict->fdtp = fdtp;
80   dict->props = props;
81 
82   return 0;
83 }
84 
ufdt_prop_dict_construct(struct ufdt_prop_dict * dict,void * fdtp)85 int ufdt_prop_dict_construct(struct ufdt_prop_dict *dict, void *fdtp) {
86   return _ufdt_prop_dict_construct_int(dict, fdtp, UFDT_PROP_DICT_INIT_SZ);
87 }
88 
ufdt_prop_dict_destruct(struct ufdt_prop_dict * dict)89 void ufdt_prop_dict_destruct(struct ufdt_prop_dict *dict) {
90   if (dict == NULL) return;
91 
92   dto_free(dict->props);
93 }
94 
_ufdt_prop_dict_enlarge_if_needed(struct ufdt_prop_dict * dict)95 static int _ufdt_prop_dict_enlarge_if_needed(struct ufdt_prop_dict *dict) {
96   if (dict == NULL) return -1;
97 
98   /* Enlarge if the used number over than DICT_LIMIT_NUM / DICT_LIMIT_DEN */
99   if (dict->num_used * DICT_LIMIT_DEN <= dict->mem_size * DICT_LIMIT_NUM) {
100     return 0;
101   }
102 
103   int new_size = dict->mem_size * 2;
104   struct ufdt_prop_dict temp_dict;
105   _ufdt_prop_dict_construct_int(&temp_dict, dict->fdtp, new_size);
106 
107   for (int i = 0; i < dict->mem_size; i++) {
108     const struct fdt_property *prop = dict->props[i];
109     if (prop == NULL) continue;
110     const struct fdt_property **new_prop_ptr =
111         _ufdt_prop_dict_find_index(&temp_dict, prop);
112     if (new_prop_ptr == NULL) {
113       dto_error("ufdt_prop_dict: failed to find new index when enlarging.\n");
114       ufdt_prop_dict_destruct(&temp_dict);
115       return -1;
116     }
117     *new_prop_ptr = prop;
118   }
119 
120   dto_free(dict->props);
121 
122   dict->mem_size = new_size;
123   dict->props = temp_dict.props;
124 
125   return 0;
126 }
127 
ufdt_prop_dict_add(struct ufdt_prop_dict * dict,const struct fdt_property * prop)128 int ufdt_prop_dict_add(struct ufdt_prop_dict *dict,
129                        const struct fdt_property *prop) {
130   const struct fdt_property **prop_ptr = _ufdt_prop_dict_find_index(dict, prop);
131   if (prop_ptr == NULL) {
132     dto_error("ufdt_prop_dict: failed to find new index when adding.\n");
133     return -1;
134   }
135 
136   if (*prop_ptr == NULL) dict->num_used++;
137   *prop_ptr = prop;
138 
139   return _ufdt_prop_dict_enlarge_if_needed(dict);
140 }
141 
ufdt_prop_dict_find(const struct ufdt_prop_dict * dict,const char * name)142 const struct fdt_property *ufdt_prop_dict_find(const struct ufdt_prop_dict *dict,
143                                                const char *name) {
144   const struct fdt_property **prop_ptr =
145       _ufdt_prop_dict_find_index_by_name(dict, name);
146   return prop_ptr ? *prop_ptr : NULL;
147 }
148