SzuWei Lin | 4f00eda | 2017-04-06 17:12:27 +0800 | [diff] [blame] | 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 | |
SzuWei Lin | 4356876 | 2017-03-30 11:44:54 +0800 | [diff] [blame] | 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 | } |