1275970Scy/* Copyright 2002 Christopher Clark */ 2275970Scy/* Copyright 2005-2012 Nick Mathewson */ 3275970Scy/* Copyright 2009-2012 Niels Provos and Nick Mathewson */ 4275970Scy/* See license at end. */ 5275970Scy 6275970Scy/* Based on ideas by Christopher Clark and interfaces from Niels Provos. */ 7275970Scy 8275970Scy#ifndef HT_INTERNAL_H_INCLUDED_ 9275970Scy#define HT_INTERNAL_H_INCLUDED_ 10275970Scy 11275970Scy#define HT_HEAD(name, type) \ 12275970Scy struct name { \ 13275970Scy /* The hash table itself. */ \ 14275970Scy struct type **hth_table; \ 15275970Scy /* How long is the hash table? */ \ 16275970Scy unsigned hth_table_length; \ 17275970Scy /* How many elements does the table contain? */ \ 18275970Scy unsigned hth_n_entries; \ 19275970Scy /* How many elements will we allow in the table before resizing it? */ \ 20275970Scy unsigned hth_load_limit; \ 21275970Scy /* Position of hth_table_length in the primes table. */ \ 22275970Scy int hth_prime_idx; \ 23275970Scy } 24275970Scy 25275970Scy#define HT_INITIALIZER() \ 26275970Scy { NULL, 0, 0, 0, -1 } 27275970Scy 28275970Scy#ifdef HT_NO_CACHE_HASH_VALUES 29275970Scy#define HT_ENTRY(type) \ 30275970Scy struct { \ 31275970Scy struct type *hte_next; \ 32275970Scy } 33275970Scy#else 34275970Scy#define HT_ENTRY(type) \ 35275970Scy struct { \ 36275970Scy struct type *hte_next; \ 37275970Scy unsigned hte_hash; \ 38275970Scy } 39275970Scy#endif 40275970Scy 41275970Scy#define HT_EMPTY(head) \ 42275970Scy ((head)->hth_n_entries == 0) 43275970Scy 44275970Scy/* How many elements in 'head'? */ 45275970Scy#define HT_SIZE(head) \ 46275970Scy ((head)->hth_n_entries) 47275970Scy 48275970Scy/* Return memory usage for a hashtable (not counting the entries themselves) */ 49275970Scy#define HT_MEM_USAGE(head) \ 50275970Scy (sizeof(*head) + (head)->hth_table_length * sizeof(void*)) 51275970Scy 52275970Scy#define HT_FIND(name, head, elm) name##_HT_FIND((head), (elm)) 53275970Scy#define HT_INSERT(name, head, elm) name##_HT_INSERT((head), (elm)) 54275970Scy#define HT_REPLACE(name, head, elm) name##_HT_REPLACE((head), (elm)) 55275970Scy#define HT_REMOVE(name, head, elm) name##_HT_REMOVE((head), (elm)) 56275970Scy#define HT_START(name, head) name##_HT_START(head) 57275970Scy#define HT_NEXT(name, head, elm) name##_HT_NEXT((head), (elm)) 58275970Scy#define HT_NEXT_RMV(name, head, elm) name##_HT_NEXT_RMV((head), (elm)) 59275970Scy#define HT_CLEAR(name, head) name##_HT_CLEAR(head) 60275970Scy#define HT_INIT(name, head) name##_HT_INIT(head) 61275970Scy/* Helper: */ 62275970Scystatic inline unsigned 63275970Scyht_improve_hash_(unsigned h) 64275970Scy{ 65275970Scy /* Aim to protect against poor hash functions by adding logic here 66275970Scy * - logic taken from java 1.4 hashtable source */ 67275970Scy h += ~(h << 9); 68275970Scy h ^= ((h >> 14) | (h << 18)); /* >>> */ 69275970Scy h += (h << 4); 70275970Scy h ^= ((h >> 10) | (h << 22)); /* >>> */ 71275970Scy return h; 72275970Scy} 73275970Scy 74275970Scy#if 0 75275970Scy/** Basic string hash function, from Java standard String.hashCode(). */ 76275970Scystatic inline unsigned 77275970Scyht_string_hash_(const char *s) 78275970Scy{ 79275970Scy unsigned h = 0; 80275970Scy int m = 1; 81275970Scy while (*s) { 82275970Scy h += ((signed char)*s++)*m; 83275970Scy m = (m<<5)-1; /* m *= 31 */ 84275970Scy } 85275970Scy return h; 86275970Scy} 87275970Scy#endif 88275970Scy 89275970Scy/** Basic string hash function, from Python's str.__hash__() */ 90275970Scystatic inline unsigned 91275970Scyht_string_hash_(const char *s) 92275970Scy{ 93275970Scy unsigned h; 94275970Scy const unsigned char *cp = (const unsigned char *)s; 95275970Scy h = *cp << 7; 96275970Scy while (*cp) { 97275970Scy h = (1000003*h) ^ *cp++; 98275970Scy } 99275970Scy /* This conversion truncates the length of the string, but that's ok. */ 100275970Scy h ^= (unsigned)(cp-(const unsigned char*)s); 101275970Scy return h; 102275970Scy} 103275970Scy 104275970Scy#ifndef HT_NO_CACHE_HASH_VALUES 105275970Scy#define HT_SET_HASH_(elm, field, hashfn) \ 106275970Scy do { (elm)->field.hte_hash = hashfn(elm); } while (0) 107275970Scy#define HT_SET_HASHVAL_(elm, field, val) \ 108275970Scy do { (elm)->field.hte_hash = (val); } while (0) 109275970Scy#define HT_ELT_HASH_(elm, field, hashfn) \ 110275970Scy ((elm)->field.hte_hash) 111275970Scy#else 112275970Scy#define HT_SET_HASH_(elm, field, hashfn) \ 113275970Scy ((void)0) 114275970Scy#define HT_ELT_HASH_(elm, field, hashfn) \ 115275970Scy (hashfn(elm)) 116275970Scy#define HT_SET_HASHVAL_(elm, field, val) \ 117275970Scy ((void)0) 118275970Scy#endif 119275970Scy 120275970Scy/* Helper: alias for the bucket containing 'elm'. */ 121275970Scy#define HT_BUCKET_(head, field, elm, hashfn) \ 122275970Scy ((head)->hth_table[HT_ELT_HASH_(elm,field,hashfn) % head->hth_table_length]) 123275970Scy 124275970Scy#define HT_FOREACH(x, name, head) \ 125275970Scy for ((x) = HT_START(name, head); \ 126275970Scy (x) != NULL; \ 127275970Scy (x) = HT_NEXT(name, head, x)) 128275970Scy 129275970Scy#define HT_PROTOTYPE(name, type, field, hashfn, eqfn) \ 130275970Scy int name##_HT_GROW(struct name *ht, unsigned min_capacity); \ 131275970Scy void name##_HT_CLEAR(struct name *ht); \ 132275970Scy int name##_HT_REP_IS_BAD_(const struct name *ht); \ 133275970Scy static inline void \ 134275970Scy name##_HT_INIT(struct name *head) { \ 135275970Scy head->hth_table_length = 0; \ 136275970Scy head->hth_table = NULL; \ 137275970Scy head->hth_n_entries = 0; \ 138275970Scy head->hth_load_limit = 0; \ 139275970Scy head->hth_prime_idx = -1; \ 140275970Scy } \ 141275970Scy /* Helper: returns a pointer to the right location in the table \ 142275970Scy * 'head' to find or insert the element 'elm'. */ \ 143275970Scy static inline struct type ** \ 144275970Scy name##_HT_FIND_P_(struct name *head, struct type *elm) \ 145275970Scy { \ 146275970Scy struct type **p; \ 147275970Scy if (!head->hth_table) \ 148275970Scy return NULL; \ 149275970Scy p = &HT_BUCKET_(head, field, elm, hashfn); \ 150275970Scy while (*p) { \ 151275970Scy if (eqfn(*p, elm)) \ 152275970Scy return p; \ 153275970Scy p = &(*p)->field.hte_next; \ 154275970Scy } \ 155275970Scy return p; \ 156275970Scy } \ 157275970Scy /* Return a pointer to the element in the table 'head' matching 'elm', \ 158275970Scy * or NULL if no such element exists */ \ 159275970Scy static inline struct type * \ 160275970Scy name##_HT_FIND(const struct name *head, struct type *elm) \ 161275970Scy { \ 162275970Scy struct type **p; \ 163275970Scy struct name *h = (struct name *) head; \ 164275970Scy HT_SET_HASH_(elm, field, hashfn); \ 165275970Scy p = name##_HT_FIND_P_(h, elm); \ 166275970Scy return p ? *p : NULL; \ 167275970Scy } \ 168275970Scy /* Insert the element 'elm' into the table 'head'. Do not call this \ 169275970Scy * function if the table might already contain a matching element. */ \ 170275970Scy static inline void \ 171275970Scy name##_HT_INSERT(struct name *head, struct type *elm) \ 172275970Scy { \ 173275970Scy struct type **p; \ 174275970Scy if (!head->hth_table || head->hth_n_entries >= head->hth_load_limit) \ 175275970Scy name##_HT_GROW(head, head->hth_n_entries+1); \ 176275970Scy ++head->hth_n_entries; \ 177275970Scy HT_SET_HASH_(elm, field, hashfn); \ 178275970Scy p = &HT_BUCKET_(head, field, elm, hashfn); \ 179275970Scy elm->field.hte_next = *p; \ 180275970Scy *p = elm; \ 181275970Scy } \ 182275970Scy /* Insert the element 'elm' into the table 'head'. If there already \ 183275970Scy * a matching element in the table, replace that element and return \ 184275970Scy * it. */ \ 185275970Scy static inline struct type * \ 186275970Scy name##_HT_REPLACE(struct name *head, struct type *elm) \ 187275970Scy { \ 188275970Scy struct type **p, *r; \ 189275970Scy if (!head->hth_table || head->hth_n_entries >= head->hth_load_limit) \ 190275970Scy name##_HT_GROW(head, head->hth_n_entries+1); \ 191275970Scy HT_SET_HASH_(elm, field, hashfn); \ 192275970Scy p = name##_HT_FIND_P_(head, elm); \ 193275970Scy r = *p; \ 194275970Scy *p = elm; \ 195275970Scy if (r && (r!=elm)) { \ 196275970Scy elm->field.hte_next = r->field.hte_next; \ 197275970Scy r->field.hte_next = NULL; \ 198275970Scy return r; \ 199275970Scy } else { \ 200275970Scy ++head->hth_n_entries; \ 201275970Scy return NULL; \ 202275970Scy } \ 203275970Scy } \ 204275970Scy /* Remove any element matching 'elm' from the table 'head'. If such \ 205275970Scy * an element is found, return it; otherwise return NULL. */ \ 206275970Scy static inline struct type * \ 207275970Scy name##_HT_REMOVE(struct name *head, struct type *elm) \ 208275970Scy { \ 209275970Scy struct type **p, *r; \ 210275970Scy HT_SET_HASH_(elm, field, hashfn); \ 211275970Scy p = name##_HT_FIND_P_(head,elm); \ 212275970Scy if (!p || !*p) \ 213275970Scy return NULL; \ 214275970Scy r = *p; \ 215275970Scy *p = r->field.hte_next; \ 216275970Scy r->field.hte_next = NULL; \ 217275970Scy --head->hth_n_entries; \ 218275970Scy return r; \ 219275970Scy } \ 220275970Scy /* Invoke the function 'fn' on every element of the table 'head', \ 221275970Scy * using 'data' as its second argument. If the function returns \ 222275970Scy * nonzero, remove the most recently examined element before invoking \ 223275970Scy * the function again. */ \ 224275970Scy static inline void \ 225275970Scy name##_HT_FOREACH_FN(struct name *head, \ 226275970Scy int (*fn)(struct type *, void *), \ 227275970Scy void *data) \ 228275970Scy { \ 229275970Scy unsigned idx; \ 230275970Scy struct type **p, **nextp, *next; \ 231275970Scy if (!head->hth_table) \ 232275970Scy return; \ 233275970Scy for (idx=0; idx < head->hth_table_length; ++idx) { \ 234275970Scy p = &head->hth_table[idx]; \ 235275970Scy while (*p) { \ 236275970Scy nextp = &(*p)->field.hte_next; \ 237275970Scy next = *nextp; \ 238275970Scy if (fn(*p, data)) { \ 239275970Scy --head->hth_n_entries; \ 240275970Scy *p = next; \ 241275970Scy } else { \ 242275970Scy p = nextp; \ 243275970Scy } \ 244275970Scy } \ 245275970Scy } \ 246275970Scy } \ 247275970Scy /* Return a pointer to the first element in the table 'head', under \ 248275970Scy * an arbitrary order. This order is stable under remove operations, \ 249275970Scy * but not under others. If the table is empty, return NULL. */ \ 250275970Scy static inline struct type ** \ 251275970Scy name##_HT_START(struct name *head) \ 252275970Scy { \ 253275970Scy unsigned b = 0; \ 254275970Scy while (b < head->hth_table_length) { \ 255275970Scy if (head->hth_table[b]) \ 256275970Scy return &head->hth_table[b]; \ 257275970Scy ++b; \ 258275970Scy } \ 259275970Scy return NULL; \ 260275970Scy } \ 261275970Scy /* Return the next element in 'head' after 'elm', under the arbitrary \ 262275970Scy * order used by HT_START. If there are no more elements, return \ 263275970Scy * NULL. If 'elm' is to be removed from the table, you must call \ 264275970Scy * this function for the next value before you remove it. \ 265275970Scy */ \ 266275970Scy static inline struct type ** \ 267275970Scy name##_HT_NEXT(struct name *head, struct type **elm) \ 268275970Scy { \ 269275970Scy if ((*elm)->field.hte_next) { \ 270275970Scy return &(*elm)->field.hte_next; \ 271275970Scy } else { \ 272275970Scy unsigned b = (HT_ELT_HASH_(*elm, field, hashfn) % head->hth_table_length)+1; \ 273275970Scy while (b < head->hth_table_length) { \ 274275970Scy if (head->hth_table[b]) \ 275275970Scy return &head->hth_table[b]; \ 276275970Scy ++b; \ 277275970Scy } \ 278275970Scy return NULL; \ 279275970Scy } \ 280275970Scy } \ 281275970Scy static inline struct type ** \ 282275970Scy name##_HT_NEXT_RMV(struct name *head, struct type **elm) \ 283275970Scy { \ 284275970Scy unsigned h = HT_ELT_HASH_(*elm, field, hashfn); \ 285275970Scy *elm = (*elm)->field.hte_next; \ 286275970Scy --head->hth_n_entries; \ 287275970Scy if (*elm) { \ 288275970Scy return elm; \ 289275970Scy } else { \ 290275970Scy unsigned b = (h % head->hth_table_length)+1; \ 291275970Scy while (b < head->hth_table_length) { \ 292275970Scy if (head->hth_table[b]) \ 293275970Scy return &head->hth_table[b]; \ 294275970Scy ++b; \ 295275970Scy } \ 296275970Scy return NULL; \ 297275970Scy } \ 298275970Scy } 299275970Scy 300275970Scy#define HT_GENERATE(name, type, field, hashfn, eqfn, load, mallocfn, \ 301275970Scy reallocfn, freefn) \ 302275970Scy static unsigned name##_PRIMES[] = { \ 303275970Scy 53, 97, 193, 389, \ 304275970Scy 769, 1543, 3079, 6151, \ 305275970Scy 12289, 24593, 49157, 98317, \ 306275970Scy 196613, 393241, 786433, 1572869, \ 307275970Scy 3145739, 6291469, 12582917, 25165843, \ 308275970Scy 50331653, 100663319, 201326611, 402653189, \ 309275970Scy 805306457, 1610612741 \ 310275970Scy }; \ 311275970Scy static unsigned name##_N_PRIMES = \ 312275970Scy (unsigned)(sizeof(name##_PRIMES)/sizeof(name##_PRIMES[0])); \ 313275970Scy /* Expand the internal table of 'head' until it is large enough to \ 314275970Scy * hold 'size' elements. Return 0 on success, -1 on allocation \ 315275970Scy * failure. */ \ 316275970Scy int \ 317275970Scy name##_HT_GROW(struct name *head, unsigned size) \ 318275970Scy { \ 319275970Scy unsigned new_len, new_load_limit; \ 320275970Scy int prime_idx; \ 321275970Scy struct type **new_table; \ 322275970Scy if (head->hth_prime_idx == (int)name##_N_PRIMES - 1) \ 323275970Scy return 0; \ 324275970Scy if (head->hth_load_limit > size) \ 325275970Scy return 0; \ 326275970Scy prime_idx = head->hth_prime_idx; \ 327275970Scy do { \ 328275970Scy new_len = name##_PRIMES[++prime_idx]; \ 329275970Scy new_load_limit = (unsigned)(load*new_len); \ 330275970Scy } while (new_load_limit <= size && \ 331275970Scy prime_idx < (int)name##_N_PRIMES); \ 332275970Scy if ((new_table = mallocfn(new_len*sizeof(struct type*)))) { \ 333275970Scy unsigned b; \ 334275970Scy memset(new_table, 0, new_len*sizeof(struct type*)); \ 335275970Scy for (b = 0; b < head->hth_table_length; ++b) { \ 336275970Scy struct type *elm, *next; \ 337275970Scy unsigned b2; \ 338275970Scy elm = head->hth_table[b]; \ 339275970Scy while (elm) { \ 340275970Scy next = elm->field.hte_next; \ 341275970Scy b2 = HT_ELT_HASH_(elm, field, hashfn) % new_len; \ 342275970Scy elm->field.hte_next = new_table[b2]; \ 343275970Scy new_table[b2] = elm; \ 344275970Scy elm = next; \ 345275970Scy } \ 346275970Scy } \ 347275970Scy if (head->hth_table) \ 348275970Scy freefn(head->hth_table); \ 349275970Scy head->hth_table = new_table; \ 350275970Scy } else { \ 351275970Scy unsigned b, b2; \ 352275970Scy new_table = reallocfn(head->hth_table, new_len*sizeof(struct type*)); \ 353275970Scy if (!new_table) return -1; \ 354275970Scy memset(new_table + head->hth_table_length, 0, \ 355275970Scy (new_len - head->hth_table_length)*sizeof(struct type*)); \ 356275970Scy for (b=0; b < head->hth_table_length; ++b) { \ 357275970Scy struct type *e, **pE; \ 358275970Scy for (pE = &new_table[b], e = *pE; e != NULL; e = *pE) { \ 359275970Scy b2 = HT_ELT_HASH_(e, field, hashfn) % new_len; \ 360275970Scy if (b2 == b) { \ 361275970Scy pE = &e->field.hte_next; \ 362275970Scy } else { \ 363275970Scy *pE = e->field.hte_next; \ 364275970Scy e->field.hte_next = new_table[b2]; \ 365275970Scy new_table[b2] = e; \ 366275970Scy } \ 367275970Scy } \ 368275970Scy } \ 369275970Scy head->hth_table = new_table; \ 370275970Scy } \ 371275970Scy head->hth_table_length = new_len; \ 372275970Scy head->hth_prime_idx = prime_idx; \ 373275970Scy head->hth_load_limit = new_load_limit; \ 374275970Scy return 0; \ 375275970Scy } \ 376275970Scy /* Free all storage held by 'head'. Does not free 'head' itself, or \ 377275970Scy * individual elements. */ \ 378275970Scy void \ 379275970Scy name##_HT_CLEAR(struct name *head) \ 380275970Scy { \ 381275970Scy if (head->hth_table) \ 382275970Scy freefn(head->hth_table); \ 383275970Scy name##_HT_INIT(head); \ 384275970Scy } \ 385275970Scy /* Debugging helper: return false iff the representation of 'head' is \ 386275970Scy * internally consistent. */ \ 387275970Scy int \ 388275970Scy name##_HT_REP_IS_BAD_(const struct name *head) \ 389275970Scy { \ 390275970Scy unsigned n, i; \ 391275970Scy struct type *elm; \ 392275970Scy if (!head->hth_table_length) { \ 393275970Scy if (!head->hth_table && !head->hth_n_entries && \ 394275970Scy !head->hth_load_limit && head->hth_prime_idx == -1) \ 395275970Scy return 0; \ 396275970Scy else \ 397275970Scy return 1; \ 398275970Scy } \ 399275970Scy if (!head->hth_table || head->hth_prime_idx < 0 || \ 400275970Scy !head->hth_load_limit) \ 401275970Scy return 2; \ 402275970Scy if (head->hth_n_entries > head->hth_load_limit) \ 403275970Scy return 3; \ 404275970Scy if (head->hth_table_length != name##_PRIMES[head->hth_prime_idx]) \ 405275970Scy return 4; \ 406275970Scy if (head->hth_load_limit != (unsigned)(load*head->hth_table_length)) \ 407275970Scy return 5; \ 408275970Scy for (n = i = 0; i < head->hth_table_length; ++i) { \ 409275970Scy for (elm = head->hth_table[i]; elm; elm = elm->field.hte_next) { \ 410275970Scy if (HT_ELT_HASH_(elm, field, hashfn) != hashfn(elm)) \ 411275970Scy return 1000 + i; \ 412275970Scy if ((HT_ELT_HASH_(elm, field, hashfn) % head->hth_table_length) != i) \ 413275970Scy return 10000 + i; \ 414275970Scy ++n; \ 415275970Scy } \ 416275970Scy } \ 417275970Scy if (n != head->hth_n_entries) \ 418275970Scy return 6; \ 419275970Scy return 0; \ 420275970Scy } 421275970Scy 422275970Scy/** Implements an over-optimized "find and insert if absent" block; 423275970Scy * not meant for direct usage by typical code, or usage outside the critical 424275970Scy * path.*/ 425275970Scy#define HT_FIND_OR_INSERT_(name, field, hashfn, head, eltype, elm, var, y, n) \ 426275970Scy { \ 427275970Scy struct name *var##_head_ = head; \ 428275970Scy struct eltype **var; \ 429275970Scy if (!var##_head_->hth_table || \ 430275970Scy var##_head_->hth_n_entries >= var##_head_->hth_load_limit) \ 431275970Scy name##_HT_GROW(var##_head_, var##_head_->hth_n_entries+1); \ 432275970Scy HT_SET_HASH_((elm), field, hashfn); \ 433275970Scy var = name##_HT_FIND_P_(var##_head_, (elm)); \ 434275970Scy if (*var) { \ 435275970Scy y; \ 436275970Scy } else { \ 437275970Scy n; \ 438275970Scy } \ 439275970Scy } 440275970Scy#define HT_FOI_INSERT_(field, head, elm, newent, var) \ 441275970Scy { \ 442275970Scy HT_SET_HASHVAL_(newent, field, (elm)->field.hte_hash); \ 443275970Scy newent->field.hte_next = NULL; \ 444275970Scy *var = newent; \ 445275970Scy ++((head)->hth_n_entries); \ 446275970Scy } 447275970Scy 448275970Scy/* 449275970Scy * Copyright 2005, Nick Mathewson. Implementation logic is adapted from code 450275970Scy * by Christopher Clark, retrofit to allow drop-in memory management, and to 451275970Scy * use the same interface as Niels Provos's tree.h. This is probably still 452275970Scy * a derived work, so the original license below still applies. 453275970Scy * 454275970Scy * Copyright (c) 2002, Christopher Clark 455275970Scy * All rights reserved. 456275970Scy * 457275970Scy * Redistribution and use in source and binary forms, with or without 458275970Scy * modification, are permitted provided that the following conditions 459275970Scy * are met: 460275970Scy * 461275970Scy * * Redistributions of source code must retain the above copyright 462275970Scy * notice, this list of conditions and the following disclaimer. 463275970Scy * 464275970Scy * * Redistributions in binary form must reproduce the above copyright 465275970Scy * notice, this list of conditions and the following disclaimer in the 466275970Scy * documentation and/or other materials provided with the distribution. 467275970Scy * 468275970Scy * * Neither the name of the original author; nor the names of any contributors 469275970Scy * may be used to endorse or promote products derived from this software 470275970Scy * without specific prior written permission. 471275970Scy * 472275970Scy * 473275970Scy * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 474275970Scy * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 475275970Scy * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 476275970Scy * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 477275970Scy * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 478275970Scy * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 479275970Scy * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 480275970Scy * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 481275970Scy * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 482275970Scy * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 483275970Scy * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 484275970Scy*/ 485275970Scy 486275970Scy#endif 487275970Scy 488