uthash.h

gtk_server的源代码

               (head)->hh.tbl->ideal_chain_maxlen;                            \
            if ((head)->hh.tbl->buckets[(head)->hh.tbl->bkt_i].count          \
               !=  (head)->hh.tbl->ideal_chain_maxlen) {                      \
               HASH_OOPS("invalid bucket count %d, actual %d\n",              \
                (head)->hh.tbl->buckets[(head)->hh.tbl->bkt_i].count,         \
                (head)->hh.tbl->ideal_chain_maxlen);                          \
            }                                                                 \
        }                                                                     \
        if ((head)->hh.tbl->keylen != (head)->hh.tbl->num_items) {            \
            HASH_OOPS("invalid hh item count %d, actual %d\n",                \
                (head)->hh.tbl->num_items, (head)->hh.tbl->keylen );          \
        }                                                                     \
        /* traverse hh in app order; check next/prev integrity, count */      \
        (head)->hh.tbl->keylen = 0;   /* item counter */                      \
        (head)->hh.tbl->key = NULL;  /* app prev */                           \
        (head)->hh.tbl->thh =  &(head)->hh;                                   \
        while ((head)->hh.tbl->thh) {                                         \
           (head)->hh.tbl->keylen++;                                          \
           if ((head)->hh.tbl->key !=(char*)((head)->hh.tbl->thh->prev)) {    \
              HASH_OOPS("invalid prev %x, actual %x\n",                       \
                    (head)->hh.tbl->thh->prev,                                \
                    (head)->hh.tbl->key );                                    \
           }                                                                  \
           (head)->hh.tbl->key = ELMT_FROM_HH((head)->hh.tbl,                 \
                                              (head)->hh.tbl->thh);           \
           (head)->hh.tbl->thh = ( (head)->hh.tbl->thh->next ?                \
             (UT_hash_handle*)((char*)((head)->hh.tbl->thh->next) +           \
                               (head)->hh.tbl->hho)                           \
                                 : NULL );                                    \
        }                                                                     \
        if ((head)->hh.tbl->keylen != (head)->hh.tbl->num_items) {            \
            HASH_OOPS("invalid app item count %d, actual %d\n",               \
                (head)->hh.tbl->num_items, (head)->hh.tbl->keylen );          \
        }                                                                     \
    }                                                                         \
} while (0)
#else
#define HASH_FSCK(hh,head) 
#endif

/* When compiled with -DHASH_EMIT_KEYS, length-prefixed keys are emitted to 
 * the descriptor to which this macro is defined for tuning the hash function.
 * The app can #include <unistd.h> to get the prototype for write(2). */
#ifdef HASH_EMIT_KEYS
#define HASH_EMIT_KEY(hh,head,keyptr,fieldlen)                                \
    (head)->hh.tbl->keylen = fieldlen;                                        \
    write(HASH_EMIT_KEYS, &((head)->hh.tbl->keylen), sizeof(int));            \
    write(HASH_EMIT_KEYS, keyptr, fieldlen);          
#else 
#define HASH_EMIT_KEY(hh,head,keyptr,fieldlen)                    
#endif

/* default to Jenkins unless specified e.g. DHASH_FUNCTION=HASH_SAX */
#ifdef HASH_FUNCTION 
#define HASH_FCN HASH_FUNCTION
#else
#define HASH_FCN HASH_JEN
#endif

/* The Bernstein hash function, used in Perl prior to v5.6 */
#define HASH_BER(key,keylen,num_bkts,hash,bkt,i,j,k)                          \
  hash = 0;                                                                   \
  while (keylen--)  hash = (hash * 33) + *key++;                              \
  bkt = hash & (num_bkts-1);          


/* SAX/FNV/OAT/JEN hash functions are macro variants of those listed at 
 * http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx */
#define HASH_SAX(key,keylen,num_bkts,hash,bkt,i,j,k)                          \
  hash = 0;                                                                   \
  for(i=0; i < keylen; i++)                                                   \
      hash ^= (hash << 5) + (hash >> 2) + key[i];                             \
  bkt = hash & (num_bkts-1);          

#define HASH_FNV(key,keylen,num_bkts,hash,bkt,i,j,k)                          \
  hash = 2166136261UL;                                                        \
  for(i=0; i < keylen; i++)                                                   \
      hash = (hash * 16777619) ^ key[i];                                      \
  bkt = hash & (num_bkts-1);          
 
#define HASH_OAT(key,keylen,num_bkts,hash,bkt,i,j,k)                          \
  hash = 0;                                                                   \
  for(i=0; i < keylen; i++) {                                                 \
      hash += key[i];                                                         \
      hash += (hash << 10);                                                   \
      hash ^= (hash >> 6);                                                    \
  }                                                                           \
  hash += (hash << 3);                                                        \
  hash ^= (hash >> 11);                                                       \
  hash += (hash << 15);                                                       \
  bkt = hash & (num_bkts-1);          

#define HASH_JEN_MIX(a,b,c)                                                   \
{                                                                             \
  a -= b; a -= c; a ^= ( c >> 13 );                                           \
  b -= c; b -= a; b ^= ( a << 8 );                                            \
  c -= a; c -= b; c ^= ( b >> 13 );                                           \
  a -= b; a -= c; a ^= ( c >> 12 );                                           \
  b -= c; b -= a; b ^= ( a << 16 );                                           \
  c -= a; c -= b; c ^= ( b >> 5 );                                            \
  a -= b; a -= c; a ^= ( c >> 3 );                                            \
  b -= c; b -= a; b ^= ( a << 10 );                                           \
  c -= a; c -= b; c ^= ( b >> 15 );                                           \
}

