initial
[prop.git] / lib-src / hash / qa.cc
blob3d148c028440dd683df1ff85f2e944d9a17b5b2e
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.
11 // Although you are under no obligation to do so, we strongly recommend that
12 // you give away all software developed using our tools.
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.
18 // This software is still under development and we welcome any suggestions
19 // and help from the users.
21 // Allen Leung
22 // 1994
23 //////////////////////////////////////////////////////////////////////////////
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
38 typedef const char * string;
40 int main()
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);
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" },
63 static struct { string first, last; } old_authors[] =
64 { { "William", "Shakespear" },
65 { "Edgar", "Poe" },
66 { "Thomas", "Jefferson" }
69 int size = sizeof(authors)/sizeof(authors[0]);
70 int i, n;
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);
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);
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)));
94 assert(a.size() == n);
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)));
101 assert(b.size() == n);
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)));
108 assert(c.size() == n);
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)));
115 assert(d.size() == n);
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)));
122 assert(e.size() == n);
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);
130 printf("OK\n");
131 return 0;