URL https://opencores.org/ocsvn/or1k/or1k/trunk

Subversion Repositories or1k

[/] [or1k/] [trunk/] [linux/] [linux-2.4/] [net/] [irda/] [irqueue.c] - Blame information for rev 1765

Details | Compare with Previous | View Log


/*********************************************************************
 *
 * Filename:      irqueue.c
 * Version:       0.3
 * Description:   General queue implementation
 * Status:        Experimental.
 * Author:        Dag Brattli <dagb@cs.uit.no>
 * Created at:    Tue Jun  9 13:29:31 1998
 * Modified at:   Sun Dec 12 13:48:22 1999
 * Modified by:   Dag Brattli <dagb@cs.uit.no>
 * Modified at:   Thu Jan  4 14:29:10 CET 2001
 * Modified by:   Marc Zyngier <mzyngier@freesurf.fr>
 *
 *     Copyright (C) 1998-1999, Aage Kvalnes <aage@cs.uit.no>
 *     Copyright (C) 1998, Dag Brattli,
 *     All Rights Reserved.
 *
 *     This code is taken from the Vortex Operating System written by Aage
 *     Kvalnes. Aage has agreed that this code can use the GPL licence,
 *     although he does not use that licence in his own code.
 *
 *     This copyright does however _not_ include the ELF hash() function
 *     which I currently don't know which licence or copyright it
 *     has. Please inform me if you know.
 *
 *     This program is free software; you can redistribute it and/or
 *     modify it under the terms of the GNU General Public License as
 *     published by the Free Software Foundation; either version 2 of
 *     the License, or (at your option) any later version.
 *
 *     Neither Dag Brattli nor University of Troms� admit liability nor
 *     provide warranty for any of this software. This material is
 *     provided "AS-IS" and at no charge.
 *
 ********************************************************************/
 
#include <net/irda/irda.h>
#include <net/irda/irqueue.h>
#include <net/irda/irmod.h>
 
static irda_queue_t *dequeue_general( irda_queue_t **queue, irda_queue_t* element);
static __u32 hash( char* name);
 
/*
 * Function hashbin_create ( type, name )
 *
 *    Create hashbin!
 *
 */
hashbin_t *hashbin_new(int type)
{
        hashbin_t* hashbin;
        int i;
 
        /*
         * Allocate new hashbin
         */
        hashbin = kmalloc( sizeof(hashbin_t), GFP_ATOMIC);
        if (!hashbin)
                return NULL;
 
        /*
         * Initialize structure
         */
        memset(hashbin, 0, sizeof(hashbin_t));
        hashbin->hb_type = type;
        hashbin->magic = HB_MAGIC;
 
        /* Make sure all spinlock's are unlocked */
        for (i=0;i<HASHBIN_SIZE;i++)
                hashbin->hb_mutex[i] = SPIN_LOCK_UNLOCKED;
 
        return hashbin;
}
 
/*
 * Function hashbin_clear (hashbin, free_func)
 *
 *    Remove all entries from the hashbin, see also the comments in
 *    hashbin_delete() below
 */
int hashbin_clear( hashbin_t* hashbin, FREE_FUNC free_func)
{
        irda_queue_t* queue;
        int i;
 
        ASSERT(hashbin != NULL, return -1;);
        ASSERT(hashbin->magic == HB_MAGIC, return -1;);
 
        /*
         * Free the entries in the hashbin
         */
        for (i = 0; i < HASHBIN_SIZE; i ++ ) {
                queue = dequeue_first( (irda_queue_t**) &hashbin->hb_queue[i]);
                while (queue) {
                        if (free_func)
                                (*free_func)(queue);
                        queue = dequeue_first(
                                (irda_queue_t**) &hashbin->hb_queue[i]);
                }
        }
        hashbin->hb_size = 0;
 
        return 0;
}
 
 
/*
 * Function hashbin_delete (hashbin, free_func)
 *
 *    Destroy hashbin, the free_func can be a user supplied special routine
 *    for deallocating this structure if it's complex. If not the user can
 *    just supply kfree, which should take care of the job.
 */
int hashbin_delete( hashbin_t* hashbin, FREE_FUNC free_func)
{
        irda_queue_t* queue;
        int i;
 
        ASSERT(hashbin != NULL, return -1;);
        ASSERT(hashbin->magic == HB_MAGIC, return -1;);
 
        /*
         *  Free the entries in the hashbin, TODO: use hashbin_clear when
         *  it has been shown to work
         */
        for (i = 0; i < HASHBIN_SIZE; i ++ ) {
                queue = dequeue_first((irda_queue_t**) &hashbin->hb_queue[i]);
                while (queue ) {
                        if (free_func)
                                (*free_func)(queue);
                        queue = dequeue_first(
                                (irda_queue_t**) &hashbin->hb_queue[i]);
                }
        }
 
        /*
         *  Free the hashbin structure
         */
        hashbin->magic = ~HB_MAGIC;
        kfree(hashbin);
 
        return 0;
}
 
/*
 * Function hashbin_insert (hashbin, entry, name)
 *
 *    Insert an entry into the hashbin
 *
 */
void hashbin_insert(hashbin_t* hashbin, irda_queue_t* entry, __u32 hashv, char* name)
{
        unsigned long flags = 0;
        int bin;
 
        IRDA_DEBUG( 4,"%s()\n", __FUNCTION__);
 
        ASSERT( hashbin != NULL, return;);
        ASSERT( hashbin->magic == HB_MAGIC, return;);
 
        /*
         * Locate hashbin
         */
        if ( name )
                hashv = hash( name );
        bin = GET_HASHBIN( hashv );
 
        /* Synchronize */
        if ( hashbin->hb_type & HB_GLOBAL ) {
                spin_lock_irqsave( &hashbin->hb_mutex[ bin ], flags);
 
        } else if ( hashbin->hb_type & HB_LOCAL ) {
                save_flags(flags);
                cli();
        } /* Default is no-lock  */
 
        /*
         * Store name and key
         */
        entry->q_hash = hashv;
        if ( name )
                strncpy( entry->q_name, name, 32);
 
        /*
         * Insert new entry first
         * TODO: Perhaps allow sorted lists?
         *       -> Merge sort if a sorted list should be created
         */
        if ( hashbin->hb_type & HB_SORTED) {
        } else {
                enqueue_first( (irda_queue_t**) &hashbin->hb_queue[ bin ],
                               entry);
        }
        hashbin->hb_size++;
 
        /* Release lock */
        if ( hashbin->hb_type & HB_GLOBAL) {
 
                spin_unlock_irqrestore( &hashbin->hb_mutex[ bin], flags);
 
        } else if ( hashbin->hb_type & HB_LOCAL) {
                restore_flags( flags);
        }
}
 
