1 files changed, 157 insertions, 0 deletions
diff --git a/hifi/xaf/hifi-dpf/include/lib/rbtree.h b/hifi/xaf/hifi-dpf/include/lib/rbtree.h
new file mode 100644
index 00000000..7f02cdf3
--- /dev/null
+++ b/hifi/xaf/hifi-dpf/include/lib/rbtree.h
@@ -0,0 +1,157 @@
+/*******************************************************************************
+* Copyright (C) 2018 Cadence Design Systems, Inc.
+* 
+* Permission is hereby granted, free of charge, to any person obtaining
+* a copy of this software and associated documentation files (the
+* "Software"), to use this Software with Cadence processor cores only and 
+* not with any other processors and platforms, subject to
+* the following conditions:
+* 
+* The above copyright notice and this permission notice shall be included
+* in all copies or substantial portions of the Software.
+* 
+* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
+* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
+* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
+* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+
+******************************************************************************/
+
+/*******************************************************************************
+ * rbtree.h
+ *
+ * Generic implmentation of red-black trees
+ *
+ *******************************************************************************/
+
+#ifndef __RBTREE_H
+#define __RBTREE_H
+
+/*******************************************************************************
+ * Red-black tree node definition
+ ******************************************************************************/
+
+/* ...reference to rb-tree node */
+typedef struct rb_node  *rb_idx_t;
+
+/* ...rb-tree node */
+typedef struct rb_node
+{
+    /* ...pointers to parent and two children */
+    rb_idx_t            parent, left, right;
+    
+    /* ...node color (least-significant-bit only) */
+    u32                 color;
+
+}   rb_node_t;
+
+/* ...rb-tree data */
+typedef struct rb_tree_t
+{
+    /* ...tree sentinel node */
+    rb_node_t           root;
+
+}   rb_tree_t;    
+
+/*******************************************************************************
+ * Helpers
+ ******************************************************************************/
+
+/* ...left child accessor */
+static inline rb_idx_t rb_left(rb_tree_t *tree, rb_idx_t n_idx)
+{
+    return n_idx->left;
+}
+
+/* ...right child accessor */
+static inline rb_idx_t rb_right(rb_tree_t *tree, rb_idx_t n_idx)
+{
+    return n_idx->right;
+}
+
+/* ...parent node accessor */
+static inline rb_idx_t rb_parent(rb_tree_t *tree, rb_idx_t n_idx)
+{
+    return n_idx->parent;
+}
+
+/* ...tree root node accessor */
+static inline rb_idx_t rb_root(rb_tree_t *tree)
+{
+    return rb_left(tree, &tree->root);
+}
+
+/* ...tree data pointer accessor */
+static inline rb_idx_t rb_cache(rb_tree_t *tree)
+{
+    return rb_right(tree, &tree->root);
+}
+
+/* ...tree null node */
+static inline rb_idx_t rb_null(rb_tree_t *tree)
+{
+    return &tree->root;
+}
+
+/* ...get user-bits stored in node color */
+static inline u32 rb_node_data(rb_tree_t *tree, rb_idx_t n_idx)
+{
+    return (n_idx->color >> 1);
+}
+
+/* ...left child assignment */
+static inline void rb_set_left(rb_tree_t *tree, rb_idx_t n_idx, rb_node_t *child)
+{
+    n_idx->left = child;
+}
+
+/* ...right child assignment */
+static inline void rb_set_right(rb_tree_t *tree, rb_idx_t n_idx, rb_node_t *child)
+{
+    n_idx->right = child;
+}
+
+/* ...cache tree client index */
+static inline void rb_set_cache(rb_tree_t *tree, rb_idx_t c_idx)
+{
+    tree->root.right = c_idx;
+}
+
+/* ...get user-bits stored in node color */
+static inline void rb_set_node_data(rb_tree_t *tree, rb_idx_t n_idx, u32 data)
+{
+    n_idx->color = (n_idx->color & 0x1) | (data << 1);
+}
+
+/*******************************************************************************
+ * API functions
+ ******************************************************************************/
+
+/* ...initialize rb-tree */
+extern void     rb_init(rb_tree_t *tree);
+
+/* ...insert node into tree as a child of p */
+extern void     rb_insert(rb_tree_t *tree, rb_idx_t n_idx, rb_idx_t p_idx);
+
+/* ...replace the node with same-key value and fixup tree pointers */
+extern void     rb_replace(rb_tree_t *tree, rb_idx_t n_idx, rb_idx_t t_idx);
+
+/* ...delete node from the tree and return its in-order predecessor/successor */
+extern rb_idx_t rb_delete(rb_tree_t *tree, rb_idx_t n_idx);
+
+/* ...first in-order item in the tree */
+extern rb_idx_t rb_first(rb_tree_t *tree);
+
+/* ...last in-order item in the tree */
+extern rb_idx_t rb_last(rb_tree_t *tree);
+
+/* ...forward tree iterator */
+extern rb_idx_t rb_next(rb_tree_t *tree, rb_idx_t n_idx);
+
+/* ...backward tree iterator */
+extern rb_idx_t rb_prev(rb_tree_t *tree, rb_idx_t n_idx);
+
+#endif  /* __RBTREE_H */