palacios/src/palacios/vmm_hashtable.c

   1 /*
   2   Copyright (c) 2002, 2004, Christopher Clark
   3   All rights reserved.
   4
   5   Redistribution and use in source and binary forms, with or without
   6   modification, are permitted provided that the following conditions
   7   are met:
   8
   9   * Redistributions of source code must retain the above copyright
  10     notice, this list of conditions and the following disclaimer.
  11
  12   * Redistributions in binary form must reproduce the above copyright
  13     notice, this list of conditions and the following disclaimer in the
  14     documentation and/or other materials provided with the distribution.
  15
  16   * Neither the name of the original author; nor the names of any contributors
  17     may be used to endorse or promote products derived from this software
  18     without specific prior written permission.
  19
  20
  21   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  24   A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  25   CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  26   EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  27   PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  28   PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  29   LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  30   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  31   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  32 */
  33
  34 /* Modifications made by Jack Lange <jarusl@cs.northwestern.edu> */
  35
  36
  37
  38 #include <palacios/vmm.h>
  39 #include <palacios/vmm_hashtable.h>
  40 #include <palacios/vmm_string.h>
  41
  42
  43
  44
  45
  46 struct hash_entry {
  47     addr_t key;
  48     addr_t value;
  49     uint_t hash;
  50     struct hash_entry * next;
  51 };
  52
  53 struct hashtable {
  54     uint_t table_length;
  55     struct hash_entry ** table;
  56     uint_t entry_count;
  57     uint_t load_limit;
  58     uint_t prime_index;
  59     uint_t (*hash_fn) (addr_t key);
  60     int (*eq_fn) (addr_t key1, addr_t key2);
  61 };
  62
  63
  64
  65 /* HASH FUNCTIONS */
  66
  67
  68
  69 static inline uint_t do_hash(struct hashtable * htable, addr_t key) {
  70     /* Aim to protect against poor hash functions by adding logic here
  71      * - logic taken from java 1.4 hashtable source */
  72     uint_t i = htable->hash_fn(key);
  73     i += ~(i << 9);
  74     i ^=  ((i >> 14) | (i << 18)); /* >>> */
  75     i +=  (i << 4);
  76     i ^=  ((i >> 10) | (i << 22)); /* >>> */
  77
  78     return i;
  79 }
  80
  81
  82 /* HASH AN UNSIGNED LONG */
  83 /* LINUX UNSIGHED LONG HASH FUNCTION */
  84 #ifdef __V3_32BIT__
  85 /* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
  86 #define GOLDEN_RATIO_PRIME 0x9e370001UL
  87 #define BITS_PER_LONG 32
  88 #elif  defined(__V3_64BIT__)
  89 /*  2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
  90 #define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL
  91 #define BITS_PER_LONG 64
  92 #else
  93 #error Define GOLDEN_RATIO_PRIME for your wordsize.
  94 #endif
  95
  96 ulong_t v3_hash_long(ulong_t val, uint_t bits) {
  97     ulong_t hash = val;
  98
  99 #ifdef __V3_64BIT__
 100     /*  Sigh, gcc can't optimise this alone like it does for 32 bits. */
 101     ulong_t n = hash;
 102     n <<= 18;
 103     hash -= n;
 104     n <<= 33;
 105     hash -= n;
 106     n <<= 3;
 107     hash += n;
 108     n <<= 3;
 109     hash -= n;
 110     n <<= 4;
 111     hash += n;
 112     n <<= 2;
 113     hash += n;
 114 #else
 115     /* On some cpus multiply is faster, on others gcc will do shifts */
 116     hash *= GOLDEN_RATIO_PRIME;
 117 #endif
 118
 119     /* High bits are more random, so use them. */
 120     return hash >> (BITS_PER_LONG - bits);
 121 }
 122
 123 /* HASH GENERIC MEMORY BUFFER */
 124 /* ELF HEADER HASH FUNCTION */
 125 ulong_t v3_hash_buffer(uchar_t * msg, uint_t length) {
 126     ulong_t hash = 0;
 127     ulong_t temp = 0;
 128     uint_t i;
 129
 130     for (i = 0; i < length; i++) {
 131         hash = (hash << 4) + *(msg + i) + i;
 132         if ((temp = (hash & 0xF0000000))) {
 133             hash ^= (temp >> 24);
 134         }
 135         hash &= ~temp;
 136     }
 137     return hash;
 138 }
 139
 140
 141
 142 /*****************************************************************************/
 143 /* indexFor */
 144 static inline uint_t indexFor(uint_t table_length, uint_t hash_value) {
 145     return (hash_value % table_length);
 146 };
 147
 148 /* Only works if table_length == 2^N */
 149 /*
 150   static inline uint_t indexFor(uint_t table_length, uint_t hashvalue)
 151   {
 152   return (hashvalue & (table_length - 1u));
 153   }
 154 */
 155
 156 /*****************************************************************************/
 157 #define freekey(X) V3_Free(X)
 158 /*define freekey(X) ; */
 159
 160
 161 static void * tmp_realloc(void * old_ptr, uint_t old_size, uint_t new_size) {
 162     void * new_buf = V3_Malloc(new_size);
 163
 164     if (new_buf == NULL) {
 165         return NULL;
 166     }
 167
 168     memcpy(new_buf, old_ptr, old_size);
 169     V3_Free(old_ptr);
 170
 171     return new_buf;
 172 }
 173
 174
 175 /*
 176   Credit for primes table: Aaron Krowne
 177   http://br.endernet.org/~akrowne/
 178   http://planetmath.org/encyclopedia/GoodHashTablePrimes.html
 179 */
 180 static const uint_t primes[] = {
 181     53, 97, 193, 389,
 182     769, 1543, 3079, 6151,
 183     12289, 24593, 49157, 98317,
 184     196613, 393241, 786433, 1572869,
 185     3145739, 6291469, 12582917, 25165843,
 186     50331653, 100663319, 201326611, 402653189,
 187     805306457, 1610612741 };
 188
 189
 190 // this assumes that the max load factor is .65
 191 static const uint_t load_factors[] = {
 192     35, 64, 126, 253,
 193     500, 1003, 2002, 3999,
 194     7988, 15986, 31953, 63907,
 195     127799, 255607, 511182, 1022365,
 196     2044731, 4089455, 8178897, 16357798,
 197     32715575, 65431158, 130862298, 261724573,
 198     523449198, 1046898282 };
 199
 200 const uint_t prime_table_length = sizeof(primes) / sizeof(primes[0]);
 201
 202
 203
 204 /*****************************************************************************/
 205 struct hashtable * v3_create_htable(uint_t min_size,
 206                                     uint_t (*hash_fn) (addr_t),
 207                                     int (*eq_fn) (addr_t, addr_t)) {
 208     struct hashtable * htable;
 209     uint_t prime_index;
 210     uint_t size = primes[0];
 211
 212     /* Check requested hashtable isn't too large */
 213     if (min_size > (1u << 30)) {
 214         return NULL;
 215     }
 216
 217     /* Enforce size as prime */
 218     for (prime_index = 0; prime_index < prime_table_length; prime_index++) {
 219         if (primes[prime_index] > min_size) {
 220             size = primes[prime_index];
 221             break;
 222         }
 223     }
 224
 225     htable = (struct hashtable *)V3_Malloc(sizeof(struct hashtable));
 226
 227     if (htable == NULL) {
 228         return NULL; /*oom*/
 229     }
 230
 231     htable->table = (struct hash_entry **)V3_Malloc(sizeof(struct hash_entry*) * size);
 232
 233     if (htable->table == NULL) {
 234         V3_Free(htable);
 235         return NULL;  /*oom*/
 236     }
 237
 238
 239     memset(htable->table, 0, size * sizeof(struct hash_entry *));
 240
 241     htable->table_length  = size;
 242     htable->prime_index   = prime_index;
 243     htable->entry_count   = 0;
 244     htable->hash_fn       = hash_fn;
 245     htable->eq_fn         = eq_fn;
 246     htable->load_limit    = load_factors[prime_index];
 247
 248     return htable;
 249 }
 250
 251
 252
 253 /*****************************************************************************/
 254 static int hashtable_expand(struct hashtable * htable) {
 255     /* Double the size of the table to accomodate more entries */
 256     struct hash_entry ** new_table;
 257     struct hash_entry * tmp_entry;
 258     struct hash_entry ** entry_ptr;
 259     uint_t new_size;
 260     uint_t i;
 261     uint_t index;
 262
 263     /* Check we're not hitting max capacity */
 264     if (htable->prime_index == (prime_table_length - 1)) {
 265         return 0;
 266     }
 267
 268     new_size = primes[++(htable->prime_index)];
 269
 270     new_table = (struct hash_entry **)V3_Malloc(sizeof(struct hash_entry*) * new_size);
 271
 272     if (new_table != NULL) {
 273         memset(new_table, 0, new_size * sizeof(struct hash_entry *));
 274         /* This algorithm is not 'stable'. ie. it reverses the list
 275          * when it transfers entries between the tables */
 276
 277         for (i = 0; i < htable->table_length; i++) {
 278
 279             while ((tmp_entry = htable->table[i]) != NULL) {
 280                 htable->table[i] = tmp_entry->next;
 281
 282                 index = indexFor(new_size, tmp_entry->hash);
 283
 284                 tmp_entry->next = new_table[index];
 285
 286                 new_table[index] = tmp_entry;
 287             }
 288         }
 289
 290         V3_Free(htable->table);
 291
 292         htable->table = new_table;
 293     } else {
 294         /* Plan B: realloc instead */
 295
 296         //new_table = (struct hash_entry **)realloc(htable->table, new_size * sizeof(struct hash_entry *));
 297         new_table = (struct hash_entry **)tmp_realloc(htable->table, primes[htable->prime_index - 1],
 298                                                       new_size * sizeof(struct hash_entry *));
 299
 300         if (new_table == NULL) {
 301             (htable->prime_index)--;
 302             return 0;
 303         }
 304
 305         htable->table = new_table;
 306
 307         memset(new_table[htable->table_length], 0, new_size - htable->table_length);
 308
 309         for (i = 0; i < htable->table_length; i++) {
 310
 311             for (entry_ptr = &(new_table[i]), tmp_entry = *entry_ptr;
 312                  tmp_entry != NULL;
 313                  tmp_entry = *entry_ptr) {
 314
 315                 index = indexFor(new_size, tmp_entry->hash);
 316
 317                 if (i == index) {
 318                     entry_ptr = &(tmp_entry->next);
 319                 } else {
 320                     *entry_ptr = tmp_entry->next;
 321                     tmp_entry->next = new_table[index];
 322                     new_table[index] = tmp_entry;
 323                 }
 324             }
 325         }
 326     }
 327
 328     htable->table_length = new_size;
 329
 330     htable->load_limit   = load_factors[htable->prime_index];
 331
 332     return -1;
 333 }
 334
 335 /*****************************************************************************/
 336 uint_t v3_htable_count(struct hashtable * htable) {
 337     return htable->entry_count;
 338 }
 339
 340 /*****************************************************************************/
 341 int v3_htable_insert(struct hashtable * htable, addr_t key, addr_t value) {
 342     /* This method allows duplicate keys - but they shouldn't be used */
 343     uint_t index;
 344     struct hash_entry * new_entry;
 345
 346     if (++(htable->entry_count) > htable->load_limit) {
 347         /* Ignore the return value. If expand fails, we should
 348          * still try cramming just this value into the existing table
 349          * -- we may not have memory for a larger table, but one more
 350          * element may be ok. Next time we insert, we'll try expanding again.*/
 351         hashtable_expand(htable);
 352     }
 353
 354
 355     new_entry = (struct hash_entry *)V3_Malloc(sizeof(struct hash_entry));
 356
 357     if (new_entry == NULL) {
 358         (htable->entry_count)--;
 359         return 0; /*oom*/
 360     }
 361
 362     new_entry->hash = do_hash(htable, key);
 363
 364     index = indexFor(htable->table_length, new_entry->hash);
 365
 366     new_entry->key = key;
 367     new_entry->value = value;
 368
 369     new_entry->next = htable->table[index];
 370
 371     htable->table[index] = new_entry;
 372
 373     return -1;
 374 }
 375
 376
 377
 378 int v3_htable_change(struct hashtable * htable, addr_t key, addr_t value, int free_value) {
 379     struct hash_entry * tmp_entry;
 380     uint_t hash_value;
 381     uint_t index;
 382
 383     hash_value = do_hash(htable, key);
 384
 385     index = indexFor(htable->table_length, hash_value);
 386
 387     tmp_entry = htable->table[index];
 388
 389     while (tmp_entry != NULL) {
 390         /* Check hash value to short circuit heavier comparison */
 391         if ((hash_value == tmp_entry->hash) && (htable->eq_fn(key, tmp_entry->key))) {
 392
 393             if (free_value) {
 394                 V3_Free((void *)(tmp_entry->value));
 395             }
 396
 397             tmp_entry->value = value;
 398             return -1;
 399         }
 400         tmp_entry = tmp_entry->next;
 401     }
 402     return 0;
 403 }
 404
 405
 406
 407 int v3_htable_inc(struct hashtable * htable, addr_t key, addr_t value) {
 408     struct hash_entry * tmp_entry;
 409     uint_t hash_value;
 410     uint_t index;
 411
 412     hash_value = do_hash(htable, key);
 413
 414     index = indexFor(htable->table_length, hash_value);
 415
 416     tmp_entry = htable->table[index];
 417
 418     while (tmp_entry != NULL) {
 419         /* Check hash value to short circuit heavier comparison */
 420         if ((hash_value == tmp_entry->hash) && (htable->eq_fn(key, tmp_entry->key))) {
 421
 422             tmp_entry->value += value;
 423             return -1;
 424         }
 425         tmp_entry = tmp_entry->next;
 426     }
 427     return 0;
 428 }
 429
 430
 431 int v3_htable_dec(struct hashtable * htable, addr_t key, addr_t value) {
 432     struct hash_entry * tmp_entry;
 433     uint_t hash_value;
 434     uint_t index;
 435
 436     hash_value = do_hash(htable, key);
 437
 438     index = indexFor(htable->table_length, hash_value);
 439
 440     tmp_entry = htable->table[index];
 441
 442     while (tmp_entry != NULL) {
 443         /* Check hash value to short circuit heavier comparison */
 444         if ((hash_value == tmp_entry->hash) && (htable->eq_fn(key, tmp_entry->key))) {
 445
 446             tmp_entry->value -= value;
 447             return -1;
 448         }
 449         tmp_entry = tmp_entry->next;
 450     }
 451     return 0;
 452 }
 453
 454
 455
 456
 457 /*****************************************************************************/
 458 /* returns value associated with key */
 459 addr_t v3_htable_search(struct hashtable * htable, addr_t key) {
 460     struct hash_entry * cursor;
 461     uint_t hash_value;
 462     uint_t index;
 463
 464     hash_value = do_hash(htable, key);
 465
 466     index = indexFor(htable->table_length, hash_value);
 467
 468     cursor = htable->table[index];
 469
 470     while (cursor != NULL) {
 471         /* Check hash value to short circuit heavier comparison */
 472         if ((hash_value == cursor->hash) &&
 473             (htable->eq_fn(key, cursor->key))) {
 474             return cursor->value;
 475         }
 476
 477         cursor = cursor->next;
 478     }
 479
 480     return (addr_t)NULL;
 481 }
 482
 483 /*****************************************************************************/
 484 /* returns value associated with key */
 485 addr_t v3_htable_remove(struct hashtable * htable, addr_t key, int free_key) {
 486     /* TODO: consider compacting the table when the load factor drops enough,
 487      *       or provide a 'compact' method. */
 488
 489     struct hash_entry * cursor;
 490     struct hash_entry ** entry_ptr;
 491     addr_t value;
 492     uint_t hash_value;
 493     uint_t index;
 494
 495     hash_value = do_hash(htable, key);
 496
 497     index = indexFor(htable->table_length, hash_value);
 498
 499     entry_ptr = &(htable->table[index]);
 500     cursor = *entry_ptr;
 501
 502     while (cursor != NULL) {
 503         /* Check hash value to short circuit heavier comparison */
 504         if ((hash_value == cursor->hash) &&
 505             (htable->eq_fn(key, cursor->key))) {
 506
 507             *entry_ptr = cursor->next;
 508             htable->entry_count--;
 509             value = cursor->value;
 510
 511             if (free_key) {
 512                 freekey((void *)(cursor->key));
 513             }
 514             V3_Free(cursor);
 515
 516             return value;
 517         }
 518
 519         entry_ptr = &(cursor->next);
 520         cursor = cursor->next;
 521     }
 522     return (addr_t)NULL;
 523 }
 524
 525 /*****************************************************************************/
 526 /* destroy */
 527 void v3_free_htable(struct hashtable * htable, int free_values, int free_keys) {
 528     uint_t i;
 529     struct hash_entry * cursor;;
 530     struct hash_entry **table = htable->table;
 531
 532     if (free_values) {
 533         for (i = 0; i < htable->table_length; i++) {
 534             cursor = table[i];
 535
 536             while (cursor != NULL) {
 537                 struct hash_entry * tmp;
 538
 539                 tmp = cursor;
 540                 cursor = cursor->next;
 541
 542                 if (free_keys) {
 543                     freekey((void *)(tmp->key));
 544                 }
 545                 V3_Free((void *)(tmp->value));
 546                 V3_Free(tmp);
 547             }
 548         }
 549     } else {
 550         for (i = 0; i < htable->table_length; i++) {
 551             cursor = table[i];
 552
 553             while (cursor != NULL) {
 554                 struct hash_entry * tmp;
 555
 556                 tmp = cursor;
 557                 cursor = cursor->next;
 558
 559                 if (free_keys) {
 560                     freekey((void *)(tmp->key));
 561                 }
 562                 V3_Free(tmp);
 563             }
 564         }
 565     }
 566
 567     V3_Free(htable->table);
 568     V3_Free(htable);
 569 }
 570
 571
 572
 573
 574 /* HASH TABLE ITERATORS */
 575
 576
 577
 578 struct hashtable_iter * v3_create_htable_iter(struct hashtable * htable) {
 579     uint_t i;
 580     uint_t table_length;
 581
 582     struct hashtable_iter * iter = (struct hashtable_iter *)V3_Malloc(sizeof(struct hashtable_iter));
 583
 584     if (iter == NULL) {
 585         return NULL;
 586     }
 587
 588     iter->htable = htable;
 589     iter->entry = NULL;
 590     iter->parent = NULL;
 591     table_length = htable->table_length;
 592     iter->index = table_length;
 593
 594     if (htable->entry_count == 0) {
 595         return iter;
 596     }
 597
 598     for (i = 0; i < table_length; i++) {
 599         if (htable->table[i] != NULL) {
 600             iter->entry = htable->table[i];
 601             iter->index = i;
 602             break;
 603         }
 604     }
 605
 606     return iter;
 607 }
 608
 609
 610 addr_t v3_htable_get_iter_key(struct hashtable_iter * iter) {
 611     return iter->entry->key;
 612 }
 613
 614 addr_t v3_htable_get_iter_value(struct hashtable_iter * iter) {
 615     return iter->entry->value;
 616 }
 617
 618
 619 /* advance - advance the iterator to the next element
 620  *           returns zero if advanced to end of table */
 621 int v3_htable_iter_advance(struct hashtable_iter * iter) {
 622     uint_t j;
 623     uint_t table_length;
 624     struct hash_entry ** table;
 625     struct hash_entry * next;
 626
 627     if (iter->entry == NULL) {
 628         return 0; /* stupidity check */
 629     }
 630
 631
 632     next = iter->entry->next;
 633
 634     if (next != NULL) {
 635         iter->parent = iter->entry;
 636         iter->entry = next;
 637         return -1;
 638     }
 639
 640     table_length = iter->htable->table_length;
 641     iter->parent = NULL;
 642
 643     if (table_length <= (j = ++(iter->index))) {
 644         iter->entry = NULL;
 645         return 0;
 646     }
 647
 648     table = iter->htable->table;
 649
 650     while ((next = table[j]) == NULL) {
 651         if (++j >= table_length) {
 652             iter->index = table_length;
 653             iter->entry = NULL;
 654             return 0;
 655         }
 656     }
 657
 658     iter->index = j;
 659     iter->entry = next;
 660
 661     return -1;
 662 }
 663
 664
 665 /* remove - remove the entry at the current iterator position
 666  *          and advance the iterator, if there is a successive
 667  *          element.
 668  *          If you want the value, read it before you remove:
 669  *          beware memory leaks if you don't.
 670  *          Returns zero if end of iteration. */
 671 int v3_htable_iter_remove(struct hashtable_iter * iter, int free_key) {
 672     struct hash_entry * remember_entry;
 673     struct hash_entry * remember_parent;
 674     int ret;
 675
 676     /* Do the removal */
 677     if ((iter->parent) == NULL) {
 678         /* element is head of a chain */
 679         iter->htable->table[iter->index] = iter->entry->next;
 680     } else {
 681         /* element is mid-chain */
 682         iter->parent->next = iter->entry->next;
 683     }
 684
 685
 686     /* itr->e is now outside the hashtable */
 687     remember_entry = iter->entry;
 688     iter->htable->entry_count--;
 689     if (free_key) {
 690         freekey((void *)(remember_entry->key));
 691     }
 692
 693     /* Advance the iterator, correcting the parent */
 694     remember_parent = iter->parent;
 695     ret = v3_htable_iter_advance(iter);
 696
 697     if (iter->parent == remember_entry) {
 698         iter->parent = remember_parent;
 699     }
 700
 701     V3_Free(remember_entry);
 702     return ret;
 703 }
 704
 705
 706 /* returns zero if not found */
 707 int v3_htable_iter_search(struct hashtable_iter * iter,
 708                               struct hashtable * htable, addr_t key) {
 709     struct hash_entry * entry;
 710     struct hash_entry * parent;
 711     uint_t hash_value;
 712     uint_t index;
 713
 714     hash_value = do_hash(htable, key);
 715     index = indexFor(htable->table_length, hash_value);
 716
 717     entry = htable->table[index];
 718     parent = NULL;
 719
 720     while (entry != NULL) {
 721         /* Check hash value to short circuit heavier comparison */
 722         if ((hash_value == entry->hash) &&
 723             (htable->eq_fn(key, entry->key))) {
 724             iter->index = index;
 725             iter->entry = entry;
 726             iter->parent = parent;
 727             iter->htable = htable;
 728             return -1;
 729         }
 730         parent = entry;
 731         entry = entry->next;
 732     }
 733     return 0;
 734 }
 735
 736 void v3_destroy_htable_iter(struct hashtable_iter * iter) {
 737     if (iter) {
 738         V3_Free(iter);
 739     }
 740 }
 741
 742
 743
 744
 745
 746
 747
 748
 749
 750
 751
 752
 753
 754
 755 /*
 756  * Copyright (c) 2002, Christopher Clark
 757  * All rights reserved.
 758  *
 759  * Redistribution and use in source and binary forms, with or without
 760  * modification, are permitted provided that the following conditions
 761  * are met:
 762  *
 763  * * Redistributions of source code must retain the above copyright
 764  * notice, this list of conditions and the following disclaimer.
 765  *
 766  * * Redistributions in binary form must reproduce the above copyright
 767  * notice, this list of conditions and the following disclaimer in the
 768  * documentation and/or other materials provided with the distribution.
 769  *
 770  * * Neither the name of the original author; nor the names of any contributors
 771  * may be used to endorse or promote products derived from this software
 772  * without specific prior written permission.
 773  *
 774  *
 775  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 776  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 777  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 778  * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER
 779  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 780  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 781  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 782  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 783  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 784  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 785  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 786  */