Subversion Repositories HelenOS

Compare Revisions

Ignore whitespace Rev 2415 → Rev 2416

/branches/rcu/kernel/generic/include/time/timeout.h
36,20 → 36,44
#define KERN_TIMEOUT_H_
 
#include <arch/types.h>
#ifdef CONFIG_TIMEOUT_EXTAVL_TREE
#if defined CONFIG_TIMEOUT_AVL_TREE
#include <adt/avl.h>
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE
#include <adt/extavl.h>
#elif defined CONFIG_TIMEOUT_EXTAVLREL_TREE
#include <adt/extavlrel.h>
#else
#include <adt/list.h>
#endif
#include <adt/list.h>
#include <cpu.h>
 
typedef void (* timeout_handler_t)(void *arg);
 
#ifdef CONFIG_TIMEOUT_EXTAVL_TREE
 
#if defined CONFIG_TIMEOUT_AVL_TREE
 
typedef struct {
SPINLOCK_DECLARE(lock);
/**
* AVL tree node structure holds information
* about connections with other timeouts.
*/
avltree_node_t node;
/** Function that will be called on timeout activation. */
timeout_handler_t handler;
/** Argument to be passed to handler() function. */
void *arg;
/** On which processor is this timeout registered. */
cpu_t *cpu;
} timeout_t;
 
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE
 
typedef struct {
SPINLOCK_DECLARE(lock);
/**
* Extended AVL tree node structure holds information
* about connections with other timeouts.
*/
62,6 → 86,24
cpu_t *cpu;
} timeout_t;
 
#elif defined CONFIG_TIMEOUT_EXTAVLREL_TREE
 
typedef struct {
SPINLOCK_DECLARE(lock);
/**
* Extended AVL tree with relative keys node structure holds information
* about connections with other timeouts.
*/
extavlreltree_node_t node;
/** Function that will be called on timeout activation. */
timeout_handler_t handler;
/** Argument to be passed to handler() function. */
void *arg;
/** On which processor is this timeout registered. */
cpu_t *cpu;
} timeout_t;
 
#else
 
typedef struct {
/branches/rcu/kernel/generic/include/cpu.h
64,9 → 64,15
volatile count_t needs_relink;
 
SPINLOCK_DECLARE(timeoutlock);
#ifdef CONFIG_TIMEOUT_EXTAVL_TREE
#if defined CONFIG_TIMEOUT_AVL_TREE
/** AVL tree structure. */
avltree_t timeout_active_tree;
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE
/** Extended AVL tree structure. */
extavltree_t timeout_active_tree;
#elif defined CONFIG_TIMEOUT_EXTAVLREL_TREE
/** Extended AVL tree structure with relative keys. */
extavlreltree_t timeout_active_tree;
#else
/** Head of list of timeouts. */
link_t timeout_active_head;
/branches/rcu/kernel/generic/include/adt/avl.h
0,0 → 1,131
/*
* Copyright (C) 2006 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 genericadt
* @{
*/
/** @file
*/
 
 
#ifndef KERN_AVLTREE_H_
#define KERN_AVLTREE_H_
 
#include <arch/types.h>
 
/*
* Makro for getting pointer to structure which enclosure avltree structure.
*
* @param link Pointer to avltree structure.
* @param type Name of outer structure.
* @param member Name of avltree atribute in outer structure.
*/
#define avltree_get_instance(link,type,member) \
((type *)(((uint8_t *)(link)) - ((uint8_t *)&(((type *)NULL)->member))))
 
 
typedef struct avltree_node avltree_node_t;
typedef struct avltree avltree_t;
 
 
/** AVL tree node structure. */
struct avltree_node
{
/**
* Pointer to left descendand of this node.
*
* All keys of nodes in the left subtree are less then key of this node.
*/
struct avltree_node *lft;
/**
* Pointer to right descendand of this node.
*
* All keys of nodes in the right subtree are greater then key of this node.
*/
struct avltree_node *rgt;
/** Pointer to parent node. Root node has NULL parent. */
struct avltree_node *par;
/** Nodes key. */
uint64_t key;
/** Difference between heights of left and right subtree of this node.*/
short balance;
};
 
/** AVL tree structure. */
struct avltree
{
/** AVL root node pointer */
struct avltree_node *root;
 
/**
* Base of tree is value that is smaller or equal then every value in tree.
*
* Base is added to current key when new node is inserted into tree.
* Base is changed to the key of node which is deleted with function
* avltree_delete_min.
*/
uint64_t base; /**< POZOR: Base time for inserting new nodes */
};
 
 
/** Create empty AVL tree.
*
* @param t AVL tree.
*/
static inline void avltree_create (avltree_t *t)
{
t->root = NULL;
t->base = 0;
}
 
/** Initialize node.
*
* @param Node which is initialized.
*/
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;
}
 
avltree_node_t *avltree_search(avltree_t *t, uint64_t key);
void avltree_insert(avltree_t *t, avltree_node_t *newnode);
void avltree_delete(avltree_t *t, avltree_node_t *node);
avltree_node_t *avltree_delete_min(avltree_t *t);
 
#endif
 
/** @}
*/
/branches/rcu/kernel/generic/include/adt/extavl.h
0,0 → 1,145
/*
* Copyright (c) 2006 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 genericadt
* @{
*/
/** @file
*/
 
 
#ifndef KERN_EXTAVLTREE_H_
#define KERN_EXTAVLTREE_H_
 
#include <arch/types.h>
 
/*
* Makro for getting pointer to structure which enclosure extavltree structure.
*
* @param link Pointer to extavltree structure.
* @param type Name of outer structure.
* @param member Name of extavltree atribute in outer structure.
*/
#define extavltree_get_instance(link,type,member) \
((type *)(((uint8_t *)(link)) - ((uint8_t *)&(((type *)NULL)->member))))
 
 
typedef struct extavltree_node extavltree_node_t;
typedef struct extavltree extavltree_t;
 
