From: Shreyansh Jain <shreyansh.jain@nxp.com>
To: <dev@dpdk.org>
Cc: <ferruh.yigit@intel.com>, <hemant.agrawal@nxp.com>
Subject: [dpdk-dev] [RFC Patch 11/39] bus/dpaa: add routines for managing a RB tree
Date: Sat, 27 May 2017 15:55:07 +0530 [thread overview]
Message-ID: <1495880735-1651-12-git-send-email-shreyansh.jain@nxp.com> (raw)
In-Reply-To: <1495880735-1651-1-git-send-email-shreyansh.jain@nxp.com>
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 <geoff.thorpe@freescale.com>
Signed-off-by: Hemant Agrawal <hemant.agrawal@nxp.com>
Signed-off-by: Shreyansh Jain <shreyansh.jain@nxp.com>
---
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 <rte_common.h>
+/************/
+/* 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.7.4
next prev parent reply other threads:[~2017-05-27 10:18 UTC|newest]
Thread overview: 41+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-05-27 10:24 [dpdk-dev] [RFC Patch 00/39] Introduce NXP DPAA Bus, Mempool and PMD Shreyansh Jain
2017-05-27 10:24 ` [dpdk-dev] [RFC Patch 01/39] eal: add Bus log type Shreyansh Jain
2017-05-27 10:28 ` Shreyansh Jain
2017-05-27 10:24 ` [dpdk-dev] [RFC Patch 02/39] eal: add support for 24 40 and 48 bit operations Shreyansh Jain
2017-05-27 10:24 ` [dpdk-dev] [RFC Patch 03/39] config: add NXP DPAA SoC build configuration Shreyansh Jain
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 04/39] bus/dpaa: introduce NXP DPAA Bus driver skeleton Shreyansh Jain
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 05/39] bus/dpaa: add compatibility and helper macros Shreyansh Jain
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 06/39] bus/dpaa: add OF parser for device scanning Shreyansh Jain
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 07/39] bus/dpaa: introducing FMan configurations Shreyansh Jain
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 08/39] bus/dpaa: add FMan hardware operations Shreyansh Jain
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 09/39] bus/dpaa: enable DPAA IOCTL portal driver Shreyansh Jain
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 10/39] bus/dpaa: add layer for interrupt emulation using pthread Shreyansh Jain
2017-05-27 10:25 ` Shreyansh Jain [this message]
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 12/39] bus/dpaa: add QMAN interface driver Shreyansh Jain
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 13/39] bus/dpaa: add QMan driver core routines Shreyansh Jain
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 14/39] bus/dpaa: add BMAN driver core Shreyansh Jain
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 15/39] bus/dpaa: add support for FMAN frame queue lookup Shreyansh Jain
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 16/39] bus/dpaa: add BMan hardware interfaces Shreyansh Jain
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 17/39] bus/dpaa: add fman flow control threshold setting Shreyansh Jain
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 18/39] bus/dpaa: integrate DPAA Bus with hardware blocks Shreyansh Jain
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 19/39] doc: add NXP DPAA PMD documentation Shreyansh Jain
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 20/39] mempool/dpaa: add support for NXP DPAA Mempool Shreyansh Jain
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 21/39] drivers: enable compilation of DPAA Mempool driver Shreyansh Jain
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 22/39] maintainers: claim ownership " Shreyansh Jain
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 23/39] net/dpaa: add NXP DPAA PMD driver skeleton Shreyansh Jain
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 24/39] config: enable NXP DPAA PMD compilation Shreyansh Jain
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 25/39] net/dpaa: add support for Tx and Rx queue setup Shreyansh Jain
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 26/39] net/dpaa: add support for MTU update Shreyansh Jain
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 27/39] net/dpaa: add support for link status update Shreyansh Jain
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 28/39] net/dpaa: add support for jumbo frames Shreyansh Jain
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 29/39] net/dpaa: add support for promiscuous toggle Shreyansh Jain
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 30/39] net/dpaa: add support for multicast toggle Shreyansh Jain
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 31/39] net/dpaa: add support for basic stats Shreyansh Jain
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 32/39] net/dpaa: add support for device info Shreyansh Jain
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 33/39] net/dpaa: support for checksum offload Shreyansh Jain
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 34/39] net/dpaa: add support for hashed RSS Shreyansh Jain
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 35/39] net/dpaa: add support for MAC address update Shreyansh Jain
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 36/39] net/dpaa: add support for packet type parsing Shreyansh Jain
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 37/39] net/dpaa: add support for Scattered Rx Shreyansh Jain
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 38/39] net/dpaa: add support for flow control Shreyansh Jain
2017-05-27 10:25 ` [dpdk-dev] [RFC Patch 39/39] net/dpaa: add packet dump for debugging Shreyansh Jain
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1495880735-1651-12-git-send-email-shreyansh.jain@nxp.com \
--to=shreyansh.jain@nxp.com \
--cc=dev@dpdk.org \
--cc=ferruh.yigit@intel.com \
--cc=hemant.agrawal@nxp.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).