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