From patchwork Thu Sep 28 12:29:29 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Shreyansh Jain X-Patchwork-Id: 29293 X-Patchwork-Delegate: ferruh.yigit@amd.com Return-Path: X-Original-To: patchwork@dpdk.org Delivered-To: patchwork@dpdk.org Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id DC6901B1EB; Thu, 28 Sep 2017 14:19:46 +0200 (CEST) Received: from NAM03-CO1-obe.outbound.protection.outlook.com (mail-co1nam03on0079.outbound.protection.outlook.com [104.47.40.79]) by dpdk.org (Postfix) with ESMTP id E00912E83 for ; Thu, 28 Sep 2017 14:19:28 +0200 (CEST) Received: from MWHPR03CA0023.namprd03.prod.outlook.com (10.175.133.161) by BN3PR03MB2353.namprd03.prod.outlook.com (10.166.74.148) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P256) id 15.20.77.7; Thu, 28 Sep 2017 12:19:27 +0000 Received: from BY2FFO11FD022.protection.gbl (2a01:111:f400:7c0c::173) by MWHPR03CA0023.outlook.office365.com (2603:10b6:300:117::33) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P256) id 15.20.56.11 via Frontend Transport; Thu, 28 Sep 2017 12:19:27 +0000 Authentication-Results: spf=fail (sender IP is 192.88.168.50) smtp.mailfrom=nxp.com; nxp.com; dkim=none (message not signed) header.d=none;nxp.com; dmarc=fail action=none header.from=nxp.com; Received-SPF: Fail (protection.outlook.com: domain of nxp.com does not designate 192.88.168.50 as permitted sender) receiver=protection.outlook.com; client-ip=192.88.168.50; helo=tx30smr01.am.freescale.net; Received: from tx30smr01.am.freescale.net (192.88.168.50) by BY2FFO11FD022.mail.protection.outlook.com (10.1.15.211) with Microsoft SMTP Server (version=TLS1_0, cipher=TLS_RSA_WITH_AES_256_CBC_SHA) id 15.20.56.11 via Frontend Transport; Thu, 28 Sep 2017 12:19:26 +0000 Received: from Tophie.ap.freescale.net ([10.232.14.39]) by tx30smr01.am.freescale.net (8.14.3/8.14.0) with ESMTP id v8SCJ722008785; Thu, 28 Sep 2017 05:19:24 -0700 From: Shreyansh Jain To: CC: , Date: Thu, 28 Sep 2017 17:59:29 +0530 Message-ID: <20170928123000.1711-10-shreyansh.jain@nxp.com> X-Mailer: git-send-email 2.9.3 In-Reply-To: <20170928123000.1711-1-shreyansh.jain@nxp.com> References: <20170928113344.12248-1-shreyansh.jain@nxp.com> <20170928123000.1711-1-shreyansh.jain@nxp.com> X-EOPAttributedMessage: 0 X-Matching-Connectors: 131510747670257882; (91ab9b29-cfa4-454e-5278-08d120cd25b8); () X-Forefront-Antispam-Report: CIP:192.88.168.50; IPV:NLI; CTRY:US; EFV:NLI; SFV:NSPM; SFS:(10009020)(6009001)(7966004)(336005)(39860400002)(39380400002)(346002)(376002)(2980300002)(1110001)(1109001)(339900001)(199003)(189002)(33646002)(5003940100001)(189998001)(47776003)(81156014)(8936002)(356003)(8676002)(81166006)(6916009)(76176999)(53936002)(2950100002)(50986999)(2906002)(2351001)(77096006)(105606002)(106466001)(498600001)(305945005)(36756003)(68736007)(50466002)(50226002)(48376002)(97736004)(1076002)(4326008)(54906003)(86362001)(104016004)(316002)(85426001)(8656003)(16586007)(5660300001); DIR:OUT; SFP:1101; SCL:1; SRVR:BN3PR03MB2353; H:tx30smr01.am.freescale.net; FPR:; SPF:Fail; PTR:InfoDomainNonexistent; A:1; MX:1; LANG:en; X-Microsoft-Exchange-Diagnostics: 1; BY2FFO11FD022; 1:19jx5QLSQhaB3aBDEM0bsOYBC5hPAB0vtN0n/spwJs37AXmitIwBNWJxMj9bWDyk7NpPkxNEu1oiy/1hkKn8gY1FNmjtr6FrA9dUHlrLQgmHz8NXrgbX2zxqxs4z0V2x MIME-Version: 1.0 X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: 48b660cc-5deb-4e5f-15d2-08d5066b296c X-Microsoft-Antispam: UriScan:; BCL:0; PCL:0; RULEID:(22001)(2017052603199)(201703131430075)(201703131517081); SRVR:BN3PR03MB2353; X-Microsoft-Exchange-Diagnostics: 1; BN3PR03MB2353; 3:E2u+y7GDc8GGfyJKkwpR1ieGLMpxJRKTHK4u4E02PQRP3puzwYV7TQf6u1vPE+ooIDUeMwjbEsL+Gem13CiPTVfOJyxthjWCZ5cv42ybeXhtloGo98HsT8+pUA31K1X9Ot27ZtUVnUKt/ezphXJBILHFMFKxhaBHAVjM2/cW/vjesiEcg8TVLQVMOBfjs40lJt0WmB2xf6gErnwEu9a+pwH8l5Zai6dzp5KMGFqB24hi4bHaJgSRMPojWHZ6QdLbWC8M+5poXdPuXsCldVW7m06m+rVh2RGmnPnY6iv3hKmUxd/0Y/gA9vU57C3gR9VJhh6Qi27WjHR+MfQky0ONlqjreKCMT2XCgS/EkEuOKUE=; 25:NUSJgFy+ObJY4ICp9jLYHJzakJtyk8IFwrr5IfU4TwVQqJJuMOSs6L1c3aKxtRaoPBR3FvR08iXwN2szuviTclD2EmExZUNm7akzTdpU53PTeHUk9LU1fl0zK+AZpBp4G1s/qMBGpnAbnNzSFAm5GapBrX9f0SiQMKI4+T7l5q5Ih/B3LAcvChyU3GBzvysCwBAEf1fnsqVcJlf81sTYPzzihNtmQ6WBP2AzIgR6Me/bKv1OnNn5Jh20lBl1EtKCN06LVt3ADHtqQ0fHhep/nwfKTJOrDg/sF3EbM1xh5ushVT1GwMi7/H2Rx8/NtkjQ/Xfy5wNrfAbnTLIK9NR9wQ== X-MS-TrafficTypeDiagnostic: BN3PR03MB2353: X-Microsoft-Exchange-Diagnostics: 1; BN3PR03MB2353; 31:PrSQq58mlPcH5rEDOWP/CxXYopu+gMoGdupPNoX0J14MTALn7IG8O4jzcQQ+KWXjg3IILGzwTiUJBlPukgV5gFCR96Y801WYE+OgbnZjVUhYU8LhpRb9LgjIso768/ZHJhFFJzzks+G5/03ZV3y8q5zQ3QncHspC9JfeWe0m/Hnt4Bwr7hjxpa9cHjR8UR5a07hrG65FnCAdgz9Rj+s4lgz7T/k0LQXfs9ObtSlpDnk=; 4:D1LEhJ7bxoeuYkmjvtXSsP07m/X7JY01rnLiu2TF12oOCo70p1CUhj+VUPPpVW8Wh/cppU1LDZoA8z4bnbcLgxZ/KCltoRx6kD+OXeAy5GjllV64M1vncmYe6kIZuOjqC9VhuqGlZ9fuTq6IZ5ENWGSQQueBG/4EHJCoMTINIUWqsClixuecct5TJmPWS+vanQ6KVV6N6fUiSn9c4C60d4vxXvmY5G3ifhzdmqA8oUws5ZivKNzwe6MdoYaASJo1JaKPWYj1LBXhjJobyR49JuigKMLHs1T3P4qKNnqCN+M= X-Exchange-Antispam-Report-Test: UriScan:(185117386973197); X-Microsoft-Antispam-PRVS: X-Exchange-Antispam-Report-CFA-Test: BCL:0; PCL:0; RULEID:(100000700101)(100105000095)(100000701101)(100105300095)(100000702101)(100105100095)(6095135)(2401047)(5005006)(8121501046)(10201501046)(3002001)(93006095)(93001095)(100000703101)(100105400095)(6055026)(6096035)(20161123556025)(20161123559100)(20161123565025)(20161123561025)(201703131430075)(201703131433075)(201703131441075)(201703131448075)(201703161259150)(20161123563025)(201708071742011)(100000704101)(100105200095)(100000705101)(100105500095); SRVR:BN3PR03MB2353; BCL:0; PCL:0; RULEID:(100000800101)(100110000095)(100000801101)(100110300095)(100000802101)(100110100095)(100000803101)(100110400095)(400006)(100000804101)(100110200095)(100000805101)(100110500095); SRVR:BN3PR03MB2353; X-Forefront-PRVS: 0444EB1997 X-Microsoft-Exchange-Diagnostics: =?us-ascii?Q?1; BN3PR03MB2353; 23:lVNWKIX6vTZkOnvLcHRPhTKYb+6bfnzq3U9nMpcks?= Y8cb422xpSlIoxrb8//ahnm1QsCL0NMHxVIGtEMBlrzx4ai1GaOgFCQGzX1enHpxgawWoU3Ad81sdRJLyFPF6rdaYMe2MZNW6RRQ1Cid47jPN06oGiu9UE3fsF9HCtBw+rBGn+lcndoXqF+mQ+4lpuqtq9ULy80mgcWmdgKWIfkh+kyAFRHeAEx/sH+JGvtq4VOUWJdosqMUzk/diYZakWnIHrf+GjDE7bOWiJmot+WNvATwDPLiC7ECCIDPvl1YFL5Qve1DL5+GV7E5xP+lq/qoY4w2Zioy5Ke2pknAJgtLqeKi2wzOSw99jNLMvxYotGj0u9i2z4JfiXHlmnet9qonn/wmjFs2Zkx5Bn8/IXtWBE4FNtZvfLrhPV606bswrq5jFaGNRLka3anULLAK/2E65VlRYT9dimYVklARA7DENFKEBXxPj5yFJkOtUS11tIP9QiMC3llsqcbgSmBi+vlWZtPYyC9ZdOJ7f1E7BtAmVeK+Rg2CSopHQvgrdYY6JYC1kcVV5gxqK54ZRGSuEh11vzcs0bZrmMl77wStsqTO3ao+HXr7uT6BlcTClGv5LBuW821cROVM+e3oNNzNTeroN/pCt+tooUv5yiBTYOd6ci0J2ktWohUpuH9hFCoOSpCvsKtLERHfambJ5VKkZ1F0h+W3WZaJwDngM1tkAGt/1TAPnc6NyBQFFV0fwuSVFcslTz9jNm6ZuXxF1VnPVr8VxolWIJjHIVvH+Vxi5SR3IzuaNiHpbDtEqODSxZ1fQnVUZdyu1yRkWoXmMWnf9Y8qxRUiUPHCG6Y6H9PI1EP9/Xw5W8bZZ5ZavLQeJt22omikE7FfcbwAVSo86AvVp6doTSaYBqB2FdG/TQ9DfK7pHsMqFndMPsj/lBK/ZcfPcMMo9VSlmd+XZY0l8zML8dl7w1Vqlhgaib5cEGdruBhz5KM4oSP8q/0GIJu8iQNBkvP6W5pVEbw8Rcpcr5WdQmRBAZW6VqJede3fBjb/I0RdPwIp2TwLsojV+a7HM9YdSGfj1azNg/nAdCyjmZJ2SS2w4ELSlqx3CnZaFBCryHEBUmiBf7u6zp25IIl1L3wSX5HS8dC/lo943Hav1y0gWp+e21lAcFaXGTEnWUSplsXSXb26aQKSINXN3otaIrQ9yA= X-Microsoft-Exchange-Diagnostics: 1; BN3PR03MB2353; 6:YPHSLYXPAOHljfYAODTnsXb+kxDHMc5j7i7U9gV5VlflQUyK3FfUUJKzEBJipc0UKnuG+ChzJE3dGp2+RzsS0KZ0SjXmfaXggwv29jg64r12a4aZz/Ci07JwtRKWDEbGh5/n0YbLK5H7IrvAcRJ8AhqfVA+aVz5Kjlbd7iJsLxfFq7ywyoeScZqZiM78myaLDFUk/N+gB6Fe3sTJnnTRXqYtJx9JfVQrR96PqFqkf8W25wQcZ08zb3+bBxWQSA+crPxPEwxzwIf7qsaVljHwp9rSDwweG7dz0cOxg+lyCCbovUpr39hzv4iMm9nOmeGaNbR5JLFkzLGBdPi8PVRL7g==; 5:9jR7jOY2+dchub83EEhtJATRVVePunMVO64vL6ln2s5e9o9ofMnaf/fi6VPVuvg7NW1P0HDxl+G0J6KV7TFj0rMoBf9I1Xv8VXhnNoxJDNId3wnid+cwXRiQjB/zv3zABPiWXVQCobp8Oj8C4QQp6Q==; 24:Sq6P77wsoDu1kuTNOBLV9w5HKCDnkIRVWdTOXrOsZplIcJDfRm+rs4Nl9LUce9F5uUeAJmfYhgNf8j6YNpfh14i9wMSwY6ftpzrTq44rw20=; 7:4rzTSIlyEgQn4s8LBgl1bxajpyyRE10YG1lryoqsKgjhCmgPI0ls8r0S/kYipzUJZe52ILgObnX9VIWNYx935M9LsVEVe6NWZv7tF1wMH7tWz8qh6iPHmzJ8FrX6ZfQsq92ZbWmwQDbOuFtufMbi3s7AFWLI1TW5D8YteM0Tf1pu+c+QbhQSXaYeGc3GqOTPY4wunMIuH2Huddd0N8yF2VcJuqzbsYb3Sk3oE30/PX0= SpamDiagnosticOutput: 1:99 SpamDiagnosticMetadata: NSPM X-MS-Exchange-CrossTenant-OriginalArrivalTime: 28 Sep 2017 12:19:26.7137 (UTC) X-MS-Exchange-CrossTenant-Id: 5afe0b00-7697-4969-b663-5eab37d5f47e X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=5afe0b00-7697-4969-b663-5eab37d5f47e; Ip=[192.88.168.50]; Helo=[tx30smr01.am.freescale.net] X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: BN3PR03MB2353 Subject: [dpdk-dev] [PATCH v6 09/40] bus/dpaa: add routines for managing a RB tree 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" QMAN frames are managed over a RB tree data structure. This patch introduces necessary routines for implementing a RB tree. Signed-off-by: Geoff Thorpe Signed-off-by: Hemant Agrawal Signed-off-by: Shreyansh Jain --- drivers/bus/dpaa/include/dpaa_rbtree.h | 143 +++++++++++++++++++++++++++++++++ 1 file changed, 143 insertions(+) create mode 100644 drivers/bus/dpaa/include/dpaa_rbtree.h diff --git a/drivers/bus/dpaa/include/dpaa_rbtree.h b/drivers/bus/dpaa/include/dpaa_rbtree.h new file mode 100644 index 0000000..f8c9b59 --- /dev/null +++ b/drivers/bus/dpaa/include/dpaa_rbtree.h @@ -0,0 +1,143 @@ +/*- + * BSD LICENSE + * + * Copyright 2017 NXP. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * * Neither the name of NXP nor the names of its + * contributors may be used to endorse or promote products derived + * from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __DPAA_RBTREE_H +#define __DPAA_RBTREE_H + +#include +/************/ +/* RB-trees */ +/************/ + +/* Linux has a good RB-tree implementation, that we can't use (GPL). It also has + * a flat/hooked-in interface that virtually requires license-contamination in + * order to write a caller-compatible implementation. Instead, I've created an + * RB-tree encapsulation on top of linux's primitives (it does some of the work + * the client logic would normally do), and this gives us something we can + * reimplement on LWE. Unfortunately there's no good+free RB-tree + * implementations out there that are license-compatible and "flat" (ie. no + * dynamic allocation). I did find a malloc-based one that I could convert, but + * that will be a task for later on. For now, LWE's RB-tree is implemented using + * an ordered linked-list. + * + * Note, the only linux-esque type is "struct rb_node", because it's used + * statically in the exported header, so it can't be opaque. Our version doesn't + * include a "rb_parent_color" field because we're doing linked-list instead of + * a true rb-tree. + */ + +struct rb_node { + struct rb_node *prev, *next; +}; + +struct dpa_rbtree { + struct rb_node *head, *tail; +}; + +#define DPAA_RBTREE { NULL, NULL } +static inline void dpa_rbtree_init(struct dpa_rbtree *tree) +{ + tree->head = tree->tail = NULL; +} + +#define QMAN_NODE2OBJ(ptr, type, node_field) \ + (type *)((char *)ptr - offsetof(type, node_field)) + +#define IMPLEMENT_DPAA_RBTREE(name, type, node_field, val_field) \ +static inline int name##_push(struct dpa_rbtree *tree, type *obj) \ +{ \ + struct rb_node *node = tree->head; \ + if (!node) { \ + tree->head = tree->tail = &obj->node_field; \ + obj->node_field.prev = obj->node_field.next = NULL; \ + return 0; \ + } \ + while (node) { \ + type *item = QMAN_NODE2OBJ(node, type, node_field); \ + if (obj->val_field == item->val_field) \ + return -EBUSY; \ + if (obj->val_field < item->val_field) { \ + if (tree->head == node) \ + tree->head = &obj->node_field; \ + else \ + node->prev->next = &obj->node_field; \ + obj->node_field.prev = node->prev; \ + obj->node_field.next = node; \ + node->prev = &obj->node_field; \ + return 0; \ + } \ + node = node->next; \ + } \ + obj->node_field.prev = tree->tail; \ + obj->node_field.next = NULL; \ + tree->tail->next = &obj->node_field; \ + tree->tail = &obj->node_field; \ + return 0; \ +} \ +static inline void name##_del(struct dpa_rbtree *tree, type *obj) \ +{ \ + if (tree->head == &obj->node_field) { \ + if (tree->tail == &obj->node_field) \ + /* Only item in the list */ \ + tree->head = tree->tail = NULL; \ + else { \ + /* Is the head, next != NULL */ \ + tree->head = tree->head->next; \ + tree->head->prev = NULL; \ + } \ + } else { \ + if (tree->tail == &obj->node_field) { \ + /* Is the tail, prev != NULL */ \ + tree->tail = tree->tail->prev; \ + tree->tail->next = NULL; \ + } else { \ + /* Is neither the head nor the tail */ \ + obj->node_field.prev->next = obj->node_field.next; \ + obj->node_field.next->prev = obj->node_field.prev; \ + } \ + } \ +} \ +static inline type *name##_find(struct dpa_rbtree *tree, u32 val) \ +{ \ + struct rb_node *node = tree->head; \ + while (node) { \ + type *item = QMAN_NODE2OBJ(node, type, node_field); \ + if (val == item->val_field) \ + return item; \ + if (val < item->val_field) \ + return NULL; \ + node = node->next; \ + } \ + return NULL; \ +} + +#endif /* __DPAA_RBTREE_H */