Index: kernel/Makefile =================================================================== --- kernel/Makefile (revision 2e4343bb577304bd2bb9c0c4825438035b24ac6f) +++ kernel/Makefile (revision ef1eab71c59f1782c6211550d5ee608250a791e0) @@ -161,5 +161,4 @@ GENERIC_SOURCES = \ - generic/src/adt/avl.c \ generic/src/adt/bitmap.c \ generic/src/adt/btree.c \ @@ -286,5 +285,4 @@ test/btree/btree1.c \ test/cht/cht1.c \ - test/avltree/avltree1.c \ test/fault/fault1.c \ test/mm/falloc1.c \ Index: kernel/generic/include/adt/avl.h =================================================================== --- kernel/generic/include/adt/avl.h (revision 2e4343bb577304bd2bb9c0c4825438035b24ac6f) +++ (revision ) @@ -1,141 +1,0 @@ -/* - * Copyright (C) 2007 Vojtech Mencl - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * - * - Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - The name of the author may not be used to endorse or promote products - * derived from this software without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR - * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. - * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, - * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT - * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF - * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - */ - -/** @addtogroup kernel_generic_adt - * @{ - */ -/** @file - */ - -#ifndef KERN_AVLTREE_H_ -#define KERN_AVLTREE_H_ - -#include -#include -#include -#include - -/** - * Macro for getting a pointer to the structure which contains the avltree - * structure. - * - * @param link Pointer to the avltree structure. - * @param type Name of the outer structure. - * @param member Name of avltree attribute in the outer structure. - */ -#define avltree_get_instance(node, type, member) \ - ((type *)(((uint8_t *)(node)) - ((uint8_t *) &(((type *) NULL)->member)))) - -typedef struct avltree_node avltree_node_t; -typedef struct avltree avltree_t; - -typedef uint64_t avltree_key_t; - -typedef bool (*avltree_walker_t)(avltree_node_t *, void *); - -/** AVL tree node structure. */ -struct avltree_node { - /** - * Pointer to the left descendant of this node. - * - * All keys of nodes in the left subtree are less than the key of this - * node. - */ - struct avltree_node *lft; - - /** - * Pointer to the right descendant of this node. - * - * All keys of nodes in the right subtree are greater than the key of - * this node. - */ - struct avltree_node *rgt; - - /** Pointer to the parent node. Root node has NULL parent. */ - struct avltree_node *par; - - /** Node's key. */ - avltree_key_t key; - - /** - * Difference between the heights of the left and the right subtree of - * this node. - */ - int8_t balance; -}; - -/** AVL tree structure. */ -struct avltree { - /** AVL root node pointer */ - struct avltree_node *root; - - /** - * Base of the tree is a value that is smaller or equal than every value - * in the tree (valid for positive keys otherwise ignore this atribute). - * - * The base is added to the current key when a new node is inserted into - * the tree. The base is changed to the key of the node which is deleted - * with avltree_delete_min(). - */ - avltree_key_t base; -}; - -/** Create empty AVL tree. - * - * @param t AVL tree. - */ -NO_TRACE static inline void avltree_create(avltree_t *t) -{ - t->root = NULL; - t->base = 0; -} - -/** Initialize node. - * - * @param node Node which is initialized. - */ -NO_TRACE static inline void avltree_node_initialize(avltree_node_t *node) -{ - node->key = 0; - node->lft = NULL; - node->rgt = NULL; - node->par = NULL; - node->balance = 0; -} - -extern avltree_node_t *avltree_find_min(avltree_t *t); -extern avltree_node_t *avltree_search(avltree_t *t, avltree_key_t key); -extern void avltree_insert(avltree_t *t, avltree_node_t *newnode); -extern void avltree_delete(avltree_t *t, avltree_node_t *node); -extern bool avltree_delete_min(avltree_t *t); -extern void avltree_walk(avltree_t *t, avltree_walker_t walker, void *arg); - -#endif - -/** @} - */ Index: kernel/generic/include/proc/task.h =================================================================== --- kernel/generic/include/proc/task.h (revision 2e4343bb577304bd2bb9c0c4825438035b24ac6f) +++ kernel/generic/include/proc/task.h (revision ef1eab71c59f1782c6211550d5ee608250a791e0) @@ -44,8 +44,8 @@ #include #include -#include #include #include #include +#include #include #include @@ -70,6 +70,6 @@ /** Task structure. */ typedef struct task { - /** Task's linkage for the tasks_tree AVL tree. */ - avltree_node_t tasks_tree_node; + /** Link to @c tasks ordered dictionary */ + odlink_t ltasks; /** Task lock. @@ -146,6 +146,8 @@ } task_t; +/** Synchronize access to @c tasks */ IRQ_SPINLOCK_EXTERN(tasks_lock); -extern avltree_t tasks_tree; +/** Ordered dictionary of all tasks by ID (of task_t structures) */ +extern odict_t tasks; extern void task_init(void); Index: kernel/generic/include/proc/thread.h =================================================================== --- kernel/generic/include/proc/thread.h (revision 2e4343bb577304bd2bb9c0c4825438035b24ac6f) +++ kernel/generic/include/proc/thread.h (revision ef1eab71c59f1782c6211550d5ee608250a791e0) @@ -42,5 +42,5 @@ #include #include -#include +#include #include #include @@ -75,6 +75,6 @@ link_t th_link; /**< Links to threads within containing task. */ - /** Threads linkage to the threads_tree. */ - avltree_node_t threads_tree_node; + /** Link to @c threads ordered dictionary. */ + odlink_t lthreads; /** Lock protecting thread structure. @@ -224,14 +224,6 @@ } thread_t; -/** Thread list lock. - * - * This lock protects the threads_tree. - * Must be acquired before T.lock for each T of type thread_t. - * - */ IRQ_SPINLOCK_EXTERN(threads_lock); - -/** AVL tree containing all threads. */ -extern avltree_t threads_tree; +extern odict_t threads; extern void thread_init(void); Index: kernel/generic/src/adt/avl.c =================================================================== --- kernel/generic/src/adt/avl.c (revision 2e4343bb577304bd2bb9c0c4825438035b24ac6f) +++ (revision ) @@ -1,729 +1,0 @@ -/* - * Copyright (c) 2007 Vojtech Mencl - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * - * - Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - The name of the author may not be used to endorse or promote products - * derived from this software without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR - * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. - * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, - * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT - * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF - * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - */ - -/** @addtogroup kernel_generic_adt - * @{ - */ - -/** - * @file - * @brief AVL tree implementation. - * - * This file implements AVL tree type and operations. - * - * Implemented AVL tree has the following properties: - * @li It is a binary search tree with non-unique keys. - * @li Difference of heights of the left and the right subtree of every node is - * one at maximum. - * - * Every node has a pointer to its parent which allows insertion of multiple - * identical keys into the tree. - * - * Be careful when using this tree because of the base atribute which is added - * to every inserted node key. There is no rule in which order nodes with the - * same key are visited. - */ - -#include -#include - -#define LEFT 0 -#define RIGHT 1 - -/** Search for the first occurence of the given key in an AVL tree. - * - * @param t AVL tree. - * @param key Key to be searched. - * - * @return Pointer to a node or NULL if there is no such key. - */ -avltree_node_t *avltree_search(avltree_t *t, avltree_key_t key) -{ - avltree_node_t *p; - - /* - * Iteratively descend to the leaf that can contain the searched key. - */ - p = t->root; - while (p != NULL) { - if (p->key > key) - p = p->lft; - else if (p->key < key) - p = p->rgt; - else - return p; - } - return NULL; -} - -/** Find the node with the smallest key in an AVL tree. - * - * @param t AVL tree. - * - * @return Pointer to a node or NULL if there is no node in the tree. - */ -avltree_node_t *avltree_find_min(avltree_t *t) -{ - avltree_node_t *p = t->root; - - /* - * Check whether the tree is empty. - */ - if (!p) - return NULL; - - /* - * Iteratively descend to the leftmost leaf in the tree. - */ - while (p->lft != NULL) - p = p->lft; - - return p; -} - -#define REBALANCE_INSERT_XX(DIR1, DIR2) \ - top->DIR1 = par->DIR2; \ - if (top->DIR1 != NULL) \ - top->DIR1->par = top; \ - par->par = top->par; \ - top->par = par; \ - par->DIR2 = top; \ - par->balance = 0; \ - top->balance = 0; \ - *dpc = par; - -#define REBALANCE_INSERT_LL() REBALANCE_INSERT_XX(lft, rgt) -#define REBALANCE_INSERT_RR() REBALANCE_INSERT_XX(rgt, lft) - -#define REBALANCE_INSERT_XY(DIR1, DIR2, SGN) \ - gpa = par->DIR2; \ - par->DIR2 = gpa->DIR1; \ - if (gpa->DIR1 != NULL) \ - gpa->DIR1->par = par; \ - gpa->DIR1 = par; \ - par->par = gpa; \ - top->DIR1 = gpa->DIR2; \ - if (gpa->DIR2 != NULL) \ - gpa->DIR2->par = top; \ - gpa->DIR2 = top; \ - gpa->par = top->par; \ - top->par = gpa; \ - \ - if (gpa->balance == -1 * SGN) { \ - par->balance = 0; \ - top->balance = 1 * SGN; \ - } else if (gpa->balance == 0) { \ - par->balance = 0; \ - top->balance = 0; \ - } else { \ - par->balance = -1 * SGN; \ - top->balance = 0; \ - } \ - gpa->balance = 0; \ - *dpc = gpa; - -#define REBALANCE_INSERT_LR() REBALANCE_INSERT_XY(lft, rgt, 1) -#define REBALANCE_INSERT_RL() REBALANCE_INSERT_XY(rgt, lft, -1) - -/** Insert new node into AVL tree. - * - * @param t AVL tree. - * @param newnode New node to be inserted. - */ -void avltree_insert(avltree_t *t, avltree_node_t *newnode) -{ - avltree_node_t *par; - avltree_node_t *gpa; - avltree_node_t *top; - avltree_node_t **dpc; - avltree_key_t key; - - assert(t); - assert(newnode); - - /* - * Creating absolute key. - */ - key = newnode->key + t->base; - - /* - * Iteratively descend to the leaf that can contain the new node. - * Last node with non-zero balance in the way to leaf is stored as top - - * it is a place of possible inbalance. - */ - dpc = &t->root; - gpa = NULL; - top = t->root; - while ((par = (*dpc)) != NULL) { - if (par->balance != 0) { - top = par; - } - gpa = par; - dpc = par->key > key ? &par->lft : &par->rgt; - } - - /* - * Initialize the new node. - */ - newnode->key = key; - newnode->lft = NULL; - newnode->rgt = NULL; - newnode->par = gpa; - newnode->balance = 0; - - /* - * Insert first node into the empty tree. - */ - if (t->root == NULL) { - *dpc = newnode; - return; - } - - /* - * Insert the new node into the previously found leaf position. - */ - *dpc = newnode; - - /* - * If the tree contains one node - end. - */ - if (top == NULL) - return; - - /* - * Store pointer of top's father which points to the node with - * potentially broken balance (top). - */ - if (top->par == NULL) { - dpc = &t->root; - } else { - if (top->par->lft == top) - dpc = &top->par->lft; - else - dpc = &top->par->rgt; - } - - /* - * Repair all balances on the way from top node to the newly inserted - * node. - */ - par = top; - while (par != newnode) { - if (par->key > key) { - par->balance--; - par = par->lft; - } else { - par->balance++; - par = par->rgt; - } - } - - /* - * To balance the tree, we must check and balance top node. - */ - if (top->balance == -2) { - par = top->lft; - if (par->balance == -1) { - /* - * LL rotation. - */ - REBALANCE_INSERT_LL(); - } else { - /* - * LR rotation. - */ - assert(par->balance == 1); - - REBALANCE_INSERT_LR(); - } - } else if (top->balance == 2) { - par = top->rgt; - if (par->balance == 1) { - /* - * RR rotation. - */ - REBALANCE_INSERT_RR(); - } else { - /* - * RL rotation. - */ - assert(par->balance == -1); - - REBALANCE_INSERT_RL(); - } - } else { - /* - * Balance is not broken, insertion is finised. - */ - return; - } - -} - -/** Repair the tree after reparenting node u. - * - * If node u has no parent, mark it as the root of the whole tree. Otherwise - * node v represents stale address of one of the children of node u's parent. - * Replace v with w as node u parent's child (for most uses, u and w will be the - * same). - * - * @param t AVL tree. - * @param u Node whose new parent has a stale child pointer. - * @param v Stale child of node u's new parent. - * @param w New child of node u's new parent. - * @param dir If not NULL, address of the variable where to store information - * about whether w replaced v in the left or the right subtree of - * u's new parent. - * @param ro Read only operation; do not modify any tree pointers. This is - * useful for tracking direction via the dir pointer. - * - * @return Zero if w became the new root of the tree, otherwise return - * non-zero. - */ -static int -repair(avltree_t *t, avltree_node_t *u, avltree_node_t *v, avltree_node_t *w, - int *dir, int ro) -{ - if (u->par == NULL) { - if (!ro) - t->root = w; - return 0; - } else { - if (u->par->lft == v) { - if (!ro) - u->par->lft = w; - if (dir) - *dir = LEFT; - } else { - assert(u->par->rgt == v); - if (!ro) - u->par->rgt = w; - if (dir) - *dir = RIGHT; - } - } - return 1; -} - -#define REBALANCE_DELETE(DIR1, DIR2, SIGN) \ - if (cur->balance == -1 * SIGN) { \ - par->balance = 0; \ - gpa->balance = 1 * SIGN; \ - if (gpa->DIR1) \ - gpa->DIR1->par = gpa; \ - par->DIR2->par = par; \ - } else if (cur->balance == 0) { \ - par->balance = 0; \ - gpa->balance = 0; \ - if (gpa->DIR1) \ - gpa->DIR1->par = gpa; \ - if (par->DIR2) \ - par->DIR2->par = par; \ - } else { \ - par->balance = -1 * SIGN; \ - gpa->balance = 0; \ - if (par->DIR2) \ - par->DIR2->par = par; \ - gpa->DIR1->par = gpa; \ - } \ - cur->balance = 0; - -#define REBALANCE_DELETE_LR() REBALANCE_DELETE(lft, rgt, 1) -#define REBALANCE_DELETE_RL() REBALANCE_DELETE(rgt, lft, -1) - -/** Delete a node from the AVL tree. - * - * Because multiple identical keys are allowed, the parent pointers are - * essential during deletion. - * - * @param t AVL tree structure. - * @param node Address of the node which will be deleted. - */ -void avltree_delete(avltree_t *t, avltree_node_t *node) -{ - avltree_node_t *cur; - avltree_node_t *par; - avltree_node_t *gpa; - int dir; - - assert(t); - assert(node); - - if (node->lft == NULL) { - if (node->rgt) { - /* - * Replace the node with its only right son. - * - * Balance of the right son will be repaired in the - * balancing cycle. - */ - cur = node->rgt; - cur->par = node->par; - gpa = cur; - dir = RIGHT; - cur->balance = node->balance; - } else { - if (node->par == NULL) { - /* - * The tree has only one node - it will become - * an empty tree and the balancing can end. - */ - t->root = NULL; - return; - } - /* - * The node has no child, it will be deleted with no - * substitution. - */ - gpa = node->par; - cur = NULL; - dir = (gpa->lft == node) ? LEFT : RIGHT; - } - } else { - /* - * The node has the left son. Find a node with the smallest key - * in the left subtree and replace the deleted node with that - * node. - */ - cur = node->lft; - while (cur->rgt != NULL) - cur = cur->rgt; - - if (cur != node->lft) { - /* - * The rightmost node of the deleted node's left subtree - * was found. Replace the deleted node with this node. - * Cutting off of the found node has two cases that - * depend on its left son. - */ - if (cur->lft) { - /* - * The found node has a left son. - */ - gpa = cur->lft; - gpa->par = cur->par; - dir = LEFT; - gpa->balance = cur->balance; - } else { - dir = RIGHT; - gpa = cur->par; - } - cur->par->rgt = cur->lft; - cur->lft = node->lft; - cur->lft->par = cur; - } else { - /* - * The left son of the node hasn't got a right son. The - * left son will take the deleted node's place. - */ - dir = LEFT; - gpa = cur; - } - if (node->rgt) - node->rgt->par = cur; - cur->rgt = node->rgt; - cur->balance = node->balance; - cur->par = node->par; - } - - /* - * Repair the parent node's pointer which pointed previously to the - * deleted node. - */ - (void) repair(t, node, node, cur, NULL, false); - - /* - * Repair cycle which repairs balances of nodes on the way from from the - * cut-off node up to the root. - */ - while (true) { - if (dir == LEFT) { - /* - * Deletion was made in the left subtree. - */ - gpa->balance++; - if (gpa->balance == 1) { - /* - * Stop balancing, the tree is balanced. - */ - break; - } else if (gpa->balance == 2) { - /* - * Bad balance, heights of left and right - * subtrees differ more than by one. - */ - par = gpa->rgt; - - if (par->balance == -1) { - /* - * RL rotation. - */ - - cur = par->lft; - par->lft = cur->rgt; - cur->rgt = par; - gpa->rgt = cur->lft; - cur->lft = gpa; - - /* - * Repair balances and paternity of - * children, depending on the balance - * factor of the grand child (cur). - */ - REBALANCE_DELETE_RL(); - - /* - * Repair paternity. - */ - cur->par = gpa->par; - gpa->par = cur; - par->par = cur; - - if (!repair(t, cur, gpa, cur, &dir, - false)) - break; - gpa = cur->par; - } else { - /* - * RR rotation. - */ - - gpa->rgt = par->lft; - if (par->lft) - par->lft->par = gpa; - par->lft = gpa; - - /* - * Repair paternity. - */ - par->par = gpa->par; - gpa->par = par; - - if (par->balance == 0) { - /* - * The right child of the - * balanced node is balanced, - * after RR rotation is done, - * the whole tree will be - * balanced. - */ - par->balance = -1; - gpa->balance = 1; - - (void) repair(t, par, gpa, par, - NULL, false); - break; - } else { - par->balance = 0; - gpa->balance = 0; - if (!repair(t, par, gpa, par, - &dir, false)) - break; - } - gpa = par->par; - } - } else { - /* - * Repair the pointer which pointed to the - * balanced node. If it was root then balancing - * is finished else continue with the next - * iteration (parent node). - */ - if (!repair(t, gpa, gpa, NULL, &dir, true)) - break; - gpa = gpa->par; - } - } else { - /* - * Deletion was made in the right subtree. - */ - gpa->balance--; - if (gpa->balance == -1) { - /* - * Stop balancing, the tree is balanced. - */ - break; - } else if (gpa->balance == -2) { - /* - * Bad balance, heights of left and right - * subtrees differ more than by one. - */ - par = gpa->lft; - - if (par->balance == 1) { - /* - * LR rotation. - */ - - cur = par->rgt; - par->rgt = cur->lft; - cur->lft = par; - gpa->lft = cur->rgt; - cur->rgt = gpa; - - /* - * Repair balances and paternity of - * children, depending on the balance - * factor of the grand child (cur). - */ - REBALANCE_DELETE_LR(); - - /* - * Repair paternity. - */ - cur->par = gpa->par; - gpa->par = cur; - par->par = cur; - - if (!repair(t, cur, gpa, cur, &dir, - false)) - break; - gpa = cur->par; - } else { - /* - * LL rotation. - */ - - gpa->lft = par->rgt; - if (par->rgt) - par->rgt->par = gpa; - par->rgt = gpa; - /* - * Repair paternity. - */ - par->par = gpa->par; - gpa->par = par; - - if (par->balance == 0) { - /* - * The left child of the - * balanced node is balanced, - * after LL rotation is done, - * the whole tree will be - * balanced. - */ - par->balance = 1; - gpa->balance = -1; - - (void) repair(t, par, gpa, par, - NULL, false); - break; - } else { - par->balance = 0; - gpa->balance = 0; - - if (!repair(t, par, gpa, par, - &dir, false)) - break; - } - gpa = par->par; - } - } else { - /* - * Repair the pointer which pointed to the - * balanced node. If it was root then balancing - * is finished. Otherwise continue with the next - * iteration (parent node). - */ - if (!repair(t, gpa, gpa, NULL, &dir, true)) - break; - gpa = gpa->par; - } - } - } -} - -/** Delete a node with the smallest key from the AVL tree. - * - * @param t AVL tree structure. - */ -bool avltree_delete_min(avltree_t *t) -{ - avltree_node_t *node; - - /* - * Start searching for the smallest key in the tree starting in the root - * node and continue in cycle to the leftmost node in the tree (which - * must have the smallest key). - */ - - node = t->root; - if (!node) - return false; - - while (node->lft != NULL) - node = node->lft; - - avltree_delete(t, node); - - return true; -} - -/** Walk a subtree of an AVL tree in-order and apply a supplied walker on each - * visited node. - * - * @param node Node representing the root of an AVL subtree to be - * walked. - * @param walker Walker function that will be appliad on each visited - * node. - * @param arg Argument for the walker. - * - * @return Zero if the walk should stop or non-zero otherwise. - */ -static bool _avltree_walk(avltree_node_t *node, avltree_walker_t walker, - void *arg) -{ - if (node->lft) { - if (!_avltree_walk(node->lft, walker, arg)) - return false; - } - if (!walker(node, arg)) - return false; - if (node->rgt) { - if (!_avltree_walk(node->rgt, walker, arg)) - return false; - } - return true; -} - -/** Walk the AVL tree in-order and apply the walker function on each visited - * node. - * - * @param t AVL tree to be walked. - * @param walker Walker function that will be called on each visited - * node. - * @param arg Argument for the walker. - */ -void avltree_walk(avltree_t *t, avltree_walker_t walker, void *arg) -{ - if (t->root) - _avltree_walk(t->root, walker, arg); -} - -/** @} - */ Index: kernel/generic/src/proc/task.c =================================================================== --- kernel/generic/src/proc/task.c (revision 2e4343bb577304bd2bb9c0c4825438035b24ac6f) +++ kernel/generic/src/proc/task.c (revision ef1eab71c59f1782c6211550d5ee608250a791e0) @@ -1,4 +1,5 @@ /* * Copyright (c) 2010 Jakub Jermar + * Copyright (c) 2018 Jiri Svoboda * All rights reserved. * @@ -47,7 +48,7 @@ #include #include -#include #include #include +#include #include #include @@ -61,11 +62,11 @@ #include -/** Spinlock protecting the tasks_tree AVL tree. */ +/** Spinlock protecting the @c tasks ordered dictionary. */ IRQ_SPINLOCK_INITIALIZE(tasks_lock); -/** AVL tree of active tasks. - * - * The task is guaranteed to exist after it was found in the tasks_tree as - * long as: +/** Ordered dictionary of active tasks. + * + * The task is guaranteed to exist after it was found in the @c tasks + * dictionary as long as: * * @li the tasks_lock is held, @@ -75,5 +76,5 @@ * */ -avltree_t tasks_tree; +odict_t tasks; static task_id_t task_counter = 0; @@ -84,5 +85,8 @@ static void task_kill_internal(task_t *); static errno_t tsk_constructor(void *, unsigned int); -static size_t tsk_destructor(void *obj); +static size_t tsk_destructor(void *); + +static void *tasks_getkey(odlink_t *); +static int tasks_cmp(void *, void *); /** Initialize kernel tasks support. @@ -92,34 +96,9 @@ { TASK = NULL; - avltree_create(&tasks_tree); + odict_initialize(&tasks, tasks_getkey, tasks_cmp); task_cache = slab_cache_create("task_t", sizeof(task_t), 0, tsk_constructor, tsk_destructor, 0); } -/** Task finish walker. - * - * The idea behind this walker is to kill and count all tasks different from - * TASK. - * - */ -static bool task_done_walker(avltree_node_t *node, void *arg) -{ - task_t *task = avltree_get_instance(node, task_t, tasks_tree_node); - size_t *cnt = (size_t *) arg; - - if (task != TASK) { - (*cnt)++; - -#ifdef CONFIG_DEBUG - printf("[%" PRIu64 "] ", task->taskid); -#endif - - task_kill_internal(task); - } - - /* Continue the walk */ - return true; -} - /** Kill all tasks except the current task. * @@ -128,4 +107,6 @@ { size_t tasks_left; + odlink_t *odlink; + task_t *task; if (ipc_box_0) { @@ -144,8 +125,22 @@ printf("Killing tasks... "); #endif - irq_spinlock_lock(&tasks_lock, true); tasks_left = 0; - avltree_walk(&tasks_tree, task_done_walker, &tasks_left); + + odlink = odict_first(&tasks); + while (odlink != NULL) { + task = odict_get_instance(odlink, task_t, ltasks); + + if (task != TASK) { + tasks_left++; +#ifdef CONFIG_DEBUG + printf("[%" PRIu64 "] ", task->taskid); +#endif + task_kill_internal(task); + } + + odlink = odict_next(odlink, &tasks); + } + irq_spinlock_unlock(&tasks_lock, true); @@ -269,7 +264,6 @@ task->taskid = ++task_counter; - avltree_node_initialize(&task->tasks_tree_node); - task->tasks_tree_node.key = task->taskid; - avltree_insert(&tasks_tree, &task->tasks_tree_node); + odlink_initialize(&task->ltasks); + odict_insert(&task->ltasks, &tasks, NULL); irq_spinlock_unlock(&tasks_lock, true); @@ -289,5 +283,5 @@ */ irq_spinlock_lock(&tasks_lock, true); - avltree_delete(&tasks_tree, &task->tasks_tree_node); + odict_remove(&task->ltasks); irq_spinlock_unlock(&tasks_lock, true); @@ -451,9 +445,7 @@ assert(irq_spinlock_locked(&tasks_lock)); - avltree_node_t *node = - avltree_search(&tasks_tree, (avltree_key_t) id); - - if (node) - return avltree_get_instance(node, task_t, tasks_tree_node); + odlink_t *odlink = odict_find_eq(&tasks, &id, NULL); + if (odlink != NULL) + return odict_get_instance(odlink, task_t, ltasks); return NULL; @@ -604,8 +596,6 @@ } -static bool task_print_walker(avltree_node_t *node, void *arg) -{ - bool *additional = (bool *) arg; - task_t *task = avltree_get_instance(node, task_t, tasks_tree_node); +static void task_print(task_t *task, bool additional) +{ irq_spinlock_lock(&task->lock, false); @@ -618,5 +608,5 @@ #ifdef __32_BITS__ - if (*additional) + if (additional) printf("%-8" PRIu64 " %9zu", task->taskid, atomic_load(&task->refcount)); @@ -629,5 +619,5 @@ #ifdef __64_BITS__ - if (*additional) + if (additional) printf("%-8" PRIu64 " %9" PRIu64 "%c %9" PRIu64 "%c " "%9zu\n", task->taskid, ucycles, usuffix, kcycles, @@ -639,5 +629,4 @@ irq_spinlock_unlock(&task->lock, false); - return true; } @@ -669,9 +658,47 @@ #endif - avltree_walk(&tasks_tree, task_print_walker, &additional); + odlink_t *odlink; + task_t *task; + + odlink = odict_first(&tasks); + while (odlink != NULL) { + task = odict_get_instance(odlink, task_t, ltasks); + task_print(task, additional); + odlink = odict_next(odlink, &tasks); + } irq_spinlock_unlock(&tasks_lock, true); } +/** Get key function for the @c tasks ordered dictionary. + * + * @param odlink Link + * @return Pointer to task ID cast as 'void *' + */ +static void *tasks_getkey(odlink_t *odlink) +{ + task_t *task = odict_get_instance(odlink, task_t, ltasks); + return (void *) &task->taskid; +} + +/** Key comparison function for the @c tasks ordered dictionary. + * + * @param a Pointer to thread A ID + * @param b Pointer to thread B ID + * @return -1, 0, 1 iff ID A is less than, equal to, greater than B + */ +static int tasks_cmp(void *a, void *b) +{ + task_id_t ida = *(task_id_t *)a; + task_id_t idb = *(task_id_t *)b; + + if (ida < idb) + return -1; + else if (ida == idb) + return 0; + else + return +1; +} + /** @} */ Index: kernel/generic/src/proc/thread.c =================================================================== --- kernel/generic/src/proc/thread.c (revision 2e4343bb577304bd2bb9c0c4825438035b24ac6f) +++ kernel/generic/src/proc/thread.c (revision ef1eab71c59f1782c6211550d5ee608250a791e0) @@ -1,4 +1,5 @@ /* * Copyright (c) 2010 Jakub Jermar + * Copyright (c) 2018 Jiri Svoboda * All rights reserved. * @@ -52,6 +53,6 @@ #include #include -#include #include +#include #include