From patchwork Fri Jun 16 05:40:40 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Shreyansh Jain X-Patchwork-Id: 25376 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@dpdk.org Delivered-To: patchwork@dpdk.org Received: from [92.243.14.124] (localhost [IPv6:::1]) by dpdk.org (Postfix) with ESMTP id 1CBF37CD5; Fri, 16 Jun 2017 07:32:59 +0200 (CEST) Received: from NAM01-BN3-obe.outbound.protection.outlook.com (mail-bn3nam01on0081.outbound.protection.outlook.com [104.47.33.81]) by dpdk.org (Postfix) with ESMTP id A6BF37CC7 for ; Fri, 16 Jun 2017 07:32:47 +0200 (CEST) Received: from DM5PR03CA0044.namprd03.prod.outlook.com (10.174.189.161) by BN3PR0301MB1186.namprd03.prod.outlook.com (10.160.156.148) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id 15.1.1178.14; Fri, 16 Jun 2017 05:32:46 +0000 Received: from BN1AFFO11FD016.protection.gbl (2a01:111:f400:7c10::105) by DM5PR03CA0044.outlook.office365.com (2603:10b6:4:3b::33) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id 15.1.1178.14 via Frontend Transport; Fri, 16 Jun 2017 05:32:45 +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 BN1AFFO11FD016.mail.protection.outlook.com (10.58.52.76) with Microsoft SMTP Server (version=TLS1_0, cipher=TLS_RSA_WITH_AES_256_CBC_SHA) id 15.1.1157.12 via Frontend Transport; Fri, 16 Jun 2017 05:32:45 +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 v5G5WNF9001003; Thu, 15 Jun 2017 22:32:43 -0700 From: Shreyansh Jain To: CC: , Date: Fri, 16 Jun 2017 11:10:40 +0530 Message-ID: <1497591668-3320-11-git-send-email-shreyansh.jain@nxp.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1497591668-3320-1-git-send-email-shreyansh.jain@nxp.com> References: <1497591668-3320-1-git-send-email-shreyansh.jain@nxp.com> X-EOPAttributedMessage: 0 X-Matching-Connectors: 131420647654319965; (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)(39840400002)(39410400002)(39400400002)(39850400002)(39860400002)(39380400002)(39450400003)(2980300002)(1109001)(1110001)(339900001)(199003)(189002)(9170700003)(85426001)(6916009)(48376002)(36756003)(33646002)(5660300001)(2950100002)(2906002)(104016004)(356003)(5003940100001)(38730400002)(105606002)(8936002)(4326008)(86362001)(81166006)(106466001)(189998001)(50226002)(77096006)(50986999)(110136004)(76176999)(47776003)(2351001)(8676002)(54906002)(50466002)(53936002)(305945005)(498600001)(8656002); DIR:OUT; SFP:1101; SCL:1; SRVR:BN3PR0301MB1186; H:tx30smr01.am.freescale.net; FPR:; SPF:Fail; MLV:ovrnspm; A:1; MX:1; PTR:InfoDomainNonexistent; LANG:en; X-Microsoft-Exchange-Diagnostics: 1; BN1AFFO11FD016; 1:v7slTKAbyJ+lRBphg2L2M1iLAz9HtnsqcDXhnT5UsptyvlMo5+6IKR7Sg+VWLrIWbwlVK4Mb4P9aRThaF5HhS99lsfFqgrA5oiGVtAGbHynND9oBfLmqYQj4KqdRJiw3mUyDQlhqxfCmpAFX25yTqRoGZeYrhgrNt968pfOha6ymC5EHMF7t3KwM/9P9qMIU1urYcg9TIJGOmjTzUHaR7+HXFOpLftwOM3QFy1Vka8lDO2jsp/9aK/KZeHdDsOmUXOfHb+d2nLWb1+WmOGU9Vkhf9ToWsUwQlFpJq4wP8204iVSFaAeakCfX/9UYjjXpyED7XSl4gjDWutNNgzRX7gQsN21Uau63/aOAo9IbDtlED+HmR9nQWTtgBTqjc/aKHiOifvxLK/6vq/IHDtiARqjuv+qiQ+yHPTF1SHd5nBimhQ72fw7SzvhRcEHIBev8CzUdPITqtA0pq3cY1U04AJgVhtP+pkyrzYymTymktf1XimR0wbbhXbJvuH7+QbQ0NAzVcRxJ7YL4z7cGHU++WPDfqKDB9P1kHmsaIWU89c3QAvWrv04Pe5aWWc+eJIPiTLK/757AwUvMGZgZqo0TWZe22ddz9enGmGn8Wg5avw8509xQoy9wCL8iDymrKLSS+XE4Cad+bZOmkq1nGMK1bpsSPRmYN0uGDx4deJaCVupAJtvU4uZwKf/HByFy9BH95VS+p36blHFDLUQsk4BWf99KAfNdLxk3V2Wjt1u/Ix8= MIME-Version: 1.0 X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: fbf3e80b-a002-4996-5c55-08d4b4791dfa X-Microsoft-Antispam: UriScan:; BCL:0; PCL:0; RULEID:(22001)(201703131430075)(201703131517081); SRVR:BN3PR0301MB1186; X-Microsoft-Exchange-Diagnostics: 1; BN3PR0301MB1186; 3:Yl4VSGahJETBGJrz3Ca6B7XoA/IzTS7LEJ79xhXFyYIzbhcXsBbdO1YU7A+OOzh+lemYu84DAoij67q+3Hi3hzhkzEgSdm0x8PZc6mdPphk5H+q0puoCCMOwOn+OGmczGfaEkj7y5EKkDoIx6tGZnElaFUqqtdeItonITEFiv5VRSb8cF4fOC2RLAEBMwT24kaJQl80xomdsV9Fq55GbKOJvZaed193UMyF8jjLqfAua67ExElxpBFOQhaLERS3p30BqFZhr0TocnfGVCYGQoxfB7mpZkGx120uv8MZU3qO5UbqA0KVxGreyLumpfKYM1qaGaO/StaFyqRfpaCf1i9SCCl8MnVJFQ94/bkhp6MjfVNmwR2Xu6XK51KF2vIvXSCRAUi7jWbWKlwABsn/ENZsa1For2DBtazX1+noil0IZ7aDknsjPEHf/aSgZRJC3; 25:n6D8p+Vl5HNExDXG+J3zrWmaxEYFbavjcO4OCABY9saeIJu1ylGbxb0FdnxXLPqWcfGfo5zkCaVyJdgUPldcvt/KUfYxMIZGppD3IQ1ilrOjwqfDCDDtR+iqJJkMlF/oqUy/SSnzrhTYwdDtEzzTiYEag6I43b97o1cfs8DgpvwlxZDR6lEACHNL6UB8Qenl3GboUzI3NhfE8QDw6xmaMRizilfnXO6Bz3E/rAevk2EKFRgSYNcCC2C2vsC+bTTbxlPcb3S327fusbLIUwjgEbIkBCuaAsOpL9D01f51H23DloJnsnCgPNv3Q993tTkJVSZiGMrfRUYx/CgjdfiI+srkDJeMqayOuTU/4R7CcgOnS/rq3YT93fOvSus22iXc8/Yxoei3lsp0fqoLmTwn5BXcLuQPzXR3G7M3mYnMubJ5Q0Puzrnq97+kFN9bkiK0anKWJ8TNpdmm3wlV6KYDhtvHIE/zsJ23+ioNjGexW6Q= X-MS-TrafficTypeDiagnostic: BN3PR0301MB1186: X-Microsoft-Exchange-Diagnostics: 1; BN3PR0301MB1186; 31:gGXkcylHCSeZTAvx/twQEed4nNPrPHl6xCJBgyHHOA2QD5rxxupbIY0ZvmBsvbVn5Ak/erHVkPVW9AX3jMkJozEK+61AZeZdGes4fOBslhMqt+ltqKpFLC4i3RJyWINleHYtw+zZ/lpZBIzaWMiB+ncJIytB+WeamnanL2xJWd/ID5bLFizkOo4aHbStkaLTIaubqpeJGLL5kcHIr0yevQwT3EPdF6l/rupwj1e0eX0mvTYLDAdCUtsddAUbKKwJOOrkh3SwhgAeARhcMK1Itg== X-Microsoft-Antispam-PRVS: X-Exchange-Antispam-Report-Test: UriScan:(185117386973197); X-Exchange-Antispam-Report-CFA-Test: BCL:0; PCL:0; RULEID:(100000700101)(100105000095)(100000701101)(100105300095)(100000702101)(100105100095)(6095135)(601004)(2401047)(5005006)(13016025)(8121501046)(13018025)(3002001)(10201501046)(100000703101)(100105400095)(93006095)(93001095)(6055026)(6096035)(20161123565025)(20161123556025)(20161123559100)(20161123563025)(201703131430075)(201703131448075)(201703131433075)(201703161259150)(201703151042153)(20161123561025)(100000704101)(100105200095)(100000705101)(100105500095); SRVR:BN3PR0301MB1186; BCL:0; PCL:0; RULEID:(100000800101)(100110000095)(100000801101)(100110300095)(100000802101)(100110100095)(100000803101)(100110400095)(400006)(100000804101)(100110200095)(100000805101)(100110500095); SRVR:BN3PR0301MB1186; X-Microsoft-Exchange-Diagnostics: =?us-ascii?Q?1; BN3PR0301MB1186; 4:HZpJytDWCp6DkyIbpTTwyxvLMl55E0BQZGYuwX8P?= 2kjWit2+G/F6v9TrKsYR+ybH/hZSQ8vXRw2+9iKIDj883dsVaRcfsY64IB++Gkj4b8jP27b3urHOH2xN3+eoIf0nElv6qyZfE/zy30QcDxCPUWBAZ/2exeG/yzHB0Z9o4NloDIJ/p+xWMva+/DX2Oc/rNF+hRn/+2RyjZ9veMaAHNY9cgR+lL9EpeYWAg3iGI4WU6D/HHR8FZH8gdPU+N5DCjr/qFX3SW/osPVtXeW4l9RBzWvNEG1jMLQ/xdt2S7SFiAk2InRxQWn6mCWTYa7OhJRJ7zUxTcGj7PjGDJX6ttOVqp0wGE5lU+uFUa1VIt0R+k/pIXYkoFT1jihbmOFnl0QwWZIQPQ1Ck9Zz5oivLjtds3dK6DUtcldzvNJ+TyyWtMQho4HNmCqruOq6tAmxLu0hYn8Wi7yR5O6NMADPw1uu/AXR7xwOikoiwNfn89awvnN1LCFmNU3aRy9q/X3CLqC69oaQ5vv8iVLSpZ6FpkaGBOIm/7TdEXum1eVwvebAdR7pUXUEEEmhZQtz05hDAiTakuu7i/XVxrVgdvxpXWEPHsQtI+1vptcpXxIupU8TS24waunaIYtX3pfTKiA06Dv9YMWtjCSHNK6VR+RJZHVeTBDHL0YglotueVgzG68NjUNYZDSXok1SiutedYpFiK4jfgCjAqAz/Sgk4Kv1FoOMN1gWSlD+/eU41JgyQvhUfQeDXCkU29IvZXv1LDGczL7D1JrZE/llckM4oZ8tPgBsfzvO+YwzQOEdHhIIpYJrBTiWndjKA4XUasQ49ckqt5elSvXGb2MeXP7IUsHK7NS1Iqj8isvdJ8NCC7QMvEnvJtL9O2C7Pe9PBKQ8EP94W7uhh3p97h8ks9KayOnqOVE0yC7/gmIKTa9ukyAEpHwu8tNQvpcRx1DSHWAQfbSmmZet72VBxnzcUmX7GRYV8ulMhSpvgEeXNL6dHE666FbYk8s+SiGOIb+Jji2n/WDhJAlguFNIX64C2/4Yh1L29ug1lN7S/eNql0IXX/RVX4CBdk+Vo74k6cKwYIwAXcMHCl+wkVtYmdkCCwozehCtOxhJJRCwGZMqrLJLv+mNlrnQczCpJiHHvgas5qBlrNi9arkf5/3If3oQSyEcer8kW5oyN7u1oN8B1XnFSei2QxGPge8kUg9WHeD4Bj6KN8pRuWyNzRXQBtObpHaZPk4CpA6jSaOEiKyo+Mr7cUMVzdNxP2IFDFRN/mB71mVv77+HU X-Forefront-PRVS: 0340850FCD X-Microsoft-Exchange-Diagnostics: =?us-ascii?Q?1; BN3PR0301MB1186; 23:Adaqd/0NcrVfaM8p4MQZogWzKt3/J6cllXkL9xy?= PMEXvpWhnOtiQJwvSbf16dH3ka/BDLQolD67Uw4v+4jsonzQ3HOPMWO0KWfamjvbilEbRaQOZ1XOAKIevFViEmhbN1upinDa2CbjZIeT9yqmc2LNqzJF+K6Nydezu3nLT3uwmpAU4+ha1lMMkslZa7wGSnV0D7eci+LpkpfW6bVBbBdQvbv8gAcI5uvIPJUdj3DLWBrd4HTEMUG5p0pHYP3AMi3iKeBctL9+LeDj2Guvzl8OsqDyuGViQSeNDvEYTaW4eUjbdhdEqfHx1slqtIR4iuOe792VTeyoI8B9u6uSlo62d6bQJ9RIfFu0Hnmwa/+Hm5mw5/y0KAyLUWXmDkH7F7iz5jv2/CUEfQwNv64/XYalXNOGalMei9CxLL/5qpQJNEpvciSOI1bA8sGz2g6uR3g4CXnEgI4KVi7RCks5c9bo+QQBDHughI5JQIA3ov4Q7cFkACSMBsrNB+3zaPRyX+gWyR7CphjzHQNO3Aol4DIfteLTRqhqAVE0hN3ktYWCksAHMeNIavOMfQqzSrN+ZOMN06VPGNt8tqpWmz6l1XeEmYca02vNY2S4Qvga/HC1MJBTVypBLVLXS6u/E75c4radqqKlVGGiAcxpByvupky0vevQBHLIqeJ59wSCuzVaLW2aiFi3yXiqUfd8yZcW54N9YtSXpogbsvkF5vcaVwI0kIKbHXc89MM43BSHlggSagXPGfrVcI6pdKm3LAHDrGEpir5PrliIiQ6KnFo2JLxuqLkjZVmxn2tBj2CYXWDCrwB8y0og6ymN3kJswd7cSQjKv5gvd/kU1zRW/RTUgWxCPop+T9DY2j99bzXdOK9m7UaX2D1z1UDpa4TxZwOysRlGEZkVBWffVUB+V2OBOsWcEnYZ6SzbTuf9pdsU9vO9wrzgjtfeLO11mR96fRJS0kqKFVrSg9Yu9I5bCRgExtcQ17+XyKyuzv1GNEszlh5n41gZ8Zbg72boFW1oTwjXBXTq966PzIfeqZFQabvfq500zQTXIZJvclJ1dEVRLFNzi9/lkZZA1WWs1KrmhA+VMUNsX8a+9bQI29bDv1plkmxT41llnpigdhXVPxAquz1wjm0XpDkY1CWPqZjBCuRscAmMfuAO3f6BFp3Da+ucGiXocL0PwSclHjujElaTzyi+/lMyUmS3cZYLnYSgfUgHGwk2VNuo5qNZSA83IAIApAw== X-Microsoft-Exchange-Diagnostics: 1; BN3PR0301MB1186; 6:rTd02RRS4+zGwIFyJc0JzlTFTO6VnDFxxiuSC0p8FxO9TK2Ig5SiI/3+m+TbOHCHDuEeBfXXzJkesavs1TTt5Q8H78hQMHfwajMQ4lNyIFBCejq7kX2eS7F7+aZyUBGNNGTZDg0bEsXTkNffsKrZMUO+KkREZWBJkV+w300Q15gxoMYvKM8ow2tYBZqHAn05FdiPxfMUzc4AeyF52IwOrcpnhfKhPAWEZCpM8srcl7Sg4jq1ihRbpEQbzwm/1r+6p1rjVufSvK4Vf7zOW4QGvuvwH8l4m9Fm00Fwy27uHiUQJzJ1nx1Q2fyQjJhSOYRHQaxJTvRdxQ0Pe0PZTUAwWkphv+MRBqjsrVsEyUu1Xy9CcXDQw4eNPDN4TPgYUJ+UwYISp17ZMjiVlALm6C/apuSrMeUWkPXSi1VJ1KAv57gblcrKQOsZYsxW77ngU9Mc60A7koMzQQ+J7Ga9PUGceQPLnWExYnevV5eWgL88Zd8v0CLpha0FRs2mi7UrhvL00ZPN0zX9y1pQPid9C+iUsw== X-Microsoft-Exchange-Diagnostics: 1; BN3PR0301MB1186; 5:QliN8rRl2GHU7Oy0MAbESLfgG/gLO/07asfp/Lou1b9jvTY7ZsPaGpjmhw8W++oHY5X72j2dkZrmkU1uYuExhvwWB1vbhyyWknOYCDkSifhn+x/Mxp68/06KeQAiqFL2pRjCi7qdjt6CthZ/PekNQ8u8t1Wgu99L9pRh4HHaG94myy4qwsAuVtckdD93a3qZJ3sC5KHiJ1xC2qwVDbiMVfjS9BB62wWSo4Lo+0SUTpODxCz4tmRT2+v0mdaxBfRDowarNDXhmmhZTjxzLCzyYqc84McJ0CqvthjbCUi/GLsy08uQlPnZJZiFHGCgBX8UNum39usYP66Fsv5ItoldN8L+nCMLx5jSpWzhgQ1MUxN2iFXjsUlmudY8mHMGsUpkAum6SpnucYZJMRBBEshrWetwATkrDB03/sdWnSIM3JsPuwNsq7xM2HRShzxDNPexFCTUNV7DET2CdTiZclQ2R+id/9PDgE2uWp1RmL7RclwSRYr9YYsxCEGRoHMU7l4t43PwIkIR+SYzTiYg26+3eg==; 24:qeQB99yQENNE3ncX/3lKqNME0JvI52Lu0U13SeLWD94LCoeDcDvxZ8KpyRGRtxncf7suJ2yOVMiKi4NcXQHjLGaGhpl7DT63cpkNCSwFdEw= SpamDiagnosticOutput: 1:99 SpamDiagnosticMetadata: NSPM X-Microsoft-Exchange-Diagnostics: 1; BN3PR0301MB1186; 7:ypk8eHs1gaqxg56zKRrbq8sVFx+9KKCivMWg4fsU7sckHXlIJ5V4CbyT2uM8Q1hdzaxKcymQQahS+MI0brPDYVZZQujs3MGgomhX0VU/nQmieIjphjmmHx/gFJS/ezR/S4of0rv2TUaa6G4Zl3YBpQjymarTlwgxyGF4zsGZYaHGriNoHoVXBd4Znm6iDNyG/Gu05A4jQx/vaHC7yOgFE+qIomMZuVnv7+sKAV2pbU4MFx7vdE1hzkQ62g+1Yfk6RsOUaN/MiW9ECshqiTKmVDhh7PFtFRcAZymGSryJADV38MwrfBnN2ynV1liRsFhEki1r6tLHfjsC6gpTvcac7Q== X-MS-Exchange-CrossTenant-OriginalArrivalTime: 16 Jun 2017 05:32:45.1355 (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: BN3PR0301MB1186 Subject: [dpdk-dev] [PATCH 10/38] 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..fff2110 --- /dev/null +++ b/drivers/bus/dpaa/include/dpaa_rbtree.h @@ -0,0 +1,143 @@ +/*- + * BSD LICENSE + * + * Copyright 2017 NXP. All rights reserved. + * + * 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 */