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 */
36struct 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 */
41void 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 */
53int 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 */
65struct ufdt_node *ufdt_node_get_property_by_name_len(
66    const struct ufdt_node *node, const char *name, int len);
67struct 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 */
77char *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 */
90char *ufdt_node_get_fdt_prop_data_by_name_len(const struct ufdt_node *node,
91                                              const char *name, int len,
92                                              int *out_len);
93char *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
108struct ufdt_node *ufdt_node_get_subnode_by_name_len(const struct ufdt_node *node,
109                                                    const char *name, int len);
110struct 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 */
124struct ufdt_node *ufdt_node_get_node_by_path_len(const struct ufdt_node *node,
125                                                 const char *path, int len);
126struct 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 */
138uint32_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 */
155struct 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 */
161void 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 */
170int 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 */
180int 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 */
191struct 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 */
206struct ufdt_node *ufdt_get_node_by_path_len(struct ufdt *tree, const char *path,
207                                            int len);
208struct 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 */
221int 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 */
229bool 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 */
281int 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 */
295struct 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 */
308int 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 */
322void ufdt_node_print(const struct ufdt_node *node, int depth);
323
324/*
325 * It's just ufdt_node_print(tree->root, 0).
326 */
327void 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 */
355void 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 */
360void ufdt_map(struct ufdt *tree, struct ufdt_node_closure closure);
361
362#endif /* LIBUFDT_H */
363