From mboxrd@z Thu Jan 1 00:00:00 1970 From: Shreyansh Jain Subject: [PATCH v6 09/40] bus/dpaa: add routines for managing a RB tree Date: Thu, 28 Sep 2017 17:59:29 +0530 Message-ID: <20170928123000.1711-10-shreyansh.jain@nxp.com> References: <20170928113344.12248-1-shreyansh.jain@nxp.com> <20170928123000.1711-1-shreyansh.jain@nxp.com> Mime-Version: 1.0 Content-Type: text/plain Cc: , To: Return-path: 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) In-Reply-To: <20170928123000.1711-1-shreyansh.jain@nxp.com> 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 */ -- 2.9.3