contrib/ntp/sntp/libevent/ht-internal.h

   1 /* Copyright 2002 Christopher Clark */
   2 /* Copyright 2005-2012 Nick Mathewson */
   3 /* Copyright 2009-2012 Niels Provos and Nick Mathewson */
   4 /* See license at end. */
   5
   6 /* Based on ideas by Christopher Clark and interfaces from Niels Provos. */
   7
   8 #ifndef HT_INTERNAL_H_INCLUDED_
   9 #define HT_INTERNAL_H_INCLUDED_
  10
  11 #define HT_HEAD(name, type)                                             \
  12   struct name {                                                         \
  13     /* The hash table itself. */                                        \
  14     struct type **hth_table;                                            \
  15     /* How long is the hash table? */                                   \
  16     unsigned hth_table_length;                                          \
  17     /* How many elements does the table contain? */                     \
  18     unsigned hth_n_entries;                                             \
  19     /* How many elements will we allow in the table before resizing it? */ \
  20     unsigned hth_load_limit;                                            \
  21     /* Position of hth_table_length in the primes table. */             \
  22     int hth_prime_idx;                                                  \
  23   }
  24
  25 #define HT_INITIALIZER()                        \
  26   { NULL, 0, 0, 0, -1 }
  27
  28 #ifdef HT_NO_CACHE_HASH_VALUES
  29 #define HT_ENTRY(type)                          \
  30   struct {                                      \
  31     struct type *hte_next;                      \
  32   }
  33 #else
  34 #define HT_ENTRY(type)                          \
  35   struct {                                      \
  36     struct type *hte_next;                      \
  37     unsigned hte_hash;                          \
  38   }
  39 #endif
  40
  41 #define HT_EMPTY(head)                          \
  42   ((head)->hth_n_entries == 0)
  43
  44 /* How many elements in 'head'? */
  45 #define HT_SIZE(head)                           \
  46   ((head)->hth_n_entries)
  47
  48 /* Return memory usage for a hashtable (not counting the entries themselves) */
  49 #define HT_MEM_USAGE(head)                         \
  50   (sizeof(*head) + (head)->hth_table_length * sizeof(void*))
  51
  52 #define HT_FIND(name, head, elm)     name##_HT_FIND((head), (elm))
  53 #define HT_INSERT(name, head, elm)   name##_HT_INSERT((head), (elm))
  54 #define HT_REPLACE(name, head, elm)  name##_HT_REPLACE((head), (elm))
  55 #define HT_REMOVE(name, head, elm)   name##_HT_REMOVE((head), (elm))
  56 #define HT_START(name, head)         name##_HT_START(head)
  57 #define HT_NEXT(name, head, elm)     name##_HT_NEXT((head), (elm))
  58 #define HT_NEXT_RMV(name, head, elm) name##_HT_NEXT_RMV((head), (elm))
  59 #define HT_CLEAR(name, head)         name##_HT_CLEAR(head)
  60 #define HT_INIT(name, head)          name##_HT_INIT(head)
  61 /* Helper: */
  62 static inline unsigned
  63 ht_improve_hash_(unsigned h)
  64 {
  65   /* Aim to protect against poor hash functions by adding logic here
  66    * - logic taken from java 1.4 hashtable source */
  67   h += ~(h << 9);
  68   h ^=  ((h >> 14) | (h << 18)); /* >>> */
  69   h +=  (h << 4);
  70   h ^=  ((h >> 10) | (h << 22)); /* >>> */
  71   return h;
  72 }
  73
  74 #if 0
  75 /** Basic string hash function, from Java standard String.hashCode(). */
  76 static inline unsigned
  77 ht_string_hash_(const char *s)
  78 {
  79   unsigned h = 0;
  80   int m = 1;
  81   while (*s) {
  82     h += ((signed char)*s++)*m;
  83     m = (m<<5)-1; /* m *= 31 */
  84   }
  85   return h;
  86 }
  87 #endif
  88
  89 /** Basic string hash function, from Python's str.__hash__() */
  90 static inline unsigned
  91 ht_string_hash_(const char *s)
  92 {
  93   unsigned h;
  94   const unsigned char *cp = (const unsigned char *)s;
  95   h = *cp << 7;
  96   while (*cp) {
  97     h = (1000003*h) ^ *cp++;
  98   }
  99   /* This conversion truncates the length of the string, but that's ok. */
 100   h ^= (unsigned)(cp-(const unsigned char*)s);
 101   return h;
 102 }
 103
 104 #ifndef HT_NO_CACHE_HASH_VALUES
 105 #define HT_SET_HASH_(elm, field, hashfn)        \
 106         do { (elm)->field.hte_hash = hashfn(elm); } while (0)
 107 #define HT_SET_HASHVAL_(elm, field, val)        \
 108         do { (elm)->field.hte_hash = (val); } while (0)
 109 #define HT_ELT_HASH_(elm, field, hashfn)        \
 110         ((elm)->field.hte_hash)
 111 #else
 112 #define HT_SET_HASH_(elm, field, hashfn)        \
 113         ((void)0)
 114 #define HT_ELT_HASH_(elm, field, hashfn)        \
 115         (hashfn(elm))
 116 #define HT_SET_HASHVAL_(elm, field, val)        \
 117         ((void)0)
 118 #endif
 119
 120 /* Helper: alias for the bucket containing 'elm'. */
 121 #define HT_BUCKET_(head, field, elm, hashfn)                            \
 122         ((head)->hth_table[HT_ELT_HASH_(elm,field,hashfn) % head->hth_table_length])
 123
 124 #define HT_FOREACH(x, name, head)                 \
 125   for ((x) = HT_START(name, head);                \
 126        (x) != NULL;                               \
 127        (x) = HT_NEXT(name, head, x))
 128
 129 #define HT_PROTOTYPE(name, type, field, hashfn, eqfn)                   \
 130   int name##_HT_GROW(struct name *ht, unsigned min_capacity);           \
 131   void name##_HT_CLEAR(struct name *ht);                                \
 132   int name##_HT_REP_IS_BAD_(const struct name *ht);                     \
 133   static inline void                                                    \
 134   name##_HT_INIT(struct name *head) {                                   \
 135     head->hth_table_length = 0;                                         \
 136     head->hth_table = NULL;                                             \
 137     head->hth_n_entries = 0;                                            \
 138     head->hth_load_limit = 0;                                           \
 139     head->hth_prime_idx = -1;                                           \
 140   }                                                                     \
 141   /* Helper: returns a pointer to the right location in the table       \
 142    * 'head' to find or insert the element 'elm'. */                     \
 143   static inline struct type **                                          \
 144   name##_HT_FIND_P_(struct name *head, struct type *elm)                \
 145   {                                                                     \
 146     struct type **p;                                                    \
 147     if (!head->hth_table)                                               \
 148       return NULL;                                                      \
 149     p = &HT_BUCKET_(head, field, elm, hashfn);                          \
 150     while (*p) {                                                        \
 151       if (eqfn(*p, elm))                                                \
 152         return p;                                                       \
 153       p = &(*p)->field.hte_next;                                        \
 154     }                                                                   \
 155     return p;                                                           \
 156   }                                                                     \
 157   /* Return a pointer to the element in the table 'head' matching 'elm', \
 158    * or NULL if no such element exists */                               \
 159   static inline struct type *                                           \
 160   name##_HT_FIND(const struct name *head, struct type *elm)             \
 161   {                                                                     \
 162     struct type **p;                                                    \
 163     struct name *h = (struct name *) head;                              \
 164     HT_SET_HASH_(elm, field, hashfn);                                   \
 165     p = name##_HT_FIND_P_(h, elm);                                      \
 166     return p ? *p : NULL;                                               \
 167   }                                                                     \
 168   /* Insert the element 'elm' into the table 'head'.  Do not call this  \
 169    * function if the table might already contain a matching element. */ \
 170   static inline void                                                    \
 171   name##_HT_INSERT(struct name *head, struct type *elm)                 \
 172   {                                                                     \
 173     struct type **p;                                                    \
 174     if (!head->hth_table || head->hth_n_entries >= head->hth_load_limit) \
 175       name##_HT_GROW(head, head->hth_n_entries+1);                      \
 176     ++head->hth_n_entries;                                              \
 177     HT_SET_HASH_(elm, field, hashfn);                                   \
 178     p = &HT_BUCKET_(head, field, elm, hashfn);                          \
 179     elm->field.hte_next = *p;                                           \
 180     *p = elm;                                                           \
 181   }                                                                     \
 182   /* Insert the element 'elm' into the table 'head'. If there already   \
 183    * a matching element in the table, replace that element and return   \
 184    * it. */                                                             \
 185   static inline struct type *                                           \
 186   name##_HT_REPLACE(struct name *head, struct type *elm)                \
 187   {                                                                     \
 188     struct type **p, *r;                                                \
 189     if (!head->hth_table || head->hth_n_entries >= head->hth_load_limit) \
 190       name##_HT_GROW(head, head->hth_n_entries+1);                      \
 191     HT_SET_HASH_(elm, field, hashfn);                                   \
 192     p = name##_HT_FIND_P_(head, elm);                                   \
 193     r = *p;                                                             \
 194     *p = elm;                                                           \
 195     if (r && (r!=elm)) {                                                \
 196       elm->field.hte_next = r->field.hte_next;                          \
 197       r->field.hte_next = NULL;                                         \
 198       return r;                                                         \
 199     } else {                                                            \
 200       ++head->hth_n_entries;                                            \
 201       return NULL;                                                      \
 202     }                                                                   \
 203   }                                                                     \
 204   /* Remove any element matching 'elm' from the table 'head'.  If such  \
 205    * an element is found, return it; otherwise return NULL. */          \
 206   static inline struct type *                                           \
 207   name##_HT_REMOVE(struct name *head, struct type *elm)                 \
 208   {                                                                     \
 209     struct type **p, *r;                                                \
 210     HT_SET_HASH_(elm, field, hashfn);                                   \
 211     p = name##_HT_FIND_P_(head,elm);                                    \
 212     if (!p || !*p)                                                      \
 213       return NULL;                                                      \
 214     r = *p;                                                             \
 215     *p = r->field.hte_next;                                             \
 216     r->field.hte_next = NULL;                                           \
 217     --head->hth_n_entries;                                              \
 218     return r;                                                           \
 219   }                                                                     \
 220   /* Invoke the function 'fn' on every element of the table 'head',     \
 221    * using 'data' as its second argument.  If the function returns      \
 222    * nonzero, remove the most recently examined element before invoking \
 223    * the function again. */                                             \
 224   static inline void                                                    \
 225   name##_HT_FOREACH_FN(struct name *head,                               \
 226                        int (*fn)(struct type *, void *),                \
 227                        void *data)                                      \
 228   {                                                                     \
 229     unsigned idx;                                                       \
 230     struct type **p, **nextp, *next;                                    \
 231     if (!head->hth_table)                                               \
 232       return;                                                           \
 233     for (idx=0; idx < head->hth_table_length; ++idx) {                  \
 234       p = &head->hth_table[idx];                                        \
 235       while (*p) {                                                      \
 236         nextp = &(*p)->field.hte_next;                                  \
 237         next = *nextp;                                                  \
 238         if (fn(*p, data)) {                                             \
 239           --head->hth_n_entries;                                        \
 240           *p = next;                                                    \
 241         } else {                                                        \
 242           p = nextp;                                                    \
 243         }                                                               \
 244       }                                                                 \
 245     }                                                                   \
 246   }                                                                     \
 247   /* Return a pointer to the first element in the table 'head', under   \
 248    * an arbitrary order.  This order is stable under remove operations, \
 249    * but not under others. If the table is empty, return NULL. */       \
 250   static inline struct type **                                          \
 251   name##_HT_START(struct name *head)                                    \
 252   {                                                                     \
 253     unsigned b = 0;                                                     \
 254     while (b < head->hth_table_length) {                                \
 255       if (head->hth_table[b])                                           \
 256         return &head->hth_table[b];                                     \
 257       ++b;                                                              \
 258     }                                                                   \
 259     return NULL;                                                        \
 260   }                                                                     \
 261   /* Return the next element in 'head' after 'elm', under the arbitrary \
 262    * order used by HT_START.  If there are no more elements, return     \
 263    * NULL.  If 'elm' is to be removed from the table, you must call     \
 264    * this function for the next value before you remove it.             \
 265    */                                                                   \
 266   static inline struct type **                                          \
 267   name##_HT_NEXT(struct name *head, struct type **elm)                  \
 268   {                                                                     \
 269     if ((*elm)->field.hte_next) {                                       \
 270       return &(*elm)->field.hte_next;                                   \
 271     } else {                                                            \
 272       unsigned b = (HT_ELT_HASH_(*elm, field, hashfn) % head->hth_table_length)+1; \
 273       while (b < head->hth_table_length) {                              \
 274         if (head->hth_table[b])                                         \
 275           return &head->hth_table[b];                                   \
 276         ++b;                                                            \
 277       }                                                                 \
 278       return NULL;                                                      \
 279     }                                                                   \
 280   }                                                                     \
 281   static inline struct type **                                          \
 282   name##_HT_NEXT_RMV(struct name *head, struct type **elm)              \
 283   {                                                                     \
 284     unsigned h = HT_ELT_HASH_(*elm, field, hashfn);                     \
 285     *elm = (*elm)->field.hte_next;                                      \
 286     --head->hth_n_entries;                                              \
 287     if (*elm) {                                                         \
 288       return elm;                                                       \
 289     } else {                                                            \
 290       unsigned b = (h % head->hth_table_length)+1;                      \
 291       while (b < head->hth_table_length) {                              \
 292         if (head->hth_table[b])                                         \
 293           return &head->hth_table[b];                                   \
 294         ++b;                                                            \
 295       }                                                                 \
 296       return NULL;                                                      \
 297     }                                                                   \
 298   }
 299
 300 #define HT_GENERATE(name, type, field, hashfn, eqfn, load, mallocfn,    \
 301                     reallocfn, freefn)                                  \
 302   static unsigned name##_PRIMES[] = {                                   \
 303     53, 97, 193, 389,                                                   \
 304     769, 1543, 3079, 6151,                                              \
 305     12289, 24593, 49157, 98317,                                         \
 306     196613, 393241, 786433, 1572869,                                    \
 307     3145739, 6291469, 12582917, 25165843,                               \
 308     50331653, 100663319, 201326611, 402653189,                          \
 309     805306457, 1610612741                                               \
 310   };                                                                    \
 311   static unsigned name##_N_PRIMES =                                     \
 312     (unsigned)(sizeof(name##_PRIMES)/sizeof(name##_PRIMES[0]));         \
 313   /* Expand the internal table of 'head' until it is large enough to    \
 314    * hold 'size' elements.  Return 0 on success, -1 on allocation       \
 315    * failure. */                                                        \
 316   int                                                                   \
 317   name##_HT_GROW(struct name *head, unsigned size)                      \
 318   {                                                                     \
 319     unsigned new_len, new_load_limit;                                   \
 320     int prime_idx;                                                      \
 321     struct type **new_table;                                            \
 322     if (head->hth_prime_idx == (int)name##_N_PRIMES - 1)                \
 323       return 0;                                                         \
 324     if (head->hth_load_limit > size)                                    \
 325       return 0;                                                         \
 326     prime_idx = head->hth_prime_idx;                                    \
 327     do {                                                                \
 328       new_len = name##_PRIMES[++prime_idx];                             \
 329       new_load_limit = (unsigned)(load*new_len);                        \
 330     } while (new_load_limit <= size &&                                  \
 331              prime_idx < (int)name##_N_PRIMES);                         \
 332     if ((new_table = mallocfn(new_len*sizeof(struct type*)))) {         \
 333       unsigned b;                                                       \
 334       memset(new_table, 0, new_len*sizeof(struct type*));               \
 335       for (b = 0; b < head->hth_table_length; ++b) {                    \
 336         struct type *elm, *next;                                        \
 337         unsigned b2;                                                    \
 338         elm = head->hth_table[b];                                       \
 339         while (elm) {                                                   \
 340           next = elm->field.hte_next;                                   \
 341           b2 = HT_ELT_HASH_(elm, field, hashfn) % new_len;              \
 342           elm->field.hte_next = new_table[b2];                          \
 343           new_table[b2] = elm;                                          \
 344           elm = next;                                                   \
 345         }                                                               \
 346       }                                                                 \
 347       if (head->hth_table)                                              \
 348         freefn(head->hth_table);                                        \
 349       head->hth_table = new_table;                                      \
 350     } else {                                                            \
 351       unsigned b, b2;                                                   \
 352       new_table = reallocfn(head->hth_table, new_len*sizeof(struct type*)); \
 353       if (!new_table) return -1;                                        \
 354       memset(new_table + head->hth_table_length, 0,                     \
 355              (new_len - head->hth_table_length)*sizeof(struct type*));  \
 356       for (b=0; b < head->hth_table_length; ++b) {                      \
 357         struct type *e, **pE;                                           \
 358         for (pE = &new_table[b], e = *pE; e != NULL; e = *pE) {         \
 359           b2 = HT_ELT_HASH_(e, field, hashfn) % new_len;                \
 360           if (b2 == b) {                                                \
 361             pE = &e->field.hte_next;                                    \
 362           } else {                                                      \
 363             *pE = e->field.hte_next;                                    \
 364             e->field.hte_next = new_table[b2];                          \
 365             new_table[b2] = e;                                          \
 366           }                                                             \
 367         }                                                               \
 368       }                                                                 \
 369       head->hth_table = new_table;                                      \
 370     }                                                                   \
 371     head->hth_table_length = new_len;                                   \
 372     head->hth_prime_idx = prime_idx;                                    \
 373     head->hth_load_limit = new_load_limit;                              \
 374     return 0;                                                           \
 375   }                                                                     \
 376   /* Free all storage held by 'head'.  Does not free 'head' itself, or  \
 377    * individual elements. */                                            \
 378   void                                                                  \
 379   name##_HT_CLEAR(struct name *head)                                    \
 380   {                                                                     \
 381     if (head->hth_table)                                                \
 382       freefn(head->hth_table);                                          \
 383     name##_HT_INIT(head);                                               \
 384   }                                                                     \
 385   /* Debugging helper: return false iff the representation of 'head' is \
 386    * internally consistent. */                                          \
 387   int                                                                   \
 388   name##_HT_REP_IS_BAD_(const struct name *head)                        \
 389   {                                                                     \
 390     unsigned n, i;                                                      \
 391     struct type *elm;                                                   \
 392     if (!head->hth_table_length) {                                      \
 393       if (!head->hth_table && !head->hth_n_entries &&                   \
 394           !head->hth_load_limit && head->hth_prime_idx == -1)           \
 395         return 0;                                                       \
 396       else                                                              \
 397         return 1;                                                       \
 398     }                                                                   \
 399     if (!head->hth_table || head->hth_prime_idx < 0 ||                  \
 400         !head->hth_load_limit)                                          \
 401       return 2;                                                         \
 402     if (head->hth_n_entries > head->hth_load_limit)                     \
 403       return 3;                                                         \
 404     if (head->hth_table_length != name##_PRIMES[head->hth_prime_idx])   \
 405       return 4;                                                         \
 406     if (head->hth_load_limit != (unsigned)(load*head->hth_table_length)) \
 407       return 5;                                                         \
 408     for (n = i = 0; i < head->hth_table_length; ++i) {                  \
 409       for (elm = head->hth_table[i]; elm; elm = elm->field.hte_next) {  \
 410         if (HT_ELT_HASH_(elm, field, hashfn) != hashfn(elm))            \
 411           return 1000 + i;                                              \
 412         if ((HT_ELT_HASH_(elm, field, hashfn) % head->hth_table_length) != i) \
 413           return 10000 + i;                                             \
 414         ++n;                                                            \
 415       }                                                                 \
 416     }                                                                   \
 417     if (n != head->hth_n_entries)                                       \
 418       return 6;                                                         \
 419     return 0;                                                           \
 420   }
 421
 422 /** Implements an over-optimized "find and insert if absent" block;
 423  * not meant for direct usage by typical code, or usage outside the critical
 424  * path.*/
 425 #define HT_FIND_OR_INSERT_(name, field, hashfn, head, eltype, elm, var, y, n) \
 426   {                                                                     \
 427     struct name *var##_head_ = head;                                    \
 428     struct eltype **var;                                                \
 429     if (!var##_head_->hth_table ||                                      \
 430         var##_head_->hth_n_entries >= var##_head_->hth_load_limit)      \
 431       name##_HT_GROW(var##_head_, var##_head_->hth_n_entries+1);        \
 432     HT_SET_HASH_((elm), field, hashfn);                                 \
 433     var = name##_HT_FIND_P_(var##_head_, (elm));                        \
 434     if (*var) {                                                         \
 435       y;                                                                \
 436     } else {                                                            \
 437       n;                                                                \
 438     }                                                                   \
 439   }
 440 #define HT_FOI_INSERT_(field, head, elm, newent, var)       \
 441   {                                                         \
 442     HT_SET_HASHVAL_(newent, field, (elm)->field.hte_hash);  \
 443     newent->field.hte_next = NULL;                          \
 444     *var = newent;                                          \
 445     ++((head)->hth_n_entries);                              \
 446   }
 447
 448 /*
 449  * Copyright 2005, Nick Mathewson.  Implementation logic is adapted from code
 450  * by Christopher Clark, retrofit to allow drop-in memory management, and to
 451  * use the same interface as Niels Provos's tree.h.  This is probably still
 452  * a derived work, so the original license below still applies.
 453  *
 454  * Copyright (c) 2002, Christopher Clark
 455  * All rights reserved.
 456  *
 457  * Redistribution and use in source and binary forms, with or without
 458  * modification, are permitted provided that the following conditions
 459  * are met:
 460  *
 461  * * Redistributions of source code must retain the above copyright
 462  * notice, this list of conditions and the following disclaimer.
 463  *
 464  * * Redistributions in binary form must reproduce the above copyright
 465  * notice, this list of conditions and the following disclaimer in the
 466  * documentation and/or other materials provided with the distribution.
 467  *
 468  * * Neither the name of the original author; nor the names of any contributors
 469  * may be used to endorse or promote products derived from this software
 470  * without specific prior written permission.
 471  *
 472  *
 473  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 474  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 475  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 476  * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER
 477  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 478  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 479  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 480  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 481  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 482  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 483  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 484 */
 485
 486 #endif
 487