1 /*- 2 * BSD LICENSE 3 * 4 * Copyright 2017 NXP. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 10 * * Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * * Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in 14 * the documentation and/or other materials provided with the 15 * distribution. 16 * * Neither the name of NXP nor the names of its 17 * contributors may be used to endorse or promote products derived 18 * from this software without specific prior written permission. 19 * 20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 21 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 22 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 23 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 24 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 25 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 26 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 27 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 28 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 29 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 30 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 31 */ 32 33 #ifndef __DPAA_RBTREE_H 34 #define __DPAA_RBTREE_H 35 36 #include <rte_common.h> 37 /************/ 38 /* RB-trees */ 39 /************/ 40 41 /* Linux has a good RB-tree implementation, that we can't use (GPL). It also has 42 * a flat/hooked-in interface that virtually requires license-contamination in 43 * order to write a caller-compatible implementation. Instead, I've created an 44 * RB-tree encapsulation on top of linux's primitives (it does some of the work 45 * the client logic would normally do), and this gives us something we can 46 * reimplement on LWE. Unfortunately there's no good+free RB-tree 47 * implementations out there that are license-compatible and "flat" (ie. no 48 * dynamic allocation). I did find a malloc-based one that I could convert, but 49 * that will be a task for later on. For now, LWE's RB-tree is implemented using 50 * an ordered linked-list. 51 * 52 * Note, the only linux-esque type is "struct rb_node", because it's used 53 * statically in the exported header, so it can't be opaque. Our version doesn't 54 * include a "rb_parent_color" field because we're doing linked-list instead of 55 * a true rb-tree. 56 */ 57 58 struct rb_node { 59 struct rb_node *prev, *next; 60 }; 61 62 struct dpa_rbtree { 63 struct rb_node *head, *tail; 64 }; 65 66 #define DPAA_RBTREE { NULL, NULL } 67 static inline void dpa_rbtree_init(struct dpa_rbtree *tree) 68 { 69 tree->head = tree->tail = NULL; 70 } 71 72 #define QMAN_NODE2OBJ(ptr, type, node_field) \ 73 (type *)((char *)ptr - offsetof(type, node_field)) 74 75 #define IMPLEMENT_DPAA_RBTREE(name, type, node_field, val_field) \ 76 static inline int name##_push(struct dpa_rbtree *tree, type *obj) \ 77 { \ 78 struct rb_node *node = tree->head; \ 79 if (!node) { \ 80 tree->head = tree->tail = &obj->node_field; \ 81 obj->node_field.prev = obj->node_field.next = NULL; \ 82 return 0; \ 83 } \ 84 while (node) { \ 85 type *item = QMAN_NODE2OBJ(node, type, node_field); \ 86 if (obj->val_field == item->val_field) \ 87 return -EBUSY; \ 88 if (obj->val_field < item->val_field) { \ 89 if (tree->head == node) \ 90 tree->head = &obj->node_field; \ 91 else \ 92 node->prev->next = &obj->node_field; \ 93 obj->node_field.prev = node->prev; \ 94 obj->node_field.next = node; \ 95 node->prev = &obj->node_field; \ 96 return 0; \ 97 } \ 98 node = node->next; \ 99 } \ 100 obj->node_field.prev = tree->tail; \ 101 obj->node_field.next = NULL; \ 102 tree->tail->next = &obj->node_field; \ 103 tree->tail = &obj->node_field; \ 104 return 0; \ 105 } \ 106 static inline void name##_del(struct dpa_rbtree *tree, type *obj) \ 107 { \ 108 if (tree->head == &obj->node_field) { \ 109 if (tree->tail == &obj->node_field) \ 110 /* Only item in the list */ \ 111 tree->head = tree->tail = NULL; \ 112 else { \ 113 /* Is the head, next != NULL */ \ 114 tree->head = tree->head->next; \ 115 tree->head->prev = NULL; \ 116 } \ 117 } else { \ 118 if (tree->tail == &obj->node_field) { \ 119 /* Is the tail, prev != NULL */ \ 120 tree->tail = tree->tail->prev; \ 121 tree->tail->next = NULL; \ 122 } else { \ 123 /* Is neither the head nor the tail */ \ 124 obj->node_field.prev->next = obj->node_field.next; \ 125 obj->node_field.next->prev = obj->node_field.prev; \ 126 } \ 127 } \ 128 } \ 129 static inline type *name##_find(struct dpa_rbtree *tree, u32 val) \ 130 { \ 131 struct rb_node *node = tree->head; \ 132 while (node) { \ 133 type *item = QMAN_NODE2OBJ(node, type, node_field); \ 134 if (val == item->val_field) \ 135 return item; \ 136 if (val < item->val_field) \ 137 return NULL; \ 138 node = node->next; \ 139 } \ 140 return NULL; \ 141 } 142 143 #endif /* __DPAA_RBTREE_H */ 144