/src/libevent/ht-internal.h

Source
/* Copyright 2002 Christopher Clark */
/* Copyright 2005-2012 Nick Mathewson */
/* Copyright 2009-2012 Niels Provos and Nick Mathewson */
/* See license at end. */

/* Based on ideas by Christopher Clark and interfaces from Niels Provos. */

#ifndef HT_INTERNAL_H_INCLUDED_
#define HT_INTERNAL_H_INCLUDED_

#define HT_HEAD(name, type)                                             \
  struct name {                                                         \
    /* The hash table itself. */                                        \
    struct type **hth_table;                                            \
    /* How long is the hash table? */                                   \
    unsigned hth_table_length;                                          \
    /* How many elements does the table contain? */                     \
    unsigned hth_n_entries;                                             \
    /* How many elements will we allow in the table before resizing it? */ \
    unsigned hth_load_limit;                                            \
    /* Position of hth_table_length in the primes table. */             \
    int hth_prime_idx;                                                  \
  }

#define HT_INITIALIZER()                        \
  { NULL, 0, 0, 0, -1 }

#ifdef HT_NO_CACHE_HASH_VALUES
#define HT_ENTRY(type)                          \
  struct {                                      \
    struct type *hte_next;                      \
  }
#else
#define HT_ENTRY(type)                          \
  struct {                                      \
    struct type *hte_next;                      \
    unsigned hte_hash;                          \
  }
#endif

#define HT_EMPTY(head)                          \
  ((head)->hth_n_entries == 0)

/* How many elements in 'head'? */
#define HT_SIZE(head)                           \
  ((head)->hth_n_entries)

/* Return memory usage for a hashtable (not counting the entries themselves) */
#define HT_MEM_USAGE(head)                         \
  (sizeof(*head) + (head)->hth_table_length * sizeof(void*))

#define HT_FIND(name, head, elm)     name##_HT_FIND((head), (elm))
#define HT_INSERT(name, head, elm)   name##_HT_INSERT((head), (elm))
#define HT_REPLACE(name, head, elm)  name##_HT_REPLACE((head), (elm))
#define HT_REMOVE(name, head, elm)   name##_HT_REMOVE((head), (elm))
#define HT_START(name, head)         name##_HT_START(head)
#define HT_NEXT(name, head, elm)     name##_HT_NEXT((head), (elm))
#define HT_NEXT_RMV(name, head, elm) name##_HT_NEXT_RMV((head), (elm))
#define HT_CLEAR(name, head)         name##_HT_CLEAR(head)
#define HT_INIT(name, head)          name##_HT_INIT(head)
/* Helper: */
static inline unsigned
ht_improve_hash_(unsigned h)
{
  /* Aim to protect against poor hash functions by adding logic here
   * - logic taken from java 1.4 hashtable source */
  h += ~(h << 9);
  h ^=  ((h >> 14) | (h << 18)); /* >>> */
  h +=  (h << 4);
  h ^=  ((h >> 10) | (h << 22)); /* >>> */
  return h;
}

#if 0
/** Basic string hash function, from Java standard String.hashCode(). */
static inline unsigned
ht_string_hash_(const char *s)
{
  unsigned h = 0;
  int m = 1;
  while (*s) {
    h += ((signed char)*s++)*m;
    m = (m<<5)-1; /* m *= 31 */
  }
  return h;
}
#endif

/** Basic string hash function, from Python's str.__hash__() */
static inline unsigned
ht_string_hash_(const char *s)
{
  unsigned h;
  const unsigned char *cp = (const unsigned char *)s;
  h = *cp << 7;
  while (*cp) {
    h = (1000003*h) ^ *cp++;
  }
  /* This conversion truncates the length of the string, but that's ok. */
  h ^= (unsigned)(cp-(const unsigned char*)s);
  return h;
}

