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