Changeset b76a2217 in mainline


Ignore:
Timestamp:
2007-07-29T19:17:25Z (17 years ago)
Author:
Jakub Jermar <jakub@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
7fe9c5b
Parents:
83a5cba
Message:

Give the AVL tree walkers the possibility to take an argument.
Each walker is now supposed to return a bool value to support walk termination.

Switch over from the tasks_btree B+tree to tasks_tree AVL tree.
This makes the fix for ticket #48 complete.

Location:
kernel/generic
Files:
5 edited

Legend:

Unmodified
Added
Removed

  • kernel/generic/include/adt/avl.h

    r83a5cba rb76a2217  
    5454typedef uint64_t avltree_key_t;
    5555
    56 typedef void (* avltree_walker_t)(avltree_node_t *);
     56typedef bool (* avltree_walker_t)(avltree_node_t *, void *);
    5757
    5858/** AVL tree node structure. */
    … …  
    134134extern void avltree_delete(avltree_t *t, avltree_node_t *node);
    135135extern bool avltree_delete_min(avltree_t *t);
    136 extern void avltree_walk(avltree_t *t, avltree_walker_t walker);
     136extern void avltree_walk(avltree_t *t, avltree_walker_t walker, void *arg);
    137137
    138138#endif

  • kernel/generic/include/proc/task.h

    r83a5cba rb76a2217  
    4242#include <synch/rwlock.h>
    4343#include <synch/futex.h>
     44#include <adt/avl.h>
    4445#include <adt/btree.h>
    4546#include <adt/list.h>
    … …  
    5758/** Task structure. */
    5859typedef struct task {
     60        /** Task's linkage for the tasks_tree AVL tree. */
     61        avltree_node_t tasks_tree_node;
     62       
    5963        /** Task lock.
    6064         *
    … …  
    107111
    108112SPINLOCK_EXTERN(tasks_lock);
    109 extern btree_t tasks_btree;
     113extern avltree_t tasks_tree;
    110114
    111115extern void task_init(void);

  • kernel/generic/src/adt/avl.c

    r83a5cba rb76a2217  
    686686}
    687687
    688 static void _avltree_walk(avltree_node_t *node, avltree_walker_t walker)
     688/** Walk a subtree of an AVL tree in-order and apply a supplied walker on each
     689 * visited node.
     690 *
     691 * @param node          Node representing the root of an AVL subtree to be
     692 *                      walked.
     693 * @param walker        Walker function that will be appliad on each visited
     694 *                      node.
     695 * @param arg           Argument for the walker.
     696 *
     697 * @return              Zero if the walk should stop or non-zero otherwise.
     698 */
     699static bool _avltree_walk(avltree_node_t *node, avltree_walker_t walker,
     700    void *arg)
    689701{
    690         if (node->lft)
    691                 _avltree_walk(node->lft, walker);
    692         walker(node);
    693         if (node->rgt)
    694                 _avltree_walk(node->rgt, walker);
     702        if (node->lft) {
     703                if (!_avltree_walk(node->lft, walker, arg))
     704                        return false;
     705        }
     706        if (!walker(node, arg))
     707                return false;
     708        if (node->rgt) {
     709                if (!_avltree_walk(node->rgt, walker, arg))
     710                        return false;
     711        }
     712        return true;
    695713}
    696714
    697 /** Walk the AVL tree and apply the walker function on each visited node.
     715/** Walk the AVL tree in-order and apply the walker function on each visited
     716 * node.
    698717 *
    699718 * @param t             AVL tree to be walked.
    700719 * @param walker        Walker function that will be called on each visited
    701720 *                      node.
    702  */
    703 void avltree_walk(avltree_t *t, avltree_walker_t walker)
     721 * @param arg           Argument for the walker.
     722 */
     723void avltree_walk(avltree_t *t, avltree_walker_t walker, void *arg)
    704724{
    705         _avltree_walk(t->root, walker);
     725        _avltree_walk(t->root, walker, arg);
    706726}
    707727

  • kernel/generic/src/proc/task.c

    r83a5cba rb76a2217  
    4747#include <arch.h>
    4848#include <panic.h>
     49#include <adt/avl.h>
    4950#include <adt/btree.h>
    5051#include <adt/list.h>
    … …  
    6263#endif
    6364
    64 /** Spinlock protecting the tasks_btree B+tree. */
     65/** Spinlock protecting the tasks_tree AVL tree. */
    6566SPINLOCK_INITIALIZE(tasks_lock);
    6667
    67 /** B+tree of active tasks.
    68  *
    69  * The task is guaranteed to exist after it was found in the tasks_btree as
     68/** AVL tree of active tasks.
     69 *
     70 * The task is guaranteed to exist after it was found in the tasks_tree as
    7071 * long as:
    7172 * @li the tasks_lock is held,
    … …  
    7576 *
    7677 */
    77 btree_t tasks_btree;
     78avltree_t tasks_tree;
    7879
    7980static task_id_t task_counter = 0;
    … …  
    8788{
    8889        TASK = NULL;
    89         btree_create(&tasks_btree);
     90        avltree_create(&tasks_tree);
     91}
     92
     93/*
     94 * The idea behind this walker is to remember a single task different from TASK.
     95 */
     96static bool task_done_walker(avltree_node_t *node, void *arg)
     97{
     98        task_t *t = avltree_get_instance(node, task_t, tasks_tree_node);
     99        task_t **tp = (task_t **) arg;
     100
     101        if (t != TASK) {
     102                *tp = t;
     103                return false;   /* stop walking */
     104        }
     105
     106        return true;    /* continue the walk */
    90107}
    91108
    … …  
    103120               
    104121                t = NULL;
    105                 link_t *cur;
    106                 for (cur = tasks_btree.leaf_head.next;
    107                     cur != &tasks_btree.leaf_head; cur = cur->next) {
    108                         btree_node_t *node;
    109                        
    110                         node = list_get_instance(cur, btree_node_t, leaf_link);
    111                        
    112                         unsigned int i;
    113                         for (i = 0; i < node->keys; i++) {
    114                                 if ((task_t *) node->value[i] != TASK) {
    115                                         t = (task_t *) node->value[i];
    116                                         break;
    117                                 }
    118                         }
    119                 }
     122                avltree_walk(&tasks_tree, task_done_walker, &t);
    120123               
    121124                if (t != NULL) {
    … …  
    188191        spinlock_lock(&tasks_lock);
    189192        ta->taskid = ++task_counter;
    190         btree_insert(&tasks_btree, (btree_key_t) ta->taskid, (void *) ta, NULL);
     193        avltree_node_initialize(&ta->tasks_tree_node);
     194        ta->tasks_tree_node.key = ta->taskid;
     195        avltree_insert(&tasks_tree, &ta->tasks_tree_node);
    191196        spinlock_unlock(&tasks_lock);
    192197        interrupts_restore(ipl);
    … …  
    205210         */
    206211        spinlock_lock(&tasks_lock);
    207         btree_remove(&tasks_btree, t->taskid, NULL);
     212        avltree_delete(&tasks_tree, &t->tasks_tree_node);
    208213        spinlock_unlock(&tasks_lock);
    209214
    … …  
    311316task_t *task_find_by_id(task_id_t id)
    312317{
    313         btree_node_t *leaf;
    314        
    315         return (task_t *) btree_search(&tasks_btree, (btree_key_t) id, &leaf);
     318        avltree_node_t *node;
     319       
     320        node = avltree_search(&tasks_tree, (avltree_key_t) id);
     321
     322        if (node)
     323                return avltree_get_instance(node, task_t, tasks_tree_node);
     324        return NULL;
    316325}
    317326
    … …  
    401410}
    402411
     412static bool task_print_walker(avltree_node_t *node, void *arg)
     413{
     414        task_t *t = avltree_get_instance(node, task_t, tasks_tree_node);
     415        int j;
     416               
     417        spinlock_lock(&t->lock);
     418                       
     419        uint64_t cycles;
     420        char suffix;
     421        order(task_get_accounting(t), &cycles, &suffix);
     422                       
     423        printf("%-6llu %-10s %-3ld %#10zx %#10zx %9llu%c %7zd %6zd",
     424            t->taskid, t->name, t->context, t, t->as, cycles, suffix,
     425            t->refcount, atomic_get(&t->active_calls));
     426        for (j = 0; j < IPC_MAX_PHONES; j++) {
     427                if (t->phones[j].callee)
     428                        printf(" %zd:%#zx", j, t->phones[j].callee);
     429        }
     430        printf("\n");
     431                       
     432        spinlock_unlock(&t->lock);
     433        return true;
     434}
     435
    403436/** Print task list */
    404437void task_print_list(void)
    405438{
    406         link_t *cur;
    407439        ipl_t ipl;
    408440       
    … …  
    416448            "------ ------>\n");
    417449
    418         for (cur = tasks_btree.leaf_head.next; cur != &tasks_btree.leaf_head;
    419             cur = cur->next) {
    420                 btree_node_t *node;
    421                 unsigned int i;
    422                
    423                 node = list_get_instance(cur, btree_node_t, leaf_link);
    424                 for (i = 0; i < node->keys; i++) {
    425                         task_t *t;
    426                         int j;
    427 
    428                         t = (task_t *) node->value[i];
    429                
    430                         spinlock_lock(&t->lock);
    431                        
    432                         uint64_t cycles;
    433                         char suffix;
    434                         order(task_get_accounting(t), &cycles, &suffix);
    435                        
    436                         printf("%-6llu %-10s %-3ld %#10zx %#10zx %9llu%c %7zd "
    437                             "%6zd", t->taskid, t->name, t->context, t, t->as,
    438                             cycles, suffix, t->refcount,
    439                             atomic_get(&t->active_calls));
    440                         for (j = 0; j < IPC_MAX_PHONES; j++) {
    441                                 if (t->phones[j].callee)
    442                                         printf(" %zd:%#zx", j,
    443                                             t->phones[j].callee);
    444                         }
    445                         printf("\n");
    446                        
    447                         spinlock_unlock(&t->lock);
    448                 }
    449         }
     450        avltree_walk(&tasks_tree, task_print_walker, NULL);
    450451
    451452        spinlock_unlock(&tasks_lock);

  • kernel/generic/src/proc/thread.c

    r83a5cba rb76a2217  
    578578}
    579579
    580 static void thread_walker(avltree_node_t *node)
     580static bool thread_walker(avltree_node_t *node, void *arg)
    581581{
    582582        thread_t *t;
    … …  
    601601                       
    602602        printf("\n");
     603
     604        return true;
    603605}
    604606
    … …  
    617619            "-- ---------- ---------- ---- ---------\n");
    618620
    619         avltree_walk(&threads_tree, thread_walker);
     621        avltree_walk(&threads_tree, thread_walker, NULL);
    620622
    621623        spinlock_unlock(&threads_lock);
Note: See TracChangeset for help on using the changeset viewer.