ht.h (35489B)
1 /* Copyright (c) 2002, Christopher Clark. 2 * Copyright (c) 2005-2006, Nick Mathewson. 3 * Copyright (c) 2007-2019, The Tor Project, Inc. */ 4 /* See license at end. */ 5 6 /* Based on ideas by Christopher Clark and interfaces from Niels Provos. */ 7 8 /* 9 These macros provide an intrustive implementation for a typesafe chaining 10 hash table, loosely based on the BSD tree.h and queue.h macros. Here's 11 how to use them. 12 13 First, pick a the structure that you'll be storing in the hashtable. Let's 14 say that's "struct dinosaur". To this structure, you add an HT_ENTRY() 15 member, as such: 16 17 struct dinosaur { 18 HT_ENTRY(dinosaur) node; // The name inside the () must match the 19 // struct. 20 21 // These are just fields from the dinosaur structure... 22 long dinosaur_id; 23 char *name; 24 long age; 25 int is_ornithischian; 26 int is_herbivorous; 27 }; 28 29 You can declare the hashtable itself as: 30 31 HT_HEAD(dinosaur_ht, dinosaur); 32 33 This declares a new 'struct dinosaur_ht' type. 34 35 Now you need to declare two functions to help implement the hashtable: one 36 compares two dinosaurs for equality, and one computes the hash of a 37 dinosaur. Let's say that two dinosaurs are equal if they have the same ID 38 and name. 39 40 int 41 dinosaurs_equal(const struct dinosaur *d1, const struct dinosaur *d2) 42 { 43 return d1->dinosaur_id == d2->dinosaur_id && 44 0 == strcmp(d1->name, d2->name); 45 } 46 47 unsigned 48 dinosaur_hash(const struct dinosaur *d) 49 { 50 // This is a very bad hash function. Use siphash24g instead. 51 return (d->dinosaur_id + d->name[0] ) * 1337 + d->name[1] * 1337; 52 } 53 54 Now you'll need to declare the functions that manipulate the hash table. 55 To do this, you put this declaration either in a header file, or inside 56 a regular module, depending on what visibility you want. 57 58 HT_PROTOTYPE(dinosaur_ht, // The name of the hashtable struct 59 dinosaur, // The name of the element struct, 60 node, // The name of HT_ENTRY member 61 dinosaur_hash, dinosaurs_equal); 62 63 Later, inside a C function, you use this macro to declare the hashtable 64 functions. 65 66 HT_GENERATE2(dinosaur_ht, dinosaur, node, dinosaur_hash, dinosaurs_equal, 67 0.6, tor_reallocarray, tor_free_); 68 69 Note the use of tor_free_, not tor_free. The 0.6 is magic. 70 71 Now you can use the hashtable! You can initialize one with 72 73 struct dinosaur_ht my_dinos = HT_INITIALIZER(); 74 75 Or create one in core with 76 77 struct dinosaur_ht *dinos = tor_malloc(sizeof(dinosaur_ht)); 78 HT_INIT(dinosaur_ht, dinos); 79 80 To the hashtable, you use the HT_FOO(dinosaur_ht, ...) macros. For 81 example, to put new_dino into dinos, you say: 82 83 HT_REPLACE(dinosaur_ht, dinos, new_dino); 84 85 If you're searching for an element, you need to use a dummy 'key' element in 86 the search. For example. 87 88 struct dinosaur dino_key; 89 dino_key.dinosaur_id = 12345; 90 dino_key.name = tor_strdup("Atrociraptor"); 91 92 struct dinosaur *found = HT_FIND(dinosaurs_ht, dinos, &dino_key); 93 94 Have fun with your hash table! 95 96 */ 97 98 #ifndef HT_H_INCLUDED_ 99 #define HT_H_INCLUDED_ 100 101 #define HT_HEAD(name, type) \ 102 struct name { \ 103 /* The hash table itself. */ \ 104 struct type **hth_table; \ 105 /* How long is the hash table? */ \ 106 unsigned hth_table_length; \ 107 /* How many elements does the table contain? */ \ 108 unsigned hth_n_entries; \ 109 /* How many elements will we allow in the table before resizing it? */ \ 110 unsigned hth_load_limit; \ 111 /* Position of hth_table_length in the primes table. */ \ 112 int hth_prime_idx; \ 113 } 114 115 #define HT_INITIALIZER() \ 116 { NULL, 0, 0, 0, -1 } 117 118 #ifdef HT_NO_CACHE_HASH_VALUES 119 #define HT_ENTRY(type) \ 120 struct { \ 121 struct type *hte_next; \ 122 } 123 #else 124 #define HT_ENTRY(type) \ 125 struct { \ 126 struct type *hte_next; \ 127 unsigned hte_hash; \ 128 } 129 #endif 130 131 /* || 0 is for -Wparentheses-equality (-Wall?) appeasement under clang */ 132 #define HT_EMPTY(head) \ 133 (((head)->hth_n_entries == 0) || 0) 134 135 /* How many elements in 'head'? */ 136 #define HT_SIZE(head) \ 137 ((head)->hth_n_entries) 138 139 /* Return memory usage for a hashtable (not counting the entries themselves) */ 140 #define HT_MEM_USAGE(head) \ 141 (sizeof(*head) + (head)->hth_table_length * sizeof(void*)) 142 143 #define HT_FIND(name, head, elm) name##_HT_FIND((head), (elm)) 144 #define HT_INSERT(name, head, elm) name##_HT_INSERT((head), (elm)) 145 #define HT_REPLACE(name, head, elm) name##_HT_REPLACE((head), (elm)) 146 #define HT_REMOVE(name, head, elm) name##_HT_REMOVE((head), (elm)) 147 #define HT_START(name, head) name##_HT_START(head) 148 #define HT_NEXT(name, head, elm) name##_HT_NEXT((head), (elm)) 149 #define HT_NEXT_RMV(name, head, elm) name##_HT_NEXT_RMV((head), (elm)) 150 #define HT_CLEAR(name, head) name##_HT_CLEAR(head) 151 #define HT_INIT(name, head) name##_HT_INIT(head) 152 #define HT_REP_IS_BAD_(name, head) name##_HT_REP_IS_BAD_(head) 153 #define HT_FOREACH_FN(name, head, fn, data) \ 154 name##_HT_FOREACH_FN((head), (fn), (data)) 155 /* Helper: */ 156 static inline unsigned 157 ht_improve_hash(unsigned h) 158 { 159 /* Aim to protect against poor hash functions by adding logic here 160 * - logic taken from java 1.4 hashtable source */ 161 h += ~(h << 9); 162 h ^= ((h >> 14) | (h << 18)); /* >>> */ 163 h += (h << 4); 164 h ^= ((h >> 10) | (h << 22)); /* >>> */ 165 return h; 166 } 167 168 #if 0 169 /** Basic string hash function, from Java standard String.hashCode(). */ 170 static inline unsigned 171 ht_string_hash(const char *s) 172 { 173 unsigned h = 0; 174 int m = 1; 175 while (*s) { 176 h += ((signed char)*s++)*m; 177 m = (m<<5)-1; /* m *= 31 */ 178 } 179 return h; 180 } 181 #endif 182 183 #if 0 184 /** Basic string hash function, from Python's str.__hash__() */ 185 static inline unsigned 186 ht_string_hash(const char *s) 187 { 188 unsigned h; 189 const unsigned char *cp = (const unsigned char *)s; 190 h = *cp << 7; 191 while (*cp) { 192 h = (1000003*h) ^ *cp++; 193 } 194 /* This conversion truncates the length of the string, but that's ok. */ 195 h ^= (unsigned)(cp-(const unsigned char*)s); 196 return h; 197 } 198 #endif 199 200 #ifndef HT_NO_CACHE_HASH_VALUES 201 #define HT_SET_HASH_(elm, field, hashfn) \ 202 do { (elm)->field.hte_hash = hashfn(elm); } while (0) 203 #define HT_SET_HASHVAL_(elm, field, val) \ 204 do { (elm)->field.hte_hash = (val); } while (0) 205 #define HT_ELT_HASH_(elm, field, hashfn) \ 206 ((elm)->field.hte_hash) 207 #else 208 #define HT_SET_HASH_(elm, field, hashfn) \ 209 ((void)0) 210 #define HT_ELT_HASH_(elm, field, hashfn) \ 211 (hashfn(elm)) 212 #define HT_SET_HASHVAL_(elm, field, val) \ 213 ((void)0) 214 #endif 215 216 #define HT_BUCKET_NUM_(head, field, elm, hashfn) \ 217 (HT_ELT_HASH_(elm,field,hashfn) % head->hth_table_length) 218 219 /* Helper: alias for the bucket containing 'elm'. */ 220 #define HT_BUCKET_(head, field, elm, hashfn) \ 221 ((head)->hth_table[HT_BUCKET_NUM_(head, field, elm, hashfn)]) 222 223 #define HT_FOREACH(x, name, head) \ 224 for ((x) = HT_START(name, head); \ 225 (x) != NULL; \ 226 (x) = HT_NEXT(name, head, x)) 227 228 #ifndef HT_NDEBUG 229 #include "lib/err/torerr.h" 230 #define HT_ASSERT_(x) raw_assert(x) 231 #else 232 #define HT_ASSERT_(x) (void)0 233 #endif 234 235 /* Macro put at the end of the end of a macro definition so that it 236 * consumes the following semicolon at file scope. Used only inside ht.h. */ 237 #define HT_EAT_SEMICOLON__ struct ht_semicolon_eater 238 239 #define HT_PROTOTYPE(name, type, field, hashfn, eqfn) \ 240 int name##_HT_GROW(struct name *ht, unsigned min_capacity); \ 241 void name##_HT_CLEAR(struct name *ht); \ 242 int name##_HT_REP_IS_BAD_(const struct name *ht); \ 243 static inline void \ 244 name##_HT_INIT(struct name *head) { \ 245 head->hth_table_length = 0; \ 246 head->hth_table = NULL; \ 247 head->hth_n_entries = 0; \ 248 head->hth_load_limit = 0; \ 249 head->hth_prime_idx = -1; \ 250 } \ 251 /* Helper: returns a pointer to the right location in the table \ 252 * 'head' to find or insert the element 'elm'. */ \ 253 static inline struct type ** \ 254 name##_HT_FIND_P_(struct name *head, struct type *elm) \ 255 { \ 256 struct type **p; \ 257 if (!head->hth_table) \ 258 return NULL; \ 259 p = &HT_BUCKET_(head, field, elm, hashfn); \ 260 while (*p) { \ 261 if (eqfn(*p, elm)) \ 262 return p; \ 263 p = &(*p)->field.hte_next; \ 264 } \ 265 return p; \ 266 } \ 267 /* Return a pointer to the element in the table 'head' matching 'elm', \ 268 * or NULL if no such element exists */ \ 269 ATTR_UNUSED static inline struct type * \ 270 name##_HT_FIND(const struct name *head, struct type *elm) \ 271 { \ 272 struct type **p; \ 273 struct name *h = (struct name *) head; \ 274 HT_SET_HASH_(elm, field, hashfn); \ 275 p = name##_HT_FIND_P_(h, elm); \ 276 return p ? *p : NULL; \ 277 } \ 278 /* Insert the element 'elm' into the table 'head'. Do not call this \ 279 * function if the table might already contain a matching element. */ \ 280 ATTR_UNUSED static inline void \ 281 name##_HT_INSERT(struct name *head, struct type *elm) \ 282 { \ 283 struct type **p; \ 284 if (!head->hth_table || head->hth_n_entries >= head->hth_load_limit) \ 285 name##_HT_GROW(head, head->hth_n_entries+1); \ 286 ++head->hth_n_entries; \ 287 HT_SET_HASH_(elm, field, hashfn); \ 288 p = &HT_BUCKET_(head, field, elm, hashfn); \ 289 elm->field.hte_next = *p; \ 290 *p = elm; \ 291 } \ 292 /* Insert the element 'elm' into the table 'head'. If there already \ 293 * a matching element in the table, replace that element and return \ 294 * it. */ \ 295 ATTR_UNUSED static inline struct type * \ 296 name##_HT_REPLACE(struct name *head, struct type *elm) \ 297 { \ 298 struct type **p, *r; \ 299 if (!head->hth_table || head->hth_n_entries >= head->hth_load_limit) \ 300 name##_HT_GROW(head, head->hth_n_entries+1); \ 301 HT_SET_HASH_(elm, field, hashfn); \ 302 p = name##_HT_FIND_P_(head, elm); \ 303 HT_ASSERT_(p != NULL); /* this holds because we called HT_GROW */ \ 304 r = *p; \ 305 *p = elm; \ 306 if (r && (r!=elm)) { \ 307 elm->field.hte_next = r->field.hte_next; \ 308 r->field.hte_next = NULL; \ 309 return r; \ 310 } else { \ 311 ++head->hth_n_entries; \ 312 return NULL; \ 313 } \ 314 } \ 315 /* Remove any element matching 'elm' from the table 'head'. If such \ 316 * an element is found, return it; otherwise return NULL. */ \ 317 ATTR_UNUSED static inline struct type * \ 318 name##_HT_REMOVE(struct name *head, struct type *elm) \ 319 { \ 320 struct type **p, *r; \ 321 HT_SET_HASH_(elm, field, hashfn); \ 322 p = name##_HT_FIND_P_(head,elm); \ 323 if (!p || !*p) \ 324 return NULL; \ 325 r = *p; \ 326 *p = r->field.hte_next; \ 327 r->field.hte_next = NULL; \ 328 --head->hth_n_entries; \ 329 return r; \ 330 } \ 331 /* Invoke the function 'fn' on every element of the table 'head', \ 332 * using 'data' as its second argument. If the function returns \ 333 * nonzero, remove the most recently examined element before invoking \ 334 * the function again. */ \ 335 ATTR_UNUSED static inline void \ 336 name##_HT_FOREACH_FN(struct name *head, \ 337 int (*fn)(struct type *, void *), \ 338 void *data) \ 339 { \ 340 unsigned idx; \ 341 struct type **p, **nextp, *next; \ 342 if (!head->hth_table) \ 343 return; \ 344 for (idx=0; idx < head->hth_table_length; ++idx) { \ 345 p = &head->hth_table[idx]; \ 346 while (*p) { \ 347 nextp = &(*p)->field.hte_next; \ 348 next = *nextp; \ 349 if (fn(*p, data)) { \ 350 --head->hth_n_entries; \ 351 *p = next; \ 352 } else { \ 353 p = nextp; \ 354 } \ 355 } \ 356 } \ 357 } \ 358 /* Return a pointer to the first element in the table 'head', under \ 359 * an arbitrary order. This order is stable under remove operations, \ 360 * but not under others. If the table is empty, return NULL. */ \ 361 ATTR_UNUSED static inline struct type ** \ 362 name##_HT_START(struct name *head) \ 363 { \ 364 unsigned b = 0; \ 365 while (b < head->hth_table_length) { \ 366 if (head->hth_table[b]) { \ 367 HT_ASSERT_(b == \ 368 HT_BUCKET_NUM_(head,field,head->hth_table[b],hashfn)); \ 369 return &head->hth_table[b]; \ 370 } \ 371 ++b; \ 372 } \ 373 return NULL; \ 374 } \ 375 /* Return the next element in 'head' after 'elm', under the arbitrary \ 376 * order used by HT_START. If there are no more elements, return \ 377 * NULL. If 'elm' is to be removed from the table, you must call \ 378 * this function for the next value before you remove it, or use \ 379 * HT_NEXT_RMV instead. \ 380 */ \ 381 ATTR_UNUSED static inline struct type ** \ 382 name##_HT_NEXT(struct name *head, struct type **elm) \ 383 { \ 384 if ((*elm)->field.hte_next) { \ 385 HT_ASSERT_(HT_BUCKET_NUM_(head,field,*elm,hashfn) == \ 386 HT_BUCKET_NUM_(head,field,(*elm)->field.hte_next,hashfn)); \ 387 return &(*elm)->field.hte_next; \ 388 } else { \ 389 unsigned b = HT_BUCKET_NUM_(head,field,*elm,hashfn)+1; \ 390 while (b < head->hth_table_length) { \ 391 if (head->hth_table[b]) { \ 392 HT_ASSERT_(b == \ 393 HT_BUCKET_NUM_(head,field,head->hth_table[b],hashfn)); \ 394 return &head->hth_table[b]; \ 395 } \ 396 ++b; \ 397 } \ 398 return NULL; \ 399 } \ 400 } \ 401 /* As HT_NEXT, but also remove the current element 'elm' from the \ 402 * table. */ \ 403 ATTR_UNUSED static inline struct type ** \ 404 name##_HT_NEXT_RMV(struct name *head, struct type **elm) \ 405 { \ 406 unsigned h = HT_ELT_HASH_(*elm, field, hashfn); \ 407 *elm = (*elm)->field.hte_next; \ 408 --head->hth_n_entries; \ 409 if (*elm) { \ 410 return elm; \ 411 } else { \ 412 unsigned b = (h % head->hth_table_length)+1; \ 413 while (b < head->hth_table_length) { \ 414 if (head->hth_table[b]) \ 415 return &head->hth_table[b]; \ 416 ++b; \ 417 } \ 418 return NULL; \ 419 } \ 420 } \ 421 HT_EAT_SEMICOLON__ 422 423 #define HT_GENERATE2(name, type, field, hashfn, eqfn, load, reallocarrayfn, \ 424 freefn) \ 425 /* Primes that aren't too far from powers of two. We stop at */ \ 426 /* P=402653189 because P*sizeof(void*) is less than SSIZE_MAX */ \ 427 /* even on a 32-bit platform. */ \ 428 static unsigned name##_PRIMES[] = { \ 429 53, 97, 193, 389, \ 430 769, 1543, 3079, 6151, \ 431 12289, 24593, 49157, 98317, \ 432 196613, 393241, 786433, 1572869, \ 433 3145739, 6291469, 12582917, 25165843, \ 434 50331653, 100663319, 201326611, 402653189 \ 435 }; \ 436 static unsigned name##_N_PRIMES = \ 437 (unsigned)(sizeof(name##_PRIMES)/sizeof(name##_PRIMES[0])); \ 438 /* Expand the internal table of 'head' until it is large enough to \ 439 * hold 'size' elements. Return 0 on success, -1 on allocation \ 440 * failure. */ \ 441 int \ 442 name##_HT_GROW(struct name *head, unsigned size) \ 443 { \ 444 unsigned new_len, new_load_limit; \ 445 int prime_idx; \ 446 struct type **new_table; \ 447 if (head->hth_prime_idx == (int)name##_N_PRIMES - 1) \ 448 return 0; \ 449 if (head->hth_load_limit > size) \ 450 return 0; \ 451 prime_idx = head->hth_prime_idx; \ 452 do { \ 453 new_len = name##_PRIMES[++prime_idx]; \ 454 new_load_limit = (unsigned)(load*new_len); \ 455 } while (new_load_limit <= size && \ 456 prime_idx < (int)name##_N_PRIMES); \ 457 if ((new_table = reallocarrayfn(NULL, new_len, sizeof(struct type*)))) { \ 458 unsigned b; \ 459 memset(new_table, 0, new_len*sizeof(struct type*)); \ 460 for (b = 0; b < head->hth_table_length; ++b) { \ 461 struct type *elm, *next; \ 462 unsigned b2; \ 463 elm = head->hth_table[b]; \ 464 while (elm) { \ 465 next = elm->field.hte_next; \ 466 b2 = HT_ELT_HASH_(elm, field, hashfn) % new_len; \ 467 elm->field.hte_next = new_table[b2]; \ 468 new_table[b2] = elm; \ 469 elm = next; \ 470 } \ 471 } \ 472 if (head->hth_table) \ 473 freefn(head->hth_table); \ 474 head->hth_table = new_table; \ 475 } else { \ 476 unsigned b, b2; \ 477 new_table = reallocarrayfn(head->hth_table, new_len, sizeof(struct type*)); \ 478 if (!new_table) return -1; \ 479 memset(new_table + head->hth_table_length, 0, \ 480 (new_len - head->hth_table_length)*sizeof(struct type*)); \ 481 for (b=0; b < head->hth_table_length; ++b) { \ 482 struct type *e, **pE; \ 483 for (pE = &new_table[b], e = *pE; e != NULL; e = *pE) { \ 484 b2 = HT_ELT_HASH_(e, field, hashfn) % new_len; \ 485 if (b2 == b) { \ 486 pE = &e->field.hte_next; \ 487 } else { \ 488 *pE = e->field.hte_next; \ 489 e->field.hte_next = new_table[b2]; \ 490 new_table[b2] = e; \ 491 } \ 492 } \ 493 } \ 494 head->hth_table = new_table; \ 495 } \ 496 head->hth_table_length = new_len; \ 497 head->hth_prime_idx = prime_idx; \ 498 head->hth_load_limit = new_load_limit; \ 499 return 0; \ 500 } \ 501 /* Free all storage held by 'head'. Does not free 'head' itself, or \ 502 * individual elements. */ \ 503 void \ 504 name##_HT_CLEAR(struct name *head) \ 505 { \ 506 if (head->hth_table) \ 507 freefn(head->hth_table); \ 508 head->hth_table_length = 0; \ 509 name##_HT_INIT(head); \ 510 } \ 511 /* Debugging helper: return false iff the representation of 'head' is \ 512 * internally consistent. */ \ 513 int \ 514 name##_HT_REP_IS_BAD_(const struct name *head) \ 515 { \ 516 unsigned n, i; \ 517 struct type *elm; \ 518 if (!head->hth_table_length) { \ 519 if (!head->hth_table && !head->hth_n_entries && \ 520 !head->hth_load_limit && head->hth_prime_idx == -1) \ 521 return 0; \ 522 else \ 523 return 1; \ 524 } \ 525 if (!head->hth_table || head->hth_prime_idx < 0 || \ 526 !head->hth_load_limit) \ 527 return 2; \ 528 if (head->hth_n_entries > head->hth_load_limit) \ 529 return 3; \ 530 if (head->hth_table_length != name##_PRIMES[head->hth_prime_idx]) \ 531 return 4; \ 532 if (head->hth_load_limit != (unsigned)(load*head->hth_table_length)) \ 533 return 5; \ 534 for (n = i = 0; i < head->hth_table_length; ++i) { \ 535 for (elm = head->hth_table[i]; elm; elm = elm->field.hte_next) { \ 536 if (HT_ELT_HASH_(elm, field, hashfn) != hashfn(elm)) \ 537 return 1000 + i; \ 538 if (HT_BUCKET_NUM_(head,field,elm,hashfn) != i) \ 539 return 10000 + i; \ 540 ++n; \ 541 } \ 542 } \ 543 if (n != head->hth_n_entries) \ 544 return 6; \ 545 return 0; \ 546 } \ 547 HT_EAT_SEMICOLON__ 548 549 #define HT_GENERATE(name, type, field, hashfn, eqfn, load, mallocfn, \ 550 reallocfn, freefn) \ 551 static void * \ 552 name##_reallocarray(void *arg, size_t a, size_t b) \ 553 { \ 554 if ((b) && (a) > SIZE_MAX / (b)) \ 555 return NULL; \ 556 if (arg) \ 557 return reallocfn((arg),(a)*(b)); \ 558 else \ 559 return mallocfn((a)*(b)); \ 560 } \ 561 HT_GENERATE2(name, type, field, hashfn, eqfn, load, \ 562 name##_reallocarray, freefn) 563 564 /** Implements an over-optimized "find and insert if absent" block; 565 * not meant for direct usage by typical code, or usage outside the critical 566 * path.*/ 567 #define HT_FIND_OR_INSERT_(name, field, hashfn, head, eltype, elm, var, y, n) \ 568 { \ 569 struct name *var##_head_ = head; \ 570 struct eltype **var; \ 571 if (!var##_head_->hth_table || \ 572 var##_head_->hth_n_entries >= var##_head_->hth_load_limit) \ 573 name##_HT_GROW(var##_head_, var##_head_->hth_n_entries+1); \ 574 HT_SET_HASH_((elm), field, hashfn); \ 575 var = name##_HT_FIND_P_(var##_head_, (elm)); \ 576 HT_ASSERT_(var); /* Holds because we called HT_GROW */ \ 577 if (*var) { \ 578 y; \ 579 } else { \ 580 n; \ 581 } \ 582 } 583 #define HT_FOI_INSERT_(field, head, elm, newent, var) \ 584 { \ 585 HT_SET_HASHVAL_(newent, field, (elm)->field.hte_hash); \ 586 newent->field.hte_next = NULL; \ 587 *var = newent; \ 588 ++((head)->hth_n_entries); \ 589 } 590 591 /* 592 * Copyright 2005, Nick Mathewson. Implementation logic is adapted from code 593 * by Christopher Clark, retrofit to allow drop-in memory management, and to 594 * use the same interface as Niels Provos's tree.h. This is probably still 595 * a derived work, so the original license below still applies. 596 * 597 * Copyright (c) 2002, Christopher Clark 598 * All rights reserved. 599 * 600 * Redistribution and use in source and binary forms, with or without 601 * modification, are permitted provided that the following conditions 602 * are met: 603 * 604 * * Redistributions of source code must retain the above copyright 605 * notice, this list of conditions and the following disclaimer. 606 * 607 * * Redistributions in binary form must reproduce the above copyright 608 * notice, this list of conditions and the following disclaimer in the 609 * documentation and/or other materials provided with the distribution. 610 * 611 * * Neither the name of the original author; nor the names of any contributors 612 * may be used to endorse or promote products derived from this software 613 * without specific prior written permission. 614 * 615 * 616 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 617 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 618 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 619 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 620 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 621 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 622 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 623 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 624 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 625 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 626 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 627 */ 628 629 #endif