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>
12 * Copyright (C) 1998-1999, Aage Kvalnes <aage@cs.uit.no>
13 * Copyright (C) 1998, Dag Brattli,
14 * All Rights Reserved.
16 * This code is taken from the Vortex Operating System written by Aage
17 * Kvalnes. Aage has agreed that this code can use the GPL licence,
18 * although he does not use that licence in his own code.
20 * This copyright does however _not_ include the ELF hash() function
21 * which I currently don't know which licence or copyright it
22 * has. Please inform me if you know.
24 * This program is free software; you can redistribute it and/or
25 * modify it under the terms of the GNU General Public License as
26 * published by the Free Software Foundation; either version 2 of
27 * the License, or (at your option) any later version.
29 * Neither Dag Brattli nor University of Tromsø admit liability nor
30 * provide warranty for any of this software. This material is
31 * provided "AS-IS" and at no charge.
33 ********************************************************************/
35 #include <net/irda/irda.h>
36 #include <net/irda/irqueue.h>
37 #include <net/irda/irmod.h>
39 static queue_t
*dequeue_general( queue_t
**queue
, queue_t
* element
);
40 static __u32
hash( char* name
);
43 * Function hashbin_create ( type, name )
48 hashbin_t
*hashbin_new(int type
)
54 * Allocate new hashbin
56 hashbin
= kmalloc( sizeof(hashbin_t
), GFP_ATOMIC
);
61 * Initialize structure
63 memset(hashbin
, 0, sizeof(hashbin_t
));
64 hashbin
->hb_type
= type
;
65 hashbin
->magic
= HB_MAGIC
;
67 /* Make sure all spinlock's are unlocked */
68 for (i
=0;i
<HASHBIN_SIZE
;i
++)
69 hashbin
->hb_mutex
[i
] = SPIN_LOCK_UNLOCKED
;
75 * Function hashbin_clear (hashbin, free_func)
77 * Remove all entries from the hashbin, see also the comments in
78 * hashbin_delete() below
80 int hashbin_clear( hashbin_t
* hashbin
, FREE_FUNC free_func
)
85 ASSERT(hashbin
!= NULL
, return -1;);
86 ASSERT(hashbin
->magic
== HB_MAGIC
, return -1;);
89 * Free the entries in the hashbin
91 for (i
= 0; i
< HASHBIN_SIZE
; i
++ ) {
92 queue
= dequeue_first( (queue_t
**) &hashbin
->hb_queue
[i
]);
96 queue
= dequeue_first(
97 (queue_t
**) &hashbin
->hb_queue
[i
]);
100 hashbin
->hb_size
= 0;
107 * Function hashbin_delete (hashbin, free_func)
109 * Destroy hashbin, the free_func can be a user supplied special routine
110 * for deallocating this structure if it's complex. If not the user can
111 * just supply kfree, which should take care of the job.
113 int hashbin_delete( hashbin_t
* hashbin
, FREE_FUNC free_func
)
118 ASSERT(hashbin
!= NULL
, return -1;);
119 ASSERT(hashbin
->magic
== HB_MAGIC
, return -1;);
122 * Free the entries in the hashbin, TODO: use hashbin_clear when
123 * it has been shown to work
125 for (i
= 0; i
< HASHBIN_SIZE
; i
++ ) {
126 queue
= dequeue_first((queue_t
**) &hashbin
->hb_queue
[i
]);
130 queue
= dequeue_first(
131 (queue_t
**) &hashbin
->hb_queue
[i
]);
136 * Free the hashbin structure
138 hashbin
->magic
= ~HB_MAGIC
;
145 * Function hashbin_lock (hashbin, hashv, name)
150 void hashbin_lock(hashbin_t
* hashbin
, __u32 hashv
, char* name
,
155 IRDA_DEBUG(0, "hashbin_lock\n");
157 ASSERT(hashbin
!= NULL
, return;);
158 ASSERT(hashbin
->magic
== HB_MAGIC
, return;);
165 bin
= GET_HASHBIN(hashv
);
168 if ( hashbin
->hb_type
& HB_GLOBAL
)
169 spin_lock_irqsave(&hashbin
->hb_mutex
[ bin
], flags
);
177 * Function hashbin_unlock (hashbin, hashv, name)
182 void hashbin_unlock(hashbin_t
* hashbin
, __u32 hashv
, char* name
,
187 IRDA_DEBUG(0, "hashbin_unlock()\n");
189 ASSERT(hashbin
!= NULL
, return;);
190 ASSERT(hashbin
->magic
== HB_MAGIC
, return;);
197 bin
= GET_HASHBIN(hashv
);
200 if ( hashbin
->hb_type
& HB_GLOBAL
)
201 spin_unlock_irq( &hashbin
->hb_mutex
[ bin
]);
202 else if (hashbin
->hb_type
& HB_LOCAL
) {
203 restore_flags( flags
);
208 * Function hashbin_insert (hashbin, entry, name)
210 * Insert an entry into the hashbin
213 void hashbin_insert(hashbin_t
* hashbin
, queue_t
* entry
, __u32 hashv
, char* name
)
215 unsigned long flags
= 0;
218 IRDA_DEBUG( 4, __FUNCTION__
"()\n");
220 ASSERT( hashbin
!= NULL
, return;);
221 ASSERT( hashbin
->magic
== HB_MAGIC
, return;);
227 hashv
= hash( name
);
228 bin
= GET_HASHBIN( hashv
);
231 if ( hashbin
->hb_type
& HB_GLOBAL
) {
232 spin_lock_irqsave( &hashbin
->hb_mutex
[ bin
], flags
);
234 } else if ( hashbin
->hb_type
& HB_LOCAL
) {
237 } /* Default is no-lock */
242 entry
->q_hash
= hashv
;
244 strncpy( entry
->q_name
, name
, 32);
247 * Insert new entry first
248 * TODO: Perhaps allow sorted lists?
249 * -> Merge sort if a sorted list should be created
251 if ( hashbin
->hb_type
& HB_SORTED
) {
253 enqueue_first( (queue_t
**) &hashbin
->hb_queue
[ bin
],
259 if ( hashbin
->hb_type
& HB_GLOBAL
) {
261 spin_unlock_irq( &hashbin
->hb_mutex
[ bin
]);
263 } else if ( hashbin
->hb_type
& HB_LOCAL
) {
264 restore_flags( flags
);
269 * Function hashbin_find (hashbin, hashv, name)
271 * Find item with the given hashv or name
274 void* hashbin_find( hashbin_t
* hashbin
, __u32 hashv
, char* name
)
276 int bin
, found
= FALSE
;
277 unsigned long flags
= 0;
280 IRDA_DEBUG( 4, "hashbin_find()\n");
282 ASSERT( hashbin
!= NULL
, return NULL
;);
283 ASSERT( hashbin
->magic
== HB_MAGIC
, return NULL
;);
289 hashv
= hash( name
);
290 bin
= GET_HASHBIN( hashv
);
293 if ( hashbin
->hb_type
& HB_GLOBAL
) {
294 spin_lock_irqsave( &hashbin
->hb_mutex
[ bin
], flags
);
296 } else if ( hashbin
->hb_type
& HB_LOCAL
) {
299 } /* Default is no-lock */
304 entry
= hashbin
->hb_queue
[ bin
];
310 if ( entry
->q_hash
== hashv
) {
315 if ( strcmp( entry
->q_name
, name
) == 0 ) {
324 entry
= entry
->q_next
;
325 } while ( entry
!= hashbin
->hb_queue
[ bin
] );
329 if ( hashbin
->hb_type
& HB_GLOBAL
) {
330 spin_unlock_irq( &hashbin
->hb_mutex
[ bin
]);
332 } else if ( hashbin
->hb_type
& HB_LOCAL
) {
333 restore_flags( flags
);
342 void *hashbin_remove_first( hashbin_t
*hashbin
)
345 queue_t
*entry
= NULL
;
350 entry
= hashbin_get_first( hashbin
);
352 hashbin_remove( hashbin
, entry
->q_hash
, NULL
);
354 restore_flags( flags
);
361 * Function hashbin_remove (hashbin, hashv, name)
363 * Remove entry with the given name
366 void* hashbin_remove( hashbin_t
* hashbin
, __u32 hashv
, char* name
)
368 int bin
, found
= FALSE
;
369 unsigned long flags
= 0;
372 IRDA_DEBUG( 4, __FUNCTION__
"()\n");
374 ASSERT( hashbin
!= NULL
, return NULL
;);
375 ASSERT( hashbin
->magic
== HB_MAGIC
, return NULL
;);
381 hashv
= hash( name
);
382 bin
= GET_HASHBIN( hashv
);
384 if ( hashbin
->hb_type
& HB_GLOBAL
) {
385 spin_lock_irqsave( &hashbin
->hb_mutex
[ bin
], flags
);
387 } else if ( hashbin
->hb_type
& HB_LOCAL
) {
390 } /* Default is no-lock */
395 entry
= hashbin
->hb_queue
[ bin
];
401 if ( entry
->q_hash
== hashv
) {
406 if ( strcmp( entry
->q_name
, name
) == 0)
416 entry
= entry
->q_next
;
417 } while ( entry
!= hashbin
->hb_queue
[ bin
] );
421 * If entry was found, dequeue it
424 dequeue_general( (queue_t
**) &hashbin
->hb_queue
[ bin
],
429 * Check if this item is the currently selected item, and in
430 * that case we must reset hb_current
432 if ( entry
== hashbin
->hb_current
)
433 hashbin
->hb_current
= NULL
;
437 if ( hashbin
->hb_type
& HB_GLOBAL
) {
438 spin_unlock_irq( &hashbin
->hb_mutex
[ bin
]);
440 } else if ( hashbin
->hb_type
& HB_LOCAL
) {
441 restore_flags( flags
);
454 * Function hashbin_get_first (hashbin)
456 * Get a pointer to first element in hashbin, this function must be
457 * called before any calls to hashbin_get_next()!
460 queue_t
*hashbin_get_first( hashbin_t
* hashbin
)
465 ASSERT( hashbin
!= NULL
, return NULL
;);
466 ASSERT( hashbin
->magic
== HB_MAGIC
, return NULL
;);
468 if ( hashbin
== NULL
)
471 for ( i
= 0; i
< HASHBIN_SIZE
; i
++ ) {
472 entry
= hashbin
->hb_queue
[ i
];
474 hashbin
->hb_current
= entry
;
479 * Did not find any item in hashbin
485 * Function hashbin_get_next (hashbin)
487 * Get next item in hashbin. A series of hashbin_get_next() calls must
488 * be started by a call to hashbin_get_first(). The function returns
489 * NULL when all items have been traversed
492 queue_t
*hashbin_get_next( hashbin_t
*hashbin
)
498 ASSERT( hashbin
!= NULL
, return NULL
;);
499 ASSERT( hashbin
->magic
== HB_MAGIC
, return NULL
;);
501 if ( hashbin
->hb_current
== NULL
) {
502 ASSERT( hashbin
->hb_current
!= NULL
, return NULL
;);
505 entry
= hashbin
->hb_current
->q_next
;
506 bin
= GET_HASHBIN( entry
->q_hash
);
509 * Make sure that we are not back at the beginning of the queue
512 if ( entry
!= hashbin
->hb_queue
[ bin
]) {
513 hashbin
->hb_current
= entry
;
519 * Check that this is not the last queue in hashbin
521 if ( bin
>= HASHBIN_SIZE
)
525 * Move to next queue in hashbin
528 for ( i
= bin
; i
< HASHBIN_SIZE
; i
++ ) {
529 entry
= hashbin
->hb_queue
[ i
];
531 hashbin
->hb_current
= entry
;
540 * Function enqueue_last (queue, proc)
542 * Insert item into end of queue.
545 static void __enqueue_last( queue_t
**queue
, queue_t
* element
)
547 IRDA_DEBUG( 4, __FUNCTION__
"()\n");
550 * Check if queue is empty.
552 if ( *queue
== NULL
) {
554 * Queue is empty. Insert one element into the queue.
556 element
->q_next
= element
->q_prev
= *queue
= element
;
560 * Queue is not empty. Insert element into end of queue.
562 element
->q_prev
= (*queue
)->q_prev
;
563 element
->q_prev
->q_next
= element
;
564 (*queue
)->q_prev
= element
;
565 element
->q_next
= *queue
;
569 inline void enqueue_last( queue_t
**queue
, queue_t
* element
)
576 __enqueue_last( queue
, element
);
578 restore_flags(flags
);
582 * Function enqueue_first (queue, proc)
584 * Insert item first in queue.
587 void enqueue_first(queue_t
**queue
, queue_t
* element
)
590 IRDA_DEBUG( 4, __FUNCTION__
"()\n");
593 * Check if queue is empty.
595 if ( *queue
== NULL
) {
597 * Queue is empty. Insert one element into the queue.
599 element
->q_next
= element
->q_prev
= *queue
= element
;
603 * Queue is not empty. Insert element into front of queue.
605 element
->q_next
= (*queue
);
606 (*queue
)->q_prev
->q_next
= element
;
607 element
->q_prev
= (*queue
)->q_prev
;
608 (*queue
)->q_prev
= element
;
614 * Function enqueue_queue (queue, list)
616 * Insert a queue (list) into the start of the first queue
619 void enqueue_queue( queue_t
** queue
, queue_t
** list
)
624 * Check if queue is empty
627 (*list
)->q_prev
->q_next
= (*queue
);
628 (*queue
)->q_prev
->q_next
= (*list
);
629 tmp
= (*list
)->q_prev
;
630 (*list
)->q_prev
= (*queue
)->q_prev
;
631 (*queue
)->q_prev
= tmp
;
640 * Function enqueue_second (queue, proc)
642 * Insert item behind head of queue.
646 static void enqueue_second(queue_t
**queue
, queue_t
* element
)
648 IRDA_DEBUG( 0, "enqueue_second()\n");
651 * Check if queue is empty.
653 if ( *queue
== NULL
) {
655 * Queue is empty. Insert one element into the queue.
657 element
->q_next
= element
->q_prev
= *queue
= element
;
661 * Queue is not empty. Insert element into ..
663 element
->q_prev
= (*queue
);
664 (*queue
)->q_next
->q_prev
= element
;
665 element
->q_next
= (*queue
)->q_next
;
666 (*queue
)->q_next
= element
;
672 * Function dequeue (queue)
674 * Remove first entry in queue
677 queue_t
*dequeue_first(queue_t
**queue
)
681 IRDA_DEBUG( 4, "dequeue_first()\n");
688 if ( *queue
== NULL
) {
692 } else if ( (*queue
)->q_next
== *queue
) {
694 * Queue only contained a single element. It will now be
700 * Queue contained several element. Remove the first one.
702 (*queue
)->q_prev
->q_next
= (*queue
)->q_next
;
703 (*queue
)->q_next
->q_prev
= (*queue
)->q_prev
;
704 *queue
= (*queue
)->q_next
;
708 * Return the removed entry (or NULL of queue was empty).
714 * Function dequeue_general (queue, element)
718 static queue_t
*dequeue_general(queue_t
**queue
, queue_t
* element
)
722 IRDA_DEBUG( 4, "dequeue_general()\n");
729 if ( *queue
== NULL
) {
733 } if ( (*queue
)->q_next
== *queue
) {
735 * Queue only contained a single element. It will now be
742 * Remove specific element.
744 element
->q_prev
->q_next
= element
->q_next
;
745 element
->q_next
->q_prev
= element
->q_prev
;
746 if ( (*queue
) == element
)
747 (*queue
) = element
->q_next
;
751 * Return the removed entry (or NULL of queue was empty).
757 * Function hash (name)
759 * This function hash the input string 'name' using the ELF hash
760 * function for strings.
762 static __u32
hash( char* name
)
768 h
= (h
<<4) + *name
++;
769 if ((g
= (h
& 0xf0000000)))