#ifndef HT_NO_CACHE_HASH_VALUES
#define HT_SET_HASH_(elm, field, hashfn)        \
  do { (elm)->field.hte_hash = hashfn(elm); } while (0)
#define HT_SET_HASHVAL_(elm, field, val)  \
  do { (elm)->field.hte_hash = (val); } while (0)
#define HT_ELT_HASH_(elm, field, hashfn)  \
  ((elm)->field.hte_hash)
#else
#define HT_SET_HASH_(elm, field, hashfn)  \
  ((void)0)
#define HT_ELT_HASH_(elm, field, hashfn)  \
  (hashfn(elm))
#define HT_SET_HASHVAL_(elm, field, val)  \
        ((void)0)
#endif

/* Helper: alias for the bucket containing 'elm'. */
#define HT_BUCKET_(head, field, elm, hashfn)        \
  ((head)->hth_table[HT_ELT_HASH_(elm,field,hashfn) % head->hth_table_length])

#define HT_FOREACH(x, name, head)                 \
  for ((x) = HT_START(name, head);                \
       (x) != NULL;                               \
       (x) = HT_NEXT(name, head, x))

#define HT_PROTOTYPE(name, type, field, hashfn, eqfn)                   \
  int name##_HT_GROW(struct name *ht, unsigned min_capacity);           \
  void name##_HT_CLEAR(struct name *ht);                                \
  int name##_HT_REP_IS_BAD_(const struct name *ht);     \
  static inline void                                                    \
  name##_HT_INIT(struct name *head) {                                   \
    head->hth_table_length = 0;                                         \
    head->hth_table = NULL;                                             \
    head->hth_n_entries = 0;                                            \
    head->hth_load_limit = 0;                                           \
    head->hth_prime_idx = -1;                                           \
  }                                                                     \
  /* Helper: returns a pointer to the right location in the table       \
   * 'head' to find or insert the element 'elm'. */                     \
  static inline struct type **                                          \
  name##_HT_FIND_P_(struct name *head, struct type *elm)    \
  {                                                                     \
    struct type **p;                                                    \
    if (!head->hth_table)                                               \
      return NULL;                                                      \
    p = &HT_BUCKET_(head, field, elm, hashfn);       \
    while (*p) {                                                        \
      if (eqfn(*p, elm))                                                \
        return p;                                                       \
      p = &(*p)->field.hte_next;                                        \
    }                                                                   \
    return p;                                                           \
  }                                                                     \
  /* Return a pointer to the element in the table 'head' matching 'elm', \
   * or NULL if no such element exists */                               \
  static inline struct type *                                           \
  name##_HT_FIND(const struct name *head, struct type *elm)             \
  {                                                                     \
    struct type **p;                                                    \
    struct name *h = (struct name *) head;                              \
    HT_SET_HASH_(elm, field, hashfn);                                   \
    p = name##_HT_FIND_P_(h, elm);          \
    return p ? *p : NULL;                                               \
  }                                                                     \
  /* Insert the element 'elm' into the table 'head'.  Do not call this  \
   * function if the table might already contain a matching element. */ \
  static inline void                                                    \
  name##_HT_INSERT(struct name *head, struct type *elm)                 \
  {                                                                     \
    struct type **p;                                                    \
    if (!head->hth_table || head->hth_n_entries >= head->hth_load_limit) \
      name##_HT_GROW(head, head->hth_n_entries+1);                      \
    ++head->hth_n_entries;                                              \
    HT_SET_HASH_(elm, field, hashfn);                                   \
    p = &HT_BUCKET_(head, field, elm, hashfn);       \
    elm->field.hte_next = *p;                                           \
    *p = elm;                                                           \
  }                                                                     \
  /* Insert the element 'elm' into the table 'head'. If there already   \
   * a matching element in the table, replace that element and return   \
   * it. */                                                             \
  static inline struct type *                                           \
  name##_HT_REPLACE(struct name *head, struct type *elm)                \
  {                                                                     \
    struct type **p, *r;                                                \
    if (!head->hth_table || head->hth_n_entries >= head->hth_load_limit) \
      name##_HT_GROW(head, head->hth_n_entries+1);                      \
    HT_SET_HASH_(elm, field, hashfn);                                   \
    p = name##_HT_FIND_P_(head, elm);         \
    r = *p;                                                             \
    *p = elm;                                                           \
    if (r && (r!=elm)) {                                                \
      elm->field.hte_next = r->field.hte_next;                          \
      r->field.hte_next = NULL;                                         \
      return r;                                                         \
    } else {                                                            \
      ++head->hth_n_entries;                                            \
      return NULL;                                                      \
    }                                                                   \
  }                                                                     \
  /* Remove any element matching 'elm' from the table 'head'.  If such  \
   * an element is found, return it; otherwise return NULL. */          \
  static inline struct type *                                           \
  name##_HT_REMOVE(struct name *head, struct type *elm)                 \
  {                                                                     \
    struct type **p, *r;                                                \
    HT_SET_HASH_(elm, field, hashfn);                                   \
    p = name##_HT_FIND_P_(head,elm);          \
    if (!p || !*p)                                                      \
      return NULL;                                                      \
    r = *p;                                                             \
    *p = r->field.hte_next;                                             \
    r->field.hte_next = NULL;                                           \
    --head->hth_n_entries;                                              \
    return r;                                                           \
  }                                                                     \
  /* Invoke the function 'fn' on every element of the table 'head',     \
   * using 'data' as its second argument.  If the function returns      \
   * nonzero, remove the most recently examined element before invoking \
   * the function again. */                                             \
  static inline void                                                    \
  name##_HT_FOREACH_FN(struct name *head,                               \
                       int (*fn)(struct type *, void *),                \
                       void *data)                                      \
  {                                                                     \
    unsigned idx;                                                       \
    struct type **p, **nextp, *next;                                    \
    if (!head->hth_table)                                               \
      return;                                                           \
    for (idx=0; idx < head->hth_table_length; ++idx) {                  \
      p = &head->hth_table[idx];                                        \
      while (*p) {                                                      \
        nextp = &(*p)->field.hte_next;                                  \
        next = *nextp;                                                  \
        if (fn(*p, data)) {                                             \
          --head->hth_n_entries;                                        \
          *p = next;                                                    \
        } else {                                                        \
          p = nextp;                                                    \
        }                                                               \
      }                                                                 \
    }                                                                   \
  }                                                                     \
  /* Return a pointer to the first element in the table 'head', under   \
   * an arbitrary order.  This order is stable under remove operations, \
   * but not under others. If the table is empty, return NULL. */       \
  static inline struct type **                                          \
  name##_HT_START(struct name *head)                                    \
  {                                                                     \
    unsigned b = 0;                                                     \
    while (b < head->hth_table_length) {                                \
      if (head->hth_table[b])                                           \
        return &head->hth_table[b];                                     \
      ++b;                                                              \
    }                                                                   \
    return NULL;                                                        \
  }                                                                     \
  /* Return the next element in 'head' after 'elm', under the arbitrary \
   * order used by HT_START.  If there are no more elements, return     \
   * NULL.  If 'elm' is to be removed from the table, you must call     \
   * this function for the next value before you remove it.             \
   */                                                                   \
  static inline struct type **                                          \
  name##_HT_NEXT(struct name *head, struct type **elm)                  \
  {                                                                     \
    if ((*elm)->field.hte_next) {                                       \
      return &(*elm)->field.hte_next;                                   \
    } else {                                                            \
      unsigned b = (HT_ELT_HASH_(*elm, field, hashfn) % head->hth_table_length)+1; \
      while (b < head->hth_table_length) {                              \
        if (head->hth_table[b])                                         \
          return &head->hth_table[b];                                   \
        ++b;                                                            \
      }                                                                 \
      return NULL;                                                      \
    }                                                                   \
  }                                                                     \
  static inline struct type **                                          \
  name##_HT_NEXT_RMV(struct name *head, struct type **elm)              \
  {                                                                     \
    unsigned h = HT_ELT_HASH_(*elm, field, hashfn);            \
    *elm = (*elm)->field.hte_next;                                      \
    --head->hth_n_entries;                                              \
    if (*elm) {                                                         \
      return elm;                                                       \
    } else {                                                            \
      unsigned b = (h % head->hth_table_length)+1;                      \
      while (b < head->hth_table_length) {                              \
        if (head->hth_table[b])                                         \
          return &head->hth_table[b];                                   \
        ++b;                                                            \
      }                                                                 \
      return NULL;                                                      \
    }                                                                   \
  }

