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 #ifndef LIBUFDT_H 18 #define LIBUFDT_H 19 20 #include "libufdt_sysdeps.h" 21 #include "ufdt_types.h" 22 23 /* 24 * BEGIN of ufdt_node methods 25 */ 26 27 /* 28 * Allocates spaces for new ufdt_node who represents a fdt node at fdt_tag_ptr. 29 * In order to get name pointer, it's neccassary to give the pointer to the 30 * entire fdt it belongs to. 31 * 32 * 33 * @return: a pointer to the newly created ufdt_node or 34 * NULL if dto_malloc failed 35 */ 36 struct ufdt_node *ufdt_node_construct(void *fdtp, fdt32_t *fdt_tag_ptr); 37 38 /* 39 * Frees all nodes in the subtree rooted at *node. 40 */ 41 void ufdt_node_destruct(struct ufdt_node *node); 42 43 /* 44 * Adds the child as a subnode of the parent. 45 * It's been done by add entries in parent->prop_list or node_list depending on 46 * the tag type of child. 47 * 48 * @return: 0 if success 49 * < 0 otherwise 50 * 51 * @Time: O(1) w.h.p. 52 */ 53 int ufdt_node_add_child(struct ufdt_node *parent, struct ufdt_node *child); 54 55 /* BEGIN of FDT_PROP related functions .*/ 56 57 /* 58 * Gets pointer to FDT_PROP subnode of node with name equals to name[0..len-1] 59 * 60 * @return: a pointer to the subnode or 61 * NULL if no such subnode. 62 * 63 * @Time: O(len = length of name) w.h.p. 64 */ 65 struct ufdt_node *ufdt_node_get_property_by_name_len( 66 const struct ufdt_node *node, const char *name, int len); 67 struct ufdt_node *ufdt_node_get_property_by_name(const struct ufdt_node *node, 68 const char *name); 69 70 /* 71 * Gets the pointer to the FDT_PROP node's data in the corresponding fdt. 72 * Also writes the length of such data to *out_len if out_len is not NULL. 73 * 74 * @return: a pointer to some data located in fdt or 75 * NULL if *node is not a FDT_PROP 76 */ 77 char *ufdt_node_get_fdt_prop_data(const struct ufdt_node *node, int *out_len); 78 79 /* 80 * Gets pointer to FDT_PROP node's data in fdt with name equals to 81 * name[0..len-1], which is a subnode of *node. 82 * It's actually a composition of ufdt_node_get_property_by_name and 83 * ufdt_node_get_fdt_prop_data 84 * 85 * @return: a pointer to some data located in fdt or 86 * NULL if no such subnode. 87 * 88 * @Time: O(len = length of name) w.h.p. 89 */ 90 char *ufdt_node_get_fdt_prop_data_by_name_len(const struct ufdt_node *node, 91 const char *name, int len, 92 int *out_len); 93 char *ufdt_node_get_fdt_prop_data_by_name(const struct ufdt_node *node, 94 const char *name, int *out_len); 95 96 /* END of FDT_PROP related functions .*/ 97 98 /* 99 * Gets pointer to FDT_BEGIN_NODE subnode of node with name equals to 100 * name[0..len-1]. 101 * 102 * @return: a pointer to the subnode or 103 * NULL if no such subnode. 104 * 105 * @Time: O(len = length of name) w.h.p. 106 */ 107 108 struct ufdt_node *ufdt_node_get_subnode_by_name_len(const struct ufdt_node *node, 109 const char *name, int len); 110 struct ufdt_node *ufdt_node_get_subnode_by_name(const struct ufdt_node *node, 111 const char *name); 112 113 /* 114 * Gets the pointer to FDT_NODE node whose relative path to *node is 115 * path[0..len-1]. 116 * Note that the relative path doesn't support parent node like: 117 * "../path/to/node". 118 * 119 * @return: a pointer to the node or 120 * NULL if no such node. 121 * 122 * @Time: O(len = length of path) w.h.p. 123 */ 124 struct ufdt_node *ufdt_node_get_node_by_path_len(const struct ufdt_node *node, 125 const char *path, int len); 126 struct ufdt_node *ufdt_node_get_node_by_path(const struct ufdt_node *node, 127 const char *path); 128 129 /* 130 * Gets the phandle value of the node if it has. 131 * 132 * @return: phandle value of that node or 133 * 0 if *node is not FDT_NODE or there's no "phandle"/"linux,phandle" 134 * property. 135 * 136 * @Time: O(1) w.h.p. 137 */ 138 uint32_t ufdt_node_get_phandle(const struct ufdt_node *node); 139 140 /* 141 * END of ufdt_node methods 142 */ 143 144 /* 145 * BEGIN of ufdt methods. 146 */ 147 148 /* 149 * Constructs a ufdt whose base fdt is fdtp. 150 * Note that this function doesn't construct the entire tree. 151 * To get the whole tree please call `fdt_to_ufdt(fdtp, fdt_size)` 152 * 153 * @return: an empty ufdt with base fdtp = fdtp 154 */ 155 struct ufdt *ufdt_construct(void *fdtp); 156 157 /* 158 * Frees the space occupied by the ufdt, including all ufdt_nodes 159 * with static_phandle_table. 160 */ 161 void ufdt_destruct(struct ufdt *tree); 162 163 /* 164 * Add a fdt into this ufdt. 165 * Note that this function just add the given fdtp into this ufdt, 166 * and doesn't create any node. 167 * 168 * @return: 0 if success. 169 */ 170 int ufdt_add_fdt(struct ufdt *tree, void *fdtp); 171 172 /* 173 * Calculate the offset in the string tables of the given string. 174 * All string tables will be concatenated in reversed order. 175 * 176 * @return: The offset is a negative number, base on the end position of 177 * all concatenated string tables 178 * Return 0 if not in any string table. 179 */ 180 int ufdt_get_string_off(const struct ufdt *tree, const char *s); 181 182 /* 183 * Gets the pointer to the ufdt_node in tree with phandle = phandle. 184 * The function do a binary search in tree->phandle_table. 185 * 186 * @return: a pointer to the target ufdt_node 187 * NULL if no ufdt_node has phandle = phandle 188 * 189 * @Time: O(log(# of nodes in tree)) = O(log(size of underlying fdt)) 190 */ 191 struct ufdt_node *ufdt_get_node_by_phandle(struct ufdt *tree, uint32_t phandle); 192 193 /* 194 * Gets the pointer to the ufdt_node in tree with absoulte path = 195 * path[0..len-1]. 196 * Absolute path has form "/path/to/node" or "some_alias/to/node". 197 * In later example, some_alias is a property in "/aliases" with data is a path 198 * to some node X. Then the funcion will return node with relative 199 * path = "to/node" w.r.t. X. 200 * 201 * @return: a pointer to the target ufdt_node or 202 * NULL if such dnt doesn't exist. 203 * 204 * @Time: O(len = length of path) w.h.p. 205 */ 206 struct ufdt_node *ufdt_get_node_by_path_len(struct ufdt *tree, const char *path, 207 int len); 208 struct ufdt_node *ufdt_get_node_by_path(struct ufdt *tree, const char *path); 209 210 /* 211 * END of ufdt methods. 212 */ 213 214 /* 215 * Compares function between 2 nodes, compare by name of each node. 216 * 217 * @return: x < 0 if a's name is lexicographically smaller 218 * x == 0 if a, b has same name 219 * x > 0 if a's name is lexicographically bigger 220 */ 221 int node_cmp(const void *a, const void *b); 222 223 /* 224 * Determines whether node->name equals to name[0..len-1] 225 * 226 * @return: true if they're equal. 227 * false otherwise 228 */ 229 bool node_name_eq(const struct ufdt_node *node, const char *name, int len); 230 231 /* 232 * Merges tree_b into tree_a with tree_b has all nodes except root disappeared. 233 * Overwrite property in tree_a if there's one with same name in tree_b. 234 * Otherwise add the property to tree_a. 235 * For subnodes with the same name, recursively run this function. 236 * 237 * Ex: 238 * tree_a : ta { 239 * b = "b"; 240 * c = "c"; 241 * d { 242 * e = "g"; 243 * }; 244 * }; 245 * 246 * tree_b : tb { 247 * c = "C"; 248 * g = "G"; 249 * d { 250 * da = "dad"; 251 * }; 252 * h { 253 * hh = "HH"; 254 * }; 255 * }; 256 * 257 * The resulting trees will be: 258 * 259 * tree_a : ta { 260 * b = "b"; 261 * c = "C"; 262 * g = "G"; 263 * d { 264 * da = "dad"; 265 * e = "g"; 266 * }; 267 * h { 268 * hh = "HH"; 269 * }; 270 * }; 271 * 272 * tree_b : tb { 273 * }; 274 * 275 * 276 * @return: 0 if merge success 277 * < 0 otherwise 278 * 279 * @Time: O(# of nodes in tree_b + total length of all names in tree_b) w.h.p. 280 */ 281 int merge_ufdt_into(struct ufdt_node *tree_a, struct ufdt_node *tree_b); 282 283 /* 284 * BEGIN of ufdt output functions 285 */ 286 287 /* 288 * Builds the ufdt for FDT pointed by fdtp. 289 * 290 * @return: the ufdt T representing fdtp or 291 * T with T.fdtp == NULL if fdtp is unvalid. 292 * 293 * @Time: O(fdt_size + nlogn) where n = # of nodes in fdt. 294 */ 295 struct ufdt *fdt_to_ufdt(void *fdtp, size_t fdt_size); 296 297 /* 298 * Sequentially dumps the whole ufdt to FDT buffer fdtp with buffer size 299 * buf_size. 300 * 301 * Basically using functions provided by libfdt/fdt_sw.c. 302 * 303 * @return: 0 if successfully dump or 304 * < 0 otherwise 305 * 306 * @Time: O(total length of all names + # of nodes in tree) 307 */ 308 int ufdt_to_fdt(const struct ufdt *tree, void *buf, int buf_size); 309 310 /* 311 * prints the entire subtree rooted at *node in form: 312 * NODE :[node name]: 313 * PROP :[prop name]: 314 * ... 315 * NODE :[subnode1 name]: 316 * ... 317 * NODE :[subnode1 name]: 318 * ... 319 * ... 320 * There're (depth * TAB_SIZE) spaces in front of each line. 321 */ 322 void ufdt_node_print(const struct ufdt_node *node, int depth); 323 324 /* 325 * It's just ufdt_node_print(tree->root, 0). 326 */ 327 void ufdt_print(struct ufdt *tree); 328 329 /* 330 * END of ufdt output functions 331 */ 332 333 /* 334 * Runs closure.func(node, closure.env) for all nodes in subtree rooted at 335 * *node. 336 * The order of each node being applied by the function is depth first. 337 * Basically it's the same order as the order printed in ufdt_node_print(). 338 * 339 * Example: 340 * 341 * void print_name(struct ufdt_node *node, void *env) { 342 * printf("%s\n", node->name); 343 * } 344 * 345 * struct ufdt_node_closure clos; 346 * clos.func = print_name; 347 * clos.env = NULL; 348 * ufdt_map(tree, clos); 349 * 350 * Then you can print all names of nodes in tree. 351 * 352 * @Time: O((# of nodes in subtree rooted at *node) * avg. running time of the 353 * function closure.func) 354 */ 355 void ufdt_node_map(struct ufdt_node *node, struct ufdt_node_closure closure); 356 357 /* 358 * It's just ufdt_node_map(tree->root, closure); 359 */ 360 void ufdt_map(struct ufdt *tree, struct ufdt_node_closure closure); 361 362 #endif /* LIBUFDT_H */ 363