From patchwork Thu Sep 28 11:33:13 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Shreyansh Jain X-Patchwork-Id: 29253 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 AA3DE1B1BF; Thu, 28 Sep 2017 13:23:36 +0200 (CEST) Received: from NAM01-SN1-obe.outbound.protection.outlook.com (mail-sn1nam01on0053.outbound.protection.outlook.com [104.47.32.53]) by dpdk.org (Postfix) with ESMTP id 4ADCC1B1A7 for ; Thu, 28 Sep 2017 13:23:15 +0200 (CEST) Received: from BN6PR03CA0064.namprd03.prod.outlook.com (10.173.137.26) by CO2PR03MB2360.namprd03.prod.outlook.com (10.166.93.20) 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 11:23:13 +0000 Received: from BN1AFFO11FD025.protection.gbl (2a01:111:f400:7c10::125) by BN6PR03CA0064.outlook.office365.com (2603:10b6:404:4c::26) 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 11:23:12 +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 BN1AFFO11FD025.mail.protection.outlook.com (10.58.52.85) 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 11:23:12 +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 v8SBMpFj016035; Thu, 28 Sep 2017 04:23:10 -0700 From: Shreyansh Jain To: CC: , Date: Thu, 28 Sep 2017 17:03:13 +0530 Message-ID: <20170928113344.12248-10-shreyansh.jain@nxp.com> X-Mailer: git-send-email 2.9.3 In-Reply-To: <20170928113344.12248-1-shreyansh.jain@nxp.com> References: <20170909112132.13936-1-shreyansh.jain@nxp.com> <20170928113344.12248-1-shreyansh.jain@nxp.com> X-EOPAttributedMessage: 0 X-Matching-Connectors: 131510713930938628; (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)(336005)(7966004)(376002)(39860400002)(346002)(39380400002)(2980300002)(1109001)(1110001)(339900001)(199003)(189002)(85426001)(5660300001)(86362001)(106466001)(68736007)(4326008)(8656003)(33646002)(50226002)(2906002)(1076002)(189998001)(50986999)(53936002)(2351001)(47776003)(76176999)(2950100002)(6916009)(5003940100001)(316002)(16586007)(50466002)(8676002)(48376002)(81166006)(81156014)(54906003)(104016004)(356003)(305945005)(97736004)(77096006)(498600001)(105606002)(8936002)(36756003); DIR:OUT; SFP:1101; SCL:1; SRVR:CO2PR03MB2360; H:tx30smr01.am.freescale.net; FPR:; SPF:Fail; PTR:InfoDomainNonexistent; A:1; MX:1; LANG:en; X-Microsoft-Exchange-Diagnostics: 1; BN1AFFO11FD025; 1:9xv623IKAwEoyBKeMX8Jk66qHW5aFpjbnm0uBurFy4mmwljrxBQeAJrInfDteT+p29+q/Syy2/19hxWxOQwcItyVTgZbVHOj1dCrgXIVx9iswsVER7l18l0m46MisChi MIME-Version: 1.0 X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: f3a3c66a-5bea-47ba-97a3-08d506634e77 X-Microsoft-Antispam: UriScan:; BCL:0; PCL:0; RULEID:(22001)(2017052603199)(201703131430075)(201703131517081); SRVR:CO2PR03MB2360; X-Microsoft-Exchange-Diagnostics: 1; CO2PR03MB2360; 3:TW1C3K+EXi1ArEN3UKVj/DXy9GDcJLgycN5Sx/skyha/hYPPF6mX5nBfiuUvYEPeOPGwuYu1voDQeyT3y9kF8EmodxlogFN7dYlFF9J005uIrfGy6uGdyQ2A5VtcV+zi6t5nELCCr5wZaubOOMbOlMzfDIIr2eM2luPWsi6jQDoRcpKHNyfqgWLMLSXi1wkV2DmBy2pBbRmxzH7iky19LR73FIALqxZQ5nnZhJ38SqTfbA1/4mD7AflGZ4LjjmTLLS9YyV2VVg2FtfyodbLf0bX7IF1+KFAhpG84ZgTvpnJgK/UT5BKf7CB6gSPREvsS6zMfhJp8W3/b94GTwCVjzIqLew6pE8A1Zv5+a7TLVu4=; 25:kn/PJ4JtAyfxR+KCtdrcv/39BzKu14FkJfydMQ/UQf4VKtB7wxt3rV/DaAUv30QsPibFnjybrzpB47OCbyhToE2ktoUxWheYVvnWnu+g8gOEBCTRjYGb6Rky8HEb+q08HdFBJUe5ogVLEnJFVl/c+Bf+Sgl20injtRxqFAGH0Z4wzZd9YGx1eQyDtv0NDgJroXjQvsX8rf1myBdD/FlOEwRaAmpsIDpG2geKNYqb1pubgQm4Qq1u2wnCkXpxTIuZ9BYqJDWCwyh43Vwx8Aw3xd9Q7c20c0Mt49V/XxvEFa6+fBac8o9+iga9LCBrHJNy4ImkfxBNnlCYB2UI6Oz1/w== X-MS-TrafficTypeDiagnostic: CO2PR03MB2360: X-Microsoft-Exchange-Diagnostics: 1; CO2PR03MB2360; 31:Hw/8i3FD7T3EanNViIgSBDeHD75ZGmHaTgmzXdlFeRkfoEcnxlhzS9DD2a0FlEa65Z1EcLiI8Nr0SgjOIDUHHbs3dRhRKzrAX7pbJP6hdOiljBbY7JU1SpSekpsfgRt2flHniqt+N8mz16CVkZrxGiH9UMLA/HkYWHJO8NdMJYLn9P5Ejgskr5x+73LL9m6MP5umG2cbhWoIIkEJ94/G2lxn7m3N9HO9Qupe2qJ5bpc=; 4:FFrVDzMdxJVGMg1BlaVTgs5lCO1EAkoqF/hyTxjJytr8cVJgeSSHSgw+I2QjDxLSKUDPBQ7A6CVJeS/Y94gZ/diCcaZ82QGCwUHGmGa8ZkQKmsoQhcOQQnYswREQ17bh6J0Dz+OFrrDT+5aPE5KiEw1smdzefqQTyAzuAA4i6D+kNYRKaK6COHSoquQFj9YhkHBqnO8uEBOhLp0fe1n1TeWZswGjLIpTLPUzsuuUX+IvStvYX0rLNR8+UtezyCx0wF6S2H3o1cTXcWWMdd+DUIiFl/QWNxgWxxNe54lCKQo= 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)(100000703101)(100105400095)(93006095)(93001095)(10201501046)(3002001)(6055026)(6096035)(201703131430075)(201703131441075)(201703131448075)(201703131433075)(201703161259150)(20161123559100)(20161123561025)(20161123563025)(20161123556025)(20161123565025)(201708071742011)(100000704101)(100105200095)(100000705101)(100105500095); SRVR:CO2PR03MB2360; BCL:0; PCL:0; RULEID:(100000800101)(100110000095)(100000801101)(100110300095)(100000802101)(100110100095)(100000803101)(100110400095)(400006)(100000804101)(100110200095)(100000805101)(100110500095); SRVR:CO2PR03MB2360; X-Forefront-PRVS: 0444EB1997 X-Microsoft-Exchange-Diagnostics: =?us-ascii?Q?1; CO2PR03MB2360; 23:Fz6LvIfSEMfqiDKOVj0QK3isQMcMWWZcBEtVt+mfD?= xppnqeH+k8/dtxo/xPMaIsbAFsbrd4CodO1B5QRuNistqOtCbGIaTLtRb0e2S7fC7ZzEOt8fGPkiuZt7MHd181DhwGAPd9x8007ZcmWlUkFMgXB2LH/4RqmucnkMelNhuj6kgaCjHgRiW6nJiLOlj+P01ELjXcwDcSsaXzFLNGEiQIzZCzRORF7bK76UXXYRkbIx4dLP2qyJTD3htdvqeK/VRyqcTWeTMx4cMl6n2IX3id/KL/9q023sKU+8r/WKNCrbC+34Accs9vfGp5F9/LUD+pFGQPHMB2D4C5vk9MjnogFxSx1k3gVtM8S1YWfq99/G7s6KLfLlxqlw/qrLX/Vd/AcwA8s82YlujSe8c/nk3IW4DzuuBiICyldKEKiXbeBQg2ifxSUteB9L0OjVYbmHWCHY0oUDsyld0O2NWBqQPGRg27/Bs9+ap1GqS9Jt+fiRBLT5NkLkH87VS8gnBYOd05Pu/ISBnGJibIOOSzcdSF9PXfgIbQeOruhLC3Yhd8N9Z653Bq/evGjzExiSfMzIggfwiudjwfhkR40d/OAtJDG+VOKpd08YLudljNA7JFa0fyxJt+TuhrjeYWp+SWV3UzqKQ5v90Io4Y1nGrbo0np2NYJpNd2MVeQq3wxQIY6sn53o8TJ0ftzKb6tsW4suQi/2hml7qBJuJZqpyrgu7O6eYXXEkI0WqUh889oE45qkolyvNLFeTCjLggTSM39eG5T7lW1zhm3oaxcpChkZDmVdQ9v6J4pVEMUamKRLrMZwkRjLetK7KOZoUfdv0JP2ydymCccdkkWaDtJY2mIaQriWWhi7m9Ybf6jTHni8lIlzCBgm9UcTI1YJTLaeCMARLRrtebHVPp9ZQCf0Zzbq6BKiSYjCjx9wBfRFFuZLNQ6BoDza7Lt3jrIk2K7D65DSiRCGqKSRnIc3Pt9ZCNy6VqRQALtAV8q1CywgqXVyb9pNAuI3hawlJUiBA12gT2MsU4J9UsVn3BLbnP30mV077IFzhorQe37KkPZ1essIp9uO7PvENkdc25wJ1ZmX9P+TH7TYq2OWdGeie5QWwPUJc5id0P/x0MMJgK/FhOmSxXcAS3YRKekGzvUXs6qLyAvVZnAGFuf2bX/BI73z0U2QS2oF51qYfk6Ne5b0GbSHILs= X-Microsoft-Exchange-Diagnostics: 1; CO2PR03MB2360; 6:wopGkKqaLe4aEt9t6DUNzN6GXVGMKYaSqFmvMVaJ0payqEjroyighhyBkhdJDj5mUE15PlgLU0eApNimeGrp7RYmgvr44UO89iD7n0PA6lwmcih/y8HwV6oXhVGqSrUMR9zbOJToNxRQN4nD4qzNJmoI9wIWb73NRHc71KIfxXrJXWlUjjP7E7BtfgqLg5L4+M4WYCTZs+SOTku0s/5b0YciLy4s+5Lh/jaaDMmiBuosam92HNM+rFXTNb09DoR2fh/GvucItKHc8QPRniRRIesFpdO9iZ6ghA7nZ4QoOHwx1oSI9Z10UMDhOOsAD3Mox4aStMvexnHPVvLqrtRk5Q==; 5:OU//hI/+sWa2aZXn96qQ0Crbqs4uoeFoEuK8gk0y/KLiOy3Sen9BjxsB33+xD8Wp66Phkv38uaads5Hg7VJuCWnLa6233HUrcUH98i13T+dDS46MQoyhHog83xybJRW6qAyE2AxBUNIlloAQ15hsHw==; 24:q1FDX/Fjy2CfO2dcKIuQ82tohqVp4pyluX/1F93BnW25fALvc4mOJfXkZpqRsRAT12KqkhQfBF0fOqNY8vwGWoYOwr88h/y6HECMiKjggXE=; 7:AsW92+9n6R1ynMhb1ji9MKVXoGOwJ1PyWwb6JQzc2IjbvOpRVMfqd/ttgZrMgw73pp1Bws7R2GY/NaERYJJa1Kd6sZTSdExQh6ig0raUIVEDGhKF1bhkjscpWUYRsYRkI017Zhq/OZjCMicRxUD0BjKvUcZiEDJc7uQXzhsbxb52t3cltoPgYTdcckd6hTfFAXfSv/T2iSIsfmMFyDPvu7LxP0/w04i8dZz79AVuXik= SpamDiagnosticOutput: 1:99 SpamDiagnosticMetadata: NSPM X-MS-Exchange-CrossTenant-OriginalArrivalTime: 28 Sep 2017 11:23:12.9066 (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: CO2PR03MB2360 Subject: [dpdk-dev] [PATCH v5 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 */