/*
 * Function hashbin_find (hashbin, hashv, name)
 *
 *    Find item with the given hashv or name
 *
 */
void* hashbin_find( hashbin_t* hashbin, __u32 hashv, char* name )
{
        int bin, found = FALSE;
        unsigned long flags = 0;
        irda_queue_t* entry;
 
        IRDA_DEBUG( 4, "hashbin_find()\n");
 
        ASSERT( hashbin != NULL, return NULL;);
        ASSERT( hashbin->magic == HB_MAGIC, return NULL;);
 
        /*
         * Locate hashbin
         */
        if ( name )
                hashv = hash( name );
        bin = GET_HASHBIN( hashv );
 
        /* Synchronize */
        if ( hashbin->hb_type & HB_GLOBAL ) {
                spin_lock_irqsave( &hashbin->hb_mutex[ bin ], flags);
 
        } else if ( hashbin->hb_type & HB_LOCAL ) {
                save_flags(flags);
                cli();
        } /* Default is no-lock  */
 
        /*
         * Search for entry
         */
        entry = hashbin->hb_queue[ bin];
        if ( entry ) {
                do {
                        /*
                         * Check for key
                         */
                        if ( entry->q_hash == hashv ) {
                                /*
                                 * Name compare too?
                                 */
                                if ( name ) {
                                        if ( strcmp( entry->q_name, name ) == 0 ) {
                                                found = TRUE;
                                                break;
                                        }
                                } else {
                                        found = TRUE;
                                        break;
                                }
                        }
                        entry = entry->q_next;
                } while ( entry != hashbin->hb_queue[ bin ] );
        }
 
        /* Release lock */
        if ( hashbin->hb_type & HB_GLOBAL) {
                spin_unlock_irqrestore( &hashbin->hb_mutex[ bin], flags);
 
        } else if ( hashbin->hb_type & HB_LOCAL) {
                restore_flags( flags);
        }
 
        if ( found )
                return entry;
        else
                return NULL;
}
 
void *hashbin_remove_first( hashbin_t *hashbin)
{
        unsigned long flags;
        irda_queue_t *entry = NULL;
 
        save_flags(flags);
        cli();
 
        entry = hashbin_get_first( hashbin);
        if ( entry != NULL)
                hashbin_remove( hashbin, entry->q_hash, NULL);
 
        restore_flags( flags);
 
        return entry;
}
 
 
/*
 *  Function hashbin_remove (hashbin, hashv, name)
 *
 *    Remove entry with the given name
 *
 */
void* hashbin_remove( hashbin_t* hashbin, __u32 hashv, char* name)
{
        int bin, found = FALSE;
        unsigned long flags = 0;
        irda_queue_t* entry;
 
        IRDA_DEBUG( 4, "%s()\n", __FUNCTION__);
 
        ASSERT( hashbin != NULL, return NULL;);
        ASSERT( hashbin->magic == HB_MAGIC, return NULL;);
 
        /*
         * Locate hashbin
         */
        if ( name )
                hashv = hash( name );
        bin = GET_HASHBIN( hashv );
 
        /* Synchronize */
        if ( hashbin->hb_type & HB_GLOBAL ) {
                spin_lock_irqsave( &hashbin->hb_mutex[ bin ], flags);
 
        } else if ( hashbin->hb_type & HB_LOCAL ) {
                save_flags(flags);
                cli();
        } /* Default is no-lock  */
 
        /*
         * Search for entry
         */
        entry = hashbin->hb_queue[ bin ];
        if ( entry ) {
                do {
                        /*
                         * Check for key
                         */
                        if ( entry->q_hash == hashv ) {
                                /*
                                 * Name compare too?
                                 */
                                if ( name ) {
                                        if ( strcmp( entry->q_name, name) == 0)
                                        {
                                                found = TRUE;
                                                break;
                                        }
                                } else {
                                        found = TRUE;
                                        break;
                                }
                        }
                        entry = entry->q_next;
                } while ( entry != hashbin->hb_queue[ bin ] );
        }
 
        /*
         * If entry was found, dequeue it
         */
        if ( found ) {
                dequeue_general( (irda_queue_t**) &hashbin->hb_queue[ bin ],
                                 (irda_queue_t*) entry );
                hashbin->hb_size--;
 
                /*
                 *  Check if this item is the currently selected item, and in
                 *  that case we must reset hb_current
                 */
                if ( entry == hashbin->hb_current)
                        hashbin->hb_current = NULL;
        }
 
        /* Release lock */
        if ( hashbin->hb_type & HB_GLOBAL) {
                spin_unlock_irqrestore( &hashbin->hb_mutex[ bin], flags);
 
        } else if ( hashbin->hb_type & HB_LOCAL) {
                restore_flags( flags);
        }
 
 
        /* Return */
        if ( found )
                return entry;
        else
                return NULL;
 
}
 
/*
 *  Function hashbin_remove (hashbin, hashv, name)
 *
 *    Remove entry with the given name
 *
 * In some cases, the user of hashbin can't guarantee the unicity
 * of either the hashv or name.
 * In those cases, using the above function is guaranteed to cause troubles,
 * so we use this one instead...
 * And by the way, it's also faster, because we skip the search phase ;-)
 */