#define HASH_JEN(key,keylen,num_bkts,hash,bkt,i,j,k)                          \
  hash = 0xfeedbeef;                                                          \
  i = j = 0x9e3779b9;                                                         \
  k = keylen;                                                                 \
  while (k >= 12) {                                                           \
    i +=    (key[0] + ( (unsigned)key[1] << 8 )                               \
        + ( (unsigned)key[2] << 16 )                                          \
        + ( (unsigned)key[3] << 24 ) );                                       \
    j +=    (key[4] + ( (unsigned)key[5] << 8 )                               \
        + ( (unsigned)key[6] << 16 )                                          \
        + ( (unsigned)key[7] << 24 ) );                                       \
    hash += (key[8] + ( (unsigned)key[9] << 8 )                               \
        + ( (unsigned)key[10] << 16 )                                         \
        + ( (unsigned)key[11] << 24 ) );                                      \
                                                                              \
     HASH_JEN_MIX(i, j, hash);                                                \
                                                                              \
     key += 12;                                                               \
     k -= 12;                                                                 \
  }                                                                           \
  hash += keylen;                                                             \
  switch ( k ) {                                                              \
     case 11: hash += ( (unsigned)key[10] << 24 );                            \
     case 10: hash += ( (unsigned)key[9] << 16 );                             \
     case 9:  hash += ( (unsigned)key[8] << 8 );                              \
     case 8:  j += ( (unsigned)key[7] << 24 );                                \
     case 7:  j += ( (unsigned)key[6] << 16 );                                \
     case 6:  j += ( (unsigned)key[5] << 8 );                                 \
     case 5:  j += key[4];                                                    \
     case 4:  i += ( (unsigned)key[3] << 24 );                                \
     case 3:  i += ( (unsigned)key[2] << 16 );                                \
     case 2:  i += ( (unsigned)key[1] << 8 );                                 \
     case 1:  i += key[0];                                                    \
  }                                                                           \
  HASH_JEN_MIX(i, j, hash);                                                   \
  bkt = hash & (num_bkts-1);          


/* key comparison function; return 0 if keys equal */
#define HASH_KEYCMP(a,b,len) memcmp(a,b,len) 

/* iterate over items in a known bucket to find desired item */
#define HASH_FIND_IN_BKT(tbl,hh,head,keyptr,keylen_in,out)                    \
out = TYPEOF(out)((head.hh_head) ? ELMT_FROM_HH(tbl,head.hh_head) : NULL);    \
while (out) {                                                                 \
    if (out->hh.keylen == keylen_in) {                                        \
        if ((HASH_KEYCMP(out->hh.key,keyptr,keylen_in)) == 0) break;          \
    }                                                                         \
    out= TYPEOF(out)((out->hh.hh_next) ?                                      \
                     ELMT_FROM_HH(tbl,out->hh.hh_next) : NULL);               \
}

/* add an item to a bucket  */
#define HASH_ADD_TO_BKT(hh,head,add)                                          \
 head.count++;                                                                \
 add->hh.hh_next = head.hh_head;                                              \
 add->hh.hh_prev = NULL;                                                      \
 if (head.hh_head) head.hh_head->hh_prev = &add->hh;                          \
 head.hh_head=&add->hh;                                                       \
 if (head.count >= ((head.expand_mult+1) * HASH_BKT_CAPACITY_THRESH)          \
     && add->hh.tbl->noexpand != 1) {                                         \
       HASH_EXPAND_BUCKETS(add->hh.tbl)                                       \
 }

/* remove an item from a given bucket */
#define HASH_DEL_IN_BKT(hh,head,hh_del)                                       \
    (head).count--;                                                           \
    if ((head).hh_head == hh_del) {                                           \
      (head).hh_head = hh_del->hh_next;                                       \
    }                                                                         \
    if (hh_del->hh_prev) {                                                    \
        hh_del->hh_prev->hh_next = hh_del->hh_next;                           \
    }                                                                         \
    if (hh_del->hh_next) {                                                    \
        hh_del->hh_next->hh_prev = hh_del->hh_prev;                           \
    }                                                                

/* Bucket expansion has the effect of doubling the number of buckets
 * and redistributing the items into the new buckets. Ideally the
 * items will distribute more or less evenly into the new buckets
 * (the extent to which this is true is a measure of the quality of
 * the hash function as it applies to the key domain). 
 * 
 * With the items distributed into more buckets, the chain length
 * (item count) in each bucket is reduced. Thus by expanding buckets
 * the hash keeps a bound on the chain length. This bounded chain 
 * length is the essence of how a hash provides constant time lookup.
 * 
 * The calculation of tbl->ideal_chain_maxlen below deserves some
 * explanation. First, keep in mind that we're calculating the ideal
 * maximum chain length based on the *new* (doubled) bucket count.
 * In fractions this is just n/b (n=number of items,b=new num buckets).
 * Since the ideal chain length is an integer, we want to calculate 
 * ceil(n/b). We don't depend on floating point arithmetic in this
 * hash, so to calculate ceil(n/b) with integers we could write
 * 
 *      ceil(n/b) = (n/b) + ((n%b)?1:0)
 * 
 * and in fact a previous version of this hash did just that.
 * But now we have improved things a bit by recognizing that b is
 * always a power of two. We keep its base 2 log handy (call it lb),
 * so now we can write this with a bit shift and logical AND:
 * 
 *      ceil(n/b) = (n>>lb) + ( (n & (b-1)) ? 1:0)
 * 
 * Actually bucket expansion is so expensive that this is a micro-