From patchwork Sat May 27 10:25:07 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Shreyansh Jain X-Patchwork-Id: 24761 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 6070B7CCF; Sat, 27 May 2017 12:18:22 +0200 (CEST) Received: from NAM01-BY2-obe.outbound.protection.outlook.com (mail-by2nam01on0040.outbound.protection.outlook.com [104.47.34.40]) by dpdk.org (Postfix) with ESMTP id 091B97CAF for ; Sat, 27 May 2017 12:18:13 +0200 (CEST) Received: from BN6PR03CA0006.namprd03.prod.outlook.com (10.168.230.144) by BY1PR0301MB0901.namprd03.prod.outlook.com (10.160.195.140) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id 15.1.1101.14; Sat, 27 May 2017 10:18:12 +0000 Received: from BN1AFFO11FD015.protection.gbl (2a01:111:f400:7c10::156) by BN6PR03CA0006.outlook.office365.com (2603:10b6:404:23::16) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id 15.1.1124.9 via Frontend Transport; Sat, 27 May 2017 10:18:11 +0000 Authentication-Results: spf=fail (sender IP is 192.88.158.2) 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.158.2 as permitted sender) receiver=protection.outlook.com; client-ip=192.88.158.2; helo=az84smr01.freescale.net; Received: from az84smr01.freescale.net (192.88.158.2) by BN1AFFO11FD015.mail.protection.outlook.com (10.58.52.75) with Microsoft SMTP Server (version=TLS1_0, cipher=TLS_RSA_WITH_AES_256_CBC_SHA) id 15.1.1075.5 via Frontend Transport; Sat, 27 May 2017 10:18:11 +0000 Received: from Tophie.ap.freescale.net ([10.232.14.39]) by az84smr01.freescale.net (8.14.3/8.14.0) with ESMTP id v4RAHYtv029968; Sat, 27 May 2017 03:18:09 -0700 From: Shreyansh Jain To: CC: , Date: Sat, 27 May 2017 15:55:07 +0530 Message-ID: <1495880735-1651-12-git-send-email-shreyansh.jain@nxp.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1495880735-1651-1-git-send-email-shreyansh.jain@nxp.com> References: <1495880735-1651-1-git-send-email-shreyansh.jain@nxp.com> X-EOPAttributedMessage: 0 X-Matching-Connectors: 131403538917006246; (91ab9b29-cfa4-454e-5278-08d120cd25b8); () X-Forefront-Antispam-Report: CIP:192.88.158.2; IPV:NLI; CTRY:US; EFV:NLI; SFV:NSPM; SFS:(10009020)(6009001)(336005)(39450400003)(39860400002)(39840400002)(39850400002)(39410400002)(39380400002)(39400400002)(2980300002)(1110001)(1109001)(339900001)(199003)(189002)(9170700003)(5660300001)(305945005)(50986999)(47776003)(104016004)(8656002)(53936002)(68736007)(81166006)(8676002)(2906002)(8936002)(2351001)(33646002)(106466001)(105606002)(50226002)(76176999)(110136004)(54906002)(2950100002)(6916009)(38730400002)(36756003)(5003940100001)(356003)(77096006)(498600001)(86362001)(4326008)(85426001)(50466002)(189998001)(48376002); DIR:OUT; SFP:1101; SCL:1; SRVR:BY1PR0301MB0901; H:az84smr01.freescale.net; FPR:; SPF:Fail; MLV:ovrnspm; PTR:InfoDomainNonexistent; A:1; MX:1; LANG:en; X-Microsoft-Exchange-Diagnostics: 1; BN1AFFO11FD015; 1:0SQ9GkdHkqcLtQFWH21U5wK4OUdfh9BKRR86XQ5DXmpXkj6H3vSzoCXv6HhKy3VJfDXBqOIvfM8NhUz7QZmIir/5r8+dq5jlFKZcTH9kc2MibxwwPKtLRvY1LMX8Yj6lY3rD9hjtVtBFDaSIsuzZ2ouD5TCUiDYaPG/h7MVfXRlR0UUjdIe3uh2FRfP+IBS+vbpznisE+N4an0Kt1by75YNG5IQLi7q9iZWXFdjwwLuP8M1IhZor7R6J5TGKPW7TVd2jGboJkx5oXaeZ7qM6CSXJyEK27s0tjeXJ3QUnMK/dl/ReZ5JOlGsf0ij6/JdnGZhmb/V2oKliISIgCR5cKrq3j+r2JS/BJrwdsdIV1z+LqZpc/WGSBEeqWZ6MKC08dDZ9O9UEt45fzc0LWDO9ok6uYM/N9MSz2aB5yNFtzCHsSCDK+blaBwE2/AjrDHcpC1Tll2QjFbI+LXK+imCPSKA4nkRoXZ8DKrsfgtaAM2Hw1P0Xt62IrEzIFFWOPcs9ZhvOF8YKRu5kuRGoRw8pKxyI+W5L74+wrkFzn7BlPxMwjC8Ms2N9V0XqbHnAGjCSrPAKG7xXK+FXA197qrXKUocTmNCiMMpBzNqW4y3QEPT0gEi23spgeAOsKC9gPQ51W3MMFJaoBte7scr/BT/FWTn/agWB81IkjvWi2p0BuViDiS/gfbsBlsaHsxO4MYWJxfeoEwBtiNO4OwgazFJkkQ== MIME-Version: 1.0 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: BY1PR0301MB0901: X-MS-Office365-Filtering-Correlation-Id: fbd8c58c-5a44-4f53-3a48-08d4a4e9add5 X-Microsoft-Antispam: UriScan:; BCL:0; PCL:0; RULEID:(22001)(201703131430075)(201703131517081); SRVR:BY1PR0301MB0901; X-Microsoft-Exchange-Diagnostics: 1; BY1PR0301MB0901; 3:GTyi4t3WNqrJ0kQ6mDZtBJva1E9NqsEb9N7mEKnD8F0eSGbJpWpUXB22/JlP6N6boiXTR2pCIWSvE3LfaJZr9rlnh6gKqaut65tWRAnlRcUE6+ZiTo6Y2HBJHEdqqlzbxNKlKkBZT0wxK28q6m4xAXDvGUWlw1Zvl3jpqzQH6bqoNuTmeaiVx3Di/qjr6Sb8gYf6KfkoLJa8fSCKXjNVfkWysbYbZnqCmDX+HnuCtzPMFFscE++0KeKfBeWFfsPj8u5d7IufLi9a2CJDoD46mdOmOvVFRVRckzkDoNq8rSXpGYYrKxoRip4twqlUMT/ywpetahrAPWNI3azc50KgxaGlp6gRTWhHWJvJmA3oobw+CNZH3wNz3DCZsVh2GuRLmdhLLLovV0tL0oKlZts6K+c1Xey0bz/hqgw7XaZRYXgegGW8MENZT1uaOr1/8vAy; 25:lfkqQ/LnOMmXpnMztZLJhVqdVfA65wxLq7KTdp8FN+DD93ndWYqB+rhoWyZgxcz87DuhsQJFBw8yeUbWbBZpzzFM7i6IV7CW2hl2E6UJIsxYu/vkWv0yadxE6eA/p32O1RFwD1vJ7aLFvgjQ9xFQsBSqPeTv4Vs4A+jkB5AxuXfLlYrL83lgdb2DNQM8Ndo7ex+OmQv1uQyOBNGAzzCdIF2uoJuQMO411HvM2QQfZJ2+hTTFFUJAX0+45PpGYdLjNBvzgAyY6JN405wzO7FW0G//Re0jMaDr3VBD/tLAi59XYrKaoyzk6/NsqsjUUzzkEdGVy5hm5yDbORRxkA4WZzFGgzALXQThCW2mmoWopVlHn9fZ7F3hnCZYOKxKN0THt/aVNgOP4jOavRRe5g13Z5vm4qq+0ilGoqFnnqqXbipFC0Am556ORDoE0WcCfjppd7B3FVn/r7BYI+1yfaAf91muc4z9K2H2DbxR2DGDcLs= X-Microsoft-Exchange-Diagnostics: 1; BY1PR0301MB0901; 31:0okrhHkRwLlcaPBJpNcQv+z2nTeYdP71h3uiqjQr6YajDa4bS+ltdMlS9rGKSNeAXyYzfoOO010Q0cIuXJwAQy+Wur7B+8VkdqzxCOjcDBcviwllDO3OCQaNpKsTNW2Q/RzYsq7btWF3ICXOOVQ/q71x6e8TSA+bMnKUp60ArJy5iWOnc/KOT3FV0/xKsV+YJn9YtF2HdDX2u3cIuJuy3J81cMiiVFImkCxdA7BwcRWH7V68ggjl1wMOvK9unIUno6PO8oCb+NBQ0sMMrcaE3w== X-Microsoft-Antispam-PRVS: X-Exchange-Antispam-Report-Test: UriScan:(185117386973197)(101931422205132); X-Exchange-Antispam-Report-CFA-Test: BCL:0; PCL:0; RULEID:(6095135)(601004)(2401047)(13018025)(8121501046)(13016025)(5005006)(93006095)(93001095)(10201501046)(3002001)(6055026)(6096035)(20161123556025)(20161123563025)(201703131430075)(201703131433075)(201703131448075)(201703161259150)(201703151042153)(20161123559100)(20161123565025)(20161123561025); SRVR:BY1PR0301MB0901; BCL:0; PCL:0; RULEID:(400006); SRVR:BY1PR0301MB0901; X-Microsoft-Exchange-Diagnostics: 1; BY1PR0301MB0901; 4:6XAMvUWUKH9niOVlb41Ee3VTRtuqGzDDrxIVSXQ0GlfSDeVynKnIOFZgILs6osIsZzoCkryBltR7smev0CPbFBExLXxAWC1VyuYDmHTiJS86yveoe3eQY3Z2GW43evSEmuOi1S9GznrPb9sVwwJTEqYLZYBmuGQsAV29BJ1ZGeIQY6a2jxtJ/jMbjO2amSN8DgJvZU7zGo4ufAMiMcSxD02Ec1MYOuSl/VJxohlWHm5VQcZuSnzjXkzJpAG3LT2uP6QQraOd5//+eW86RLa5U0Coaq2jGq1GDp8tR5wS3X+Dm8CBsdP0xMJr8ydYQUczfXJV77hV9kS58GFvQmxoX3YUyFYkadgpuPJnZLsWZO9XwF0IbTFj35+gSBc4fMBPl8tssNYkyCTbzFnRjH1d4OXiN5Q/vU4HP66xWk/4msZJ/igHY9zTdkbppWdnfDl5TyxWbXXLnZKjWxZEJRENRibIx25mVrqdanAa12MlbABGnx6I62p5PEHm+YIb0yXic1tYkfF3OYch8vW8btqNgoz3bAL7wE/h7Wjxw7AUuhKiDOi8nO3L9J4leYizFVCoMMcYBjf4D68QgcszUuRxbCWvqo00dLaoP91G0YWDoRZkylRm2TDcahy2JDRna25pr4/4NIGO0Tod/dZnVYeeRyfofS+r62Virq9SxMDmIJd7/A8Af3hr1x+gtBGTN9iH1dXctKti0d5DWA7CEUOgeebsX9VdICT9pKmWrwdtInGPVh4y2zrvpZnKmHJfrPJrGHXdj3nFEfkdlEPwemIvhzyb4Ihveh7sFvSngxwc5fYqPXthnhSbQdbGIf1IxqwRe6IeeyrWlTYVHRDBGVlIfXMgwH1WSM5r2K+iRhwF5S69weo94a2E4fPakRoQh7TfGMQZnY3iWriNovHMBhmer0g9H8exSoPido4fFajuU7Xh7KxK8QI7QhizJRsDHm1D X-Forefront-PRVS: 0320B28BE1 X-Microsoft-Exchange-Diagnostics: =?us-ascii?Q?1; BY1PR0301MB0901; 23:KDub/D232WZWRazuWsof6VevWvgJpB5nvOEJTSA?= O4lQRNOoYHDRSMJ4wO0vyqbviRFR4lPpOXVA0buTq53hFc4ByTDLqYcP0hh9SU70exXWIThVG7nILifBCCSYOOM5G4QXFdv0rKFKlVrXR16u/9VikEkduLZjY3G7zQjYImIxI5lOnytCMn/Ml3KZ3k1tWTnJuq1L/j10HOuLEl82AmqCEsyCnKmwHyawwNx4nYkH9MHvLJ2K+BiFpAzNRzgFxB6XqfYMjBfJewMfXZAinfh26hHC3FCY+QgPRrLW6j/sJ2zfj8OPyyWQ3dmIJP3afM9xJvV/w/mWWP6vsuCEVKCo9RV06Xfbc/xUtXOyhEYXcTnJ5fc1L2JxLkaF6Uh6IUSM7IcpkTEHIWcL44HQgDPx+ou/rsUSTzlIgLdkLG35NwELkh3kf2Wpl6rScxwke9Mb6PAAKCinqMgtVoP6/qvjcfwEpLHyUJSn+/M13maFJjFpIt5TiKBMNHG+q/xdAv1faXPnNNgJCIIkdY8UMdnEj2RDjsUD2LK+ZhDtxFGpeqUN21gGUlx+MDJ1U19J7gBbejHRAinm3vGwO38lqSW1UNqeQxmGYx00sFRDR40eGmTcryO8SBK1HwiBRMhJq3NigyDTX9CeY/adwGmAjGPykekmHki/h2e4yR/9XD6P2iLAYBF3ErxJ6k3L8EfK7DVjg6NljdP9it6Wsh3xq56YBPXVi0AZKx5eEVY8iPRQMzUVabmQ87zdVLkpP4LEcb8M/QQyOwp4DtRlgRzHma04ARpfRmn4YWvHB3w3MzpqBkG+SFHM8qWHKy4E9FZWLqj6O7zpySdTP053KWU0ua/z9ckY2fdQjUeU8AIYVERLUHPCuKqsQWHY/6txWeZycEhXsJNquyRVYPFbJpIYGosMbYM7Vg3vkRfd+WCMPHQ6dLRLW4YT2NK2WhbbLNapjTx284/78a9sEcieoNQe9333csj444r4RJZ6xI/WoOlm2fB++uHjGKDVwSSaf0fHfQzR7lyXOpy0IQiKgzzg7N7ZcYnFF06Zo8YhOuWvt753ujtqXd296rmYyO7H6Ulhh/wIkNUillmrNVo4fp2Cfb6+dKP3f2m9uGpsEsOqIFv7YR4JtrkBB7caLTJv9a9sTNfSPTpHxqAkHrzePInOU9RxmF8JJ2t0TcMrJOUDUdG5CWaEwrETgp5nkAolkH1hBafqN2yxyxNIMQ5yZb9q5dV0ZfLl4agZMFzqg5FL0jmo= X-Microsoft-Exchange-Diagnostics: 1; BY1PR0301MB0901; 6:rwsS9liEtXPlE8WNy5qpp6whPG8VX1cPG952WqQYwfYyL/3gcNGf5EKaQqO3ZJD8sEca80uy/UPsXFqmQOOANGWtyk6ruQ/E0lz3TeSmIIkpVAx17UyKFWYY6btpZ0G2Wt5josHx7bvQadr0EGyHo+j9bi+AgLpPoR872eY7cAHAXqt/SshCNm3De6JmgsMj+YcGcoIowgjoBlLuD6iZv5pw1JAKZxa6QuuUR5ySOJSZpLZdxEyWWBZ4cecsJlymqAuA++ZOob7YcqgSsTM/LoQFds2HCKZJeBYw0PmTtEs7hLtntEY6my9+yuOVqwMBl89PA4OB9ZiZ8teD6j4wx/BbB9HrNl/0+nKkpIXNB0aimiiFE7SpdgGZjVI8rcSp0Cfv4WhJoaFlqBkXbrtkzIalt/zy8nIaxYif+jrauWXEkx2p5Yp275QOy/LUQ/ULAoT2d1Xnc58i2pve71q8sbeGoApebcrJymrlDs5LwiSJA6BOQTyHfmmPm7+g3K1u3rCI5lfXxXMY22c5NmkJpA==; 5:A7KX3lvR/IHQHmIWY8sKPKeAQq2EGPg5xYB1WDXBmmfxG1nobRZZ1Ylzz6Lxsui5Twqj2A8q3WqrKm9XRL50hpoXTPKU+yl52fbwqtC3tbIvSEjxnJ8UExBkgbnc9K9nEmZLhJTT5j0x5gd+2AQCFlH0PYQcJAcOAwEobRhDL7EgVOVdW0G08kURkMs2mQ3Q; 24:xjyWMEe7xmDE/Z5QYY/kredpSMHucO+5Ki7cQoTW2YYYzMX7lunTv9M+of2Gm+y13u0aE+PBwx/htL/9/MlVRlwCPVdTSy0Cw2T+sbW+/Lg= SpamDiagnosticOutput: 1:99 SpamDiagnosticMetadata: NSPM X-Microsoft-Exchange-Diagnostics: 1; BY1PR0301MB0901; 7:ocASKe4O146C+Ki97Rf2ehEEEMb+c4W7+Bpgnbi6yfnZ0Vi2PaKydFBY6PjVg6FBYuG0SeyLDhtIVkeqMZMI0IIx14Q8TDE3zKq5sywIYEN3NIgDngnsgoHzD5u/ourqIRylUPZrtwNe3W4RorE4jJ/Wxm+0ovZHLUAiiKRXILuilD/51D5uIcP3/Lt/5dODUddHaMAUHCiu27GTDRhabzgvnlHowvQN9Hp0INB194E+qTiTFNerzNYtrfM11vPae5VXVZUziH6nsE4Xi3Nhqcgjzmwu7hAbsLWq9rSGOtOxNOT4ffkOx3XvXcmWgsAFPvzNrm/3iIWR0dKgb0AAYg== X-MS-Exchange-CrossTenant-OriginalArrivalTime: 27 May 2017 10:18:11.4666 (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.158.2]; Helo=[az84smr01.freescale.net] X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: BY1PR0301MB0901 Subject: [dpdk-dev] [RFC Patch 11/39] 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 */