#define HT_GENERATE(name, type, field, hashfn, eqfn, load, mallocfn,    \
                    reallocfn, freefn)                                  \
  static unsigned name##_PRIMES[] = {                                   \
    53, 97, 193, 389,                                                   \
    769, 1543, 3079, 6151,                                              \
    12289, 24593, 49157, 98317,                                         \
    196613, 393241, 786433, 1572869,                                    \
    3145739, 6291469, 12582917, 25165843,                               \
    50331653, 100663319, 201326611, 402653189,                          \
    805306457, 1610612741                                               \
  };                                                                    \
  static unsigned name##_N_PRIMES =                                     \
    (unsigned)(sizeof(name##_PRIMES)/sizeof(name##_PRIMES[0])) - 1;     \
  /* Expand the internal table of 'head' until it is large enough to    \
   * hold 'size' elements.  Return 0 on success, -1 on allocation       \
   * failure. */                                                        \
  int                                                                   \
  name##_HT_GROW(struct name *head, unsigned size)                      \
  {                                                                     \
    unsigned new_len, new_load_limit;                                   \
    int prime_idx;                                                      \
    struct type **new_table;                                            \
    if (head->hth_prime_idx == (int)name##_N_PRIMES)                    \
      return 0;                                                         \
    if (head->hth_load_limit > size)                                    \
      return 0;                                                         \
    prime_idx = head->hth_prime_idx;                                    \
    do {                                                                \
      new_len = name##_PRIMES[++prime_idx];                             \
      new_load_limit = (unsigned)(load*new_len);                        \
    } while (new_load_limit <= size &&                                  \
             prime_idx < (int)name##_N_PRIMES);                         \
    if ((new_table = mallocfn(new_len*sizeof(struct type*)))) {         \
      unsigned b;                                                       \
      memset(new_table, 0, new_len*sizeof(struct type*));               \
      for (b = 0; b < head->hth_table_length; ++b) {                    \
        struct type *elm, *next;                                        \
        unsigned b2;                                                    \
        elm = head->hth_table[b];                                       \
        while (elm) {                                                   \
          next = elm->field.hte_next;                                   \
          b2 = HT_ELT_HASH_(elm, field, hashfn) % new_len;              \
          elm->field.hte_next = new_table[b2];                          \
          new_table[b2] = elm;                                          \
          elm = next;                                                   \
        }                                                               \
      }                                                                 \
      if (head->hth_table)                                              \
        freefn(head->hth_table);                                        \
      head->hth_table = new_table;                                      \
    } else {                                                            \
      unsigned b, b2;                                                   \
      new_table = reallocfn(head->hth_table, new_len*sizeof(struct type*)); \
      if (!new_table) return -1;                                        \
      memset(new_table + head->hth_table_length, 0,                     \
             (new_len - head->hth_table_length)*sizeof(struct type*));  \
      for (b=0; b < head->hth_table_length; ++b) {                      \
        struct type *e, **pE;                                           \
        for (pE = &new_table[b], e = *pE; e != NULL; e = *pE) {         \
          b2 = HT_ELT_HASH_(e, field, hashfn) % new_len;                \
          if (b2 == b) {                                                \
            pE = &e->field.hte_next;                                    \
          } else {                                                      \
            *pE = e->field.hte_next;                                    \
            e->field.hte_next = new_table[b2];                          \
            new_table[b2] = e;                                          \
          }                                                             \
        }                                                               \
      }                                                                 \
      head->hth_table = new_table;                                      \
    }                                                                   \
    head->hth_table_length = new_len;                                   \
    head->hth_prime_idx = prime_idx;                                    \
    head->hth_load_limit = new_load_limit;                              \
    return 0;                                                           \
  }                                                                     \
  /* Free all storage held by 'head'.  Does not free 'head' itself, or  \
   * individual elements. */                                            \
  void                                                                  \
  name##_HT_CLEAR(struct name *head)                                    \
  {                                                                     \
    if (head->hth_table)                                                \
      freefn(head->hth_table);                                          \
    name##_HT_INIT(head);                                               \
  }                                                                     \
  /* Debugging helper: return false iff the representation of 'head' is \
   * internally consistent. */                                          \
  int                                                                   \
  name##_HT_REP_IS_BAD_(const struct name *head)      \
  {                                                                     \
    unsigned n, i;                                                      \
    struct type *elm;                                                   \
    if (!head->hth_table_length) {                                      \
      if (!head->hth_table && !head->hth_n_entries &&                   \
          !head->hth_load_limit && head->hth_prime_idx == -1)           \
        return 0;                                                       \
      else                                                              \
        return 1;                                                       \
    }                                                                   \
    if (!head->hth_table || head->hth_prime_idx < 0 ||                  \
        !head->hth_load_limit)                                          \
      return 2;                                                         \
    if (head->hth_n_entries > head->hth_load_limit)                     \
      return 3;                                                         \
    if (head->hth_table_length != name##_PRIMES[head->hth_prime_idx])   \
      return 4;                                                         \
    if (head->hth_load_limit != (unsigned)(load*head->hth_table_length)) \
      return 5;                                                         \
    for (n = i = 0; i < head->hth_table_length; ++i) {                  \
      for (elm = head->hth_table[i]; elm; elm = elm->field.hte_next) {  \
        if (HT_ELT_HASH_(elm, field, hashfn) != hashfn(elm))         \
          return 1000 + i;                                              \
        if ((HT_ELT_HASH_(elm, field, hashfn) % head->hth_table_length) != i) \
          return 10000 + i;                                             \
        ++n;                                                            \
      }                                                                 \
    }                                                                   \
    if (n != head->hth_n_entries)                                       \
      return 6;                                                         \
    return 0;                                                           \
  }

/** Implements an over-optimized "find and insert if absent" block;
 * not meant for direct usage by typical code, or usage outside the critical
 * path.*/
#define HT_FIND_OR_INSERT_(name, field, hashfn, head, eltype, elm, var, y, n) \
  {                                                                     \
    struct name *var##_head_ = head;                                    \
    struct eltype **var;                                                \
    if (!var##_head_->hth_table ||                                      \
        var##_head_->hth_n_entries >= var##_head_->hth_load_limit)      \
      name##_HT_GROW(var##_head_, var##_head_->hth_n_entries+1);        \
    HT_SET_HASH_((elm), field, hashfn);                                 \
    var = name##_HT_FIND_P_(var##_head_, (elm));                        \
    if (*var) {                                                         \
      y;                                                                \
    } else {                                                            \
      n;                                                                \
    }                                                                   \
  }
#define HT_FOI_INSERT_(field, head, elm, newent, var)       \
  {                                                         \
    HT_SET_HASHVAL_(newent, field, (elm)->field.hte_hash);  \
    newent->field.hte_next = NULL;                          \
    *var = newent;                                          \
    ++((head)->hth_n_entries);                              \
  }

/*
 * Copyright 2005, Nick Mathewson.  Implementation logic is adapted from code
 * by Christopher Clark, retrofit to allow drop-in memory management, and to
 * use the same interface as Niels Provos's tree.h.  This is probably still
 * a derived work, so the original license below still applies.
 *
 * Copyright (c) 2002, Christopher Clark
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * * Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *
 * * Redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution.
 *
 * * Neither the name of the original author; nor the names of any contributors
 * may be used to endorse or promote products derived from this software
 * without specific prior written permission.
 *
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

#endif


Coverage Report

Created: 2025-10-28 06:56

Line	Count	Source
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	0	#define HT_FIND(name, head, elm) name##_HT_FIND((head), (elm))
53	0	#define HT_INSERT(name, head, elm) name##_HT_INSERT((head), (elm))
54		#define HT_REPLACE(name, head, elm) name##_HT_REPLACE((head), (elm))
55	0	#define HT_REMOVE(name, head, elm) name##_HT_REMOVE((head), (elm))
56	0	#define HT_START(name, head) name##_HT_START(head)
57		#define HT_NEXT(name, head, elm) name##_HT_NEXT((head), (elm))
58	0	#define HT_NEXT_RMV(name, head, elm) name##_HT_NEXT_RMV((head), (elm))
59	0	#define HT_CLEAR(name, head) name##_HT_CLEAR(head)
60	0	#define HT_INIT(name, head) name##_HT_INIT(head)
61		/* Helper: */
62		static inline unsigned
63		ht_improve_hash_(unsigned h)
64	0	{
65	0	/* Aim to protect against poor hash functions by adding logic here
66	0	* - logic taken from java 1.4 hashtable source */
67	0	h += ~(h << 9);
68	0	h ^= ((h >> 14) \| (h << 18)); /* >>> */
69	0	h += (h << 4);
70	0	h ^= ((h >> 10) \| (h << 22)); /* >>> */
71	0	return h;
72	0	}
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	0	{
93	0	unsigned h;
94	0	const unsigned char cp = (const unsigned char )s;
95	0	h = *cp << 7;
96	0	while (*cp) {
97	0	h = (1000003h) ^ cp++;
98	0	}
99	0	/* This conversion truncates the length of the string, but that's ok. */
100	0	h ^= (unsigned)(cp-(const unsigned char*)s);
101	0	return h;
102	0	}
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	0	((void)0)
114		#define HT_ELT_HASH_(elm, field, hashfn) \
115	0	(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	0	((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	0	name##_HT_INIT(struct name *head) { \
135	0	head->hth_table_length = 0; \
136	0	head->hth_table = NULL; \
137	0	head->hth_n_entries = 0; \
138	0	head->hth_load_limit = 0; \
139	0	head->hth_prime_idx = -1; \
140	0	} \
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	0	{ \
146	0	struct type **p; \
147	0	if (!head->hth_table) \
148	0	return NULL; \
149	0	p = &HT_BUCKET_(head, field, elm, hashfn); \
150	0	while (*p) { \
151	0	if (eqfn(*p, elm)) \
152	0	return p; \
153	0	p = &(*p)->field.hte_next; \
154	0	} \
155	0	return p; \
156	0	} \
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	0	{ \
162	0	struct type **p; \
163	0	struct name h = (struct name ) head; \
164	0	HT_SET_HASH_(elm, field, hashfn); \
165	0	p = name##_HT_FIND_P_(h, elm); \
166	0	return p ? *p : NULL; \
167	0	} \
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	0	{ \
173	0	struct type **p; \
174	0	if (!head->hth_table \|\| head->hth_n_entries >= head->hth_load_limit) \
175	0	name##_HT_GROW(head, head->hth_n_entries+1); \
176	0	++head->hth_n_entries; \
177	0	HT_SET_HASH_(elm, field, hashfn); \
178	0	p = &HT_BUCKET_(head, field, elm, hashfn); \
179	0	elm->field.hte_next = *p; \
180	0	*p = elm; \
181	0	} \
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	0	{ \
188	0	struct type *p, r; \
189	0	if (!head->hth_table \|\| head->hth_n_entries >= head->hth_load_limit) \
190	0	name##_HT_GROW(head, head->hth_n_entries+1); \
191	0	HT_SET_HASH_(elm, field, hashfn); \
192	0	p = name##_HT_FIND_P_(head, elm); \
193	0	r = *p; \
194	0	*p = elm; \
195	0	if (r && (r!=elm)) { \
196	0	elm->field.hte_next = r->field.hte_next; \
197	0	r->field.hte_next = NULL; \
198	0	return r; \
199	0	} else { \
200	0	++head->hth_n_entries; \
201	0	return NULL; \
202	0	} \
203	0	} \
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	0	{ \
209	0	struct type *p, r; \
210	0	HT_SET_HASH_(elm, field, hashfn); \
211	0	p = name##_HT_FIND_P_(head,elm); \
212	0	if (!p \|\| !*p) \
213	0	return NULL; \
214	0	r = *p; \
215	0	*p = r->field.hte_next; \
216	0	r->field.hte_next = NULL; \
217	0	--head->hth_n_entries; \
218	0	return r; \
219	0	} \
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	0	{ \
229	0	unsigned idx; \
230	0	struct type p, nextp, *next; \
231	0	if (!head->hth_table) \
232	0	return; \
233	0	for (idx=0; idx < head->hth_table_length; ++idx) { \
234	0	p = &head->hth_table[idx]; \
235	0	while (*p) { \
236	0	nextp = &(*p)->field.hte_next; \
237	0	next = *nextp; \
238	0	if (fn(*p, data)) { \
239	0	--head->hth_n_entries; \
240	0	*p = next; \
241	0	} else { \
242	0	p = nextp; \
243	0	} \
244	0	} \
245	0	} \
246	0	} \
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	0	{ \
253	0	unsigned b = 0; \
254	0	while (b < head->hth_table_length) { \
255	0	if (head->hth_table[b]) \
256	0	return &head->hth_table[b]; \
257	0	++b; \
258	0	} \
259	0	return NULL; \
260	0	} \
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	0	{ \
269	0	if ((*elm)->field.hte_next) { \
270	0	return &(*elm)->field.hte_next; \
271	0	} else { \
272	0	unsigned b = (HT_ELT_HASH_(*elm, field, hashfn) % head->hth_table_length)+1; \
273	0	while (b < head->hth_table_length) { \
274	0	if (head->hth_table[b]) \
275	0	return &head->hth_table[b]; \
276	0	++b; \
277	0	} \
278	0	return NULL; \
279	0	} \
280	0	} \
281		static inline struct type ** \
282		name##_HT_NEXT_RMV(struct name head, struct type *elm) \
283	0	{ \
284	0	unsigned h = HT_ELT_HASH_(*elm, field, hashfn); \
285	0	elm = (elm)->field.hte_next; \
286	0	--head->hth_n_entries; \
287	0	if (*elm) { \
288	0	return elm; \
289	0	} else { \
290	0	unsigned b = (h % head->hth_table_length)+1; \
291	0	while (b < head->hth_table_length) { \
292	0	if (head->hth_table[b]) \
293	0	return &head->hth_table[b]; \
294	0	++b; \
295	0	} \
296	0	return NULL; \
297	0	} \
298	0	}
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])) - 1; \
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	0	{ \
319	0	unsigned new_len, new_load_limit; \
320	0	int prime_idx; \
321	0	struct type **new_table; \
322	0	if (head->hth_prime_idx == (int)name##_N_PRIMES) \
323	0	return 0; \
324	0	if (head->hth_load_limit > size) \
325	0	return 0; \
326	0	prime_idx = head->hth_prime_idx; \
327	0	do { \
328	0	new_len = name##_PRIMES[++prime_idx]; \
329	0	new_load_limit = (unsigned)(load*new_len); \
330	0	} while (new_load_limit <= size && \
331	0	prime_idx < (int)name##_N_PRIMES); \
332	0	if ((new_table = mallocfn(new_lensizeof(struct type)))) { \
333	0	unsigned b; \
334	0	memset(new_table, 0, new_lensizeof(struct type)); \
335	0	for (b = 0; b < head->hth_table_length; ++b) { \
336	0	struct type elm, next; \
337	0	unsigned b2; \
338	0	elm = head->hth_table[b]; \
339	0	while (elm) { \
340	0	next = elm->field.hte_next; \
341	0	b2 = HT_ELT_HASH_(elm, field, hashfn) % new_len; \
342	0	elm->field.hte_next = new_table[b2]; \
343	0	new_table[b2] = elm; \
344	0	elm = next; \
345	0	} \
346	0	} \
347	0	if (head->hth_table) \
348	0	freefn(head->hth_table); \
349	0	head->hth_table = new_table; \
350	0	} else { \
351	0	unsigned b, b2; \
352	0	new_table = reallocfn(head->hth_table, new_lensizeof(struct type)); \
353	0	if (!new_table) return -1; \
354	0	memset(new_table + head->hth_table_length, 0, \
355	0	(new_len - head->hth_table_length)sizeof(struct type)); \
356	0	for (b=0; b < head->hth_table_length; ++b) { \
357	0	struct type e, *pE; \
358	0	for (pE = &new_table[b], e = pE; e != NULL; e = pE) { \
359	0	b2 = HT_ELT_HASH_(e, field, hashfn) % new_len; \
360	0	if (b2 == b) { \
361	0	pE = &e->field.hte_next; \
362	0	} else { \
363	0	*pE = e->field.hte_next; \
364	0	e->field.hte_next = new_table[b2]; \
365	0	new_table[b2] = e; \
366	0	} \
367	0	} \
368	0	} \
369	0	head->hth_table = new_table; \
370	0	} \
371	0	head->hth_table_length = new_len; \
372	0	head->hth_prime_idx = prime_idx; \
373	0	head->hth_load_limit = new_load_limit; \
374	0	return 0; \
375	0	} \
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	0	{ \
381	0	if (head->hth_table) \
382	0	freefn(head->hth_table); \
383	0	name##_HT_INIT(head); \
384	0	} \
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	0	{ \
390	0	unsigned n, i; \
391	0	struct type *elm; \
392	0	if (!head->hth_table_length) { \
393	0	if (!head->hth_table && !head->hth_n_entries && \
394	0	!head->hth_load_limit && head->hth_prime_idx == -1) \
395	0	return 0; \
396	0	else \
397	0	return 1; \
398	0	} \
399	0	if (!head->hth_table \|\| head->hth_prime_idx < 0 \|\| \
400	0	!head->hth_load_limit) \
401	0	return 2; \
402	0	if (head->hth_n_entries > head->hth_load_limit) \
403	0	return 3; \
404	0	if (head->hth_table_length != name##_PRIMES[head->hth_prime_idx]) \
405	0	return 4; \
406	0	if (head->hth_load_limit != (unsigned)(load*head->hth_table_length)) \
407	0	return 5; \
408	0	for (n = i = 0; i < head->hth_table_length; ++i) { \
409	0	for (elm = head->hth_table[i]; elm; elm = elm->field.hte_next) { \
410	0	if (HT_ELT_HASH_(elm, field, hashfn) != hashfn(elm)) \
411	0	return 1000 + i; \
412	0	if ((HT_ELT_HASH_(elm, field, hashfn) % head->hth_table_length) != i) \
413	0	return 10000 + i; \
414	0	++n; \
415	0	} \
416	0	} \
417	0	if (n != head->hth_n_entries) \
418	0	return 6; \
419	0	return 0; \
420	0	}
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