[NETFILTER]: Add NAT support for nf_conntrack
[linux-2.6] / 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 /*
38  * NOTE :
39  * There are various problems with this package :
40  *      o the hash function for ints is pathetic (but could be changed)
41  *      o locking is sometime suspicious (especially during enumeration)
42  *      o most users have only a few elements (== overhead)
43  *      o most users never use seach, so don't benefit from hashing
44  * Problem already fixed :
45  *      o not 64 bit compliant (most users do hashv = (int) self)
46  *      o hashbin_remove() is broken => use hashbin_remove_this()
47  * I think most users would be better served by a simple linked list
48  * (like include/linux/list.h) with a global spinlock per list.
49  * Jean II
50  */
51
52 /*
53  * Notes on the concurrent access to hashbin and other SMP issues
54  * -------------------------------------------------------------
55  *      Hashbins are very often in the IrDA stack a global repository of
56  * information, and therefore used in a very asynchronous manner following
57  * various events (driver calls, timers, user calls...).
58  *      Therefore, very often it is highly important to consider the
59  * management of concurrent access to the hashbin and how to guarantee the
60  * consistency of the operations on it.
61  *
62  *      First, we need to define the objective of locking :
63  *              1) Protect user data (content pointed by the hashbin)
64  *              2) Protect hashbin structure itself (linked list in each bin)
65  *
66  *                           OLD LOCKING
67  *                           -----------
68  *
69  *      The previous locking strategy, either HB_LOCAL or HB_GLOBAL were
70  * both inadequate in *both* aspect.
71  *              o HB_GLOBAL was using a spinlock for each bin (local locking).
72  *              o HB_LOCAL was disabling irq on *all* CPUs, so use a single
73  *                global semaphore.
74  *      The problems were :
75  *              A) Global irq disabling is no longer supported by the kernel
76  *              B) No protection for the hashbin struct global data
77  *                      o hashbin_delete()
78  *                      o hb_current
79  *              C) No protection for user data in some cases
80  *
81  *      A) HB_LOCAL use global irq disabling, so doesn't work on kernel
82  * 2.5.X. Even when it is supported (kernel 2.4.X and earlier), its
83  * performance is not satisfactory on SMP setups. Most hashbins were
84  * HB_LOCAL, so (A) definitely need fixing.
85  *      B) HB_LOCAL could be modified to fix (B). However, because HB_GLOBAL
86  * lock only the individual bins, it will never be able to lock the
87  * global data, so can't do (B).
88  *      C) Some functions return pointer to data that is still in the
89  * hashbin :
90  *              o hashbin_find()
91  *              o hashbin_get_first()
92  *              o hashbin_get_next()
93  *      As the data is still in the hashbin, it may be changed or free'd
94  * while the caller is examinimg the data. In those case, locking can't
95  * be done within the hashbin, but must include use of the data within
96  * the caller.
97  *      The caller can easily do this with HB_LOCAL (just disable irqs).
98  * However, this is impossible with HB_GLOBAL because the caller has no
99  * way to know the proper bin, so don't know which spinlock to use.
100  *
101  *      Quick summary : can no longer use HB_LOCAL, and HB_GLOBAL is
102  * fundamentally broken and will never work.
103  *
104  *                           NEW LOCKING
105  *                           -----------
106  *
107  *      To fix those problems, I've introduce a few changes in the
108  * hashbin locking :
109  *              1) New HB_LOCK scheme
110  *              2) hashbin->hb_spinlock
111  *              3) New hashbin usage policy
112  *
113  * HB_LOCK :
114  * -------
115  *      HB_LOCK is a locking scheme intermediate between the old HB_LOCAL
116  * and HB_GLOBAL. It uses a single spinlock to protect the whole content
117  * of the hashbin. As it is a single spinlock, it can protect the global
118  * data of the hashbin and not only the bins themselves.
119  *      HB_LOCK can only protect some of the hashbin calls, so it only lock
120  * call that can be made 100% safe and leave other call unprotected.
121  *      HB_LOCK in theory is slower than HB_GLOBAL, but as the hashbin
122  * content is always small contention is not high, so it doesn't matter
123  * much. HB_LOCK is probably faster than HB_LOCAL.
124  *
125  * hashbin->hb_spinlock :
126  * --------------------
127  *      The spinlock that HB_LOCK uses is available for caller, so that
128  * the caller can protect unprotected calls (see below).
129  *      If the caller want to do entirely its own locking (HB_NOLOCK), he
130  * can do so and may use safely this spinlock.
131  *      Locking is done like this :
132  *              spin_lock_irqsave(&hashbin->hb_spinlock, flags);
133  *      Releasing the lock :
134  *              spin_unlock_irqrestore(&hashbin->hb_spinlock, flags);
135  *
136  * Safe & Protected calls :
137  * ----------------------
138  *      The following calls are safe or protected via HB_LOCK :
139  *              o hashbin_new()         -> safe
140  *              o hashbin_delete()
141  *              o hashbin_insert()
142  *              o hashbin_remove_first()
143  *              o hashbin_remove()
144  *              o hashbin_remove_this()
145  *              o HASHBIN_GET_SIZE()    -> atomic
146  *
147  *      The following calls only protect the hashbin itself :
148  *              o hashbin_lock_find()
149  *              o hashbin_find_next()
150  *
151  * Unprotected calls :
152  * -----------------
153  *      The following calls need to be protected by the caller :
154  *              o hashbin_find()
155  *              o hashbin_get_first()
156  *              o hashbin_get_next()
157  *
158  * Locking Policy :
159  * --------------
160  *      If the hashbin is used only in a single thread of execution
161  * (explicitly or implicitely), you can use HB_NOLOCK
162  *      If the calling module already provide concurrent access protection,
163  * you may use HB_NOLOCK.
164  *
165  *      In all other cases, you need to use HB_LOCK and lock the hashbin
166  * every time before calling one of the unprotected calls. You also must
167  * use the pointer returned by the unprotected call within the locked
168  * region.
169  *
170  * Extra care for enumeration :
171  * --------------------------
172  *      hashbin_get_first() and hashbin_get_next() use the hashbin to
173  * store the current position, in hb_current.
174  *      As long as the hashbin remains locked, this is safe. If you unlock
175  * the hashbin, the current position may change if anybody else modify
176  * or enumerate the hashbin.
177  *      Summary : do the full enumeration while locked.
178  *
179  *      Alternatively, you may use hashbin_find_next(). But, this will
180  * be slower, is more complex to use and doesn't protect the hashbin
181  * content. So, care is needed here as well.
182  *
183  * Other issues :
184  * ------------
185  *      I believe that we are overdoing it by using spin_lock_irqsave()
186  * and we should use only spin_lock_bh() or similar. But, I don't have
187  * the balls to try it out.
188  *      Don't believe that because hashbin are now (somewhat) SMP safe
189  * that the rest of the code is. Higher layers tend to be safest,
190  * but LAP and LMP would need some serious dedicated love.
191  *
192  * Jean II
193  */
194 #include <linux/module.h>
195
196 #include <net/irda/irda.h>
197 #include <net/irda/irqueue.h>
198
199 /************************ QUEUE SUBROUTINES ************************/
200
201 /*
202  * Hashbin
203  */
204 #define GET_HASHBIN(x) ( x & HASHBIN_MASK )
205
206 /*
207  * Function hash (name)
208  *
209  *    This function hash the input string 'name' using the ELF hash
210  *    function for strings.
211  */
212 static __u32 hash( const char* name)
213 {
214         __u32 h = 0;
215         __u32 g;
216         
217         while(*name) {
218                 h = (h<<4) + *name++;
219                 if ((g = (h & 0xf0000000)))
220                         h ^=g>>24;
221                 h &=~g;
222         }
223         return h;
224 }
225
226 /*
227  * Function enqueue_first (queue, proc)
228  *
229  *    Insert item first in queue.
230  *
231  */
232 static void enqueue_first(irda_queue_t **queue, irda_queue_t* element)
233 {
234         
235         IRDA_DEBUG( 4, "%s()\n", __FUNCTION__);
236
237         /*
238          * Check if queue is empty.
239          */
240         if ( *queue == NULL ) {
241                 /*
242                  * Queue is empty.  Insert one element into the queue.
243                  */
244                 element->q_next = element->q_prev = *queue = element;
245                 
246         } else {
247                 /*
248                  * Queue is not empty.  Insert element into front of queue.
249                  */
250                 element->q_next          = (*queue);
251                 (*queue)->q_prev->q_next = element;
252                 element->q_prev          = (*queue)->q_prev;
253                 (*queue)->q_prev         = element;
254                 (*queue)                 = element;
255         }
256 }
257
258
259 /*
260  * Function dequeue (queue)
261  *
262  *    Remove first entry in queue
263  *
264  */
265 static irda_queue_t *dequeue_first(irda_queue_t **queue)
266 {
267         irda_queue_t *ret;
268
269         IRDA_DEBUG( 4, "dequeue_first()\n");
270         
271         /*
272          * Set return value
273          */
274         ret =  *queue;
275         
276         if ( *queue == NULL ) {
277                 /*
278                  * Queue was empty.
279                  */
280         } else if ( (*queue)->q_next == *queue ) {
281                 /* 
282                  *  Queue only contained a single element. It will now be
283                  *  empty.  
284                  */
285                 *queue = NULL;
286         } else {
287                 /*
288                  * Queue contained several element.  Remove the first one.
289                  */
290                 (*queue)->q_prev->q_next = (*queue)->q_next;
291                 (*queue)->q_next->q_prev = (*queue)->q_prev;
292                 *queue = (*queue)->q_next;
293         }
294         
295         /*
296          * Return the removed entry (or NULL of queue was empty).
297          */
298         return ret;
299 }
300
301 /*
302  * Function dequeue_general (queue, element)
303  *
304  *
305  */
306 static irda_queue_t *dequeue_general(irda_queue_t **queue, irda_queue_t* element)
307 {
308         irda_queue_t *ret;
309         
310         IRDA_DEBUG( 4, "dequeue_general()\n");
311         
312         /*
313          * Set return value
314          */
315         ret =  *queue;
316                 
317         if ( *queue == NULL ) {
318                 /*
319                  * Queue was empty.
320                  */
321         } else if ( (*queue)->q_next == *queue ) {
322                 /* 
323                  *  Queue only contained a single element. It will now be
324                  *  empty.  
325                  */
326                 *queue = NULL;
327                 
328         } else {
329                 /*
330                  *  Remove specific element.
331                  */
332                 element->q_prev->q_next = element->q_next;
333                 element->q_next->q_prev = element->q_prev;
334                 if ( (*queue) == element)
335                         (*queue) = element->q_next;
336         }
337         
338         /*
339          * Return the removed entry (or NULL of queue was empty).
340          */
341         return ret;
342 }
343
344 /************************ HASHBIN MANAGEMENT ************************/
345
346 /*
347  * Function hashbin_create ( type, name )
348  *
349  *    Create hashbin!
350  *
351  */
352 hashbin_t *hashbin_new(int type)
353 {
354         hashbin_t* hashbin;
355         
356         /*
357          * Allocate new hashbin
358          */
359         hashbin = kzalloc(sizeof(*hashbin), GFP_ATOMIC);
360         if (!hashbin)
361                 return NULL;
362
363         /*
364          * Initialize structure
365          */
366         hashbin->hb_type = type;
367         hashbin->magic = HB_MAGIC;
368         //hashbin->hb_current = NULL;
369
370         /* Make sure all spinlock's are unlocked */
371         if ( hashbin->hb_type & HB_LOCK ) {
372                 spin_lock_init(&hashbin->hb_spinlock);
373         }
374
375         return hashbin;
376 }
377 EXPORT_SYMBOL(hashbin_new);
378
379
380 /*
381  * Function hashbin_delete (hashbin, free_func)
382  *
383  *    Destroy hashbin, the free_func can be a user supplied special routine 
384  *    for deallocating this structure if it's complex. If not the user can 
385  *    just supply kfree, which should take care of the job.
386  */
387 int hashbin_delete( hashbin_t* hashbin, FREE_FUNC free_func)
388 {
389         irda_queue_t* queue;
390         unsigned long flags = 0;
391         int i;
392
393         IRDA_ASSERT(hashbin != NULL, return -1;);
394         IRDA_ASSERT(hashbin->magic == HB_MAGIC, return -1;);
395         
396         /* Synchronize */
397         if ( hashbin->hb_type & HB_LOCK ) {
398                 spin_lock_irqsave(&hashbin->hb_spinlock, flags);
399         }
400
401         /*
402          *  Free the entries in the hashbin, TODO: use hashbin_clear when
403          *  it has been shown to work
404          */
405         for (i = 0; i < HASHBIN_SIZE; i ++ ) {
406                 queue = dequeue_first((irda_queue_t**) &hashbin->hb_queue[i]);
407                 while (queue ) {
408                         if (free_func)
409                                 (*free_func)(queue);
410                         queue = dequeue_first( 
411                                 (irda_queue_t**) &hashbin->hb_queue[i]);
412                 }
413         }
414         
415         /* Cleanup local data */
416         hashbin->hb_current = NULL;
417         hashbin->magic = ~HB_MAGIC;
418
419         /* Release lock */
420         if ( hashbin->hb_type & HB_LOCK) {
421                 spin_unlock_irqrestore(&hashbin->hb_spinlock, flags);
422         }
423
424         /*
425          *  Free the hashbin structure
426          */
427         kfree(hashbin);
428
429         return 0;
430 }
431 EXPORT_SYMBOL(hashbin_delete);
432
433 /********************* HASHBIN LIST OPERATIONS *********************/
434
435 /*
436  * Function hashbin_insert (hashbin, entry, name)
437  *
438  *    Insert an entry into the hashbin
439  *
440  */
441 void hashbin_insert(hashbin_t* hashbin, irda_queue_t* entry, long hashv, 
442                     const char* name)
443 {
444         unsigned long flags = 0;
445         int bin;
446
447         IRDA_DEBUG( 4, "%s()\n", __FUNCTION__);
448
449         IRDA_ASSERT( hashbin != NULL, return;);
450         IRDA_ASSERT( hashbin->magic == HB_MAGIC, return;);
451
452         /*
453          * Locate hashbin
454          */
455         if ( name )
456                 hashv = hash( name );
457         bin = GET_HASHBIN( hashv );
458
459         /* Synchronize */
460         if ( hashbin->hb_type & HB_LOCK ) {
461                 spin_lock_irqsave(&hashbin->hb_spinlock, flags);
462         } /* Default is no-lock  */
463         
464         /*
465          * Store name and key
466          */
467         entry->q_hash = hashv;
468         if ( name )
469                 strlcpy( entry->q_name, name, sizeof(entry->q_name));
470         
471         /*
472          * Insert new entry first
473          */
474         enqueue_first( (irda_queue_t**) &hashbin->hb_queue[ bin ],
475                        entry);
476         hashbin->hb_size++;
477
478         /* Release lock */
479         if ( hashbin->hb_type & HB_LOCK ) {
480                 spin_unlock_irqrestore(&hashbin->hb_spinlock, flags);
481         } /* Default is no-lock  */
482 }
483 EXPORT_SYMBOL(hashbin_insert);
484
485 /* 
486  *  Function hashbin_remove_first (hashbin)
487  *
488  *    Remove first entry of the hashbin
489  *
490  * Note : this function no longer use hashbin_remove(), but does things
491  * similar to hashbin_remove_this(), so can be considered safe.
492  * Jean II
493  */
494 void *hashbin_remove_first( hashbin_t *hashbin)
495 {
496         unsigned long flags = 0;
497         irda_queue_t *entry = NULL;
498
499         /* Synchronize */
500         if ( hashbin->hb_type & HB_LOCK ) {
501                 spin_lock_irqsave(&hashbin->hb_spinlock, flags);
502         } /* Default is no-lock  */
503
504         entry = hashbin_get_first( hashbin);
505         if ( entry != NULL) {
506                 int     bin;
507                 long    hashv;
508                 /*
509                  * Locate hashbin
510                  */
511                 hashv = entry->q_hash;
512                 bin = GET_HASHBIN( hashv );
513
514                 /*
515                  * Dequeue the entry...
516                  */
517                 dequeue_general( (irda_queue_t**) &hashbin->hb_queue[ bin ],
518                                  (irda_queue_t*) entry );
519                 hashbin->hb_size--;
520                 entry->q_next = NULL;
521                 entry->q_prev = NULL;
522
523                 /*
524                  *  Check if this item is the currently selected item, and in
525                  *  that case we must reset hb_current
526                  */
527                 if ( entry == hashbin->hb_current)
528                         hashbin->hb_current = NULL;
529         }
530
531         /* Release lock */
532         if ( hashbin->hb_type & HB_LOCK ) {
533                 spin_unlock_irqrestore(&hashbin->hb_spinlock, flags);
534         } /* Default is no-lock  */
535
536         return entry;
537 }
538
539
540 /* 
541  *  Function hashbin_remove (hashbin, hashv, name)
542  *
543  *    Remove entry with the given name
544  *
545  *  The use of this function is highly discouraged, because the whole
546  *  concept behind hashbin_remove() is broken. In many cases, it's not
547  *  possible to guarantee the unicity of the index (either hashv or name),
548  *  leading to removing the WRONG entry.
549  *  The only simple safe use is :
550  *              hashbin_remove(hasbin, (int) self, NULL);
551  *  In other case, you must think hard to guarantee unicity of the index.
552  *  Jean II
553  */
554 void* hashbin_remove( hashbin_t* hashbin, long hashv, const char* name)
555 {
556         int bin, found = FALSE;
557         unsigned long flags = 0;
558         irda_queue_t* entry;
559
560         IRDA_DEBUG( 4, "%s()\n", __FUNCTION__);
561
562         IRDA_ASSERT( hashbin != NULL, return NULL;);
563         IRDA_ASSERT( hashbin->magic == HB_MAGIC, return NULL;);
564         
565         /*
566          * Locate hashbin
567          */
568         if ( name )
569                 hashv = hash( name );
570         bin = GET_HASHBIN( hashv );
571
572         /* Synchronize */
573         if ( hashbin->hb_type & HB_LOCK ) {
574                 spin_lock_irqsave(&hashbin->hb_spinlock, flags);
575         } /* Default is no-lock  */
576
577         /*
578          * Search for entry
579          */
580         entry = hashbin->hb_queue[ bin ];
581         if ( entry ) {
582                 do {
583                         /*
584                          * Check for key
585                          */
586                         if ( entry->q_hash == hashv ) {
587                                 /*
588                                  * Name compare too?
589                                  */
590                                 if ( name ) {
591                                         if ( strcmp( entry->q_name, name) == 0)
592                                         {
593                                                 found = TRUE;
594                                                 break;
595                                         }
596                                 } else {
597                                         found = TRUE;
598                                         break;
599                                 }
600                         }
601                         entry = entry->q_next;
602                 } while ( entry != hashbin->hb_queue[ bin ] );
603         }
604         
605         /*
606          * If entry was found, dequeue it
607          */
608         if ( found ) {
609                 dequeue_general( (irda_queue_t**) &hashbin->hb_queue[ bin ],
610                                  (irda_queue_t*) entry );
611                 hashbin->hb_size--;
612
613                 /*
614                  *  Check if this item is the currently selected item, and in
615                  *  that case we must reset hb_current
616                  */
617                 if ( entry == hashbin->hb_current)
618                         hashbin->hb_current = NULL;
619         }
620
621         /* Release lock */
622         if ( hashbin->hb_type & HB_LOCK ) {
623                 spin_unlock_irqrestore(&hashbin->hb_spinlock, flags);
624         } /* Default is no-lock  */
625        
626         
627         /* Return */
628         if ( found ) 
629                 return entry;
630         else
631                 return NULL;
632         
633 }
634 EXPORT_SYMBOL(hashbin_remove);
635
636 /* 
637  *  Function hashbin_remove_this (hashbin, entry)
638  *
639  *    Remove entry with the given name
640  *
641  * In some cases, the user of hashbin can't guarantee the unicity
642  * of either the hashv or name.
643  * In those cases, using the above function is guaranteed to cause troubles,
644  * so we use this one instead...
645  * And by the way, it's also faster, because we skip the search phase ;-)
646  */
647 void* hashbin_remove_this( hashbin_t* hashbin, irda_queue_t* entry)
648 {
649         unsigned long flags = 0;
650         int     bin;
651         long    hashv;
652
653         IRDA_DEBUG( 4, "%s()\n", __FUNCTION__);
654
655         IRDA_ASSERT( hashbin != NULL, return NULL;);
656         IRDA_ASSERT( hashbin->magic == HB_MAGIC, return NULL;);
657         IRDA_ASSERT( entry != NULL, return NULL;);
658         
659         /* Synchronize */
660         if ( hashbin->hb_type & HB_LOCK ) {
661                 spin_lock_irqsave(&hashbin->hb_spinlock, flags);
662         } /* Default is no-lock  */
663
664         /* Check if valid and not already removed... */
665         if((entry->q_next == NULL) || (entry->q_prev == NULL)) {
666                 entry = NULL;
667                 goto out;
668         }
669
670         /*
671          * Locate hashbin
672          */
673         hashv = entry->q_hash;
674         bin = GET_HASHBIN( hashv );
675
676         /*
677          * Dequeue the entry...
678          */
679         dequeue_general( (irda_queue_t**) &hashbin->hb_queue[ bin ],
680                          (irda_queue_t*) entry );
681         hashbin->hb_size--;
682         entry->q_next = NULL;
683         entry->q_prev = NULL;
684
685         /*
686          *  Check if this item is the currently selected item, and in
687          *  that case we must reset hb_current
688          */
689         if ( entry == hashbin->hb_current)
690                 hashbin->hb_current = NULL;
691 out:
692         /* Release lock */
693         if ( hashbin->hb_type & HB_LOCK ) {
694                 spin_unlock_irqrestore(&hashbin->hb_spinlock, flags);
695         } /* Default is no-lock  */
696
697         return entry;
698 }
699 EXPORT_SYMBOL(hashbin_remove_this);
700
701 /*********************** HASHBIN ENUMERATION ***********************/
702
703 /*
704  * Function hashbin_common_find (hashbin, hashv, name)
705  *
706  *    Find item with the given hashv or name
707  *
708  */
709 void* hashbin_find( hashbin_t* hashbin, long hashv, const char* name )
710 {
711         int bin;
712         irda_queue_t* entry;
713
714         IRDA_DEBUG( 4, "hashbin_find()\n");
715
716         IRDA_ASSERT( hashbin != NULL, return NULL;);
717         IRDA_ASSERT( hashbin->magic == HB_MAGIC, return NULL;);
718
719         /*
720          * Locate hashbin
721          */
722         if ( name )
723                 hashv = hash( name );
724         bin = GET_HASHBIN( hashv );
725         
726         /*
727          * Search for entry
728          */
729         entry = hashbin->hb_queue[ bin];
730         if ( entry ) {
731                 do {
732                         /*
733                          * Check for key
734                          */
735                         if ( entry->q_hash == hashv ) {
736                                 /*
737                                  * Name compare too?
738                                  */
739                                 if ( name ) {
740                                         if ( strcmp( entry->q_name, name ) == 0 ) {
741                                                 return entry;
742                                         }
743                                 } else {
744                                         return entry;
745                                 }
746                         }
747                         entry = entry->q_next;
748                 } while ( entry != hashbin->hb_queue[ bin ] );
749         }
750
751         return NULL;
752 }
753 EXPORT_SYMBOL(hashbin_find);
754
755 /*
756  * Function hashbin_lock_find (hashbin, hashv, name)
757  *
758  *    Find item with the given hashv or name
759  *
760  * Same, but with spinlock protection...
761  * I call it safe, but it's only safe with respect to the hashbin, not its
762  * content. - Jean II
763  */
764 void* hashbin_lock_find( hashbin_t* hashbin, long hashv, const char* name )
765 {
766         unsigned long flags = 0;
767         irda_queue_t* entry;
768
769         /* Synchronize */
770         spin_lock_irqsave(&hashbin->hb_spinlock, flags);
771
772         /*
773          * Search for entry
774          */
775         entry = (irda_queue_t* ) hashbin_find( hashbin, hashv, name );
776
777         /* Release lock */
778         spin_unlock_irqrestore(&hashbin->hb_spinlock, flags);
779
780         return entry;
781 }
782 EXPORT_SYMBOL(hashbin_lock_find);
783
784 /*
785  * Function hashbin_find (hashbin, hashv, name, pnext)
786  *
787  *    Find an item with the given hashv or name, and its successor
788  *
789  * This function allow to do concurrent enumerations without the
790  * need to lock over the whole session, because the caller keep the
791  * context of the search. On the other hand, it might fail and return
792  * NULL if the entry is removed. - Jean II
793  */
794 void* hashbin_find_next( hashbin_t* hashbin, long hashv, const char* name,
795                          void ** pnext)
796 {
797         unsigned long flags = 0;
798         irda_queue_t* entry;
799
800         /* Synchronize */
801         spin_lock_irqsave(&hashbin->hb_spinlock, flags);
802
803         /*
804          * Search for current entry
805          * This allow to check if the current item is still in the
806          * hashbin or has been removed.
807          */
808         entry = (irda_queue_t* ) hashbin_find( hashbin, hashv, name );
809
810         /*
811          * Trick hashbin_get_next() to return what we want
812          */
813         if(entry) {
814                 hashbin->hb_current = entry;
815                 *pnext = hashbin_get_next( hashbin );
816         } else
817                 *pnext = NULL;
818
819         /* Release lock */
820         spin_unlock_irqrestore(&hashbin->hb_spinlock, flags);
821
822         return entry;
823 }
824
825 /*
826  * Function hashbin_get_first (hashbin)
827  *
828  *    Get a pointer to first element in hashbin, this function must be
829  *    called before any calls to hashbin_get_next()!
830  *
831  */
832 irda_queue_t *hashbin_get_first( hashbin_t* hashbin) 
833 {
834         irda_queue_t *entry;
835         int i;
836
837         IRDA_ASSERT( hashbin != NULL, return NULL;);
838         IRDA_ASSERT( hashbin->magic == HB_MAGIC, return NULL;);
839
840         if ( hashbin == NULL)
841                 return NULL;
842
843         for ( i = 0; i < HASHBIN_SIZE; i ++ ) {
844                 entry = hashbin->hb_queue[ i];
845                 if ( entry) {
846                         hashbin->hb_current = entry;
847                         return entry;
848                 }
849         }
850         /*
851          *  Did not find any item in hashbin
852          */
853         return NULL;
854 }
855 EXPORT_SYMBOL(hashbin_get_first);
856
857 /*
858  * Function hashbin_get_next (hashbin)
859  *
860  *    Get next item in hashbin. A series of hashbin_get_next() calls must
861  *    be started by a call to hashbin_get_first(). The function returns
862  *    NULL when all items have been traversed
863  * 
864  * The context of the search is stored within the hashbin, so you must
865  * protect yourself from concurrent enumerations. - Jean II
866  */
867 irda_queue_t *hashbin_get_next( hashbin_t *hashbin)
868 {
869         irda_queue_t* entry;
870         int bin;
871         int i;
872
873         IRDA_ASSERT( hashbin != NULL, return NULL;);
874         IRDA_ASSERT( hashbin->magic == HB_MAGIC, return NULL;);
875
876         if ( hashbin->hb_current == NULL) {
877                 IRDA_ASSERT( hashbin->hb_current != NULL, return NULL;);
878                 return NULL;
879         }       
880         entry = hashbin->hb_current->q_next;
881         bin = GET_HASHBIN( entry->q_hash);
882
883         /*  
884          *  Make sure that we are not back at the beginning of the queue
885          *  again 
886          */
887         if ( entry != hashbin->hb_queue[ bin ]) {
888                 hashbin->hb_current = entry;
889
890                 return entry;
891         }
892
893         /*
894          *  Check that this is not the last queue in hashbin
895          */
896         if ( bin >= HASHBIN_SIZE)
897                 return NULL;
898         
899         /*
900          *  Move to next queue in hashbin
901          */
902         bin++;
903         for ( i = bin; i < HASHBIN_SIZE; i++ ) {
904                 entry = hashbin->hb_queue[ i];
905                 if ( entry) {
906                         hashbin->hb_current = entry;
907                         
908                         return entry;
909                 }
910         }
911         return NULL;
912 }
913 EXPORT_SYMBOL(hashbin_get_next);