diff options
Diffstat (limited to 'hifi/xaf/hifi-dpf/core/xf-sched.c')
-rw-r--r-- | hifi/xaf/hifi-dpf/core/xf-sched.c | 153 |
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); +} |