1204431Sraj/* 2204431Sraj * (C) Copyright David Gibson <dwg@au1.ibm.com>, IBM Corporation. 2005. 3204431Sraj * 4204431Sraj * 5204431Sraj * This program is free software; you can redistribute it and/or 6204431Sraj * modify it under the terms of the GNU General Public License as 7204431Sraj * published by the Free Software Foundation; either version 2 of the 8204431Sraj * License, or (at your option) any later version. 9204431Sraj * 10204431Sraj * This program is distributed in the hope that it will be useful, 11204431Sraj * but WITHOUT ANY WARRANTY; without even the implied warranty of 12204431Sraj * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 13204431Sraj * General Public License for more details. 14204431Sraj * 15204431Sraj * You should have received a copy of the GNU General Public License 16204431Sraj * along with this program; if not, write to the Free Software 17204431Sraj * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 18204431Sraj * USA 19204431Sraj */ 20204431Sraj 21204431Sraj#include "dtc.h" 22204431Sraj 23204431Sraj/* 24204431Sraj * Tree building functions 25204431Sraj */ 26204431Sraj 27238742Simpvoid add_label(struct label **labels, char *label) 28204431Sraj{ 29238742Simp struct label *new; 30238742Simp 31238742Simp /* Make sure the label isn't already there */ 32266130Sian for_each_label_withdel(*labels, new) 33266130Sian if (streq(new->label, label)) { 34266130Sian new->deleted = 0; 35238742Simp return; 36266130Sian } 37238742Simp 38238742Simp new = xmalloc(sizeof(*new)); 39266130Sian memset(new, 0, sizeof(*new)); 40238742Simp new->label = label; 41238742Simp new->next = *labels; 42238742Simp *labels = new; 43238742Simp} 44238742Simp 45266130Sianvoid delete_labels(struct label **labels) 46266130Sian{ 47266130Sian struct label *label; 48266130Sian 49266130Sian for_each_label(*labels, label) 50266130Sian label->deleted = 1; 51266130Sian} 52266130Sian 53238742Simpstruct property *build_property(char *name, struct data val) 54238742Simp{ 55204431Sraj struct property *new = xmalloc(sizeof(*new)); 56204431Sraj 57238742Simp memset(new, 0, sizeof(*new)); 58238742Simp 59204431Sraj new->name = name; 60204431Sraj new->val = val; 61204431Sraj 62204431Sraj return new; 63204431Sraj} 64204431Sraj 65266130Sianstruct property *build_property_delete(char *name) 66266130Sian{ 67266130Sian struct property *new = xmalloc(sizeof(*new)); 68266130Sian 69266130Sian memset(new, 0, sizeof(*new)); 70266130Sian 71266130Sian new->name = name; 72266130Sian new->deleted = 1; 73266130Sian 74266130Sian return new; 75266130Sian} 76266130Sian 77204431Srajstruct property *chain_property(struct property *first, struct property *list) 78204431Sraj{ 79204431Sraj assert(first->next == NULL); 80204431Sraj 81204431Sraj first->next = list; 82204431Sraj return first; 83204431Sraj} 84204431Sraj 85204431Srajstruct property *reverse_properties(struct property *first) 86204431Sraj{ 87204431Sraj struct property *p = first; 88204431Sraj struct property *head = NULL; 89204431Sraj struct property *next; 90204431Sraj 91204431Sraj while (p) { 92204431Sraj next = p->next; 93204431Sraj p->next = head; 94204431Sraj head = p; 95204431Sraj p = next; 96204431Sraj } 97204431Sraj return head; 98204431Sraj} 99204431Sraj 100204431Srajstruct node *build_node(struct property *proplist, struct node *children) 101204431Sraj{ 102204431Sraj struct node *new = xmalloc(sizeof(*new)); 103204431Sraj struct node *child; 104204431Sraj 105204431Sraj memset(new, 0, sizeof(*new)); 106204431Sraj 107204431Sraj new->proplist = reverse_properties(proplist); 108204431Sraj new->children = children; 109204431Sraj 110204431Sraj for_each_child(new, child) { 111204431Sraj child->parent = new; 112204431Sraj } 113204431Sraj 114204431Sraj return new; 115204431Sraj} 116204431Sraj 117266130Sianstruct node *build_node_delete(void) 118266130Sian{ 119266130Sian struct node *new = xmalloc(sizeof(*new)); 120266130Sian 121266130Sian memset(new, 0, sizeof(*new)); 122266130Sian 123266130Sian new->deleted = 1; 124266130Sian 125266130Sian return new; 126266130Sian} 127266130Sian 128238742Simpstruct node *name_node(struct node *node, char *name) 129204431Sraj{ 130204431Sraj assert(node->name == NULL); 131204431Sraj 132204431Sraj node->name = name; 133204431Sraj 134204431Sraj return node; 135204431Sraj} 136204431Sraj 137238742Simpstruct node *merge_nodes(struct node *old_node, struct node *new_node) 138238742Simp{ 139238742Simp struct property *new_prop, *old_prop; 140238742Simp struct node *new_child, *old_child; 141238742Simp struct label *l; 142238742Simp 143266130Sian old_node->deleted = 0; 144266130Sian 145238742Simp /* Add new node labels to old node */ 146266130Sian for_each_label_withdel(new_node->labels, l) 147238742Simp add_label(&old_node->labels, l->label); 148238742Simp 149238742Simp /* Move properties from the new node to the old node. If there 150238742Simp * is a collision, replace the old value with the new */ 151238742Simp while (new_node->proplist) { 152238742Simp /* Pop the property off the list */ 153238742Simp new_prop = new_node->proplist; 154238742Simp new_node->proplist = new_prop->next; 155238742Simp new_prop->next = NULL; 156238742Simp 157266130Sian if (new_prop->deleted) { 158266130Sian delete_property_by_name(old_node, new_prop->name); 159266130Sian free(new_prop); 160266130Sian continue; 161266130Sian } 162266130Sian 163238742Simp /* Look for a collision, set new value if there is */ 164266130Sian for_each_property_withdel(old_node, old_prop) { 165238742Simp if (streq(old_prop->name, new_prop->name)) { 166238742Simp /* Add new labels to old property */ 167266130Sian for_each_label_withdel(new_prop->labels, l) 168238742Simp add_label(&old_prop->labels, l->label); 169238742Simp 170238742Simp old_prop->val = new_prop->val; 171266130Sian old_prop->deleted = 0; 172238742Simp free(new_prop); 173238742Simp new_prop = NULL; 174238742Simp break; 175238742Simp } 176238742Simp } 177238742Simp 178238742Simp /* if no collision occurred, add property to the old node. */ 179238742Simp if (new_prop) 180238742Simp add_property(old_node, new_prop); 181238742Simp } 182238742Simp 183238742Simp /* Move the override child nodes into the primary node. If 184238742Simp * there is a collision, then merge the nodes. */ 185238742Simp while (new_node->children) { 186238742Simp /* Pop the child node off the list */ 187238742Simp new_child = new_node->children; 188238742Simp new_node->children = new_child->next_sibling; 189238742Simp new_child->parent = NULL; 190238742Simp new_child->next_sibling = NULL; 191238742Simp 192266130Sian if (new_child->deleted) { 193266130Sian delete_node_by_name(old_node, new_child->name); 194266130Sian free(new_child); 195266130Sian continue; 196266130Sian } 197266130Sian 198238742Simp /* Search for a collision. Merge if there is */ 199266130Sian for_each_child_withdel(old_node, old_child) { 200238742Simp if (streq(old_child->name, new_child->name)) { 201238742Simp merge_nodes(old_child, new_child); 202238742Simp new_child = NULL; 203238742Simp break; 204238742Simp } 205238742Simp } 206238742Simp 207238742Simp /* if no collision occured, add child to the old node. */ 208238742Simp if (new_child) 209238742Simp add_child(old_node, new_child); 210238742Simp } 211238742Simp 212238742Simp /* The new node contents are now merged into the old node. Free 213238742Simp * the new node. */ 214238742Simp free(new_node); 215238742Simp 216238742Simp return old_node; 217238742Simp} 218238742Simp 219204431Srajstruct node *chain_node(struct node *first, struct node *list) 220204431Sraj{ 221204431Sraj assert(first->next_sibling == NULL); 222204431Sraj 223204431Sraj first->next_sibling = list; 224204431Sraj return first; 225204431Sraj} 226204431Sraj 227204431Srajvoid add_property(struct node *node, struct property *prop) 228204431Sraj{ 229204431Sraj struct property **p; 230204431Sraj 231204431Sraj prop->next = NULL; 232204431Sraj 233204431Sraj p = &node->proplist; 234204431Sraj while (*p) 235204431Sraj p = &((*p)->next); 236204431Sraj 237204431Sraj *p = prop; 238204431Sraj} 239204431Sraj 240266130Sianvoid delete_property_by_name(struct node *node, char *name) 241266130Sian{ 242266130Sian struct property *prop = node->proplist; 243266130Sian 244266130Sian while (prop) { 245266130Sian if (!strcmp(prop->name, name)) { 246266130Sian delete_property(prop); 247266130Sian return; 248266130Sian } 249266130Sian prop = prop->next; 250266130Sian } 251266130Sian} 252266130Sian 253266130Sianvoid delete_property(struct property *prop) 254266130Sian{ 255266130Sian prop->deleted = 1; 256266130Sian delete_labels(&prop->labels); 257266130Sian} 258266130Sian 259204431Srajvoid add_child(struct node *parent, struct node *child) 260204431Sraj{ 261204431Sraj struct node **p; 262204431Sraj 263204431Sraj child->next_sibling = NULL; 264204431Sraj child->parent = parent; 265204431Sraj 266204431Sraj p = &parent->children; 267204431Sraj while (*p) 268204431Sraj p = &((*p)->next_sibling); 269204431Sraj 270204431Sraj *p = child; 271204431Sraj} 272204431Sraj 273266130Sianvoid delete_node_by_name(struct node *parent, char *name) 274266130Sian{ 275266130Sian struct node *node = parent->children; 276266130Sian 277266130Sian while (node) { 278266130Sian if (!strcmp(node->name, name)) { 279266130Sian delete_node(node); 280266130Sian return; 281266130Sian } 282266130Sian node = node->next_sibling; 283266130Sian } 284266130Sian} 285266130Sian 286266130Sianvoid delete_node(struct node *node) 287266130Sian{ 288266130Sian struct property *prop; 289266130Sian struct node *child; 290266130Sian 291266130Sian node->deleted = 1; 292266130Sian for_each_child(node, child) 293266130Sian delete_node(child); 294266130Sian for_each_property(node, prop) 295266130Sian delete_property(prop); 296266130Sian delete_labels(&node->labels); 297266130Sian} 298266130Sian 299238742Simpstruct reserve_info *build_reserve_entry(uint64_t address, uint64_t size) 300204431Sraj{ 301204431Sraj struct reserve_info *new = xmalloc(sizeof(*new)); 302204431Sraj 303238742Simp memset(new, 0, sizeof(*new)); 304238742Simp 305204431Sraj new->re.address = address; 306204431Sraj new->re.size = size; 307204431Sraj 308204431Sraj return new; 309204431Sraj} 310204431Sraj 311204431Srajstruct reserve_info *chain_reserve_entry(struct reserve_info *first, 312204431Sraj struct reserve_info *list) 313204431Sraj{ 314204431Sraj assert(first->next == NULL); 315204431Sraj 316204431Sraj first->next = list; 317204431Sraj return first; 318204431Sraj} 319204431Sraj 320204431Srajstruct reserve_info *add_reserve_entry(struct reserve_info *list, 321204431Sraj struct reserve_info *new) 322204431Sraj{ 323204431Sraj struct reserve_info *last; 324204431Sraj 325204431Sraj new->next = NULL; 326204431Sraj 327204431Sraj if (! list) 328204431Sraj return new; 329204431Sraj 330204431Sraj for (last = list; last->next; last = last->next) 331204431Sraj ; 332204431Sraj 333204431Sraj last->next = new; 334204431Sraj 335204431Sraj return list; 336204431Sraj} 337204431Sraj 338204431Srajstruct boot_info *build_boot_info(struct reserve_info *reservelist, 339204431Sraj struct node *tree, uint32_t boot_cpuid_phys) 340204431Sraj{ 341204431Sraj struct boot_info *bi; 342204431Sraj 343204431Sraj bi = xmalloc(sizeof(*bi)); 344204431Sraj bi->reservelist = reservelist; 345204431Sraj bi->dt = tree; 346204431Sraj bi->boot_cpuid_phys = boot_cpuid_phys; 347204431Sraj 348204431Sraj return bi; 349204431Sraj} 350204431Sraj 351204431Sraj/* 352204431Sraj * Tree accessor functions 353204431Sraj */ 354204431Sraj 355204431Srajconst char *get_unitname(struct node *node) 356204431Sraj{ 357204431Sraj if (node->name[node->basenamelen] == '\0') 358204431Sraj return ""; 359204431Sraj else 360204431Sraj return node->name + node->basenamelen + 1; 361204431Sraj} 362204431Sraj 363204431Srajstruct property *get_property(struct node *node, const char *propname) 364204431Sraj{ 365204431Sraj struct property *prop; 366204431Sraj 367204431Sraj for_each_property(node, prop) 368204431Sraj if (streq(prop->name, propname)) 369204431Sraj return prop; 370204431Sraj 371204431Sraj return NULL; 372204431Sraj} 373204431Sraj 374204431Srajcell_t propval_cell(struct property *prop) 375204431Sraj{ 376204431Sraj assert(prop->val.len == sizeof(cell_t)); 377204431Sraj return fdt32_to_cpu(*((cell_t *)prop->val.val)); 378204431Sraj} 379204431Sraj 380238742Simpstruct property *get_property_by_label(struct node *tree, const char *label, 381238742Simp struct node **node) 382238742Simp{ 383238742Simp struct property *prop; 384238742Simp struct node *c; 385238742Simp 386238742Simp *node = tree; 387238742Simp 388238742Simp for_each_property(tree, prop) { 389238742Simp struct label *l; 390238742Simp 391238742Simp for_each_label(prop->labels, l) 392238742Simp if (streq(l->label, label)) 393238742Simp return prop; 394238742Simp } 395238742Simp 396238742Simp for_each_child(tree, c) { 397238742Simp prop = get_property_by_label(c, label, node); 398238742Simp if (prop) 399238742Simp return prop; 400238742Simp } 401238742Simp 402238742Simp *node = NULL; 403238742Simp return NULL; 404238742Simp} 405238742Simp 406238742Simpstruct marker *get_marker_label(struct node *tree, const char *label, 407238742Simp struct node **node, struct property **prop) 408238742Simp{ 409238742Simp struct marker *m; 410238742Simp struct property *p; 411238742Simp struct node *c; 412238742Simp 413238742Simp *node = tree; 414238742Simp 415238742Simp for_each_property(tree, p) { 416238742Simp *prop = p; 417238742Simp m = p->val.markers; 418238742Simp for_each_marker_of_type(m, LABEL) 419238742Simp if (streq(m->ref, label)) 420238742Simp return m; 421238742Simp } 422238742Simp 423238742Simp for_each_child(tree, c) { 424238742Simp m = get_marker_label(c, label, node, prop); 425238742Simp if (m) 426238742Simp return m; 427238742Simp } 428238742Simp 429238742Simp *prop = NULL; 430238742Simp *node = NULL; 431238742Simp return NULL; 432238742Simp} 433238742Simp 434204431Srajstruct node *get_subnode(struct node *node, const char *nodename) 435204431Sraj{ 436204431Sraj struct node *child; 437204431Sraj 438204431Sraj for_each_child(node, child) 439204431Sraj if (streq(child->name, nodename)) 440204431Sraj return child; 441204431Sraj 442204431Sraj return NULL; 443204431Sraj} 444204431Sraj 445204431Srajstruct node *get_node_by_path(struct node *tree, const char *path) 446204431Sraj{ 447204431Sraj const char *p; 448204431Sraj struct node *child; 449204431Sraj 450266130Sian if (!path || ! (*path)) { 451266130Sian if (tree->deleted) 452266130Sian return NULL; 453204431Sraj return tree; 454266130Sian } 455204431Sraj 456204431Sraj while (path[0] == '/') 457204431Sraj path++; 458204431Sraj 459204431Sraj p = strchr(path, '/'); 460204431Sraj 461204431Sraj for_each_child(tree, child) { 462204431Sraj if (p && strneq(path, child->name, p-path)) 463204431Sraj return get_node_by_path(child, p+1); 464204431Sraj else if (!p && streq(path, child->name)) 465204431Sraj return child; 466204431Sraj } 467204431Sraj 468204431Sraj return NULL; 469204431Sraj} 470204431Sraj 471204431Srajstruct node *get_node_by_label(struct node *tree, const char *label) 472204431Sraj{ 473204431Sraj struct node *child, *node; 474238742Simp struct label *l; 475204431Sraj 476204431Sraj assert(label && (strlen(label) > 0)); 477204431Sraj 478238742Simp for_each_label(tree->labels, l) 479238742Simp if (streq(l->label, label)) 480238742Simp return tree; 481204431Sraj 482204431Sraj for_each_child(tree, child) { 483204431Sraj node = get_node_by_label(child, label); 484204431Sraj if (node) 485204431Sraj return node; 486204431Sraj } 487204431Sraj 488204431Sraj return NULL; 489204431Sraj} 490204431Sraj 491204431Srajstruct node *get_node_by_phandle(struct node *tree, cell_t phandle) 492204431Sraj{ 493204431Sraj struct node *child, *node; 494204431Sraj 495204431Sraj assert((phandle != 0) && (phandle != -1)); 496204431Sraj 497266130Sian if (tree->phandle == phandle) { 498266130Sian if (tree->deleted) 499266130Sian return NULL; 500204431Sraj return tree; 501266130Sian } 502204431Sraj 503204431Sraj for_each_child(tree, child) { 504204431Sraj node = get_node_by_phandle(child, phandle); 505204431Sraj if (node) 506204431Sraj return node; 507204431Sraj } 508204431Sraj 509204431Sraj return NULL; 510204431Sraj} 511204431Sraj 512204431Srajstruct node *get_node_by_ref(struct node *tree, const char *ref) 513204431Sraj{ 514204431Sraj if (ref[0] == '/') 515204431Sraj return get_node_by_path(tree, ref); 516204431Sraj else 517204431Sraj return get_node_by_label(tree, ref); 518204431Sraj} 519204431Sraj 520204431Srajcell_t get_node_phandle(struct node *root, struct node *node) 521204431Sraj{ 522204431Sraj static cell_t phandle = 1; /* FIXME: ick, static local */ 523204431Sraj 524204431Sraj if ((node->phandle != 0) && (node->phandle != -1)) 525204431Sraj return node->phandle; 526204431Sraj 527204431Sraj while (get_node_by_phandle(root, phandle)) 528204431Sraj phandle++; 529204431Sraj 530204431Sraj node->phandle = phandle; 531204431Sraj 532204433Sraj if (!get_property(node, "linux,phandle") 533204433Sraj && (phandle_format & PHANDLE_LEGACY)) 534204433Sraj add_property(node, 535204433Sraj build_property("linux,phandle", 536238742Simp data_append_cell(empty_data, phandle))); 537204433Sraj 538204433Sraj if (!get_property(node, "phandle") 539204433Sraj && (phandle_format & PHANDLE_EPAPR)) 540204433Sraj add_property(node, 541204433Sraj build_property("phandle", 542238742Simp data_append_cell(empty_data, phandle))); 543204433Sraj 544204433Sraj /* If the node *does* have a phandle property, we must 545204433Sraj * be dealing with a self-referencing phandle, which will be 546204433Sraj * fixed up momentarily in the caller */ 547204433Sraj 548204431Sraj return node->phandle; 549204431Sraj} 550238742Simp 551238742Simpuint32_t guess_boot_cpuid(struct node *tree) 552238742Simp{ 553238742Simp struct node *cpus, *bootcpu; 554238742Simp struct property *reg; 555238742Simp 556238742Simp cpus = get_node_by_path(tree, "/cpus"); 557238742Simp if (!cpus) 558238742Simp return 0; 559238742Simp 560238742Simp 561238742Simp bootcpu = cpus->children; 562238742Simp if (!bootcpu) 563238742Simp return 0; 564238742Simp 565238742Simp reg = get_property(bootcpu, "reg"); 566238742Simp if (!reg || (reg->val.len != sizeof(uint32_t))) 567238742Simp return 0; 568238742Simp 569238742Simp /* FIXME: Sanity check node? */ 570238742Simp 571238742Simp return propval_cell(reg); 572238742Simp} 573238742Simp 574238742Simpstatic int cmp_reserve_info(const void *ax, const void *bx) 575238742Simp{ 576238742Simp const struct reserve_info *a, *b; 577238742Simp 578238742Simp a = *((const struct reserve_info * const *)ax); 579238742Simp b = *((const struct reserve_info * const *)bx); 580238742Simp 581238742Simp if (a->re.address < b->re.address) 582238742Simp return -1; 583238742Simp else if (a->re.address > b->re.address) 584238742Simp return 1; 585238742Simp else if (a->re.size < b->re.size) 586238742Simp return -1; 587238742Simp else if (a->re.size > b->re.size) 588238742Simp return 1; 589238742Simp else 590238742Simp return 0; 591238742Simp} 592238742Simp 593238742Simpstatic void sort_reserve_entries(struct boot_info *bi) 594238742Simp{ 595238742Simp struct reserve_info *ri, **tbl; 596238742Simp int n = 0, i = 0; 597238742Simp 598238742Simp for (ri = bi->reservelist; 599238742Simp ri; 600238742Simp ri = ri->next) 601238742Simp n++; 602238742Simp 603238742Simp if (n == 0) 604238742Simp return; 605238742Simp 606238742Simp tbl = xmalloc(n * sizeof(*tbl)); 607238742Simp 608238742Simp for (ri = bi->reservelist; 609238742Simp ri; 610238742Simp ri = ri->next) 611238742Simp tbl[i++] = ri; 612238742Simp 613238742Simp qsort(tbl, n, sizeof(*tbl), cmp_reserve_info); 614238742Simp 615238742Simp bi->reservelist = tbl[0]; 616238742Simp for (i = 0; i < (n-1); i++) 617238742Simp tbl[i]->next = tbl[i+1]; 618238742Simp tbl[n-1]->next = NULL; 619238742Simp 620238742Simp free(tbl); 621238742Simp} 622238742Simp 623238742Simpstatic int cmp_prop(const void *ax, const void *bx) 624238742Simp{ 625238742Simp const struct property *a, *b; 626238742Simp 627238742Simp a = *((const struct property * const *)ax); 628238742Simp b = *((const struct property * const *)bx); 629238742Simp 630238742Simp return strcmp(a->name, b->name); 631238742Simp} 632238742Simp 633238742Simpstatic void sort_properties(struct node *node) 634238742Simp{ 635238742Simp int n = 0, i = 0; 636238742Simp struct property *prop, **tbl; 637238742Simp 638266130Sian for_each_property_withdel(node, prop) 639238742Simp n++; 640238742Simp 641238742Simp if (n == 0) 642238742Simp return; 643238742Simp 644238742Simp tbl = xmalloc(n * sizeof(*tbl)); 645238742Simp 646266130Sian for_each_property_withdel(node, prop) 647238742Simp tbl[i++] = prop; 648238742Simp 649238742Simp qsort(tbl, n, sizeof(*tbl), cmp_prop); 650238742Simp 651238742Simp node->proplist = tbl[0]; 652238742Simp for (i = 0; i < (n-1); i++) 653238742Simp tbl[i]->next = tbl[i+1]; 654238742Simp tbl[n-1]->next = NULL; 655238742Simp 656238742Simp free(tbl); 657238742Simp} 658238742Simp 659238742Simpstatic int cmp_subnode(const void *ax, const void *bx) 660238742Simp{ 661238742Simp const struct node *a, *b; 662238742Simp 663238742Simp a = *((const struct node * const *)ax); 664238742Simp b = *((const struct node * const *)bx); 665238742Simp 666238742Simp return strcmp(a->name, b->name); 667238742Simp} 668238742Simp 669238742Simpstatic void sort_subnodes(struct node *node) 670238742Simp{ 671238742Simp int n = 0, i = 0; 672238742Simp struct node *subnode, **tbl; 673238742Simp 674266130Sian for_each_child_withdel(node, subnode) 675238742Simp n++; 676238742Simp 677238742Simp if (n == 0) 678238742Simp return; 679238742Simp 680238742Simp tbl = xmalloc(n * sizeof(*tbl)); 681238742Simp 682266130Sian for_each_child_withdel(node, subnode) 683238742Simp tbl[i++] = subnode; 684238742Simp 685238742Simp qsort(tbl, n, sizeof(*tbl), cmp_subnode); 686238742Simp 687238742Simp node->children = tbl[0]; 688238742Simp for (i = 0; i < (n-1); i++) 689238742Simp tbl[i]->next_sibling = tbl[i+1]; 690238742Simp tbl[n-1]->next_sibling = NULL; 691238742Simp 692238742Simp free(tbl); 693238742Simp} 694238742Simp 695238742Simpstatic void sort_node(struct node *node) 696238742Simp{ 697238742Simp struct node *c; 698238742Simp 699238742Simp sort_properties(node); 700238742Simp sort_subnodes(node); 701266130Sian for_each_child_withdel(node, c) 702238742Simp sort_node(c); 703238742Simp} 704238742Simp 705238742Simpvoid sort_tree(struct boot_info *bi) 706238742Simp{ 707238742Simp sort_reserve_entries(bi); 708238742Simp sort_node(bi->dt); 709238742Simp} 710