void* hashbin_remove_this( hashbin_t* hashbin, irda_queue_t* entry)
{
        unsigned long flags = 0;
        int     bin;
        __u32   hashv;
 
        IRDA_DEBUG( 4, "%s()\n", __FUNCTION__);
 
        ASSERT( hashbin != NULL, return NULL;);
        ASSERT( hashbin->magic == HB_MAGIC, return NULL;);
        ASSERT( entry != NULL, return NULL;);
 
        /* Check if valid and not already removed... */
        if((entry->q_next == NULL) || (entry->q_prev == NULL))
                return NULL;
 
        /*
         * Locate hashbin
         */
        hashv = entry->q_hash;
        bin = GET_HASHBIN( hashv );
 
        /* Synchronize */
        if ( hashbin->hb_type & HB_GLOBAL ) {
                spin_lock_irqsave( &hashbin->hb_mutex[ bin ], flags);
 
        } else if ( hashbin->hb_type & HB_LOCAL ) {
                save_flags(flags);
                cli();
        } /* Default is no-lock  */
 
        /*
         * Dequeue the entry...
         */
        dequeue_general( (irda_queue_t**) &hashbin->hb_queue[ bin ],
                         (irda_queue_t*) entry );
        hashbin->hb_size--;
        entry->q_next = NULL;
        entry->q_prev = NULL;
 
        /*
         *  Check if this item is the currently selected item, and in
         *  that case we must reset hb_current
         */
        if ( entry == hashbin->hb_current)
                hashbin->hb_current = NULL;
 
        /* Release lock */
        if ( hashbin->hb_type & HB_GLOBAL) {
                spin_unlock_irqrestore( &hashbin->hb_mutex[ bin], flags);
 
        } else if ( hashbin->hb_type & HB_LOCAL) {
                restore_flags( flags);
        }
 
        return entry;
}
 
/*
 * Function hashbin_get_first (hashbin)
 *
 *    Get a pointer to first element in hashbin, this function must be
 *    called before any calls to hashbin_get_next()!
 *
 */
irda_queue_t *hashbin_get_first( hashbin_t* hashbin)
{
        irda_queue_t *entry;
        int i;
 
        ASSERT( hashbin != NULL, return NULL;);
        ASSERT( hashbin->magic == HB_MAGIC, return NULL;);
 
        if ( hashbin == NULL)
                return NULL;
 
        for ( i = 0; i < HASHBIN_SIZE; i ++ ) {
                entry = hashbin->hb_queue[ i];
                if ( entry) {
                        hashbin->hb_current = entry;
                        return entry;
                }
        }
        /*
         *  Did not find any item in hashbin
         */
        return NULL;
}
 
/*
 * Function hashbin_get_next (hashbin)
 *
 *    Get next item in hashbin. A series of hashbin_get_next() calls must
 *    be started by a call to hashbin_get_first(). The function returns
 *    NULL when all items have been traversed
 *
 */
irda_queue_t *hashbin_get_next( hashbin_t *hashbin)
{
        irda_queue_t* entry;
        int bin;
        int i;
 
        ASSERT( hashbin != NULL, return NULL;);
        ASSERT( hashbin->magic == HB_MAGIC, return NULL;);
 
        if ( hashbin->hb_current == NULL) {
                ASSERT( hashbin->hb_current != NULL, return NULL;);
                return NULL;
        }
        entry = hashbin->hb_current->q_next;
        bin = GET_HASHBIN( entry->q_hash);
 
        /*
         *  Make sure that we are not back at the beginning of the queue
         *  again
         */
        if ( entry != hashbin->hb_queue[ bin ]) {
                hashbin->hb_current = entry;
 
                return entry;
        }
 
        /*
         *  Check that this is not the last queue in hashbin
         */
        if ( bin >= HASHBIN_SIZE)
                return NULL;
 
        /*
         *  Move to next queue in hashbin
         */
        bin++;
        for ( i = bin; i < HASHBIN_SIZE; i++ ) {
                entry = hashbin->hb_queue[ i];
                if ( entry) {
                        hashbin->hb_current = entry;
 
                        return entry;
                }
        }
        return NULL;
}
 
/*
 * Function enqueue_last (queue, proc)
 *
 *    Insert item into end of queue.
 *
 */
static void __enqueue_last( irda_queue_t **queue, irda_queue_t* element)
{
        IRDA_DEBUG( 4, "%s()\n", __FUNCTION__);
 
        /*
         * Check if queue is empty.
         */
        if ( *queue == NULL ) {
                /*
                 * Queue is empty.  Insert one element into the queue.
                 */
                element->q_next = element->q_prev = *queue = element;
 
        } else {
                /*
                 * Queue is not empty.  Insert element into end of queue.
                 */
                element->q_prev         = (*queue)->q_prev;
                element->q_prev->q_next = element;
                (*queue)->q_prev        = element;
                element->q_next         = *queue;
        }
}
 
inline void enqueue_last( irda_queue_t **queue, irda_queue_t* element)
{
        unsigned long flags;
 
        save_flags(flags);
        cli();
 
        __enqueue_last( queue, element);
 
        restore_flags(flags);
}
 
/*
 * Function enqueue_first (queue, proc)
 *
 *    Insert item first in queue.
 *
 */
void enqueue_first(irda_queue_t **queue, irda_queue_t* element)
{
 
        IRDA_DEBUG( 4, "%s()\n", __FUNCTION__);
 
        /*
         * Check if queue is empty.
         */
        if ( *queue == NULL ) {
                /*
                 * Queue is empty.  Insert one element into the queue.
                 */
                element->q_next = element->q_prev = *queue = element;
 
        } else {
                /*
                 * Queue is not empty.  Insert element into front of queue.
                 */
                element->q_next          = (*queue);
                (*queue)->q_prev->q_next = element;
                element->q_prev          = (*queue)->q_prev;
                (*queue)->q_prev         = element;
                (*queue)                 = element;
        }
}
 
/*
 * Function enqueue_queue (queue, list)
 *
 *    Insert a queue (list) into the start of the first queue
 *
 */
