uthash.h

在LINUX下实现对哈希表的操作

out = (head.hh_head) ? (head.hh_head->elmt) : NULL;                  \
while (out) {                                                        \
    if (out->hh.keylen == keylen_in) {                               \
        if ((HASH_KEYCMP(out->hh.key,keyptr,keylen_in)) == 0) break; \
    }                                                                \
    out= (out->hh.hh_next) ? (out->hh.hh_next->elmt) : 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,delptr)                              \
    (head).count--;                                                  \
    if ((head).hh_head->elmt == delptr) {                            \
      (head).hh_head = delptr->hh.hh_next;                           \
    }                                                                \
    if (delptr->hh.hh_prev) {                                        \
        delptr->hh.hh_prev->hh_next = delptr->hh.hh_next;            \
    }                                                                \
    if (delptr->hh.hh_next) {                                        \
        delptr->hh.hh_next->hh_prev = delptr->hh.hh_prev;            \
    }                                                                

#define HASH_EXPAND_BUCKETS(tbl)                                     \
    tbl->new_buckets = (UT_hash_bucket*)uthash_bkt_malloc(           \
             2 * tbl->num_buckets * sizeof(struct UT_hash_bucket));  \
    if (!tbl->new_buckets) { uthash_fatal( "out of memory"); }       \
    memset(tbl->new_buckets, 0,                                      \
            2 * tbl->num_buckets * sizeof(struct UT_hash_bucket));   \
    tbl->bkt_ideal= (tbl->num_items /  tbl->num_buckets*2) +         \
                   ((tbl->num_items % (tbl->num_buckets*2)) ? 1 : 0);\
    tbl->sum_of_deltas = 0;                                          \
    for(tbl->bkt_i = 0; tbl->bkt_i < tbl->num_buckets; tbl->bkt_i++) \
    {                                                                \
        tbl->hh = tbl->buckets[ tbl->bkt_i ].hh_head;                \
        while (tbl->hh) {                                            \
           tbl->hh_nxt = tbl->hh->hh_next;                           \
           tbl->key = tbl->hh->key;                                  \
           tbl->keylen = tbl->hh->keylen;                            \
           HASH_FCN(tbl->key,tbl->keylen,tbl->num_buckets*2,tbl->bkt,\
                   tbl->i,tbl->j,tbl->k);                            \
           tbl->newbkt = &(tbl->new_buckets[ tbl->bkt ]);            \
           if (++(tbl->newbkt->count) > tbl->bkt_ideal) {            \
             tbl->sum_of_deltas++;                                   \
             tbl->newbkt->expand_mult = tbl->newbkt->count /         \
                                        tbl->bkt_ideal;              \
           }                                                         \
           tbl->hh->hh_prev = NULL;                                  \
           tbl->hh->hh_next = tbl->newbkt->hh_head;                  \
           if (tbl->newbkt->hh_head) tbl->newbkt->hh_head->hh_prev = \
                tbl->hh;                                             \
           tbl->newbkt->hh_head = tbl->hh;                           \
           tbl->hh = tbl->hh_nxt;                                    \
        }                                                            \
    }                                                                \
    tbl->num_buckets *= 2;                                           \
    uthash_bkt_free( tbl->buckets );                                 \
    tbl->buckets = tbl->new_buckets;                                 \
    tbl->new_hash_q = 1-(tbl->sum_of_deltas * 1.0 / tbl->num_items); \
    if (tbl->hash_q < 0.5 && tbl->new_hash_q < 0.5) {                \
        tbl->noexpand=1;                                             \
        uthash_noexpand_fyi(tbl);                                    \
    }                                                                \
    tbl->hash_q = tbl->new_hash_q;                                   \
    uthash_expand_fyi(tbl);                                         


