/*********************************************************************
- *
+ *
* Filename: irqueue.c
* Version: 0.3
* Description: General queue implementation
* 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,
+ * 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
+ *
+ * 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
+ * provide warranty for any of this software. This material is
* provided "AS-IS" and at no charge.
- *
+ *
********************************************************************/
/*
{
__u32 h = 0;
__u32 g;
-
+
while(*name) {
h = (h<<4) + *name++;
if ((g = (h & 0xf0000000)))
*/
static void enqueue_first(irda_queue_t **queue, irda_queue_t* element)
{
-
+
IRDA_DEBUG( 4, "%s()\n", __FUNCTION__);
/*
* 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.
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.
+ * empty.
*/
*queue = NULL;
} else {
(*queue)->q_next->q_prev = (*queue)->q_prev;
*queue = (*queue)->q_next;
}
-
+
/*
* Return the removed entry (or NULL of queue was empty).
*/
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.
+ * empty.
*/
*queue = NULL;
-
+
} else {
/*
* Remove specific element.
if ( (*queue) == element)
(*queue) = element->q_next;
}
-
+
/*
* Return the removed entry (or NULL of queue was empty).
*/
hashbin_t *hashbin_new(int type)
{
hashbin_t* hashbin;
-
+
/*
* Allocate new hashbin
*/
- hashbin = kmalloc( sizeof(hashbin_t), GFP_ATOMIC);
+ hashbin = kzalloc(sizeof(*hashbin), GFP_ATOMIC);
if (!hashbin)
return NULL;
/*
* Initialize structure
*/
- memset(hashbin, 0, sizeof(hashbin_t));
hashbin->hb_type = type;
hashbin->magic = HB_MAGIC;
//hashbin->hb_current = NULL;
/*
* 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
+ * 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.
*/
+#ifdef CONFIG_LOCKDEP
+static int hashbin_lock_depth = 0;
+#endif
int hashbin_delete( hashbin_t* hashbin, FREE_FUNC free_func)
{
irda_queue_t* queue;
IRDA_ASSERT(hashbin != NULL, return -1;);
IRDA_ASSERT(hashbin->magic == HB_MAGIC, return -1;);
-
+
/* Synchronize */
if ( hashbin->hb_type & HB_LOCK ) {
- spin_lock_irqsave(&hashbin->hb_spinlock, flags);
+ spin_lock_irqsave_nested(&hashbin->hb_spinlock, flags,
+ hashbin_lock_depth++);
}
/*
while (queue ) {
if (free_func)
(*free_func)(queue);
- queue = dequeue_first(
+ queue = dequeue_first(
(irda_queue_t**) &hashbin->hb_queue[i]);
}
}
-
+
/* Cleanup local data */
hashbin->hb_current = NULL;
hashbin->magic = ~HB_MAGIC;
/* Release lock */
if ( hashbin->hb_type & HB_LOCK) {
spin_unlock_irqrestore(&hashbin->hb_spinlock, flags);
+#ifdef CONFIG_LOCKDEP
+ hashbin_lock_depth--;
+#endif
}
/*
* Insert an entry into the hashbin
*
*/
-void hashbin_insert(hashbin_t* hashbin, irda_queue_t* entry, long hashv,
+void hashbin_insert(hashbin_t* hashbin, irda_queue_t* entry, long hashv,
const char* name)
{
unsigned long flags = 0;
if ( hashbin->hb_type & HB_LOCK ) {
spin_lock_irqsave(&hashbin->hb_spinlock, flags);
} /* Default is no-lock */
-
+
/*
* Store name and key
*/
entry->q_hash = hashv;
if ( name )
strlcpy( entry->q_name, name, sizeof(entry->q_name));
-
+
/*
* Insert new entry first
*/
}
EXPORT_SYMBOL(hashbin_insert);
-/*
+/*
* Function hashbin_remove_first (hashbin)
*
* Remove first entry of the hashbin
}
-/*
+/*
* Function hashbin_remove (hashbin, hashv, name)
*
* Remove entry with the given name
IRDA_ASSERT( hashbin != NULL, return NULL;);
IRDA_ASSERT( hashbin->magic == HB_MAGIC, return NULL;);
-
+
/*
* Locate hashbin
*/
entry = entry->q_next;
} while ( entry != hashbin->hb_queue[ bin ] );
}
-
+
/*
* If entry was found, dequeue it
*/
if ( hashbin->hb_type & HB_LOCK ) {
spin_unlock_irqrestore(&hashbin->hb_spinlock, flags);
} /* Default is no-lock */
-
-
+
+
/* Return */
- if ( found )
+ if ( found )
return entry;
else
return NULL;
-
+
}
EXPORT_SYMBOL(hashbin_remove);
-/*
+/*
* Function hashbin_remove_this (hashbin, entry)
*
* Remove entry with the given name
IRDA_ASSERT( hashbin != NULL, return NULL;);
IRDA_ASSERT( hashbin->magic == HB_MAGIC, return NULL;);
IRDA_ASSERT( entry != NULL, return NULL;);
-
+
/* Synchronize */
if ( hashbin->hb_type & HB_LOCK ) {
spin_lock_irqsave(&hashbin->hb_spinlock, flags);
if ( name )
hashv = hash( name );
bin = GET_HASHBIN( hashv );
-
+
/*
* Search for entry
*/
* called before any calls to hashbin_get_next()!
*
*/
-irda_queue_t *hashbin_get_first( hashbin_t* hashbin)
+irda_queue_t *hashbin_get_first( hashbin_t* hashbin)
{
irda_queue_t *entry;
int i;
* 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
- *
+ *
* The context of the search is stored within the hashbin, so you must
* protect yourself from concurrent enumerations. - Jean II
*/
if ( hashbin->hb_current == NULL) {
IRDA_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
+ * again
*/
if ( entry != hashbin->hb_queue[ bin ]) {
hashbin->hb_current = entry;
*/
if ( bin >= HASHBIN_SIZE)
return NULL;
-
+
/*
* Move to next queue in hashbin
*/
entry = hashbin->hb_queue[ i];
if ( entry) {
hashbin->hb_current = entry;
-
+
return entry;
}
}