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 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 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 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 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 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 89 void ufdt_prop_dict_destruct(struct ufdt_prop_dict *dict) { 90 if (dict == NULL) return; 91 92 dto_free(dict->props); 93 } 94 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 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 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
