From patchwork Mon Jan 18 03:23:16 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Oliver O'Halloran X-Patchwork-Id: 569404 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from lists.ozlabs.org (lists.ozlabs.org [103.22.144.68]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 89A38140662 for ; Mon, 18 Jan 2016 14:23:59 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.b=UiYuBUOr; dkim-atps=neutral Received: from lists.ozlabs.org (lists.ozlabs.org [IPv6:2401:3900:2:1::3]) by lists.ozlabs.org (Postfix) with ESMTP id 6BB1A1A0A3F for ; Mon, 18 Jan 2016 14:23:59 +1100 (AEDT) Authentication-Results: lists.ozlabs.org; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.b=UiYuBUOr; dkim-atps=neutral X-Original-To: skiboot@lists.ozlabs.org Delivered-To: skiboot@lists.ozlabs.org Received: from mail-pa0-x244.google.com (mail-pa0-x244.google.com [IPv6:2607:f8b0:400e:c03::244]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by lists.ozlabs.org (Postfix) with ESMTPS id 4CA361A004E for ; Mon, 18 Jan 2016 14:23:54 +1100 (AEDT) Authentication-Results: lists.ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.b=UiYuBUOr; dkim-atps=neutral Received: by mail-pa0-x244.google.com with SMTP id pv5so33050041pac.0 for ; Sun, 17 Jan 2016 19:23:54 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=NcHLzUlev+4bIaRNMOCDiqvPxyvfff05O7hyLNXbJGw=; b=UiYuBUOrl+jHXwpBdddX8L/y4PoN75z/jHEZoL0z7PnRLbuvC3FF6YhBC5b2vgcm7v 9z9y+0wiD1H/rUG+lGqlN6BKuOetzCnZyMEaB/VYEh/InXxtLSttxobcNUWP3hWaPV5u 4o/IDTAQHNR462s7TdC5x470GOyxs90/3TUyRRx5vjtCqNIDwOoG54Qs7Egz8A/ku1Ms LevZEwYdTsCl+UpuNVMS61K41KiHhfbIJiEmbyx2OStYruNYoWKFWSE0+2RrEWHkRdLb eR1lfdboUJWIgG+q7Q7N5m1iOLvfxI0/nFuz0buZeDLxZwl5TAg9Kg/759+lJynR1hvK Sumg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=NcHLzUlev+4bIaRNMOCDiqvPxyvfff05O7hyLNXbJGw=; b=c802TATQUGEh5KKPQ1a4wbl4lrkMLOanXUsZJywOeRqLS3MMW6KxPGzuDh4Ekn+QZh EgnpeGmH1jOwE1ZSQIaRFEZ/09yyHGkNf1dTkMfrZ3B3qfOUiNBK+KHF3GImjppkOOOz Ab7BDlG/uaLrm79MSGGeyAKY8jFFogiTol00yhCs+DhSMZuaqSQ4F9HeRLFP94RiAGj2 3INP1UBXpEANJJv7Ip012YFXq5K1O57NjKlkebDbpcZCwdiVZQSMGPo3Uk9J7an4E4wF pY5otqqglrQRQoS5L/AjK7HynaKx6t8LxJXRFK+JmorDasOdrkp1ANB3QZ+vzrvQ0KVe ck0Q== X-Gm-Message-State: ALoCoQnOM5Sp6QdS/dq63lbhEWv0VuoWS+hKKygOBtVQsksGfCIlEz4MkgbQH8HVnMc8P2jpWkuWHRhht7rKKkxYeRqZCP06XQ== X-Received: by 10.66.232.74 with SMTP id tm10mr33736411pac.128.1453087432346; Sun, 17 Jan 2016 19:23:52 -0800 (PST) Received: from canetoad.ozlabs.ibm.com ([122.99.82.10]) by smtp.gmail.com with ESMTPSA id f12sm29929787pat.20.2016.01.17.19.23.50 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 17 Jan 2016 19:23:51 -0800 (PST) From: Oliver O'Halloran To: skiboot@lists.ozlabs.org Date: Mon, 18 Jan 2016 14:23:16 +1100 Message-Id: <1453087398-15241-2-git-send-email-oohall@gmail.com> X-Mailer: git-send-email 2.5.0 In-Reply-To: <1453087398-15241-1-git-send-email-oohall@gmail.com> References: <1453087398-15241-1-git-send-email-oohall@gmail.com> Subject: [Skiboot] [PATCH v2 2/4] core/device.c: Sort nodes with name@unit names by unit X-BeenThere: skiboot@lists.ozlabs.org X-Mailman-Version: 2.1.20 Precedence: list List-Id: Mailing list for skiboot development List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Errors-To: skiboot-bounces+incoming=patchwork.ozlabs.org@lists.ozlabs.org Sender: "Skiboot" When unflattening (or building from hdat) a device tree child nodes are added in the order in which they are encountered. For nodes that have a @ style name with a common basename it is useful to have them in the tree sorted by the unit in ascending order. Currently this requires the source data to present them in sorted order, but this isn't always the case. This patch modifies the node insertion process to insert new nodes in the correct location so the list of child nodes is sorted. Signed-off-by: Oliver O'Halloran --- core/device.c | 56 ++++++++++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 52 insertions(+), 4 deletions(-) diff --git a/core/device.c b/core/device.c index c5f8634..baa37c5 100644 --- a/core/device.c +++ b/core/device.c @@ -65,21 +65,69 @@ struct dt_node *dt_new_root(const char *name) return new_node(name); } +static const char *get_unitname(const struct dt_node *node) +{ + const char *c = strchr(node->name, '@'); + + if (!c) + return NULL; + + return c + 1; +} + +static int dt_cmp_subnodes(const struct dt_node *a, const struct dt_node *b) +{ + const char *a_unit = get_unitname(a); + const char *b_unit = get_unitname(b); + + ptrdiff_t basenamelen = a_unit - a->name; + + /* sort hex unit addresses by number */ + if (a_unit && b_unit && !strncmp(a->name, b->name, basenamelen)) { + unsigned long long a_num, b_num; + char *a_end, *b_end; + + a_num = strtoul(a_unit, &a_end, 16); + b_num = strtoul(b_unit, &b_end, 16); + + /* only compare if the unit addr parsed correctly */ + if (*a_end == 0 && *b_end == 0) + return (a_num > b_num) - (a_num < b_num); + } + + return strcmp(a->name, b->name); +} + bool dt_attach_root(struct dt_node *parent, struct dt_node *root) { struct dt_node *node; - /* Look for duplicates */ - assert(!root->parent); + + if (list_empty(&parent->children)) { + list_add(&parent->children, &root->list); + root->parent = parent; + + return true; + } + dt_for_each_child(parent, node) { - if (!strcmp(node->name, root->name)) { + int cmp = dt_cmp_subnodes(node, root); + + /* Look for duplicates */ + if (cmp == 0) { prerror("DT: %s failed, duplicate %s\n", __func__, root->name); return false; } + + /* insert before the first node that's larger + * the the node we're inserting */ + if (cmp > 0) + break; } - list_add_tail(&parent->children, &root->list); + + list_add_before(&parent->children, &root->list, &node->list); root->parent = parent; return true;