void enqueue_queue( irda_queue_t** queue, irda_queue_t** list )
{
        irda_queue_t* tmp;
 
        /*
         * Check if queue is empty
         */
        if ( *queue ) {
                (*list)->q_prev->q_next  = (*queue);
                (*queue)->q_prev->q_next = (*list);
                tmp                      = (*list)->q_prev;
                (*list)->q_prev          = (*queue)->q_prev;
                (*queue)->q_prev         = tmp;
        } else {
                *queue                   = (*list);
        }
 
        (*list) = NULL;
}
 
/*
 * Function enqueue_second (queue, proc)
 *
 *    Insert item behind head of queue.
 *
 */
#if 0
static void enqueue_second(irda_queue_t **queue, irda_queue_t* element)
{
        IRDA_DEBUG( 0, "enqueue_second()\n");
 
        /*
         * Check if queue is empty.
         */
        if ( *queue == NULL ) {
                /*
                 * Queue is empty.  Insert one element into the queue.
                 */
                element->q_next = element->q_prev = *queue = element;
 
        } else {
                /*
                 * Queue is not empty.  Insert element into ..
                 */
                element->q_prev = (*queue);
                (*queue)->q_next->q_prev = element;
                element->q_next = (*queue)->q_next;
                (*queue)->q_next = element;
        }
}
#endif
 
/*
 * Function dequeue (queue)
 *
 *    Remove first entry in queue
 *
 */
irda_queue_t *dequeue_first(irda_queue_t **queue)
{
        irda_queue_t *ret;
 
        IRDA_DEBUG( 4, "dequeue_first()\n");
 
        /*
         * Set return value
         */
        ret =  *queue;
 
        if ( *queue == NULL ) {
                /*
                 * Queue was empty.
                 */
        } else if ( (*queue)->q_next == *queue ) {
                /*
                 *  Queue only contained a single element. It will now be
                 *  empty.
                 */
                *queue = NULL;
        } else {
                /*
                 * Queue contained several element.  Remove the first one.
                 */
                (*queue)->q_prev->q_next = (*queue)->q_next;
                (*queue)->q_next->q_prev = (*queue)->q_prev;
                *queue = (*queue)->q_next;
        }
 
        /*
         * Return the removed entry (or NULL of queue was empty).
         */
        return ret;
}
 
/*
 * Function dequeue_general (queue, element)
 *
 *
 */
static irda_queue_t *dequeue_general(irda_queue_t **queue, irda_queue_t* element)
{
        irda_queue_t *ret;
 
        IRDA_DEBUG( 4, "dequeue_general()\n");
 
        /*
         * Set return value
         */
        ret =  *queue;
 
        if ( *queue == NULL ) {
                /*
                 * Queue was empty.
                 */
        } else if ( (*queue)->q_next == *queue ) {
                /*
                 *  Queue only contained a single element. It will now be
                 *  empty.
                 */
                *queue = NULL;
 
        } else {
                /*
                 *  Remove specific element.
                 */
                element->q_prev->q_next = element->q_next;
                element->q_next->q_prev = element->q_prev;
                if ( (*queue) == element)
                        (*queue) = element->q_next;
        }
 
        /*
         * Return the removed entry (or NULL of queue was empty).
         */
        return ret;
}
 
/*
 * Function hash (name)
 *
 *    This function hash the input string 'name' using the ELF hash
 *    function for strings.
 */
static __u32 hash( char* name)
{
        __u32 h = 0;
        __u32 g;
 
        while(*name) {
                h = (h<<4) + *name++;
                if ((g = (h & 0xf0000000)))
                        h ^=g>>24;
                h &=~g;
        }
        return h;
}

Browse

Tools

Subversion Repositories or1k

[/] [or1k/] [trunk/] [linux/] [linux-2.4/] [net/] [irda/] [irqueue.c] - Blame information for rev 1765

