| |
| #include "libufdt.h" |
| #include "ufdt_util.h" |
| |
| /* |
| * BEGIN of Hash table internal implementations. |
| */ |
| |
| #define DICT_LIMIT_NUM 2 |
| #define DICT_LIMIT_DEN 3 |
| |
| static bool _ufdt_node_dict_is_too_full(struct ufdt_node_dict *dict) { |
| /* |
| * We say a dict is too full if it's DICT_LIMIT_NUM / DICT_LIMIT_DEN full. |
| */ |
| if (dict->num_used * DICT_LIMIT_DEN > dict->mem_size * DICT_LIMIT_NUM) |
| return true; |
| return false; |
| } |
| |
| /* |
| * If collision happened, use linear probing to find idx in the hash table. |
| */ |
| static int _ufdt_node_dict_find_index_by_name_len(struct ufdt_node **hash_table, |
| int size, const char *name, |
| int len) { |
| if (!name || !size) return -1; |
| /* |
| * All size should be 2^k for some k |
| */ |
| int hsh = get_hash_len(name, len); |
| int idx = hsh & (size - 1); |
| for (int cnt = 0; cnt < size; ++cnt) { |
| if (hash_table[idx] == NULL) return idx; |
| if (node_name_eq(hash_table[idx], name, len) == 1) return idx; |
| ++idx; |
| idx &= (size - 1); |
| } |
| return -1; |
| } |
| |
| static int _ufdt_node_dict_find_index_by_name(struct ufdt_node **hash_table, |
| int size, const char *name) { |
| return _ufdt_node_dict_find_index_by_name_len(hash_table, size, name, |
| dto_strlen(name)); |
| } |
| |
| static int _ufdt_node_dict_find_index_in_ht(struct ufdt_node **hash_table, |
| int size, struct ufdt_node *x) { |
| if (x == NULL) return -1; |
| return _ufdt_node_dict_find_index_by_name(hash_table, size, name_of(x)); |
| } |
| |
| /* |
| * END of Hash table internal implementations. |
| */ |
| |
| /* |
| * ufdt_node_dict methods. |
| */ |
| |
| struct ufdt_node_dict ufdt_node_dict_construct() { |
| struct ufdt_node_dict res; |
| res.mem_size = DTNL_INIT_SZ; |
| res.num_used = 0; |
| res.nodes = dto_malloc(DTNL_INIT_SZ * sizeof(struct ufdt_node *)); |
| if (res.nodes == NULL) { |
| res.mem_size = 0; |
| return res; |
| } |
| dto_memset(res.nodes, 0, DTNL_INIT_SZ * sizeof(struct ufdt_node *)); |
| return res; |
| } |
| |
| void ufdt_node_dict_destruct(struct ufdt_node_dict *dict) { |
| if (dict == NULL) return; |
| dto_free(dict->nodes); |
| dict->mem_size = dict->num_used = 0; |
| } |
| |
| static int ufdt_node_dict_resize(struct ufdt_node_dict *dict) { |
| if (dict == NULL) return -1; |
| |
| int new_size = dict->mem_size << 1; |
| |
| struct ufdt_node **new_nodes = |
| dto_malloc(new_size * sizeof(struct ufdt_node *)); |
| |
| dto_memset(new_nodes, 0, new_size * sizeof(struct ufdt_node *)); |
| |
| for (int i = 0; i < dict->mem_size; i++) { |
| struct ufdt_node *node = dict->nodes[i]; |
| if (node == NULL) continue; |
| int idx = _ufdt_node_dict_find_index_in_ht(new_nodes, new_size, node); |
| if (idx < 0) { |
| dto_error( |
| "failed to find new index in ufdt_node_dict resize for entry :%s:\n", |
| name_of(node)); |
| dto_free(new_nodes); |
| return -1; |
| } |
| new_nodes[idx] = node; |
| } |
| |
| dto_free(dict->nodes); |
| |
| dict->mem_size = new_size; |
| dict->nodes = new_nodes; |
| return 0; |
| } |
| |
| int ufdt_node_dict_add(struct ufdt_node_dict *dict, struct ufdt_node *node) { |
| if (node == NULL) return -1; |
| if (dict == NULL) return -1; |
| |
| int idx = _ufdt_node_dict_find_index_in_ht(dict->nodes, dict->mem_size, node); |
| if (idx < 0) { |
| dto_error("failed to find new index in ufdt_node_dict add for entry :%s:\n", |
| name_of(node)); |
| return -1; |
| } |
| |
| if (dict->nodes[idx] == NULL) ++dict->num_used; |
| dict->nodes[idx] = node; |
| |
| /* |
| * When the hash table is too full, double the size and rehashing. |
| */ |
| int err = 0; |
| if (_ufdt_node_dict_is_too_full(dict)) { |
| err = ufdt_node_dict_resize(dict); |
| } |
| |
| return err; |
| } |
| |
| /* |
| * BEGIN of ufdt_dict searching related methods. |
| */ |
| |
| /* |
| * return a pointer to the hash table entry |
| */ |
| struct ufdt_node **ufdt_node_dict_find_len(struct ufdt_node_dict *dict, |
| const char *name, int len) { |
| if (dict == NULL) return NULL; |
| int idx = _ufdt_node_dict_find_index_by_name_len(dict->nodes, dict->mem_size, |
| name, len); |
| if (idx < 0) return NULL; |
| if (dict->nodes[idx] == NULL) return NULL; |
| return dict->nodes + idx; |
| } |
| |
| struct ufdt_node **ufdt_node_dict_find(struct ufdt_node_dict *dict, |
| const char *name) { |
| return ufdt_node_dict_find_len(dict, name, dto_strlen(name)); |
| } |
| |
| struct ufdt_node *ufdt_node_dict_find_node_len(struct ufdt_node_dict *dict, |
| const char *name, int len) { |
| struct ufdt_node **res = ufdt_node_dict_find_len(dict, name, len); |
| if (res == NULL) return NULL; |
| return *res; |
| } |
| |
| struct ufdt_node *ufdt_node_dict_find_node(struct ufdt_node_dict *dict, |
| const char *name) { |
| return ufdt_node_dict_find_node_len(dict, name, dto_strlen(name)); |
| } |
| |
| /* |
| * END of ufdt_dict searching related methods. |
| */ |
| |
| void ufdt_node_dict_print(struct ufdt_node_dict *dict) { |
| struct ufdt_node **it; |
| for_each(it, dict) dto_print("%ld -> %s\n", it - dict->nodes, name_of(*it)); |
| } |