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     if (prime_index==prime_table_length) {
 226         return NULL;
 227     }
 228
 229     htable = (struct hashtable *)V3_Malloc(sizeof(struct hashtable));
 230
 231     if (htable == NULL) {
 232         return NULL; /*oom*/
 233     }
 234
 235     htable->table = (struct hash_entry **)V3_Malloc(sizeof(struct hash_entry*) * size);
 236
 237     if (htable->table == NULL) {
 238         V3_Free(htable);
 239         return NULL;  /*oom*/
 240     }
 241
 242
 243     memset(htable->table, 0, size * sizeof(struct hash_entry *));
 244
 245     htable->table_length  = size;
 246     htable->prime_index   = prime_index;
 247     htable->entry_count   = 0;
 248     htable->hash_fn       = hash_fn;
 249     htable->eq_fn         = eq_fn;
 250     htable->load_limit    = load_factors[prime_index];
 251
 252     return htable;
 253 }
 254
 255
 256
 257 /*****************************************************************************/
 258 static int hashtable_expand(struct hashtable * htable) {
 259     /* Double the size of the table to accomodate more entries */
 260     struct hash_entry ** new_table;
 261     struct hash_entry * tmp_entry;
 262     struct hash_entry ** entry_ptr;
 263     uint_t new_size;
 264     uint_t i;
 265     uint_t index;
 266
 267     /* Check we're not hitting max capacity */
 268     if (htable->prime_index == (prime_table_length - 1)) {
 269         return 0;
 270     }
 271
 272     new_size = primes[++(htable->prime_index)];
 273
 274     new_table = (struct hash_entry **)V3_Malloc(sizeof(struct hash_entry*) * new_size);
 275
 276     if (new_table != NULL) {
 277         memset(new_table, 0, new_size * sizeof(struct hash_entry *));
 278         /* This algorithm is not 'stable'. ie. it reverses the list
 279          * when it transfers entries between the tables */
 280
 281         for (i = 0; i < htable->table_length; i++) {
 282
 283             while ((tmp_entry = htable->table[i]) != NULL) {
 284                 htable->table[i] = tmp_entry->next;
 285
 286                 index = indexFor(new_size, tmp_entry->hash);
 287
 288                 tmp_entry->next = new_table[index];
 289
 290                 new_table[index] = tmp_entry;
 291             }
 292         }
 293
 294         V3_Free(htable->table);
 295
 296         htable->table = new_table;
 297     } else {
 298         /* Plan B: realloc instead */
 299
 300         //new_table = (struct hash_entry **)realloc(htable->table, new_size * sizeof(struct hash_entry *));
 301         new_table = (struct hash_entry **)tmp_realloc(htable->table, primes[htable->prime_index - 1],
 302                                                       new_size * sizeof(struct hash_entry *));
 303
 304         if (new_table == NULL) {
 305             (htable->prime_index)--;
 306             return 0;
 307         }
 308
 309         htable->table = new_table;
 310
 311         memset(new_table[htable->table_length], 0, new_size - htable->table_length);
 312
 313         for (i = 0; i < htable->table_length; i++) {
 314
 315             for (entry_ptr = &(new_table[i]), tmp_entry = *entry_ptr;
 316                  tmp_entry != NULL;
 317                  tmp_entry = *entry_ptr) {
 318
 319                 index = indexFor(new_size, tmp_entry->hash);
 320
 321                 if (i == index) {
 322                     entry_ptr = &(tmp_entry->next);
 323                 } else {
 324                     *entry_ptr = tmp_entry->next;
 325                     tmp_entry->next = new_table[index];
 326                     new_table[index] = tmp_entry;
 327                 }
 328             }
 329         }
 330     }
 331
 332     htable->table_length = new_size;
 333
 334     htable->load_limit   = load_factors[htable->prime_index];
 335
 336     return -1;
 337 }
 338
 339 /*****************************************************************************/
 340 uint_t v3_htable_count(struct hashtable * htable) {
 341     return htable->entry_count;
 342 }
 343
 344 /*****************************************************************************/
 345 int v3_htable_insert(struct hashtable * htable, addr_t key, addr_t value) {
 346     /* This method allows duplicate keys - but they shouldn't be used */
 347     uint_t index;
 348     struct hash_entry * new_entry;
 349
 350     if (++(htable->entry_count) > htable->load_limit) {
 351         /* Ignore the return value. If expand fails, we should
 352          * still try cramming just this value into the existing table
 353          * -- we may not have memory for a larger table, but one more
 354          * element may be ok. Next time we insert, we'll try expanding again.*/
 355         hashtable_expand(htable);
 356     }
 357
 358
 359     new_entry = (struct hash_entry *)V3_Malloc(sizeof(struct hash_entry));
 360
 361     if (new_entry == NULL) {
 362         (htable->entry_count)--;
 363         return 0; /*oom*/
 364     }
 365
 366     new_entry->hash = do_hash(htable, key);
 367
 368     index = indexFor(htable->table_length, new_entry->hash);
 369
 370     new_entry->key = key;
 371     new_entry->value = value;
 372
 373     new_entry->next = htable->table[index];
 374
 375     htable->table[index] = new_entry;
 376
 377     return -1;
 378 }
 379
 380
 381
 382 int v3_htable_change(struct hashtable * htable, addr_t key, addr_t value, int free_value) {
 383     struct hash_entry * tmp_entry;
 384     uint_t hash_value;
 385     uint_t index;
 386
 387     hash_value = do_hash(htable, key);
 388
 389     index = indexFor(htable->table_length, hash_value);
 390
 391     tmp_entry = htable->table[index];
 392
 393     while (tmp_entry != NULL) {
 394         /* Check hash value to short circuit heavier comparison */
 395         if ((hash_value == tmp_entry->hash) && (htable->eq_fn(key, tmp_entry->key))) {
 396
 397             if (free_value) {
 398                 V3_Free((void *)(tmp_entry->value));
 399             }
 400
 401             tmp_entry->value = value;
 402             return -1;
 403         }
 404         tmp_entry = tmp_entry->next;
 405     }
 406     return 0;
 407 }
 408
 409
 410
 411 int v3_htable_inc(struct hashtable * htable, addr_t key, addr_t value) {
 412     struct hash_entry * tmp_entry;
 413     uint_t hash_value;
 414     uint_t index;
 415
 416     hash_value = do_hash(htable, key);
 417
 418     index = indexFor(htable->table_length, hash_value);
 419
 420     tmp_entry = htable->table[index];
 421
 422     while (tmp_entry != NULL) {
 423         /* Check hash value to short circuit heavier comparison */
 424         if ((hash_value == tmp_entry->hash) && (htable->eq_fn(key, tmp_entry->key))) {
 425
 426             tmp_entry->value += value;
 427             return -1;
 428         }
 429         tmp_entry = tmp_entry->next;
 430     }
 431     return 0;
 432 }
 433
 434
 435 int v3_htable_dec(struct hashtable * htable, addr_t key, addr_t value) {
 436     struct hash_entry * tmp_entry;
 437     uint_t hash_value;
 438     uint_t index;
 439
 440     hash_value = do_hash(htable, key);
 441
 442     index = indexFor(htable->table_length, hash_value);
 443
 444     tmp_entry = htable->table[index];
 445
 446     while (tmp_entry != NULL) {
 447         /* Check hash value to short circuit heavier comparison */
 448         if ((hash_value == tmp_entry->hash) && (htable->eq_fn(key, tmp_entry->key))) {
 449
 450             tmp_entry->value -= value;
 451             return -1;
 452         }
 453         tmp_entry = tmp_entry->next;
 454     }
 455     return 0;
 456 }
 457
 458
 459
 460
 461 /*****************************************************************************/
 462 /* returns value associated with key */
 463 addr_t v3_htable_search(struct hashtable * htable, addr_t key) {
 464     struct hash_entry * cursor;
 465     uint_t hash_value;
 466     uint_t index;
 467
 468     hash_value = do_hash(htable, key);
 469
 470     index = indexFor(htable->table_length, hash_value);
 471
 472     cursor = htable->table[index];
 473
 474     while (cursor != NULL) {
 475         /* Check hash value to short circuit heavier comparison */
 476         if ((hash_value == cursor->hash) &&
 477             (htable->eq_fn(key, cursor->key))) {
 478             return cursor->value;
 479         }
 480
 481         cursor = cursor->next;
 482     }
 483
 484     return (addr_t)NULL;
 485 }
 486
 487 /*****************************************************************************/
 488 /* returns value associated with key */
 489 addr_t v3_htable_remove(struct hashtable * htable, addr_t key, int free_key) {
 490     /* TODO: consider compacting the table when the load factor drops enough,
 491      *       or provide a 'compact' method. */
 492
 493     struct hash_entry * cursor;
 494     struct hash_entry ** entry_ptr;
 495     addr_t value;
 496     uint_t hash_value;
 497     uint_t index;
 498
 499     hash_value = do_hash(htable, key);
 500
 501     index = indexFor(htable->table_length, hash_value);
 502
 503     entry_ptr = &(htable->table[index]);
 504     cursor = *entry_ptr;
 505
 506     while (cursor != NULL) {
 507         /* Check hash value to short circuit heavier comparison */
 508         if ((hash_value == cursor->hash) &&
 509             (htable->eq_fn(key, cursor->key))) {
 510
 511             *entry_ptr = cursor->next;
 512             htable->entry_count--;
 513             value = cursor->value;
 514
 515             if (free_key) {
 516                 freekey((void *)(cursor->key));
 517             }
 518             V3_Free(cursor);
 519
 520             return value;
 521         }
 522
 523         entry_ptr = &(cursor->next);
 524         cursor = cursor->next;
 525     }
 526     return (addr_t)NULL;
 527 }
 528
 529 /*****************************************************************************/
 530 /* destroy */
 531 void v3_free_htable(struct hashtable * htable, int free_values, int free_keys) {
 532     uint_t i;
 533     struct hash_entry * cursor;;
 534     struct hash_entry **table = htable->table;
 535
 536     if (free_values) {
 537         for (i = 0; i < htable->table_length; i++) {
 538             cursor = table[i];
 539
 540             while (cursor != NULL) {
 541                 struct hash_entry * tmp;
 542
 543                 tmp = cursor;
 544                 cursor = cursor->next;
 545
 546                 if (free_keys) {
 547                     freekey((void *)(tmp->key));
 548                 }
 549                 V3_Free((void *)(tmp->value));
 550                 V3_Free(tmp);
 551             }
 552         }
 553     } else {
 554         for (i = 0; i < htable->table_length; i++) {
 555             cursor = table[i];
 556
 557             while (cursor != NULL) {
 558                 struct hash_entry * tmp;
 559
 560                 tmp = cursor;
 561                 cursor = cursor->next;
 562
 563                 if (free_keys) {
 564                     freekey((void *)(tmp->key));
 565                 }
 566                 V3_Free(tmp);
 567             }
 568         }
 569     }
 570
 571     V3_Free(htable->table);
 572     V3_Free(htable);
 573 }
 574
 575
 576
 577
 578 /* HASH TABLE ITERATORS */
 579
 580
 581
 582 struct hashtable_iter * v3_create_htable_iter(struct hashtable * htable) {
 583     uint_t i;
 584     uint_t table_length;
 585
 586     struct hashtable_iter * iter = (struct hashtable_iter *)V3_Malloc(sizeof(struct hashtable_iter));
 587
 588     if (iter == NULL) {
 589         return NULL;
 590     }
 591
 592     iter->htable = htable;
 593     iter->entry = NULL;
 594     iter->parent = NULL;
 595     table_length = htable->table_length;
 596     iter->index = table_length;
 597
 598     if (htable->entry_count == 0) {
 599         return iter;
 600     }
 601
 602     for (i = 0; i < table_length; i++) {
 603         if (htable->table[i] != NULL) {
 604             iter->entry = htable->table[i];
 605             iter->index = i;
 606             break;
 607         }
 608     }
 609
 610     return iter;
 611 }
 612
 613
 614 addr_t v3_htable_get_iter_key(struct hashtable_iter * iter) {
 615     return iter->entry->key;
 616 }
 617
 618 addr_t v3_htable_get_iter_value(struct hashtable_iter * iter) {
 619     return iter->entry->value;
 620 }
 621
 622
 623 /* advance - advance the iterator to the next element
 624  *           returns zero if advanced to end of table */
 625 int v3_htable_iter_advance(struct hashtable_iter * iter) {
 626     uint_t j;
 627     uint_t table_length;
 628     struct hash_entry ** table;
 629     struct hash_entry * next;
 630
 631     if (iter->entry == NULL) {
 632         return 0; /* stupidity check */
 633     }
 634
 635
 636     next = iter->entry->next;
 637
 638     if (next != NULL) {
 639         iter->parent = iter->entry;
 640         iter->entry = next;
 641         return -1;
 642     }
 643
 644     table_length = iter->htable->table_length;
 645     iter->parent = NULL;
 646
 647     if (table_length <= (j = ++(iter->index))) {
 648         iter->entry = NULL;
 649         return 0;
 650     }
 651
 652     table = iter->htable->table;
 653
 654     while ((next = table[j]) == NULL) {
 655         if (++j >= table_length) {
 656             iter->index = table_length;
 657             iter->entry = NULL;
 658             return 0;
 659         }
 660     }
 661
 662     iter->index = j;
 663     iter->entry = next;
 664
 665     return -1;
 666 }
 667
 668
 669 /* remove - remove the entry at the current iterator position
 670  *          and advance the iterator, if there is a successive
 671  *          element.
 672  *          If you want the value, read it before you remove:
 673  *          beware memory leaks if you don't.
 674  *          Returns zero if end of iteration. */
 675 int v3_htable_iter_remove(struct hashtable_iter * iter, int free_key) {
 676     struct hash_entry * remember_entry;
 677     struct hash_entry * remember_parent;
 678     int ret;
 679
 680     /* Do the removal */
 681     if ((iter->parent) == NULL) {
 682         /* element is head of a chain */
 683         iter->htable->table[iter->index] = iter->entry->next;
 684     } else {
 685         /* element is mid-chain */
 686         iter->parent->next = iter->entry->next;
 687     }
 688
 689
 690     /* itr->e is now outside the hashtable */
 691     remember_entry = iter->entry;
 692     iter->htable->entry_count--;
 693     if (free_key) {
 694         freekey((void *)(remember_entry->key));
 695     }
 696
 697     /* Advance the iterator, correcting the parent */
 698     remember_parent = iter->parent;
 699     ret = v3_htable_iter_advance(iter);
 700
 701     if (iter->parent == remember_entry) {
 702         iter->parent = remember_parent;
 703     }
 704
 705     V3_Free(remember_entry);
 706     return ret;
 707 }
 708
 709
 710 /* returns zero if not found */
 711 int v3_htable_iter_search(struct hashtable_iter * iter,
 712                               struct hashtable * htable, addr_t key) {
 713     struct hash_entry * entry;
 714     struct hash_entry * parent;
 715     uint_t hash_value;
 716     uint_t index;
 717
 718     hash_value = do_hash(htable, key);
 719     index = indexFor(htable->table_length, hash_value);
 720
 721     entry = htable->table[index];
 722     parent = NULL;
 723
 724     while (entry != NULL) {
 725         /* Check hash value to short circuit heavier comparison */
 726         if ((hash_value == entry->hash) &&
 727             (htable->eq_fn(key, entry->key))) {
 728             iter->index = index;
 729             iter->entry = entry;
 730             iter->parent = parent;
 731             iter->htable = htable;
 732             return -1;
 733         }
 734         parent = entry;
 735         entry = entry->next;
 736     }
 737     return 0;
 738 }
 739
 740 void v3_destroy_htable_iter(struct hashtable_iter * iter) {
 741     if (iter) {
 742         V3_Free(iter);
 743     }
 744 }
 745
 746
 747
 748
 749
 750
 751
 752
 753
 754
 755
 756
 757
 758
 759 /*
 760  * Copyright (c) 2002, Christopher Clark
 761  * All rights reserved.
 762  *
 763  * Redistribution and use in source and binary forms, with or without
 764  * modification, are permitted provided that the following conditions
 765  * are met:
 766  *
 767  * * Redistributions of source code must retain the above copyright
 768  * notice, this list of conditions and the following disclaimer.
 769  *
 770  * * Redistributions in binary form must reproduce the above copyright
 771  * notice, this list of conditions and the following disclaimer in the
 772  * documentation and/or other materials provided with the distribution.
 773  *
 774  * * Neither the name of the original author; nor the names of any contributors
 775  * may be used to endorse or promote products derived from this software
 776  * without specific prior written permission.
 777  *
 778  *
 779  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 780  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 781  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 782  * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER
 783  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 784  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 785  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 786  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 787  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 788  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 789  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 790  */