Extendible Hashing Implementation

1. /*
2.  *      ExtendedHashing.cpp
3.  *      
4.  *      Copyright 2009 roKB <rooparambhakar@gmail.com>
5.  *      
6.  *      This program is free software; you can redistribute it and/or modify
7.  *      it under the terms of the GNU General Public License as published by
8.  *      the Free Software Foundation; either version 2 of the License, or
9.  *      (at your option) any later version.
10.  *      
11.  *      This program is distributed in the hope that it will be useful,
12.  *      but WITHOUT ANY WARRANTY; without even the implied warranty of
13.  *      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14.  *      GNU General Public License for more details.
15.  *      
16.  *      You should have received a copy of the GNU General Public License
17.  *      along with this program; if not, write to the Free Software
18.  *      Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
19.  *      MA 02110-1301, USA.
20.  */
21.  
22. #include <string>
23. #include <cassert>
24. #include <iostream>
25. #include <cstdio>
26. #include <cstdlib>
27.  
28. int hashCode(std::string const & key)
29. /*
30.  * calculates the hash of key using polynomial expansion,
31.  * with x = 37
32.  */
33. {
34.   const long x = 41L;
35.   int n = key.length();
36.   long value = 0L;
37.   while( n-- > 0 ) {
38.     value *= x;   value += key[n];
39.   }
40.   return static_cast<int>(value);
41. }
42.  
43. // ------------------------------------------------------------------------
44. // ------------------------------------------------------------------------
45. struct Student
46. {
47.   std::string entryNo;
48.   std::string name;
49. };
50.  
51. std::ostream& operator << (std::ostream& out, Student& s) {
52.   out << s.entryNo << " : " << s.name;
53.   return out;
54. }
55. // ------------------------------------------------------------------------
56. // ------------------------------------------------------------------------
57.  
58.  
59. struct Node
60. /* sentinal nodes of linked list */
61. {
62.   Node *next;
63. };
64.  
65. struct Pair {
66.   int first;
67.   Student *second;
68.  
69.   ~Pair() {
70.     if(second != NULL)
71.       delete second;
72.   }
73. };
74.  
75. struct InternalNode : public Node
76. /* internal nodes of linked list */
77. {
78.   Pair *element;
79.  
80.   ~InternalNode() {
81.     delete element;
82.   }
83. };
84.  
85. class LinkedList
86. /*
87.  * buckets in hash table
88.  */
89. {
90. public:
91.   LinkedList() {
92.     head = new Node();
93.     head->next = NULL;
94.   }
95.   ~LinkedList() {
96.     del(head);
97.   }
98.   void insert(Student & elem, int hashkey) {
99.     // create hash, data pair
100.     Pair *data = new Pair();
101.     data->first = hashkey;
102.     data->second = &elem;
103.     // create node in list
104.     InternalNode *temp = new InternalNode();
105.     temp->next = head->next;
106.     temp->element = data;
107.     head->next = temp;
108.   }
109.   Student* search(int hashkey) {
110.     Node *current = head->next;
111.     while(current != NULL) {
112.       if(static_cast<InternalNode*>(current)->element->first == hashkey)
113.         return static_cast<InternalNode*>(current)->element->second;
114.       current = current->next;
115.     }
116.     return NULL;
117.   }
118.   void remove(int hashkey) {
119.     Node *current = head->next;
120.     Node *parent = head;
121.     while(current != NULL) {
122.       if(static_cast<InternalNode*>(current)->element->first == hashkey) {
123.         // fix links in list then remove and return
124.         parent->next = current->next;
125.         current->next = NULL;
126.         del(current);
127.         return;
128.       }
129.       parent = current;
130.       current = current->next;
131.     }
132.   }
133.   void removeAll() {
134.     del(head->next);
135.     head->next = NULL;
136.   }
137.   void print(){
138.     InternalNode *current = static_cast<InternalNode*>(head->next);
139.     int i = 1;
140.     while(current != NULL) {
141.       std::cout << i << " : hashkey(0x" << std::hex << static_cast<unsigned int>( current->element->first ) << ") <" << *(current->element->second) << ">" << std::endl;
142.       current = static_cast<InternalNode*>(current->next);
143.       ++i;
144.     }
145.   }
146.   Node *getList() {
147.     return head->next;
148.   }
149. private:
150.   void del(Node *node) {
151.     if(node == NULL)
152.       return;
153.      
154.     del(node->next);
155.     delete node;
156.   }
157.   Node *head;
158. };
159.  
160. class Bucket
161. /*
162.  * uses LinkedList for storage
163.  * bucket overflow and underflow is left for xtendedHashing functions
164.  * they should check for underflow and overflow in bucket, otherwise
165.  * program will terminate
166.  */
167. {
168. public:
169.   Bucket(int c, int s = 0) : sig_bits(s), cap(c), sz(0), code(0), root(false) {
170.     data = new LinkedList();
171.   }
172.   ~Bucket() {
173.     delete data;
174.   }
175.   int capacity() {
176.     return cap;
177.   }
178.   int size() {
179.     return sz;
180.   }
181.   void insert(Student& elem, int hashkey) {
182.     data->insert(elem, hashkey);
183.     ++sz;
184.     if(root)
185.       return;
186.     assert( ( size() <= capacity() ) );
187.   }
188.   Student* search(int hashkey) {
189.     return data->search(hashkey);
190.   }
191.   void remove(int hashkey) {
192.     if(search(hashkey) != NULL)
193.       --sz;
194.     data->remove(hashkey);
195.     assert( (size() >= 0) );
196.   }
197.   void emptyBucket() {
198.     data->removeAll();
199.     sig_bits = 0;
200.     sz = 0;
201.   }
202.   bool isEmpty() {
203.     return size() == 0;
204.   }
205.   void print() {
206.     std::cout << "----- <BUCKET (";
207.     printcode();
208.     std::cout << ") > -----" << std::endl;
209.     std::cout << "SIG_BITS : " << sig_bits << std::endl;
210.     data->print();
211.     std::cout << std::endl;
212.   }
213.   Node* getList() {
214.     return data->getList();
215.   }
216.   int getSIG_BITS() {
217.     return sig_bits;
218.   }
219.   void setSIG_BITS(int s) {
220.     sig_bits = s;
221.     assert( (sig_bits >= 0) );
222.   }
223.   void setCODE(int c) {
224.     code = c;
225.   }
226.   void setROOT(bool state) {
227.     root = state;
228.   }
229. private:
230.   void printcode() {
231.     int length = sig_bits;
232.     int temp = code;
233.     while(length-- > 0) {
234.       std::cout << temp%2;
235.       temp >>= 1;
236.     }
237.   }
238.   LinkedList *data;
239.   int sig_bits;
240.   int cap;
241.   int sz;
242.   int code;
243.   bool root;
244. };
245.  
246. struct TrieNode
247. {
248.   Bucket *page;
249.   TrieNode *next[2];
250.   TrieNode *parent;
251.  
252.   ~TrieNode() {
253.     if(page != NULL)
254.       delete page;
255.   }
256. };
257.  
258. class HashTable
259. /*
260.  * at last we are at the implementation of Extendible-hashTable ^v^
261.  * uses tries index for bucket lookup
262.  * "now is the time to show your coding skills rrc"
263.  */
264. {
265. public:
266.   HashTable(int buk = DFL_BUCKET_SIZE) : bucket_size(buk) {
267.     sig_bits = 0;
268.     //root = false;
269.     index = new TrieNode();
270.     index->page = new Bucket(bucket_size, sig_bits);
271.     index->next[0] = NULL;
272.     index->next[1] = NULL;
273.     index->parent = NULL;
274.     no_of_buckets = 1;
275.   }
276.   ~HashTable() {
277.     del(index);
278.   }
279.   Student* search(std::string number) {
280.     int code;
281.     int hashkey = hashCode(number);
282.     TrieNode *node = findNode(hashkey, &code);
283.     return node->page->search(hashkey);
284.   }
285.   void insert(Student stu) {
286.     Student & st = *new Student();
287.     st.name = stu.name;
288.     st.entryNo = stu.entryNo;
289.     int hashkey = hashCode(st.entryNo);
290.     int code;
291.     TrieNode *node = findNode(hashkey, &code);
292.     Bucket *page = node->page;
293.     //if(root || page->size()+1 <= page->capacity())
294.     if(page->size()+1 <= page->capacity())
295.     {
296.       // insert in bucket
297.       // page->setROOT(root);
298.       page->insert(st, hashkey);
299.       // page->setROOT(false);
300.       return;
301.     } else {    // bucket is full, make a new bucket
302.       // step 7
303.       Bucket *newPage = new Bucket(bucket_size);
304.       no_of_buckets++;
305.       // step 8
306.       LinkedList *Q = new LinkedList();
307.       InternalNode *current = static_cast<InternalNode*>( page->getList() );
308.       while(current != NULL) {
309.         Q->insert(*(current->element->second), current->element->first);
310.         current = static_cast<InternalNode*>(current->next);
311.       }
312.       Q->insert(st, hashkey);
313.       // step 9
314.       int oldD = page->getSIG_BITS();
315.       int MASK = 1 << oldD;
316.       newPage->setSIG_BITS(oldD + 1);
317.       // step 10
318.       page->emptyBucket();
319.       page->setSIG_BITS(oldD + 1);
320.       if(oldD+1 > sig_bits){
321.         ++sig_bits;
322.       }
323.         node->page = NULL;
324.         TrieNode *left = new TrieNode();
325.         TrieNode *right = new TrieNode();
326.         node->next[0] = left;
327.         node->next[1] = right;
328.         left->page = page;
329.         right->page = newPage;
330.         left->next[0] = left->next[1] = NULL; left->parent = node;
331.         right->next[0] = right->next[1] = NULL; right->parent = node;
332.         left->page->setCODE(code);
333.         right->page->setCODE(code | MASK);
334.  
335.       current = static_cast<InternalNode*>( Q->getList() );
336.       // root = true;
337.       while(current != NULL) {
338.         insert( *(current->element->second) );
339.         current = static_cast<InternalNode*>( current->next );
340.       }
341.       // root = false;
342.     }
343.   }
344.   void remove(std::string number){
345.     int hashkey = hashCode(number);
346.     int code;
347.     TrieNode *node = findNode(hashkey, &code);
348.     Bucket *page = node->page;
349.     if(page->search(hashkey) == NULL)
350.       return;
351.     page->remove(hashkey);
352.     if(page->size() == 0 && node->parent != NULL)
353.     {
354.       TrieNode *parent = node->parent;
355.       TrieNode *sibling = (parent->next[0] == node)?
356.             (parent->next[1]) : (parent->next[0]);
357.       if(sibling->next[0] != NULL || sibling->next[1] != NULL)
358.         return;
359.      
360.       no_of_buckets--;
361.       parent->page = sibling->page;
362.       sibling->page = NULL;
363.       parent->next[0] = NULL;
364.       parent->next[1] = NULL;
365.       del(node);
366.       del(sibling);
367.       parent->page->setSIG_BITS(parent->page->getSIG_BITS() - 1);
368.       int MASK = 1 << parent->page->getSIG_BITS();
369.       MASK -= 1;
370.       code &= MASK;
371.       parent->page->setCODE(code);
372.       sig_bits = max_bits(index);
373.     }
374.   }
375.   void print() {
376.     std::cout << "-----------------------------------------" << std::endl;
377.     std::cout << "bucket.capacity : " << bucket_size << "\t|||\t";
378.     std::cout << "number ( buckets ) : " << no_of_buckets << "\t|||\t";
379.     std::cout << "max sig_bits : " << sig_bits << std::endl;
380.     int total = printNode(index);
381.     std::cout << "-----------------------------------------" << std::endl;
382.     std::cout << "elements in hashtable : " << total << std::endl;
383.     std::cout << "-----------------------------------------" << std::endl;
384.   }
385. private:
386.   TrieNode* findNode(int hashkey, int *const code)
387.   // using lower sig_bits of hashCode to calculate key
388.   {
389.     int d = 1;  // mask for calculating key from k
390.     d <<= sig_bits;
391.     d -= 1;   // all ones
392.     int key = hashkey & d;
393.     *code = 0;
394.     int length = 0;
395.     TrieNode *current = index;
396.     while(current != NULL) {
397.       if(current->page != NULL)
398.         return current;
399.       if(current->next[key & 1] != NULL){
400.         current = current->next[key & 1];
401.         int MASK = key&1; // current decision
402.         if(length != 0)
403.           MASK <<= length;
404.         *code |= MASK;
405.         key >>= 1;
406.         ++length;
407.       }
408.     }
409.     assert( 0 );  // should not come here.
410.     return NULL;
411.   }
412.   void del(TrieNode *node) {
413.     if(node == NULL)
414.       return;
415.     TrieNode *left, *right;
416.     left = node->next[0];
417.     right = node->next[1];
418.     del(left);
419.     del(right);
420.     delete node;
421.   }
422.   int printNode(TrieNode *current) {
423.     if(current == NULL)
424.       return 0;
425.     if(current->page != NULL) {
426.       current->page->print();
427.       return current->page->size();
428.     }
429.     int number = printNode(current->next[0]);
430.     number += printNode(current->next[1]);
431.     return number;
432.   }
433.   int max_bits(TrieNode *node) {
434.     if(node->page != NULL)
435.       return node->page->getSIG_BITS();
436.     int left = max_bits(node->next[0]);
437.     int right = max_bits(node->next[1]);
438.     int max = (left > right) ? left : right;
439.     return max;
440.   }
441.   const static int DFL_BUCKET_SIZE = 4;   // default bucket size
442.   TrieNode *index;
443.   int sig_bits;
444.   int bucket_size;
445.   int no_of_buckets;
446.   //bool root;
447. };
448.  
449. int printMenu() {
450.   std::system("clear");
451.   std::cout << "-----------------------------------------" << std::endl;
452.   std::cout << "Extendible Hashing Implementation." << std::endl;
453.   std::cout << "-----------------------------------------" << std::endl;
454.   std::cout << "\t\t 1. Insert a Record" << std::endl;
455.   std::cout << "\t\t 2. Search a Record" << std::endl;
456.   std::cout << "\t\t 3. Delete a Record" << std::endl;
457.   std::cout << "\t\t 4. Show All Records"<< std::endl;
458.   std::cout << "\t\t 5. Delete All Records" << std::endl;
459.   std::cout << "\t\t 6. Exit" << std::endl;
460.   int choice;
461.   std::cout << "\nChoice : ";
462.   std::cin >> choice;
463.   std::cout.flush();
464.   return choice;
465. }
466.  
467. void credits() {
468.   std::system("clear");
469.   std::cout << "\n\n\n";
470.   std::cout << "\t\t\t  ----------------------------------------------" << std::endl;
471.   std::cout << "\t\t\t /\\--------------------------------------------/\\" << std::endl;
472.   std::cout << "\t\t\t|| Thanks for evaluating our Extendible Hashing ||" << std::endl;
473.   std::cout << "\t\t\t|| \t\tImplementation.\t\t\t||" << std::endl;
474.   std::cout << "\t\t\t \\/--------------------------------------------\\/" << std::endl;
475.   std::cout << "\t\t\t  ----------------------------------------------" << std::endl;
476.   std::cout << "\n\n\t\tImplementors:-\n";
477.   std::cout << "\t\t\t2006ECS20\tRooparam Choudhary\t(Main Coder)" << std::endl;
478.   std::cout << "\t\t\t2006ECS57\tKumar Ranjeet\t\t(Creative Head)" << std::endl;
479.   std::cout << "\n\nenter to quit...";
480.   std::getchar();
481. }
482.  
483. int main()
484. {
485.   std::cout << "Enter bucket-size : ";
486.   int n;
487.   char ch;
488.   std::cin >> n;
489.   HashTable *table = new HashTable(n);
490.   while(true) {
491.     int choice = printMenu();
492.     ch = std::getchar();  // eat newline
493.     switch(choice) {
494.       case 1:   // Insert a record
495.       {
496.         Student st;
497.         std::cout << "\nEnter Student Name : ";
498.         std::getline(std::cin, st.name);
499.         std::cout << "Enter Entry Number : ";
500.         std::getline(std::cin, st.entryNo);
501.         table->insert(st);
502.         break;
503.       }
504.       case 2:   // search a Record
505.       {
506.         std::string entNum;
507.         std::cout << "\nEnter Entry Number: ";
508.         std::getline(std::cin, entNum);
509.         Student *st = table->search(entNum);
510.         std::cout << *st;
511.         std::cout << std::endl << "enter to continue ...";
512.         ch = std::getchar();
513.         break;
514.       }
515.       case 3:   // delete a Record
516.       {
517.         std::string entNum;
518.         std::cout << "\nEnter Entry Number: ";
519.         std::getline(std::cin, entNum);
520.         table->remove(entNum);
521.         break;
522.       }
523.       case 4:   // show All Records
524.         std::system("clear");
525.         table->print();
526.         std::cout << std::endl << "enter to continue ...";
527.         ch = std::getchar();
528.         break;
529.       case 5:   // clear All Data
530.         delete table;
531.         table = new HashTable(n);
532.         break;
533.       case 6:   // Exit
534.         goto DONE;
535.     }
536.   }
537.   DONE:
538.   delete table;
539.   credits();
540.   return 0;
541. }
542.