Viewing file:  irqueue.c (16.1 KB) -rw-r--r--
Select action/file-type:
 (+) |  (+) |  (+) | Code (+) | Session (+) |  (+) | SDB (+) |  (+) |  (+) |  (+) |  (+) |  (+) |
/*********************************************************************
*
* 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, __FUNCTION__"()\n");
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, __FUNCTION__ "()\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 ] );
}
/*
* 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, __FUNCTION__ "()\n");
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, __FUNCTION__ "()\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 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, __FUNCTION__ "()\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 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;
}
|