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 14A38A0588; Tue, 7 Apr 2020 14:28:18 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id E44262BD8; Tue, 7 Apr 2020 14:28:17 +0200 (CEST) Received: from mail-il1-f194.google.com (mail-il1-f194.google.com [209.85.166.194]) by dpdk.org (Postfix) with ESMTP id 623802B96 for ; Tue, 7 Apr 2020 14:28:16 +0200 (CEST) Received: by mail-il1-f194.google.com with SMTP id r5so2963577ilq.6 for ; Tue, 07 Apr 2020 05:28:16 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=m8wxu8f1kK+38ZFFGUj+STc7YtjVZZlp3ycoJaWYo00=; b=fkxWfmdqOuWe+czzPxCH+q7P5DwqD0QXRkJCI0s7i/1kJ/mwHTk4mXqiqe28MaEzAI LCy+FC4qiNOqcNbhpWHcfw3ruciOIiVEYCU9bF9NfDc3zbrD9ocnwRVnUm8H1qVTrMpo jERzuTi/aYlP68Hp4CAzB5PTESuqBHyoO5E6boWI6PejM+eknXeohtkosqFAmW9PSLHB NT9pfhStiRXZ6oLyzW1OkcI82z/km4aQHyJxTVVFzzQkK4mnqVseSyHGKHGsVhJyhKJb jByqta/5ebQtz1aQcAKh6sEF34ektcHchZnzZqXPG0fscognJp4XP1nPPZGFXvdciRoF o/YQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=m8wxu8f1kK+38ZFFGUj+STc7YtjVZZlp3ycoJaWYo00=; b=t53ZticeLxeLIsfc0VSCJr5U/G+eZbRPPhn9+JkkqmLf7IeolQ6dp8jR1XZ2Lpfya5 LicNspijUd4IuRtypaTJbWKQaoFqCbu9U4K9dxrwsVOM+bmydTgC4GU39Jzx7JFeRGbD am1kDArvRD/Wa/8XXNLATgBb6R4MUqHNYtLnMDjupKtXYTrHjIB1a7IgS36K4M4EHwI5 nSF5Fk8w206bELvLesdDlRO4cth3978W5GvTpDTdK4LV1+kFBGrf2pLZIH2u8Wc4CXv+ razDBBFw5E1PUhrKA2YvNv0p2v2+RRLWU1eNxr7BAUqBUAQDOREq8R3O6PJxir9VTonH cNbA== X-Gm-Message-State: AGi0PuZE5SrM8WAxE92D3n29jgVvMupYpuDLf+E1CTkA0EwLsw/zjQAD CkFUU5B+SHmjhQeEfrKpFT5mrEU5+T/k+bbkhhc= X-Google-Smtp-Source: APiQypLlg3v70XWsADRTunp1WrkiTQINP3TYRMcPbgCkjHhjfl+BhdF1+viLq502AJilXuZlyiXMOP7sND52xb92+qA= X-Received: by 2002:a92:8159:: with SMTP id e86mr2030908ild.60.1586262495680; Tue, 07 Apr 2020 05:28:15 -0700 (PDT) MIME-Version: 1.0 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> In-Reply-To: <097e35c5-ffb0-854c-12b6-184849f2d922@semihalf.com> From: Jerin Jacob Date: Tue, 7 Apr 2020 17:57:59 +0530 Message-ID: To: Andrzej Ostruszka Cc: dpdk-dev Content-Type: text/plain; charset="UTF-8" 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 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. > > With regards > Andrzej Ostruszka