From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id CAE92A0588; Tue, 7 Apr 2020 14:54:55 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 35A072B96; Tue, 7 Apr 2020 14:54:55 +0200 (CEST) Received: from mail-lj1-f194.google.com (mail-lj1-f194.google.com [209.85.208.194]) by dpdk.org (Postfix) with ESMTP id 681192B86 for ; Tue, 7 Apr 2020 14:54:53 +0200 (CEST) Received: by mail-lj1-f194.google.com with SMTP id t17so3522757ljc.12 for ; Tue, 07 Apr 2020 05:54:53 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=semihalf-com.20150623.gappssmtp.com; s=20150623; h=subject:to:cc:references:from:message-id:date:user-agent :mime-version:in-reply-to:content-language:content-transfer-encoding; bh=IRoRMlVFgw3SVziuwZTU7hZgz1VYTqUtMcbenuZxUeQ=; b=jBjaa+XHQo0zO1yTQbuRpxx5hOnxQoC4tTMEeRShJ6JbRNqUGz39r73RKvIQjybZru JZ5ZaV5NPm9shwKcLQ8zYGE6ftNM7w2J3L1lIiug1Q4Pys/bC8ZFu7Xh807ssz0FR890 lBPy8LGEaQXax/tsUyhgRB6/rjVM7ndQizJg8EMKCZTpKV08pbacaDnYcSiw78/+haGz np/R1KYKCXfejsdx8hryP8/Fwxc2Pbuk0zvOmzxHkNCgGsOYuxjsVBUcmhmuxL4ncVXI Pt24Gj39d+WZVrQhY1mSjEXgfS4DGawJWy7mGk3SoCBMZwp7VBO8EnoAG4bpwEkNrNbV +snw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:cc:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=IRoRMlVFgw3SVziuwZTU7hZgz1VYTqUtMcbenuZxUeQ=; b=TsgjOwi4zaVBy91blKTjSRxcQXkdt+rpspT1uMSfJ5PSB3IMaS7Z27jyubdSHrFHhX otCCVPX+O6SZo1SRJb4QRe6PaG+ljKUS3x12d1/GUg1txN5b59Vjwh2iwFVXSU6Qjj2u zURzFxb2TpqJ16JyaCgZ8pS1DIKqwDhhnvUXzBKzU0o3p9hau1GlIi3Q4T7tSXy83PHY 6QFi0HmYwHujTUReC+2ZAUqPuYHO3YPi3un23sgz2yneeVqaRxBeD/rVHVGIh5AmU5jz MQbLXXa1AUCJcRs3xPUnsYjNL7D07eRt4rXHec35CYZ2OjTAmMKjbmCVzWzPx5QUYciO 2TZQ== X-Gm-Message-State: AGi0Pubq/oQNe8EJdsX7yKQYnl2UE9hB6cfYSuthBjiGfW6CQs9lcQMu Atl0pBi3q8yC82KFRWXj7YULS2/cP5g= X-Google-Smtp-Source: APiQypLLlkIR39GvYNb6cSQYNix9vf6yWjFuCILlLkSmrBezRuX12IjuZKoYlkAVSnq9tMdCogqbNQ== X-Received: by 2002:a2e:b018:: with SMTP id y24mr1724483ljk.268.1586264092499; Tue, 07 Apr 2020 05:54:52 -0700 (PDT) Received: from [192.168.8.100] (user-5-173-33-152.play-internet.pl. [5.173.33.152]) by smtp.gmail.com with ESMTPSA id c4sm8559998ljd.30.2020.04.07.05.54.51 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 07 Apr 2020 05:54:51 -0700 (PDT) To: Jerin Jacob Cc: dpdk-dev References: <20200331192945.2466880-1-jerinj@marvell.com> <20200405085613.1336841-1-jerinj@marvell.com> <20200405085613.1336841-6-jerinj@marvell.com> <097e35c5-ffb0-854c-12b6-184849f2d922@semihalf.com> From: Andrzej Ostruszka Message-ID: <551b1959-eb68-0265-8c22-b792fd8bff56@semihalf.com> Date: Tue, 7 Apr 2020 14:54:51 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Firefox/68.0 Thunderbird/68.4.1 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 7bit Subject: Re: [dpdk-dev] [PATCH v4 05/29] graph: implement internal graph operation helpers X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" On 4/7/20 2:27 PM, Jerin Jacob wrote: > On Tue, Apr 7, 2020 at 5:46 PM Andrzej Ostruszka wrote: > >>> +int >>> +graph_bfs(struct graph *graph, struct graph_node *start) >>> +{ >>> + struct graph_node **queue, *v, *tmp; >>> + uint16_t head = 0, tail = 0; >>> + rte_edge_t i; >>> + size_t sz; >>> + >>> + sz = sizeof(struct graph_node *) * graph_nodes_count(graph); >>> + queue = malloc(sz); >>> + if (queue == NULL) >>> + SET_ERR_JMP(ENOMEM, fail, "Failed to alloc BFS queue of %zu", >>> + sz); >>> + >>> + /* BFS algorithm */ >>> + queue[tail++] = start; >>> + start->visited = true; >>> + while (head != tail) { >>> + v = queue[head++]; >>> + for (i = 0; i < v->node->nb_edges; i++) { >>> + tmp = v->adjacency_list[i]; >>> + if (tmp->visited == false) { >>> + queue[tail++] = tmp; >>> + tmp->visited = true; >>> + } >>> + } >>> + } >>> + >>> + free(queue); >>> + return 0; >>> + >>> +fail: >>> + return -rte_errno; >>> +} >> >> What is the purpose of this function? It looks like just marking as >> visited. Then maybe change the name to graph_mark_bfs() or something >> like that. > > graph_ops.c has all generic graph-related functions. > BFS(Breadth-First Search) is a generic graph operation. The primitive > can be used for various other graph operations. > IMO, It is better to avoid connecting with a marking using case in the > function name. > > >> >>> + >>> +/* Check whether a node has connected path or parent node */ >>> +int >>> +graph_has_isolated_node(struct graph *graph) >>> +{ >>> + struct graph_node *graph_node; >>> + >>> + graph_mark_nodes_as_not_visited(graph); > > See below, > >>> + >>> + STAILQ_FOREACH(graph_node, &graph->node_list, next) { >>> + if (graph_node->node->flags & RTE_NODE_SOURCE_F) { >>> + if (graph_node->node->nb_edges == 0) >>> + SET_ERR_JMP(EINVAL, fail, >>> + "%s node needs minimum one edge", >>> + graph_node->node->name); >>> + if (graph_bfs(graph, graph_node)) >>> + goto fail; >>> + } >>> + } >>> + >>> + STAILQ_FOREACH(graph_node, &graph->node_list, next) >>> + if (graph_node->visited == false) >>> + SET_ERR_JMP(EINVAL, fail, "Found isolated node %s", >>> + graph_node->node->name);> + >>> + return 0; >> >> You don't want to clear visited because it will not be used or cleared >> on next call? > > See above graph_mark_nodes_as_not_visited() function. Yes I noticed that and referred to it in the question. My intention was to ask whether you are fine with graph having visited=true for the rest of its life, or should we clear them again at the end of this function. With regards Andrzej Ostruszka