Branch data     Line data    Source code

       1                 :            : /* SPDX-License-Identifier: BSD-3-Clause
       2                 :            :  *
       3                 :            :  *   Copyright 2017 NXP
       4                 :            :  *
       5                 :            :  */
       6                 :            : 
       7                 :            : #ifndef __DPAA_RBTREE_H
       8                 :            : #define __DPAA_RBTREE_H
       9                 :            : 
      10                 :            : #include <rte_common.h>
      11                 :            : /************/
      12                 :            : /* RB-trees */
      13                 :            : /************/
      14                 :            : 
      15                 :            : /* Linux has a good RB-tree implementation, that we can't use (GPL). It also has
      16                 :            :  * a flat/hooked-in interface that virtually requires license-contamination in
      17                 :            :  * order to write a caller-compatible implementation. Instead, I've created an
      18                 :            :  * RB-tree encapsulation on top of linux's primitives (it does some of the work
      19                 :            :  * the client logic would normally do), and this gives us something we can
      20                 :            :  * reimplement on LWE. Unfortunately there's no good+free RB-tree
      21                 :            :  * implementations out there that are license-compatible and "flat" (ie. no
      22                 :            :  * dynamic allocation). I did find a malloc-based one that I could convert, but
      23                 :            :  * that will be a task for later on. For now, LWE's RB-tree is implemented using
      24                 :            :  * an ordered linked-list.
      25                 :            :  *
      26                 :            :  * Note, the only linux-esque type is "struct rb_node", because it's used
      27                 :            :  * statically in the exported header, so it can't be opaque. Our version doesn't
      28                 :            :  * include a "rb_parent_color" field because we're doing linked-list instead of
      29                 :            :  * a true rb-tree.
      30                 :            :  */
      31                 :            : 
      32                 :            : struct rb_node {
      33                 :            :         struct rb_node *prev, *next;
      34                 :            : };
      35                 :            : 
      36                 :            : struct dpa_rbtree {
      37                 :            :         struct rb_node *head, *tail;
      38                 :            : };
      39                 :            : 
      40                 :            : #define DPAA_RBTREE { NULL, NULL }
      41                 :            : static inline void dpa_rbtree_init(struct dpa_rbtree *tree)
      42                 :            : {
      43                 :          0 :         tree->head = tree->tail = NULL;
      44                 :            : }
      45                 :            : 
      46                 :            : #define QMAN_NODE2OBJ(ptr, type, node_field) \
      47                 :            :         (type *)((char *)ptr - offsetof(type, node_field))
      48                 :            : 
      49                 :            : #define IMPLEMENT_DPAA_RBTREE(name, type, node_field, val_field) \
      50                 :            : static inline int name##_push(struct dpa_rbtree *tree, type *obj) \
      51                 :            : { \
      52                 :            :         struct rb_node *node = tree->head; \
      53                 :            :         if (!node) { \
      54                 :            :                 tree->head = tree->tail = &obj->node_field; \
      55                 :            :                 obj->node_field.prev = obj->node_field.next = NULL; \
      56                 :            :                 return 0; \
      57                 :            :         } \
      58                 :            :         while (node) { \
      59                 :            :                 type *item = QMAN_NODE2OBJ(node, type, node_field); \
      60                 :            :                 if (obj->val_field == item->val_field) \
      61                 :            :                         return -EBUSY; \
      62                 :            :                 if (obj->val_field < item->val_field) { \
      63                 :            :                         if (tree->head == node) \
      64                 :            :                                 tree->head = &obj->node_field; \
      65                 :            :                         else \
      66                 :            :                                 node->prev->next = &obj->node_field; \
      67                 :            :                         obj->node_field.prev = node->prev; \
      68                 :            :                         obj->node_field.next = node; \
      69                 :            :                         node->prev = &obj->node_field; \
      70                 :            :                         return 0; \
      71                 :            :                 } \
      72                 :            :                 node = node->next; \
      73                 :            :         } \
      74                 :            :         obj->node_field.prev = tree->tail; \
      75                 :            :         obj->node_field.next = NULL; \
      76                 :            :         tree->tail->next = &obj->node_field; \
      77                 :            :         tree->tail = &obj->node_field; \
      78                 :            :         return 0; \
      79                 :            : } \
      80                 :            : static inline void name##_del(struct dpa_rbtree *tree, type *obj) \
      81                 :            : { \
      82                 :            :         if (tree->head == &obj->node_field) { \
      83                 :            :                 if (tree->tail == &obj->node_field) \
      84                 :            :                         /* Only item in the list */ \
      85                 :            :                         tree->head = tree->tail = NULL; \
      86                 :            :                 else { \
      87                 :            :                         /* Is the head, next != NULL */ \
      88                 :            :                         tree->head = tree->head->next; \
      89                 :            :                         tree->head->prev = NULL; \
      90                 :            :                 } \
      91                 :            :         } else { \
      92                 :            :                 if (tree->tail == &obj->node_field) { \
      93                 :            :                         /* Is the tail, prev != NULL */ \
      94                 :            :                         tree->tail = tree->tail->prev; \
      95                 :            :                         tree->tail->next = NULL; \
      96                 :            :                 } else { \
      97                 :            :                         /* Is neither the head nor the tail */ \
      98                 :            :                         obj->node_field.prev->next = obj->node_field.next; \
      99                 :            :                         obj->node_field.next->prev = obj->node_field.prev; \
     100                 :            :                 } \
     101                 :            :         } \
     102                 :            : } \
     103                 :            : static inline type *name##_find(struct dpa_rbtree *tree, u32 val) \
     104                 :            : { \
     105                 :            :         struct rb_node *node = tree->head; \
     106                 :            :         while (node) { \
     107                 :            :                 type *item = QMAN_NODE2OBJ(node, type, node_field); \
     108                 :            :                 if (val == item->val_field) \
     109                 :            :                         return item; \
     110                 :            :                 if (val < item->val_field) \
     111                 :            :                         return NULL; \
     112                 :            :                 node = node->next; \
     113                 :            :         } \
     114                 :            :         return NULL; \
     115                 :            : }
     116                 :            : 
     117                 :            : #endif /* __DPAA_RBTREE_H */