/** Extended AVL tree node structure. */
struct extavltree_node
{
/**
* Pointer to left descendand of this node.
*
* All keys of nodes in the left subtree are less then key of this node.
*/
extavltree_node_t *lft;
 
/**
* Pointer to right descendand of this node.
*
* All keys of nodes in the right subtree are greater then key of this node.
*/
extavltree_node_t *rgt;
/** Pointer to parent node. Root node has NULL parent. */
extavltree_node_t *par;
 
/** Pointer to next node which has equal or the closest greater key or head. */
extavltree_node_t *next;
/** Pointer to previous node which has equal or the closest lesser key or head. */
extavltree_node_t *prev;
/** Height of left subtree. */
int16_t lft_height;
 
/** Height of right subtree. */
int16_t rgt_height;
 
/** Nodes key. */
uint64_t key;
};
 
/** Extended AVL tree structure. */
struct extavltree
{
/** Extended AVL root node pointer. */
extavltree_node_t *root;
 
/** Head of doubly linked list of nodes. */
extavltree_node_t head;
 
/**
* Base of tree is value that is smaller or equal then every value in tree.
*
* Base is added to current key when new node is inserted into tree.
* Base is changed to the key of node which is deleted with function
* extavltree_delete_min.
*/
uint64_t base;
};
 
/** Initialize node.
*
* @param node Node which is initialized.
*/
static inline void extavltree_node_initialize(extavltree_node_t *node)
{
node->lft = NULL;
node->rgt = NULL;
node->lft_height = 0;
node->rgt_height = 0;
node->par = NULL;
node->next = node;
node->prev = node;
node->key = 0;
};
 
/** Create empty Extended AVL tree.
*
* @param t Extended AVL tree structure.
*/
static inline void extavltree_create (extavltree_t *t) //jen inicializace
{
t->root = NULL;
t->base = 0;
extavltree_node_initialize(&t->head);
};
 
extavltree_node_t *extavltree_search(extavltree_t *t, uint64_t key);
void extavltree_insert(extavltree_t *t, extavltree_node_t *newnode);
void extavltree_delete(extavltree_t *t, extavltree_node_t *node);
bool extavltree_delete_min(extavltree_t *t);
 
#endif
 
/** @}
*/
/branches/rcu/kernel/generic/include/adt/extavlrel.h
0,0 → 1,149
/*
* Copyright (C) 2006 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 genericadt
* @{
*/
/** @file
*/
 
 
#ifndef KERN_EXTAVLRELTREE_H_
#define KERN_EXTAVLRELTREE_H_
 
#include <arch/types.h>
 
typedef struct extavlreltree_node extavlreltree_node_t;
typedef struct extavlreltree extavlreltree_t;
 
 
/*
* Makro for getting pointer to structure which enclosure extavlreltree structure.
*
* @param link Pointer to extavlreltree structure.
* @param type Name of outer structure.
* @param member Name of extavlreltree atribute in outer structure.
*/
#define extavlreltree_get_instance(link,type,member) \
((type *)(((uint8_t *)(link)) - ((uint8_t *)&(((type *)NULL)->member))))
 
 
 
/** Relative key Extended AVL tree node structure. */
struct extavlreltree_node
{
/**
* Pointer to left descendand of this node.
*
* All keys of nodes in the left subtree are less then key of this node.
*/
extavlreltree_node_t *lft;
 
/**
* Pointer to right descendand of this node.
*
* All keys of nodes in the right subtree are greater then key of this node.
*/
extavlreltree_node_t *rgt;
/** Pointer to parent node. Root node has NULL parent. */
extavlreltree_node_t *par;
 
/** Pointer to next node which has equal or the closest greater key or head. */
extavlreltree_node_t *next;
/** Pointer to previous node which has equal or the closest lesser key or head. */
extavlreltree_node_t *prev;
/** Height of left subtree. */
int16_t lft_height;
 
/** Height of right subtree. */
int16_t rgt_height;
 
/** Nodes key. */
uint64_t key;
 
/** Sum of all keys in the right subtree. */
uint64_t rgt_sum;
};
 
/** Relative key Extended AVL tree structure (ExtAvlrel). */
#ifdef AVLTREE_TEST
struct extavlreltree
{
/*
* ExtAvlrel root node pointer.
*
* Important only for recognition of non tree node.
*/
extavlreltree_node_t *root;
 
/** Head of doubly linked list of nodes. It is entrance point to the tree. */
extavlreltree_node_t head;
};
 
 
 
/** Create empty Extended AVL tree.
*
* @param t Extended AVL tree structure.
*/
void extavlreltree_create (extavlreltree_t *t)
{
t->root = NULL;
 
t->head.next = &t->head;
t->head.prev = &t->head;
}
 
/** Initialize node.
*
* @param node Node which is initialized.
*/
void extavlreltree_node_initialize(extavlreltree_node_t *node)
{
node->lft = NULL;
node->rgt = NULL;
node->lft_height = 0;
node->rgt_height = 0;
node->par = NULL;
node->next = node;
node->prev = node;
node->rgt_sum = 0;
}
 
extavlreltree_node_t *extavlreltree_search(extavlreltree_t *t, uint64_t key);
void extavlreltree_insert(extavlreltree_t *t, extavlreltree_node_t *newnode);
void extavlreltree_delete(extavlreltree_t *t, extavlreltree_node_t *node);
bool extavlreltree_delete_min(extavlreltree_t *t);
 
#endif
 
/** @}
*/