Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Jun 25th, 2012  |  syntax: C  |  size: 2.74 KB  |  views: 195  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include <stdlib.h>
  2. #include <assert.h>
  3.  
  4. typedef struct Tuple Tuple;
  5. typedef struct Htab Htab;
  6. typedef unsigned long hash_t;
  7.  
  8. struct Tuple {
  9.         int     n;
  10.         int     p;
  11.         int     q;
  12. };
  13.  
  14. struct Htab {
  15.         size_t  sz;
  16.         size_t  count;
  17.         hash_t  *hashes;
  18.         Tuple   *keys;
  19.         int     *vals;
  20. };
  21.  
  22. void hput(Htab *ht, Tuple *k, int v);
  23. int hget(Htab *ht, Tuple *k, int *v);
  24. Htab *hnew(void);
  25.  
  26. static hash_t hash(Tuple *t)
  27. {
  28.         hash_t h;
  29.         /* dumb, crappy hash function.
  30.          * Something better is left as an
  31.          * exercise to the reader */
  32.         h = t->n ^ t->p << 8 ^ t->q << 16;
  33.         if (!h)
  34.                 h++;
  35.         return h;
  36. }
  37.  
  38. static int eq(Tuple *a, Tuple *b)
  39. {
  40.         return a->n == b->n && a->p == b->p && a->q == b->q;
  41. }
  42.  
  43. static void grow(Htab *ht)
  44. {
  45.         hash_t  *oldh;
  46.         Tuple   *oldk;
  47.         int     *oldv;
  48.         size_t  oldsz, i;
  49.  
  50.         oldh = ht->hashes;
  51.         oldk = ht->keys;
  52.         oldv = ht->vals;
  53.         oldsz = ht->sz;
  54.  
  55.         ht->count = 0;
  56.         ht->sz = oldsz * 2;
  57.         ht->hashes = calloc(sizeof(hash_t), ht->sz);
  58.         ht->keys = calloc(sizeof(Tuple), ht->sz);
  59.         ht->vals = calloc(sizeof(int), ht->sz);
  60.         assert(ht->hashes != NULL && ht->keys != NULL && ht->vals != NULL);
  61.  
  62.         for (i = 0; i < oldsz; i++)
  63.                 if (oldh[i] != 0)
  64.                         hput(ht, &oldk[i], oldv[i]);
  65.         free(oldh);
  66.         free(oldk);
  67.         free(oldv);
  68. }
  69.  
  70. Htab *hnew()
  71. {
  72.         Htab *ht;
  73.  
  74.         ht = malloc(sizeof(Htab));
  75.         if (!ht)
  76.                 abort();
  77.         ht->sz = 16; /* or some other reasonable size */
  78.         ht->count = 0;
  79.         ht->hashes = calloc(sizeof(hash_t), ht->sz);
  80.         ht->keys = calloc(sizeof(Tuple), ht->sz);
  81.         ht->vals = calloc(sizeof(int), ht->sz);
  82.         assert(ht->hashes != NULL && ht->keys != NULL && ht->vals != NULL);
  83.  
  84.         return ht;
  85. }
  86.  
  87. void hfree(Htab *ht)
  88. {
  89.         free(ht->hashes);
  90.         free(ht->keys);
  91.         free(ht->vals);
  92.         free(ht);
  93. }
  94.  
  95. void hput(Htab *ht, Tuple *k, int v)
  96. {
  97.         size_t i, di;
  98.         hash_t h;
  99.  
  100.         di = 0;
  101.         h = hash(k);
  102.         i = h % ht->sz;
  103.         while (ht->hashes[i]) {
  104.                 if (ht->hashes[i] == h && eq(k, &ht->keys[i]))
  105.                         break;
  106.                 di++;
  107.                 i = (h + di) % ht->sz;
  108.         }
  109.  
  110.         ht->hashes[i] = h;
  111.         ht->keys[i] = *k;
  112.         ht->vals[i] = v;
  113.         ht->count++;
  114.         if (ht->sz < ht->count*2)
  115.                 grow(ht);
  116. }
  117.  
  118. int hget(Htab *ht, Tuple *k, int *v)
  119. {
  120.         size_t i, di;
  121.         hash_t h;
  122.  
  123.         di = 0;
  124.         h = hash(k);
  125.         i = h % ht->sz;
  126.         do {
  127.                 while (ht->hashes[i] && ht->hashes[i] != h) {
  128.                         di++;
  129.                         i = (h + di) % ht->sz;
  130.                 }
  131.                 if (!ht->hashes[i])
  132.                         return 0;
  133.         } while (!eq(k, &ht->keys[i]));
  134.         *v = ht->vals[i];
  135.         return 1;
  136. }
  137.  
  138. int main(int argc, char **argv)
  139. {
  140.         Tuple tu[] = {
  141.                 {1,1,2},
  142.                 {2,1,3},
  143.                 {1,1,0},
  144.                 {1,1,1},
  145.         };
  146.         Htab *ht;
  147.         int v;
  148.  
  149.         ht = hnew();
  150.         hput(ht, &tu[0], 3);
  151.         hput(ht, &tu[1], 2);
  152.         hput(ht, &tu[2], 1);
  153.         if (!hget(ht, &tu[0], &v))
  154.                 assert(v == 3);
  155.         if (!hget(ht, &tu[1], &v))
  156.                 assert(v == 2);
  157.         if (!hget(ht, &tu[2], &v))
  158.                 assert(v == 1);
  159.         assert(!hget(ht, &tu[3], &v));
  160.         return 0;
  161. }