1 files changed, 153 insertions, 0 deletions
diff --git a/hifi/xaf/hifi-dpf/core/xf-sched.c b/hifi/xaf/hifi-dpf/core/xf-sched.c
new file mode 100644
index 00000000..cc1b4e8d
--- /dev/null
+++ b/hifi/xaf/hifi-dpf/core/xf-sched.c
@@ -0,0 +1,153 @@
+/*******************************************************************************
+* 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.
+
+******************************************************************************/
+
+/*******************************************************************************
+ * xf-sched.c
+ *
+ * Non-preemptive earliest-deadline-first scheduler
+ *
+ ******************************************************************************/
+
+#define MODULE_TAG                      SCHED
+
+/*******************************************************************************
+ * Includes
+ ******************************************************************************/
+
+#include "xf.h"
+
+/*******************************************************************************
+ * Tracing configuration
+ ******************************************************************************/
+
+TRACE_TAG(DEBUG, 1);
+
+/*******************************************************************************
+ * Global functions definitions
+ ******************************************************************************/
+
+/* ...place task into scheduler queue */
+void xf_sched_put(xf_sched_t *sched, xf_task_t *t, u32 ts)
+{
+    rb_tree_t  *tree = (rb_tree_t *)sched;
+    rb_node_t  *node = (rb_node_t *)t;
+    rb_idx_t    p_idx, t_idx;
+    u32         _ts;
+
+    /* ...set scheduling timestamp */
+    xf_task_timestamp_set(t, ts);
+    
+    /* ...find a place in the tree where the message should be inserted */
+    for (p_idx = rb_root(tree); p_idx != rb_null(tree); p_idx = t_idx)
+    {
+        /* ...get timestamp of the p_idx */
+        _ts = xf_task_timestamp((xf_task_t *)p_idx);
+
+        /* ...ordering respects FIFO order of messages with same timestamp */
+        if (xf_timestamp_before(ts, _ts))
+        {
+            if ((t_idx = rb_left(tree, p_idx)) == rb_null(tree))
+            {
+                /* ...p_idx is a direct successor of the message */
+                rb_set_left(tree, p_idx, node);
+
+                /* ...adjust head of the tree if needed */
+                if (p_idx == rb_cache(tree))    goto insert_head;
+                else                            goto insert;
+            }
+        }
+        else
+        {
+            if ((t_idx = rb_right(tree, p_idx)) == rb_null(tree))
+            {
+                /* ...p_idx is a direct predeccessor of the message */
+                rb_set_right(tree, p_idx, node);
+
+                goto insert;
+            }
+        }        
+    }
+
+insert_head:
+    /* ...adjust scheduler head element */
+    rb_set_cache(tree, node);
+
+insert:    
+    /* ...insert item and rebalance the tree */
+    rb_insert(tree, node, p_idx);
+
+    /* ...head cannot be NULL */
+    BUG(rb_cache(tree) == rb_null(tree), _x("Invalid scheduler state"));
+    
+    TRACE(DEBUG, _b("in:  %x:[%p] (ts:%x)"), ts, node, xf_sched_timestamp(sched));
+}
+
+/* ...get first item from the scheduler */
+xf_task_t * xf_sched_get(xf_sched_t *sched)
+{
+    rb_tree_t      *tree = (rb_tree_t *)sched;
+    rb_idx_t        n_idx, t_idx;
+    u32             ts;
+    
+    /* ...head of the tree is cached; replace it with its parent (direct successor) */
+    if ((n_idx = rb_cache(tree)) == rb_null(tree))
+    {
+        /* ...tree is empty; bail out */
+        return NULL;
+    }
+    else
+    {
+        /* ...delete current node and rebalance the tree */
+        t_idx = rb_delete(tree, n_idx), rb_set_cache(tree, t_idx);
+
+        /* ...get task timestamp */
+        ts = xf_task_timestamp((xf_task_t *)n_idx);
+        
+        /* ...advance scheduler timestamp */
+        xf_sched_timestamp_set(sched, ts);
+        
+        TRACE(DEBUG, _b("out: %x:[%p]"), ts, n_idx);
+        
+        /* ...return task */
+        return (xf_task_t *)n_idx;
+    }
+}
+
+/* ...cancel specified task execution (must be scheduled!) */
+void xf_sched_cancel(xf_sched_t *sched, xf_task_t *t)
+{
+    rb_tree_t      *tree = (rb_tree_t *)sched;
+    rb_idx_t        n_idx = t;
+    rb_idx_t        t_idx;
+
+    /* ...delete message from tree */
+    t_idx = rb_delete(tree, n_idx);
+
+    /* ...adjust head if that was the first message */
+    (n_idx == rb_cache(tree) ? rb_set_cache(tree, t_idx), 1 : 0);
+}
+
+/* ...initialize scheduler data */
+void xf_sched_init(xf_sched_t *sched)
+{
+    rb_init((rb_tree_t *)sched);
+}