lib-src/hash/qa.cc

   1 //////////////////////////////////////////////////////////////////////////////
   2 // NOTICE:
   3 //
   4 // ADLib, Prop and their related set of tools and documentation are in the
   5 // public domain.   The author(s) of this software reserve no copyrights on
   6 // the source code and any code generated using the tools.  You are encouraged
   7 // to use ADLib and Prop to develop software, in both academic and commercial
   8 // settings, and are free to incorporate any part of ADLib and Prop into
   9 // your programs.
  10 //
  11 // Although you are under no obligation to do so, we strongly recommend that
  12 // you give away all software developed using our tools.
  13 //
  14 // We also ask that credit be given to us when ADLib and/or Prop are used in
  15 // your programs, and that this notice be preserved intact in all the source
  16 // code.
  17 //
  18 // This software is still under development and we welcome any suggestions
  19 // and help from the users.
  20 //
  21 // Allen Leung
  22 // 1994
  23 //////////////////////////////////////////////////////////////////////////////
  24
  25 #include <assert.h>
  26 #include <stdio.h>
  27 #include <AD/hash/chash.h>   // coalesced hashing hash table
  28 #include <AD/hash/dchash.h>  // direct chaining hash table
  29 #include <AD/hash/dhash.h>   // double hashing hash table
  30 #include <AD/hash/lhash.h>   // linear probing hash table
  31 #include <AD/hash/ohash.h>   // ordered hashing hash table
  32 #include <AD/hash/chash2.h>   // coalesced hashing hash table
  33 #include <AD/hash/dchash2.h>  // direct chaining hash table
  34 #include <AD/hash/dhash2.h>   // double hashing hash table
  35 #include <AD/hash/lhash2.h>   // linear probing hash table
  36 #include <AD/hash/ohash2.h>   // ordered hashing hash table
  37
  38 typedef const char * string;
  39
  40 int main()
  41 {
  42    CHashTable<string,string>  a(10);
  43    DCHashTable<string,string> b(10,2);
  44    DHashTable<string,string>  c(10);
  45    LHashTable<string,string>  d(10);
  46    OHashTable<string,string>  e(10);
  47
  48    static struct { string first, last; } authors[] =
  49    {  { "Edgar",    "Doctorow"   },
  50       { "James",    "Joyce"      },
  51       { "Vladimir", "Nabokov"    },
  52       { "Pablo",    "Neruda",    },
  53       { "William",  "Faulkner",  },
  54       { "Ernest",   "Hemingway"  },
  55       { "Gabriel",  "Garcia Marquez" },
  56       { "Isabel",   "Allende" },
  57       { "Thomas",   "Pynchon" },
  58       { "Kurt",     "Vonnegurt" },
  59       { "Ken",      "Casey" },
  60       { "Norman",   "Mailer" },
  61    };
  62
  63    static struct { string first, last; } old_authors[] =
  64    {  { "William", "Shakespear" },
  65       { "Edgar",   "Poe" },
  66       { "Thomas",  "Jefferson" }
  67    };
  68
  69    int size = sizeof(authors)/sizeof(authors[0]);
  70    int i, n;
  71
  72    for (i = 0; i < sizeof(old_authors)/sizeof(old_authors[0]); i++) {
  73       a.insert(old_authors[i].first, old_authors[i].last);
  74       b.insert(old_authors[i].first, old_authors[i].last);
  75       c.insert(old_authors[i].first, old_authors[i].last);
  76       d.insert(old_authors[i].first, old_authors[i].last);
  77       e.insert(old_authors[i].first, old_authors[i].last);
  78    }
  79
  80    for (i = 0; i < sizeof(authors)/sizeof(authors[0]); i++) {
  81       a.insert(authors[i].first, authors[i].last);
  82       b.insert(authors[i].first, authors[i].last);
  83       c.insert(authors[i].first, authors[i].last);
  84       d.insert(authors[i].first, authors[i].last);
  85       e.insert(authors[i].first, authors[i].last);
  86    }
  87
  88    Ix ix;
  89    printf("[Coalesced hashing (size = %d, capacity = %d)]\n", a.size(), a.capacity());
  90    for (n = 0, ix = a.first(); ix; ix = a.next(ix), n++) {
  91       printf("Name %s %s\n", a.key(ix), a.value(ix));
  92       assert(a.lookup(a.key(ix)));
  93    }
  94    assert(a.size() == n);
  95
  96    printf("[Direct chaining (size = %d, capacity = %d)]\n", e.size(), e.capacity());
  97    for (n = 0, ix = b.first(); ix; ix = b.next(ix), n++) {
  98       printf("Name %s %s\n", b.key(ix), b.value(ix));
  99       assert(b.lookup(b.key(ix)));
 100    }
 101    assert(b.size() == n);
 102
 103    printf("[Double hashing (size = %d, capacity = %d)]\n", a.size(), a.capacity());
 104    for (n = 0, ix = c.first(); ix; ix = c.next(ix), n++) {
 105       printf("Name %s %s\n", c.key(ix), c.value(ix));
 106       assert(c.lookup(c.key(ix)));
 107    }
 108    assert(c.size() == n);
 109
 110    printf("[Linear hashing (size = %d, capacity = %d)]\n", b.size(), b.capacity());
 111    for (n = 0, ix = d.first(); ix; ix = d.next(ix), n++) {
 112       printf("Name %s %s\n", d.key(ix), d.value(ix));
 113       assert(d.lookup(d.key(ix)));
 114    }
 115    assert(d.size() == n);
 116
 117    printf("[Ordered hashing (size = %d, capacity = %d)]\n", c.size(), c.capacity());
 118    for (n = 0, ix = e.first(); ix; ix = e.next(ix), n++) {
 119       printf("Name %s %s\n", e.key(ix), e.value(ix));
 120       assert(e.lookup(e.key(ix)));
 121    }
 122    assert(e.size() == n);
 123
 124    assert(a.size() == size);
 125    assert(b.size() == size);
 126    assert(c.size() == size);
 127    assert(d.size() == size);
 128    assert(e.size() == size);
 129
 130    printf("OK\n");
 131    return 0;
 132 }