File: /usr/src/linux/net/irda/irqueue.c
1 /*********************************************************************
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, __FUNCTION__"()\n");
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, __FUNCTION__ "()\n");
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, __FUNCTION__ "()\n");
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, __FUNCTION__ "()\n");
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, __FUNCTION__ "()\n");
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 }
784