/* This is an adaptation of Simon Tatham's O(n log(n)) mergesort */
#define HASH_SORT(head,cmpfcn)                                                 \
  if (head) {                                                                  \
      (head)->hh.tbl->insize = 1;                                              \
      (head)->hh.tbl->looping = 1;                                             \
      (head)->hh.tbl->list = &((head)->hh);                                    \
      while ((head)->hh.tbl->looping) {                                        \
          (head)->hh.tbl->p = (head)->hh.tbl->list;                            \
          (head)->hh.tbl->list = NULL;                                         \
          (head)->hh.tbl->tale = NULL;                                         \
          (head)->hh.tbl->nmerges = 0;                                         \
          while ((head)->hh.tbl->p) {                                          \
              (head)->hh.tbl->nmerges++;                                       \
              (head)->hh.tbl->q = (head)->hh.tbl->p;                           \
              (head)->hh.tbl->psize = 0;                                       \
              for ( (head)->hh.tbl->i = 0;                                     \
                    (head)->hh.tbl->i  < (head)->hh.tbl->insize;               \
                    (head)->hh.tbl->i++ ) {                                    \
                  (head)->hh.tbl->psize++;                                     \
                  (head)->hh.tbl->q = (((head)->hh.tbl->q->next) ?             \
                      ((void*)(((long)((head)->hh.tbl->q->next)) +             \
                      (head)->hh.tbl->hho)) : NULL);                           \
                  if (! ((head)->hh.tbl->q) ) break;                           \
              }                                                                \
              (head)->hh.tbl->qsize = (head)->hh.tbl->insize;                  \
              while (((head)->hh.tbl->psize > 0) ||                            \
                      (((head)->hh.tbl->qsize > 0) && (head)->hh.tbl->q )) {   \
                  if ((head)->hh.tbl->psize == 0) {                            \
                      (head)->hh.tbl->e = (head)->hh.tbl->q;                   \
                      (head)->hh.tbl->q = (((head)->hh.tbl->q->next) ?         \
                          ((void*)(((long)((head)->hh.tbl->q->next)) +         \
                          (head)->hh.tbl->hho)) : NULL);                       \
                      (head)->hh.tbl->qsize--;                                 \
                  } else if ( ((head)->hh.tbl->qsize == 0) ||                  \
                             !((head)->hh.tbl->q) ) {                          \
                      (head)->hh.tbl->e = (head)->hh.tbl->p;                   \
                      (head)->hh.tbl->p = (((head)->hh.tbl->p->next) ?         \
                          ((void*)(((long)((head)->hh.tbl->p->next)) +         \
                          (head)->hh.tbl->hho)) : NULL);                       \
                      (head)->hh.tbl->psize--;                                 \
                  } else if ((                                                 \
                      cmpfcn((head)->hh.tbl->p->elmt,(head)->hh.tbl->q->elmt)) \
                          <= 0) {                                              \
                      (head)->hh.tbl->e = (head)->hh.tbl->p;                   \
                      (head)->hh.tbl->p = (((head)->hh.tbl->p->next) ?         \
                          ((void*)(((long)((head)->hh.tbl->p->next)) +         \
                          (head)->hh.tbl->hho)) : NULL);                       \
                      (head)->hh.tbl->psize--;                                 \
                  } else {                                                     \
                      (head)->hh.tbl->e = (head)->hh.tbl->q;                   \
                      (head)->hh.tbl->q = (((head)->hh.tbl->q->next) ?         \
                          ((void*)(((long)((head)->hh.tbl->q->next)) +         \
                                   (head)->hh.tbl->hho)) : NULL);              \
                      (head)->hh.tbl->qsize--;                                 \
                  }                                                            \
                  if ( (head)->hh.tbl->tale ) {                                \
                      (head)->hh.tbl->tale->next = (((head)->hh.tbl->e) ?      \
                               ((head)->hh.tbl->e->elmt) : NULL);              \
                  } else {                                                     \
                      (head)->hh.tbl->list = (head)->hh.tbl->e;                \
                  }                                                            \
                  (head)->hh.tbl->e->prev = (((head)->hh.tbl->tale) ?          \
                                 ((head)->hh.tbl->tale->elmt) : NULL);         \
                  (head)->hh.tbl->tale = (head)->hh.tbl->e;                    \
              }                                                                \
              (head)->hh.tbl->p = (head)->hh.tbl->q;                           \
          }                                                                    \
          (head)->hh.tbl->tale->next = NULL;                                   \
          if ( (head)->hh.tbl->nmerges <= 1 ) {                                \
              (head)->hh.tbl->looping=0;                                       \
              (head)->hh.tbl->tail = (head)->hh.tbl->tale;                     \
              (head) = (head)->hh.tbl->list->elmt;                             \
          }                                                                    \
          (head)->hh.tbl->insize *= 2;                                         \
      }                                                                        \
      HASH_FSCK(head);                                                         \
 }

typedef struct UT_hash_bucket {
   struct UT_hash_handle *hh_head;
   unsigned count;  
   unsigned expand_mult;  
} UT_hash_bucket;

typedef struct UT_hash_table {
   UT_hash_bucket *buckets;
   unsigned num_buckets;
   unsigned num_items;
   int noexpand;  /* when set, inhibits expansion of buckets for this hash  */
   double hash_q; /* measures the evenness of the items among buckets (0-1) */
   struct UT_hash_handle *tail; /* tail hh in app order, for fast append    */
   char *name;    /* macro-stringified name of list head, used by libut     */
   int hho;
   /* scratch */
   unsigned bkt;
   char *key;
   int keylen;
   unsigned i,j,k;
   /* scratch for bucket expansion */
   UT_hash_bucket *new_buckets, *newbkt;
   struct UT_hash_handle *hh, *hh_nxt;
   unsigned bkt_i, bkt_ideal, sum_of_deltas;
   double new_hash_q;
   /* scratch for sort */
   int looping,nmerges,insize,psize,qsize;
   struct UT_hash_handle *p, *q, *e, *list, *tale;
   
} UT_hash_table;


typedef struct UT_hash_handle {
   struct UT_hash_table *tbl;
   void *elmt;                       /* ptr to enclosing element       */
   void *prev; //一个项的前一个指针                      /* prev element in app order      */
   void *next;  //一项的后一个指针                     /* next element in app order      */、

   //指向这一项的上下一项
   struct UT_hash_handle *hh_prev;   /* previous hh in bucket order    */
   struct UT_hash_handle *hh_next;   /* next hh in bucket order        */
   void *key;                        /* ptr to enclosing struct's key  */
   int keylen;                       /* enclosing struct's key len     */
} UT_hash_handle;

#endif /* UTHASH_H */