Line No.	Rev	Author	Line
1	1275	phoenix	`/*********************************************************************`
2			`*`
3			`* Filename: irqueue.c`
4			`* Version: 0.3`
5			`* Description: General queue implementation`
6			`* Status: Experimental.`
7			`* Author: Dag Brattli <dagb@cs.uit.no>`
8			`* Created at: Tue Jun 9 13:29:31 1998`
9			`* Modified at: Sun Dec 12 13:48:22 1999`
10			`* Modified by: Dag Brattli <dagb@cs.uit.no>`
11			`* Modified at: Thu Jan 4 14:29:10 CET 2001`
12			`* Modified by: Marc Zyngier <mzyngier@freesurf.fr>`
13			`*`
14			`* Copyright (C) 1998-1999, Aage Kvalnes <aage@cs.uit.no>`
15			`* Copyright (C) 1998, Dag Brattli,`
16			`* All Rights Reserved.`
17			`*`
18			`* This code is taken from the Vortex Operating System written by Aage`
19			`* Kvalnes. Aage has agreed that this code can use the GPL licence,`
20			`* although he does not use that licence in his own code.`
21			`*`
22			`* This copyright does however _not_ include the ELF hash() function`
23			`* which I currently don't know which licence or copyright it`
24			`* has. Please inform me if you know.`
25			`*`
26			`* This program is free software; you can redistribute it and/or`
27			`* modify it under the terms of the GNU General Public License as`
28			`* published by the Free Software Foundation; either version 2 of`
29			`* the License, or (at your option) any later version.`
30			`*`
31			`* Neither Dag Brattli nor University of Troms� admit liability nor`
32			`* provide warranty for any of this software. This material is`
33			`* provided "AS-IS" and at no charge.`
34			`*`
35			`********************************************************************/`
36
37			`#include <net/irda/irda.h>`
38			`#include <net/irda/irqueue.h>`
39			`#include <net/irda/irmod.h>`
40
41			`static irda_queue_t dequeue_general( irda_queue_t queue, irda_queue_t element);`
42			`static __u32 hash( char* name);`
43
44			`/*`
45			`* Function hashbin_create ( type, name )`
46			`*`
47			`* Create hashbin!`
48			`*`
49			`*/`
50			`hashbin_t *hashbin_new(int type)`
51			`{`
52			`hashbin_t* hashbin;`
53			`int i;`
54
55			`/*`
56			`* Allocate new hashbin`
57			`*/`
58			`hashbin = kmalloc( sizeof(hashbin_t), GFP_ATOMIC);`
59			`if (!hashbin)`
60			`return NULL;`
61
62			`/*`
63			`* Initialize structure`
64			`*/`
65			`memset(hashbin, 0, sizeof(hashbin_t));`
66			`hashbin->hb_type = type;`
67			`hashbin->magic = HB_MAGIC;`
68
69			`/* Make sure all spinlock's are unlocked */`
70			`for (i=0;i<HASHBIN_SIZE;i++)`
71			`hashbin->hb_mutex[i] = SPIN_LOCK_UNLOCKED;`
72
73			`return hashbin;`
74			`}`
75
76			`/*`
77			`* Function hashbin_clear (hashbin, free_func)`
78			`*`
79			`* Remove all entries from the hashbin, see also the comments in`
80			`* hashbin_delete() below`
81			`*/`
82			`int hashbin_clear( hashbin_t* hashbin, FREE_FUNC free_func)`
83			`{`
84			`irda_queue_t* queue;`
85			`int i;`
86
87			`ASSERT(hashbin != NULL, return -1;);`
88			`ASSERT(hashbin->magic == HB_MAGIC, return -1;);`
89
90			`/*`
91			`* Free the entries in the hashbin`
92			`*/`
93			`for (i = 0; i < HASHBIN_SIZE; i ++ ) {`
94			`queue = dequeue_first( (irda_queue_t**) &hashbin->hb_queue[i]);`
95			`while (queue) {`
96			`if (free_func)`
97			`(*free_func)(queue);`
98			`queue = dequeue_first(`
99			`(irda_queue_t**) &hashbin->hb_queue[i]);`
100			`}`
101			`}`
102			`hashbin->hb_size = 0;`
103
104			`return 0;`
105			`}`
106
107
108			`/*`
109			`* Function hashbin_delete (hashbin, free_func)`
110			`*`
111			`* Destroy hashbin, the free_func can be a user supplied special routine`
112			`* for deallocating this structure if it's complex. If not the user can`
113			`* just supply kfree, which should take care of the job.`
114			`*/`
115			`int hashbin_delete( hashbin_t* hashbin, FREE_FUNC free_func)`
116			`{`
117			`irda_queue_t* queue;`
118			`int i;`
119
120			`ASSERT(hashbin != NULL, return -1;);`
121			`ASSERT(hashbin->magic == HB_MAGIC, return -1;);`
122
123			`/*`
124			`* Free the entries in the hashbin, TODO: use hashbin_clear when`
125			`* it has been shown to work`
126			`*/`
127			`for (i = 0; i < HASHBIN_SIZE; i ++ ) {`
128			`queue = dequeue_first((irda_queue_t**) &hashbin->hb_queue[i]);`
129			`while (queue ) {`
130			`if (free_func)`
131			`(*free_func)(queue);`
132			`queue = dequeue_first(`
133			`(irda_queue_t**) &hashbin->hb_queue[i]);`
134			`}`
135			`}`
136
137			`/*`
138			`* Free the hashbin structure`
139			`*/`
140			`hashbin->magic = ~HB_MAGIC;`
141			`kfree(hashbin);`
142
143			`return 0;`
144			`}`
145
146			`/*`
147			`* Function hashbin_insert (hashbin, entry, name)`
148			`*`
149			`* Insert an entry into the hashbin`
150			`*`
151			`*/`
152			`void hashbin_insert(hashbin_t* hashbin, irda_queue_t* entry, __u32 hashv, char* name)`
153			`{`
154			`unsigned long flags = 0;`
155			`int bin;`
156
157			`IRDA_DEBUG( 4,"%s()\n", __FUNCTION__);`
158
159			`ASSERT( hashbin != NULL, return;);`
160			`ASSERT( hashbin->magic == HB_MAGIC, return;);`
161
162			`/*`
163			`* Locate hashbin`
164			`*/`
165			`if ( name )`
166			`hashv = hash( name );`
167			`bin = GET_HASHBIN( hashv );`
168
169			`/* Synchronize */`
170			`if ( hashbin->hb_type & HB_GLOBAL ) {`
171			`spin_lock_irqsave( &hashbin->hb_mutex[ bin ], flags);`
172
173			`} else if ( hashbin->hb_type & HB_LOCAL ) {`
174			`save_flags(flags);`
175			`cli();`
176			`} /* Default is no-lock */`
177
178			`/*`
179			`* Store name and key`
180			`*/`
181			`entry->q_hash = hashv;`
182			`if ( name )`
183			`strncpy( entry->q_name, name, 32);`
184
185			`/*`
186			`* Insert new entry first`
187			`* TODO: Perhaps allow sorted lists?`
188			`* -> Merge sort if a sorted list should be created`
189			`*/`
190			`if ( hashbin->hb_type & HB_SORTED) {`
191			`} else {`
192			`enqueue_first( (irda_queue_t**) &hashbin->hb_queue[ bin ],`
193			`entry);`
194			`}`
195			`hashbin->hb_size++;`
196
197			`/* Release lock */`
198			`if ( hashbin->hb_type & HB_GLOBAL) {`
199
200			`spin_unlock_irqrestore( &hashbin->hb_mutex[ bin], flags);`
201
202			`} else if ( hashbin->hb_type & HB_LOCAL) {`
203			`restore_flags( flags);`
204			`}`
205			`}`
206
207			`/*`
208			`* Function hashbin_find (hashbin, hashv, name)`
209			`*`
210			`* Find item with the given hashv or name`
211			`*`
212			`*/`
213			`void* hashbin_find( hashbin_t* hashbin, __u32 hashv, char* name )`
214			`{`
215			`int bin, found = FALSE;`
216			`unsigned long flags = 0;`
217			`irda_queue_t* entry;`
218
219			`IRDA_DEBUG( 4, "hashbin_find()\n");`
220
221			`ASSERT( hashbin != NULL, return NULL;);`
222			`ASSERT( hashbin->magic == HB_MAGIC, return NULL;);`
223
224			`/*`
225			`* Locate hashbin`
226			`*/`
227			`if ( name )`
228			`hashv = hash( name );`
229			`bin = GET_HASHBIN( hashv );`
230
231			`/* Synchronize */`
232			`if ( hashbin->hb_type & HB_GLOBAL ) {`
233			`spin_lock_irqsave( &hashbin->hb_mutex[ bin ], flags);`
234
235			`} else if ( hashbin->hb_type & HB_LOCAL ) {`
236			`save_flags(flags);`
237			`cli();`
238			`} /* Default is no-lock */`
239
240			`/*`
241			`* Search for entry`
242			`*/`
243			`entry = hashbin->hb_queue[ bin];`
244			`if ( entry ) {`
245			`do {`
246			`/*`
247			`* Check for key`
248			`*/`
249			`if ( entry->q_hash == hashv ) {`
250			`/*`
251			`* Name compare too?`
252			`*/`
253			`if ( name ) {`
254			`if ( strcmp( entry->q_name, name ) == 0 ) {`
255			`found = TRUE;`
256			`break;`
257			`}`
258			`} else {`
259			`found = TRUE;`
260			`break;`
261			`}`
262			`}`
263			`entry = entry->q_next;`
264			`} while ( entry != hashbin->hb_queue[ bin ] );`
265			`}`
266
267			`/* Release lock */`
268			`if ( hashbin->hb_type & HB_GLOBAL) {`
269			`spin_unlock_irqrestore( &hashbin->hb_mutex[ bin], flags);`
270
271			`} else if ( hashbin->hb_type & HB_LOCAL) {`
272			`restore_flags( flags);`
273			`}`
274
275			`if ( found )`
276			`return entry;`
277			`else`
278			`return NULL;`
279			`}`
280
281			`void hashbin_remove_first( hashbin_t hashbin)`
282			`{`
283			`unsigned long flags;`
284			`irda_queue_t *entry = NULL;`
285
286			`save_flags(flags);`
287			`cli();`
288
289			`entry = hashbin_get_first( hashbin);`
290			`if ( entry != NULL)`
291			`hashbin_remove( hashbin, entry->q_hash, NULL);`
292
293			`restore_flags( flags);`
294
295			`return entry;`
296			`}`
297
298
299			`/*`
300			`* Function hashbin_remove (hashbin, hashv, name)`
301			`*`
302			`* Remove entry with the given name`
303			`*`
304			`*/`
305			`void* hashbin_remove( hashbin_t* hashbin, __u32 hashv, char* name)`
306			`{`
307			`int bin, found = FALSE;`
308			`unsigned long flags = 0;`
309			`irda_queue_t* entry;`
310
311			`IRDA_DEBUG( 4, "%s()\n", __FUNCTION__);`
312
313			`ASSERT( hashbin != NULL, return NULL;);`
314			`ASSERT( hashbin->magic == HB_MAGIC, return NULL;);`
315
316			`/*`
317			`* Locate hashbin`
318			`*/`
319			`if ( name )`
320			`hashv = hash( name );`
321			`bin = GET_HASHBIN( hashv );`
322
323			`/* Synchronize */`
324			`if ( hashbin->hb_type & HB_GLOBAL ) {`
325			`spin_lock_irqsave( &hashbin->hb_mutex[ bin ], flags);`
326
327			`} else if ( hashbin->hb_type & HB_LOCAL ) {`
328			`save_flags(flags);`
329			`cli();`
330			`} /* Default is no-lock */`
331
332			`/*`
333			`* Search for entry`
334			`*/`
335			`entry = hashbin->hb_queue[ bin ];`
336			`if ( entry ) {`
337			`do {`
338			`/*`
339			`* Check for key`
340			`*/`
341			`if ( entry->q_hash == hashv ) {`
342			`/*`
343			`* Name compare too?`
344			`*/`
345			`if ( name ) {`
346			`if ( strcmp( entry->q_name, name) == 0)`
347			`{`
348			`found = TRUE;`
349			`break;`
350			`}`
351			`} else {`
352			`found = TRUE;`
353			`break;`
354			`}`
355			`}`
356			`entry = entry->q_next;`
357			`} while ( entry != hashbin->hb_queue[ bin ] );`
358			`}`
359
360			`/*`
361			`* If entry was found, dequeue it`
362			`*/`
363			`if ( found ) {`
364			`dequeue_general( (irda_queue_t**) &hashbin->hb_queue[ bin ],`
365			`(irda_queue_t*) entry );`
366			`hashbin->hb_size--;`
367
368			`/*`
369			`* Check if this item is the currently selected item, and in`
370			`* that case we must reset hb_current`
371			`*/`
372			`if ( entry == hashbin->hb_current)`
373			`hashbin->hb_current = NULL;`
374			`}`
375
376			`/* Release lock */`
377			`if ( hashbin->hb_type & HB_GLOBAL) {`
378			`spin_unlock_irqrestore( &hashbin->hb_mutex[ bin], flags);`
379
380			`} else if ( hashbin->hb_type & HB_LOCAL) {`
381			`restore_flags( flags);`
382			`}`
383
384
385			`/* Return */`
386			`if ( found )`
387			`return entry;`
388			`else`
389			`return NULL;`
390
391			`}`
392
393			`/*`
394			`* Function hashbin_remove (hashbin, hashv, name)`
395			`*`
396			`* Remove entry with the given name`
397			`*`
398			`* In some cases, the user of hashbin can't guarantee the unicity`
399			`* of either the hashv or name.`
400			`* In those cases, using the above function is guaranteed to cause troubles,`
401			`* so we use this one instead...`
402			`* And by the way, it's also faster, because we skip the search phase ;-)`
403			`*/`
404			`void* hashbin_remove_this( hashbin_t* hashbin, irda_queue_t* entry)`
405			`{`
406			`unsigned long flags = 0;`
407			`int bin;`
408			`__u32 hashv;`
409
410			`IRDA_DEBUG( 4, "%s()\n", __FUNCTION__);`
411
412			`ASSERT( hashbin != NULL, return NULL;);`
413			`ASSERT( hashbin->magic == HB_MAGIC, return NULL;);`
414			`ASSERT( entry != NULL, return NULL;);`
415
416			`/* Check if valid and not already removed... */`
417			`if((entry->q_next == NULL) \|\| (entry->q_prev == NULL))`
418			`return NULL;`
419
420			`/*`
421			`* Locate hashbin`
422			`*/`
423			`hashv = entry->q_hash;`
424			`bin = GET_HASHBIN( hashv );`
425
426			`/* Synchronize */`
427			`if ( hashbin->hb_type & HB_GLOBAL ) {`
428			`spin_lock_irqsave( &hashbin->hb_mutex[ bin ], flags);`
429
430			`} else if ( hashbin->hb_type & HB_LOCAL ) {`
431			`save_flags(flags);`
432			`cli();`
433			`} /* Default is no-lock */`
434
435			`/*`
436			`* Dequeue the entry...`
437			`*/`
438			`dequeue_general( (irda_queue_t**) &hashbin->hb_queue[ bin ],`
439			`(irda_queue_t*) entry );`
440			`hashbin->hb_size--;`
441			`entry->q_next = NULL;`
442			`entry->q_prev = NULL;`
443
444			`/*`
445			`* Check if this item is the currently selected item, and in`
446			`* that case we must reset hb_current`
447			`*/`
448			`if ( entry == hashbin->hb_current)`
449			`hashbin->hb_current = NULL;`
450
451			`/* Release lock */`
452			`if ( hashbin->hb_type & HB_GLOBAL) {`
453			`spin_unlock_irqrestore( &hashbin->hb_mutex[ bin], flags);`
454
455			`} else if ( hashbin->hb_type & HB_LOCAL) {`
456			`restore_flags( flags);`
457			`}`
458
459			`return entry;`
460			`}`
461
462			`/*`
463			`* Function hashbin_get_first (hashbin)`
464			`*`
465			`* Get a pointer to first element in hashbin, this function must be`
466			`* called before any calls to hashbin_get_next()!`
467			`*`
468			`*/`
469			`irda_queue_t hashbin_get_first( hashbin_t hashbin)`
470			`{`
471			`irda_queue_t *entry;`
472			`int i;`
473
474			`ASSERT( hashbin != NULL, return NULL;);`
475			`ASSERT( hashbin->magic == HB_MAGIC, return NULL;);`
476
477			`if ( hashbin == NULL)`
478			`return NULL;`
479
480			`for ( i = 0; i < HASHBIN_SIZE; i ++ ) {`
481			`entry = hashbin->hb_queue[ i];`
482			`if ( entry) {`
483			`hashbin->hb_current = entry;`
484			`return entry;`
485			`}`
486			`}`
487			`/*`
488			`* Did not find any item in hashbin`
489			`*/`
490			`return NULL;`
491			`}`
492
493			`/*`
494			`* Function hashbin_get_next (hashbin)`
495			`*`
496			`* Get next item in hashbin. A series of hashbin_get_next() calls must`
497			`* be started by a call to hashbin_get_first(). The function returns`
498			`* NULL when all items have been traversed`
499			`*`
500			`*/`
501			`irda_queue_t hashbin_get_next( hashbin_t hashbin)`
502			`{`
503			`irda_queue_t* entry;`
504			`int bin;`
505			`int i;`
506
507			`ASSERT( hashbin != NULL, return NULL;);`
508			`ASSERT( hashbin->magic == HB_MAGIC, return NULL;);`
509
510			`if ( hashbin->hb_current == NULL) {`
511			`ASSERT( hashbin->hb_current != NULL, return NULL;);`
512			`return NULL;`
513			`}`
514			`entry = hashbin->hb_current->q_next;`
515			`bin = GET_HASHBIN( entry->q_hash);`
516
517			`/*`
518			`* Make sure that we are not back at the beginning of the queue`
519			`* again`
520			`*/`
521			`if ( entry != hashbin->hb_queue[ bin ]) {`
522			`hashbin->hb_current = entry;`
523
524			`return entry;`
525			`}`
526
527			`/*`
528			`* Check that this is not the last queue in hashbin`
529			`*/`
530			`if ( bin >= HASHBIN_SIZE)`
531			`return NULL;`
532
533			`/*`
534			`* Move to next queue in hashbin`
535			`*/`
536			`bin++;`
537			`for ( i = bin; i < HASHBIN_SIZE; i++ ) {`
538			`entry = hashbin->hb_queue[ i];`
539			`if ( entry) {`
540			`hashbin->hb_current = entry;`
541
542			`return entry;`
543			`}`
544			`}`
545			`return NULL;`
546			`}`
547
548			`/*`
549			`* Function enqueue_last (queue, proc)`
550			`*`
551			`* Insert item into end of queue.`
552			`*`
553			`*/`
554			`static void __enqueue_last( irda_queue_t *queue, irda_queue_t element)`
555			`{`
556			`IRDA_DEBUG( 4, "%s()\n", __FUNCTION__);`
557
558			`/*`
559			`* Check if queue is empty.`
560			`*/`
561			`if ( *queue == NULL ) {`
562			`/*`
563			`* Queue is empty. Insert one element into the queue.`
564			`*/`
565			`element->q_next = element->q_prev = *queue = element;`
566
567			`} else {`
568			`/*`
569			`* Queue is not empty. Insert element into end of queue.`
570			`*/`
571			`element->q_prev = (*queue)->q_prev;`
572			`element->q_prev->q_next = element;`
573			`(*queue)->q_prev = element;`
574			`element->q_next = *queue;`
575			`}`
576			`}`
577
578			`inline void enqueue_last( irda_queue_t *queue, irda_queue_t element)`
579			`{`
580			`unsigned long flags;`
581
582			`save_flags(flags);`
583			`cli();`
584
585			`__enqueue_last( queue, element);`
586
587			`restore_flags(flags);`
588			`}`
589
590			`/*`
591			`* Function enqueue_first (queue, proc)`
592			`*`
593			`* Insert item first in queue.`
594			`*`
595			`*/`
596			`void enqueue_first(irda_queue_t *queue, irda_queue_t element)`
597			`{`
598
599			`IRDA_DEBUG( 4, "%s()\n", __FUNCTION__);`
600
601			`/*`
602			`* Check if queue is empty.`
603			`*/`
604			`if ( *queue == NULL ) {`
605			`/*`
606			`* Queue is empty. Insert one element into the queue.`
607			`*/`
608			`element->q_next = element->q_prev = *queue = element;`
609
610			`} else {`
611			`/*`
612			`* Queue is not empty. Insert element into front of queue.`
613			`*/`
614			`element->q_next = (*queue);`
615			`(*queue)->q_prev->q_next = element;`
616			`element->q_prev = (*queue)->q_prev;`
617			`(*queue)->q_prev = element;`
618			`(*queue) = element;`
619			`}`
620			`}`
621
622			`/*`
623			`* Function enqueue_queue (queue, list)`
624			`*`
625			`* Insert a queue (list) into the start of the first queue`
626			`*`
627			`*/`
628			`void enqueue_queue( irda_queue_t queue, irda_queue_t list )`
629			`{`
630			`irda_queue_t* tmp;`
631
632			`/*`
633			`* Check if queue is empty`
634			`*/`
635			`if ( *queue ) {`
636			`(list)->q_prev->q_next = (queue);`
637			`(queue)->q_prev->q_next = (list);`
638			`tmp = (*list)->q_prev;`
639			`(list)->q_prev = (queue)->q_prev;`
640			`(*queue)->q_prev = tmp;`
641			`} else {`
642			`queue = (list);`
643			`}`
644
645			`(*list) = NULL;`
646			`}`
647
648			`/*`
649			`* Function enqueue_second (queue, proc)`
650			`*`
651			`* Insert item behind head of queue.`
652			`*`
653			`*/`
654			`#if 0`
655			`static void enqueue_second(irda_queue_t *queue, irda_queue_t element)`
656			`{`
657			`IRDA_DEBUG( 0, "enqueue_second()\n");`
658
659			`/*`
660			`* Check if queue is empty.`
661			`*/`
662			`if ( *queue == NULL ) {`
663			`/*`
664			`* Queue is empty. Insert one element into the queue.`
665			`*/`
666			`element->q_next = element->q_prev = *queue = element;`
667
668			`} else {`
669			`/*`
670			`* Queue is not empty. Insert element into ..`
671			`*/`
672			`element->q_prev = (*queue);`
673			`(*queue)->q_next->q_prev = element;`
674			`element->q_next = (*queue)->q_next;`
675			`(*queue)->q_next = element;`
676			`}`
677			`}`
678			`#endif`
679
680			`/*`
681			`* Function dequeue (queue)`
682			`*`
683			`* Remove first entry in queue`
684			`*`
685			`*/`
686			`irda_queue_t dequeue_first(irda_queue_t *queue)`
687			`{`
688			`irda_queue_t *ret;`
689
690			`IRDA_DEBUG( 4, "dequeue_first()\n");`
691
692			`/*`
693			`* Set return value`
694			`*/`
695			`ret = *queue;`
696
697			`if ( *queue == NULL ) {`
698			`/*`
699			`* Queue was empty.`
700			`*/`
701			`} else if ( (queue)->q_next == queue ) {`
702			`/*`
703			`* Queue only contained a single element. It will now be`
704			`* empty.`
705			`*/`
706			`*queue = NULL;`
707			`} else {`
708			`/*`
709			`* Queue contained several element. Remove the first one.`
710			`*/`
711			`(queue)->q_prev->q_next = (queue)->q_next;`
712			`(queue)->q_next->q_prev = (queue)->q_prev;`
713			`queue = (queue)->q_next;`
714			`}`
715
716			`/*`
717			`* Return the removed entry (or NULL of queue was empty).`
718			`*/`
719			`return ret;`
720			`}`
721
722			`/*`
723			`* Function dequeue_general (queue, element)`
724			`*`
725			`*`
726			`*/`
727			`static irda_queue_t dequeue_general(irda_queue_t queue, irda_queue_t element)`
728			`{`
729			`irda_queue_t *ret;`
730
731			`IRDA_DEBUG( 4, "dequeue_general()\n");`
732
733			`/*`
734			`* Set return value`
735			`*/`
736			`ret = *queue;`
737
738			`if ( *queue == NULL ) {`
739			`/*`
740			`* Queue was empty.`
741			`*/`
742			`} else if ( (queue)->q_next == queue ) {`
743			`/*`
744			`* Queue only contained a single element. It will now be`
745			`* empty.`
746			`*/`
747			`*queue = NULL;`
748
749			`} else {`
750			`/*`
751			`* Remove specific element.`
752			`*/`
753			`element->q_prev->q_next = element->q_next;`
754			`element->q_next->q_prev = element->q_prev;`
755			`if ( (*queue) == element)`
756			`(*queue) = element->q_next;`
757			`}`
758
759			`/*`
760			`* Return the removed entry (or NULL of queue was empty).`
761			`*/`
762			`return ret;`
763			`}`
764
765			`/*`
766			`* Function hash (name)`
767			`*`
768			`* This function hash the input string 'name' using the ELF hash`
769			`* function for strings.`
770			`*/`
771			`static __u32 hash( char* name)`
772			`{`
773			`__u32 h = 0;`
774			`__u32 g;`
775
776			`while(*name) {`
777			`h = (h<<4) + *name++;`
778			`if ((g = (h & 0xf0000000)))`
779			`h ^=g>>24;`
780			`h &=~g;`
781			`}`
782			`return h;`
783			`}`