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,"%s()\n", __FUNCTION__);
 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, "%s()\n", __FUNCTION__);
 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, "%s()\n", __FUNCTION__);
 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, "%s()\n", __FUNCTION__);
 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, "%s()\n", __FUNCTION__);
 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 }