1 /*********************************************************************
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>
14 * Copyright (C) 1998-1999, Aage Kvalnes <aage@cs.uit.no>
15 * Copyright (C) 1998, Dag Brattli,
16 * All Rights Reserved.
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.
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.
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.
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.
35 ********************************************************************/
37 #include <net/irda/irda.h>
38 #include <net/irda/irqueue.h>
39 #include <net/irda/irmod.h>
41 static irda_queue_t *dequeue_general( irda_queue_t **queue, irda_queue_t* element);
42 static __u32 hash( char* name);
45 * Function hashbin_create ( type, name )
50 hashbin_t *hashbin_new(int type)
56 * Allocate new hashbin
58 hashbin = kmalloc( sizeof(hashbin_t), GFP_ATOMIC);
63 * Initialize structure
65 memset(hashbin, 0, sizeof(hashbin_t));
66 hashbin->hb_type = type;
67 hashbin->magic = HB_MAGIC;
69 /* Make sure all spinlock's are unlocked */
70 for (i=0;i<HASHBIN_SIZE;i++)
71 hashbin->hb_mutex[i] = SPIN_LOCK_UNLOCKED;
77 * Function hashbin_clear (hashbin, free_func)
79 * Remove all entries from the hashbin, see also the comments in
80 * hashbin_delete() below
82 int hashbin_clear( hashbin_t* hashbin, FREE_FUNC free_func)
87 ASSERT(hashbin != NULL, return -1;);
88 ASSERT(hashbin->magic == HB_MAGIC, return -1;);
91 * Free the entries in the hashbin
93 for (i = 0; i < HASHBIN_SIZE; i ++ ) {
94 queue = dequeue_first( (irda_queue_t**) &hashbin->hb_queue[i]);
98 queue = dequeue_first(
99 (irda_queue_t**) &hashbin->hb_queue[i]);
102 hashbin->hb_size = 0;
109 * Function hashbin_delete (hashbin, free_func)
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.
115 int hashbin_delete( hashbin_t* hashbin, FREE_FUNC free_func)
120 ASSERT(hashbin != NULL, return -1;);
121 ASSERT(hashbin->magic == HB_MAGIC, return -1;);
124 * Free the entries in the hashbin, TODO: use hashbin_clear when
125 * it has been shown to work
127 for (i = 0; i < HASHBIN_SIZE; i ++ ) {
128 queue = dequeue_first((irda_queue_t**) &hashbin->hb_queue[i]);
132 queue = dequeue_first(
133 (irda_queue_t**) &hashbin->hb_queue[i]);
138 * Free the hashbin structure
140 hashbin->magic = ~HB_MAGIC;
147 * Function hashbin_insert (hashbin, entry, name)
149 * Insert an entry into the hashbin
152 void hashbin_insert(hashbin_t* hashbin, irda_queue_t* entry, __u32 hashv, char* name)
154 unsigned long flags = 0;
157 IRDA_DEBUG( 4, __FUNCTION__"()\n");
159 ASSERT( hashbin != NULL, return;);
160 ASSERT( hashbin->magic == HB_MAGIC, return;);
166 hashv = hash( name );
167 bin = GET_HASHBIN( hashv );
170 if ( hashbin->hb_type & HB_GLOBAL ) {
171 spin_lock_irqsave( &hashbin->hb_mutex[ bin ], flags);
173 } else if ( hashbin->hb_type & HB_LOCAL ) {
176 } /* Default is no-lock */
181 entry->q_hash = hashv;
183 strncpy( entry->q_name, name, 32);
186 * Insert new entry first
187 * TODO: Perhaps allow sorted lists?
188 * -> Merge sort if a sorted list should be created
190 if ( hashbin->hb_type & HB_SORTED) {
192 enqueue_first( (irda_queue_t**) &hashbin->hb_queue[ bin ],
198 if ( hashbin->hb_type & HB_GLOBAL) {
200 spin_unlock_irqrestore( &hashbin->hb_mutex[ bin], flags);
202 } else if ( hashbin->hb_type & HB_LOCAL) {
203 restore_flags( flags);
208 * Function hashbin_find (hashbin, hashv, name)
210 * Find item with the given hashv or name
213 void* hashbin_find( hashbin_t* hashbin, __u32 hashv, char* name )
215 int bin, found = FALSE;
216 unsigned long flags = 0;
219 IRDA_DEBUG( 4, "hashbin_find()\n");
221 ASSERT( hashbin != NULL, return NULL;);
222 ASSERT( hashbin->magic == HB_MAGIC, return NULL;);
228 hashv = hash( name );
229 bin = GET_HASHBIN( hashv );
232 if ( hashbin->hb_type & HB_GLOBAL ) {
233 spin_lock_irqsave( &hashbin->hb_mutex[ bin ], flags);
235 } else if ( hashbin->hb_type & HB_LOCAL ) {
238 } /* Default is no-lock */
243 entry = hashbin->hb_queue[ bin];
249 if ( entry->q_hash == hashv ) {
254 if ( strcmp( entry->q_name, name ) == 0 ) {
263 entry = entry->q_next;
264 } while ( entry != hashbin->hb_queue[ bin ] );
268 if ( hashbin->hb_type & HB_GLOBAL) {
269 spin_unlock_irqrestore( &hashbin->hb_mutex[ bin], flags);
271 } else if ( hashbin->hb_type & HB_LOCAL) {
272 restore_flags( flags);
281 void *hashbin_remove_first( hashbin_t *hashbin)
284 irda_queue_t *entry = NULL;
289 entry = hashbin_get_first( hashbin);
291 hashbin_remove( hashbin, entry->q_hash, NULL);
293 restore_flags( flags);
300 * Function hashbin_remove (hashbin, hashv, name)
302 * Remove entry with the given name
305 void* hashbin_remove( hashbin_t* hashbin, __u32 hashv, char* name)
307 int bin, found = FALSE;
308 unsigned long flags = 0;
311 IRDA_DEBUG( 4, __FUNCTION__ "()\n");
313 ASSERT( hashbin != NULL, return NULL;);
314 ASSERT( hashbin->magic == HB_MAGIC, return NULL;);
320 hashv = hash( name );
321 bin = GET_HASHBIN( hashv );
324 if ( hashbin->hb_type & HB_GLOBAL ) {
325 spin_lock_irqsave( &hashbin->hb_mutex[ bin ], flags);
327 } else if ( hashbin->hb_type & HB_LOCAL ) {
330 } /* Default is no-lock */
335 entry = hashbin->hb_queue[ bin ];
341 if ( entry->q_hash == hashv ) {
346 if ( strcmp( entry->q_name, name) == 0)
356 entry = entry->q_next;
357 } while ( entry != hashbin->hb_queue[ bin ] );
361 * If entry was found, dequeue it
364 dequeue_general( (irda_queue_t**) &hashbin->hb_queue[ bin ],
365 (irda_queue_t*) entry );
369 * Check if this item is the currently selected item, and in
370 * that case we must reset hb_current
372 if ( entry == hashbin->hb_current)
373 hashbin->hb_current = NULL;
377 if ( hashbin->hb_type & HB_GLOBAL) {
378 spin_unlock_irqrestore( &hashbin->hb_mutex[ bin], flags);
380 } else if ( hashbin->hb_type & HB_LOCAL) {
381 restore_flags( flags);
394 * Function hashbin_remove (hashbin, hashv, name)
396 * Remove entry with the given name
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 ;-)
404 void* hashbin_remove_this( hashbin_t* hashbin, irda_queue_t* entry)
406 unsigned long flags = 0;
410 IRDA_DEBUG( 4, __FUNCTION__ "()\n");
412 ASSERT( hashbin != NULL, return NULL;);
413 ASSERT( hashbin->magic == HB_MAGIC, return NULL;);
414 ASSERT( entry != NULL, return NULL;);
416 /* Check if valid and not already removed... */
417 if((entry->q_next == NULL) || (entry->q_prev == NULL))
423 hashv = entry->q_hash;
424 bin = GET_HASHBIN( hashv );
427 if ( hashbin->hb_type & HB_GLOBAL ) {
428 spin_lock_irqsave( &hashbin->hb_mutex[ bin ], flags);
430 } else if ( hashbin->hb_type & HB_LOCAL ) {
433 } /* Default is no-lock */
436 * Dequeue the entry...
438 dequeue_general( (irda_queue_t**) &hashbin->hb_queue[ bin ],
439 (irda_queue_t*) entry );
441 entry->q_next = NULL;
442 entry->q_prev = NULL;
445 * Check if this item is the currently selected item, and in
446 * that case we must reset hb_current
448 if ( entry == hashbin->hb_current)
449 hashbin->hb_current = NULL;
452 if ( hashbin->hb_type & HB_GLOBAL) {
453 spin_unlock_irqrestore( &hashbin->hb_mutex[ bin], flags);
455 } else if ( hashbin->hb_type & HB_LOCAL) {
456 restore_flags( flags);
463 * Function hashbin_get_first (hashbin)
465 * Get a pointer to first element in hashbin, this function must be
466 * called before any calls to hashbin_get_next()!
469 irda_queue_t *hashbin_get_first( hashbin_t* hashbin)
474 ASSERT( hashbin != NULL, return NULL;);
475 ASSERT( hashbin->magic == HB_MAGIC, return NULL;);
477 if ( hashbin == NULL)
480 for ( i = 0; i < HASHBIN_SIZE; i ++ ) {
481 entry = hashbin->hb_queue[ i];
483 hashbin->hb_current = entry;
488 * Did not find any item in hashbin
494 * Function hashbin_get_next (hashbin)
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
501 irda_queue_t *hashbin_get_next( hashbin_t *hashbin)
507 ASSERT( hashbin != NULL, return NULL;);
508 ASSERT( hashbin->magic == HB_MAGIC, return NULL;);
510 if ( hashbin->hb_current == NULL) {
511 ASSERT( hashbin->hb_current != NULL, return NULL;);
514 entry = hashbin->hb_current->q_next;
515 bin = GET_HASHBIN( entry->q_hash);
518 * Make sure that we are not back at the beginning of the queue
521 if ( entry != hashbin->hb_queue[ bin ]) {
522 hashbin->hb_current = entry;
528 * Check that this is not the last queue in hashbin
530 if ( bin >= HASHBIN_SIZE)
534 * Move to next queue in hashbin
537 for ( i = bin; i < HASHBIN_SIZE; i++ ) {
538 entry = hashbin->hb_queue[ i];
540 hashbin->hb_current = entry;
549 * Function enqueue_last (queue, proc)
551 * Insert item into end of queue.
554 static void __enqueue_last( irda_queue_t **queue, irda_queue_t* element)
556 IRDA_DEBUG( 4, __FUNCTION__ "()\n");
559 * Check if queue is empty.
561 if ( *queue == NULL ) {
563 * Queue is empty. Insert one element into the queue.
565 element->q_next = element->q_prev = *queue = element;
569 * Queue is not empty. Insert element into end of queue.
571 element->q_prev = (*queue)->q_prev;
572 element->q_prev->q_next = element;
573 (*queue)->q_prev = element;
574 element->q_next = *queue;
578 inline void enqueue_last( irda_queue_t **queue, irda_queue_t* element)
585 __enqueue_last( queue, element);
587 restore_flags(flags);
591 * Function enqueue_first (queue, proc)
593 * Insert item first in queue.
596 void enqueue_first(irda_queue_t **queue, irda_queue_t* element)
599 IRDA_DEBUG( 4, __FUNCTION__ "()\n");
602 * Check if queue is empty.
604 if ( *queue == NULL ) {
606 * Queue is empty. Insert one element into the queue.
608 element->q_next = element->q_prev = *queue = element;
612 * Queue is not empty. Insert element into front of queue.
614 element->q_next = (*queue);
615 (*queue)->q_prev->q_next = element;
616 element->q_prev = (*queue)->q_prev;
617 (*queue)->q_prev = element;
623 * Function enqueue_queue (queue, list)
625 * Insert a queue (list) into the start of the first queue
628 void enqueue_queue( irda_queue_t** queue, irda_queue_t** list )
633 * Check if queue is empty
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;
649 * Function enqueue_second (queue, proc)
651 * Insert item behind head of queue.
655 static void enqueue_second(irda_queue_t **queue, irda_queue_t* element)
657 IRDA_DEBUG( 0, "enqueue_second()\n");
660 * Check if queue is empty.
662 if ( *queue == NULL ) {
664 * Queue is empty. Insert one element into the queue.
666 element->q_next = element->q_prev = *queue = element;
670 * Queue is not empty. Insert element into ..
672 element->q_prev = (*queue);
673 (*queue)->q_next->q_prev = element;
674 element->q_next = (*queue)->q_next;
675 (*queue)->q_next = element;
681 * Function dequeue (queue)
683 * Remove first entry in queue
686 irda_queue_t *dequeue_first(irda_queue_t **queue)
690 IRDA_DEBUG( 4, "dequeue_first()\n");
697 if ( *queue == NULL ) {
701 } else if ( (*queue)->q_next == *queue ) {
703 * Queue only contained a single element. It will now be
709 * Queue contained several element. Remove the first one.
711 (*queue)->q_prev->q_next = (*queue)->q_next;
712 (*queue)->q_next->q_prev = (*queue)->q_prev;
713 *queue = (*queue)->q_next;
717 * Return the removed entry (or NULL of queue was empty).
723 * Function dequeue_general (queue, element)
727 static irda_queue_t *dequeue_general(irda_queue_t **queue, irda_queue_t* element)
731 IRDA_DEBUG( 4, "dequeue_general()\n");
738 if ( *queue == NULL ) {
742 } else if ( (*queue)->q_next == *queue ) {
744 * Queue only contained a single element. It will now be
751 * Remove specific element.
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;
760 * Return the removed entry (or NULL of queue was empty).
766 * Function hash (name)
768 * This function hash the input string 'name' using the ELF hash
769 * function for strings.
771 static __u32 hash( char* name)
777 h = (h<<4) + *name++;
778 if ((g = (h & 0xf0000000)))