From patchwork Tue Jan 29 13:09:55 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ilya Maximets X-Patchwork-Id: 1032727 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=openvswitch.org (client-ip=140.211.169.12; helo=mail.linuxfoundation.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=samsung.com Authentication-Results: ozlabs.org; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=samsung.com header.i=@samsung.com header.b="st6PUBNa"; dkim-atps=neutral Received: from mail.linuxfoundation.org (mail.linuxfoundation.org [140.211.169.12]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 43pn7B4Thfz9sNJ for ; Wed, 30 Jan 2019 00:15:50 +1100 (AEDT) Received: from mail.linux-foundation.org (localhost [127.0.0.1]) by mail.linuxfoundation.org (Postfix) with ESMTP id 86FE32ED9; Tue, 29 Jan 2019 13:15:47 +0000 (UTC) X-Original-To: ovs-dev@openvswitch.org Delivered-To: ovs-dev@mail.linuxfoundation.org Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 8DC042E5B for ; Tue, 29 Jan 2019 13:10:06 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mailout2.w1.samsung.com (mailout2.w1.samsung.com [210.118.77.12]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 3701A1FB for ; Tue, 29 Jan 2019 13:10:04 +0000 (UTC) Received: from eucas1p1.samsung.com (unknown [182.198.249.206]) by mailout2.w1.samsung.com (KnoxPortal) with ESMTP id 20190129131003euoutp0231bd00e1fca65bf689ce575b66c66a84~_U79Xs86o1096510965euoutp02N for ; Tue, 29 Jan 2019 13:10:03 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 mailout2.w1.samsung.com 20190129131003euoutp0231bd00e1fca65bf689ce575b66c66a84~_U79Xs86o1096510965euoutp02N DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=samsung.com; s=mail20170921; t=1548767403; bh=ruYhJPc4dYGntIdL8MGGpBaLcjBJXJ4GzvtEdgC2kEI=; h=From:To:Cc:Subject:Date:References:From; b=st6PUBNah/wdi7OmTHrP2LtLPbmNIj0eTiomlHqw+93M/xUgIbsKOWP984EGdwou5 Y0o6XERfY0nJmHP6PPWRKlDs7baCtLquUyRNZnXD3xIs8WzdF+GHj0SV59dqEuDkgY rG6MC61KybBKoVhYy54v5OPCCKaNum7zovqJzY0U= Received: from eusmges3new.samsung.com (unknown [203.254.199.245]) by eucas1p1.samsung.com (KnoxPortal) with ESMTP id 20190129131002eucas1p1424a0417f3726095136db8751d514026~_U7874dGP3130631306eucas1p1g; Tue, 29 Jan 2019 13:10:02 +0000 (GMT) Received: from eucas1p2.samsung.com ( [182.198.249.207]) by eusmges3new.samsung.com (EUCPMTA) with SMTP id 79.61.04806.AA0505C5; Tue, 29 Jan 2019 13:10:02 +0000 (GMT) Received: from eusmtrp2.samsung.com (unknown [182.198.249.139]) by eucas1p1.samsung.com (KnoxPortal) with ESMTPA id 20190129131001eucas1p1345da99be71739a72602d747528014fd~_U78HsiQE1791517915eucas1p1Z; Tue, 29 Jan 2019 13:10:01 +0000 (GMT) Received: from eusmgms2.samsung.com (unknown [182.198.249.180]) by eusmtrp2.samsung.com (KnoxPortal) with ESMTP id 20190129131001eusmtrp2c38517a2dd98da06d34b3e90904264a9~_U775UmRZ2336923369eusmtrp2W; Tue, 29 Jan 2019 13:10:01 +0000 (GMT) X-AuditID: cbfec7f5-79db79c0000012c6-56-5c5050aadc2b Received: from eusmtip2.samsung.com ( [203.254.199.222]) by eusmgms2.samsung.com (EUCPMTA) with SMTP id D9.BE.04128.9A0505C5; Tue, 29 Jan 2019 13:10:01 +0000 (GMT) Received: from imaximets.rnd.samsung.ru (unknown [106.109.129.180]) by eusmtip2.samsung.com (KnoxPortal) with ESMTPA id 20190129131000eusmtip2eb5c28aabed187f433ac9b2d40fa053f~_U77OVogQ0115201152eusmtip21; Tue, 29 Jan 2019 13:10:00 +0000 (GMT) From: Ilya Maximets To: ovs-dev@openvswitch.org, Ben Pfaff Date: Tue, 29 Jan 2019 16:09:55 +0300 Message-Id: <20190129130955.28197-1-i.maximets@samsung.com> X-Mailer: git-send-email 2.17.1 X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFnrCIsWRmVeSWpSXmKPExsWy7djP87qrAgJiDF5sE7Z4NbmB0aKh6TyT xZX2n+wWM1b8YbWY++k5owOrx65djewez27+Z/R4fq2HxeP9vqtsHn1bVjEGsEZx2aSk5mSW pRbp2yVwZezoX8JaMEuw4lrjEvYGxmncXYycHBICJhKrTx9h7GLk4hASWMEocbmnE8r5wigx +egVdpAqIYHPjBKvDsfBdHzb848Fomg5o8SlLRegnB+MEqcWfGEEqWIT0JE4tfoImC0C1LFs 6jc2kCJmgVZGiRN9f4DGcnAICzhLLOqQAqlhEVCVOPf7NFg9r4C1xIGzt5ggtslLrN5wgBnC PsEmseGyMoTtIrF9/itWCFtY4tXxLewQtozE/53zoXrrJe63vAR7R0Kgg1Fi+qF/UAl7iS2v z4HdwCygKbF+lz5E2FHi64QmsLCEAJ/EjbeCIGFmIHPStunMEGFeiY42IYhqFYnfB5dDXSYl cfPdZ6gLPCQm/5zFDAm3WImZixawTWCUm4WwawEj4ypG8dTS4tz01GLjvNRyveLE3OLSvHS9 5PzcTYzAuD/97/jXHYz7/iQdYhTgYFTi4TVg848RYk0sK67MPcQowcGsJMJr+BsoxJuSWFmV WpQfX1Sak1p8iFGag0VJnLea4UG0kEB6YklqdmpqQWoRTJaJg1OqgTE9yzA2Iy+LQ1CEa49m KGdllGrcEva9sjp3l884b9s97cLNyLC7T+KZFxvMZNP5IZ8UIDFZ3/a8kENtXkCeYIf4N9OK p3933RFaVHnixjpntuNcljVL/3XGnz9wfN21vskSrwx322c8+9NeUzn95XaJCzHuHz6Zzygo 0DC9vzirPUi/a/fNr0osxRmJhlrMRcWJAFJmEvn3AgAA X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFtrNLMWRmVeSWpSXmKPExsVy+t/xe7orAwJiDLqXyFi8mtzAaNHQdJ7J 4kr7T3aLGSv+sFrM/fSc0YHVY9euRnaPZzf/M3o8v9bD4vF+31U2j74tqxgDWKP0bIryS0tS FTLyi0tslaINLYz0DC0t9IxMLPUMjc1jrYxMlfTtbFJSczLLUov07RL0Mnb0L2EtmCVYca1x CXsD4zTuLkZODgkBE4lve/6xdDFycQgJLGWUODZ5GitEQkrix68LULawxJ9rXWwQRd8YJd7d nM0EkmAT0JE4tfoIYxcjB4eIgJnEln+WIDXMAu2MErNbnoLFhQWcJRZ1SIGUswioSpz7fZoR xOYVsJY4cPYWE8R8eYnVGw4wT2DkWcDIsIpRJLW0ODc9t9hIrzgxt7g0L10vOT93EyMw4LYd +7llB2PXu+BDjAIcjEo8vAZs/jFCrIllxZW5hxglOJiVRHgNfwOFeFMSK6tSi/Lji0pzUosP MZoCLZ/ILCWanA+MhrySeENTQ3MLS0NzY3NjMwslcd7zBpVRQgLpiSWp2ampBalFMH1MHJxS DYxdEQ8/Va3/6z07Loh7Y9Ca1nW7dmyV2KU4P49lgYPLzD2PKipvyUypvrKv5arkZNEJGYIT Hu1RT8xQMVpUfkJXuNgrwfduzYHDb44bJOfk3Z357/3yniAh9ZaH2cV7mZ/sV+dNsji9dYvo nvTMlTnGx6r/NTzSK1VYMW+J6uKCS4HvHSVNK6OVWIozEg21mIuKEwHj8eGfTgIAAA== X-CMS-MailID: 20190129131001eucas1p1345da99be71739a72602d747528014fd X-Msg-Generator: CA X-RootMTR: 20190129131001eucas1p1345da99be71739a72602d747528014fd X-EPHeader: CA CMS-TYPE: 201P X-CMS-RootMailID: 20190129131001eucas1p1345da99be71739a72602d747528014fd References: X-Spam-Status: No, score=-7.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, RCVD_IN_DNSWL_HI autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Cc: Ilya Maximets , Lance Richardson , Esteban Rodriguez Betancourt Subject: [ovs-dev] [PATCH] skiplist: Drop data comparison in skiplist_delete. X-BeenThere: ovs-dev@openvswitch.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Sender: ovs-dev-bounces@openvswitch.org Errors-To: ovs-dev-bounces@openvswitch.org Current version of 'skiplist_delete' uses data comparator to check if the node that we're removing exists on current level. i.e. our node 'x' is the next of update[i] on the level i. But it's enough to just check pointers for that purpose. Here is the small example of how the data structures looks at this moment: i a b c x d e f 0 [ ]>[ ]>[*] ---> [ ] ---> [#]>[ ]>[ ] 1 [ ]>[*] -------> [ ] -------> [#]>[ ] 2 [ ]>[*] -------> [ ] -----------> [#] 3 [ ]>[*] ------------------------> [ ] 4 [*] ----------------------------> [ ] 0 1 2 3 4 update[] = { c, b, b, b, a } x.forward[] = { d, e, f } c.forward[0] = x b.forward[1] = x b.forward[2] = x b.forward[3] = f a.forward[4] = f Target: i a b c d e f 0 [ ]>[ ]>[*] ------------> [#]>[ ]>[ ] 1 [ ]>[*] --------------------> [#]>[ ] 2 [ ]>[*] ------------------------> [#] 3 [ ]>[*] ------------------------> [ ] 4 [*] ----------------------------> [ ] c.forward[0] = x.forward[0] = d b.forward[1] = x.forward[1] = e b.forward[2] = x.forward[2] = f b.forward[3] = f a.forward[4] = f i.e. we're updating forward pointers while update[i].forward[i] == x. Signed-off-by: Ilya Maximets --- lib/skiplist.c | 4 +--- 1 file changed, 1 insertion(+), 3 deletions(-) diff --git a/lib/skiplist.c b/lib/skiplist.c index 2cea6d8df..ed33e97bb 100644 --- a/lib/skiplist.c +++ b/lib/skiplist.c @@ -190,9 +190,7 @@ skiplist_delete(struct skiplist *list, const void *value) if (x && list->cmp(x->data, value, list->cfg) == 0) { for (i = 0; i <= list->level; i++) { - if (!update[i]->forward[i] || - list->cmp(update[i]->forward[i]->data, value, - list->cfg) != 0) { + if (update[i]->forward[i] != x) { break; } update[i]->forward[i] = x->forward[i];