Facebook
From Sludgy Cat, 2 Months ago, written in C.
Embed
Download Paste or View Raw
Hits: 29
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <string.h>
  4. #include <math.h>
  5. #include "GenericHashTable.h"
  6.  
  7. #define INT_TYPE 0
  8. #define STR_TYPE 1
  9.  
  10. void duplicateTable(Table *table)
  11. {
  12.     int prev_size = table->currentSize; // A variable to hold the old size, before duplicatoin.
  13.     table->arr = (Object **)realloc(table->arr, table->currentSize * 2 * sizeof(Object *)); // Reallocate the array, making it twice bigger.
  14.     if(table->arr == NULL)
  15.     {
  16.         printf("Error occured while duplicating the array. \n");
  17.         return;
  18.     }
  19.     table->currentSize = table->currentSize * 2; // Update the size.
  20.     table->ratio = table->currentSize / table->originalSize; // Update the rate of currentSize/originalSize.
  21.     for (int i = prev_size; i < table->currentSize; i++) // Initialize new cells of the array with NULLs.
  22.     {
  23.         table->arr[i] = NULL;
  24.     }
  25.     for (int i = table->currentSize - 1; i > 0; i--) // Loop to move all old data to thier new location, for i'th cell it would be: 2*i.
  26.     {
  27.         if (table->arr[i] != NULL)
  28.         {
  29.  
  30.             table->arr[2 * i] = table->arr[i];
  31.             table->arr[i] = NULL; // Initialize old index.
  32.         }
  33.     }
  34. }
  35. int listLength(Object *obj)
  36. {
  37.     int count = 1;
  38.     if (obj == NULL)
  39.         return 0;
  40.     while (obj->nextObj != NULL)
  41.     {
  42.         count++;
  43.         obj = obj->nextObj;
  44.     }
  45.     return count;
  46. }
  47. int intHashFun(int *key, int origSize)
  48. {
  49.     int toReturn = 0;
  50.     toReturn = *key % origSize;
  51.     return toReturn;
  52. }
  53. int strHashFun(char *key, int origSize)
  54. {
  55.     int ascii_val = 0;
  56.     int toReturn = 0;
  57.     for (int i = 0; i < strlen(key); key++)
  58.     {
  59.         ascii_val += key[i];
  60.     }
  61.     toReturn = ascii_val % origSize;
  62.     return toReturn;
  63. }
  64. Object *createObject(void *data)
  65. {
  66.     Object *new_obj = (Object *)calloc(1, sizeof(Object)); // Allocate the memory for the new object.
  67.     if (new_obj == NULL)
  68.     {
  69.         printf("An error occured creating an object. \n");
  70.         return NULL;
  71.     }
  72.     new_obj->data = data;
  73.     if (new_obj->data == NULL)
  74.     {
  75.         printf("An error occured creating an object. \n");
  76.         return NULL;
  77.     }
  78.     else
  79.     {
  80.         new_obj->nextObj = NULL;
  81.         return new_obj;
  82.     }
  83. }
  84. Table *createTable(int size, int dType, int listLength)
  85. {
  86.     Table *new_table = (Table *)calloc(1, sizeof(Table)); // Allocate memory for the table.
  87.     if (new_table == NULL)
  88.     {
  89.         printf("An error occured while allocating the table.\n");
  90.         return NULL;
  91.     }
  92.     //------Variables Initialization--------///
  93.     new_table->listLen = listLength;
  94.     new_table->dataType = dType;
  95.     new_table->originalSize = size;
  96.     new_table->ratio = 1;
  97.     new_table->currentSize = size;
  98.     new_table->arr = (Object **)calloc(size, sizeof(Object *));
  99.     if (new_table->arr == NULL)
  100.     {
  101.         printf("An error occured while allocating the table.\n");
  102.         return NULL;
  103.     }
  104.     else
  105.     {
  106.         return new_table;
  107.     }
  108. }
  109. void printTable(Table *table)
  110. {
  111.     Object *current_object;
  112.     int data_int = 0;
  113.     char *data_string = NULL;
  114.     if (table->dataType == INT_TYPE)
  115.     {
  116.         for (int i = 0; i < table->currentSize; i++)
  117.         {
  118.             printf("[%d]: \t", i);
  119.             current_object = table->arr[i];
  120.             while (current_object != NULL)
  121.             {
  122.                 data_int = *((int *)(current_object->data));
  123.                 if (current_object->nextObj == NULL)
  124.                 {
  125.                     printf("%d", data_int);
  126.                 }
  127.                 else
  128.                     printf("%d \t --> \t", data_int);
  129.                 current_object = current_object->nextObj;
  130.             }
  131.             printf("\n");
  132.         }
  133.         printf("--------------------------------------------------\n");
  134.     }
  135.     else if (table->dataType == STR_TYPE)
  136.     {
  137.         for (int i = 0; i < table->currentSize; i++)
  138.         {
  139.             printf("[%d]: \t", i);
  140.             current_object = table->arr[i];
  141.             while (current_object != NULL)
  142.             {
  143.                 data_string = (char *)current_object->data;
  144.                 if (current_object->nextObj == NULL)
  145.                 {
  146.                     printf("%s", data_string);
  147.                 }
  148.                 else
  149.                     printf("%s \t --> \t", data_string);
  150.                 current_object = current_object->nextObj;
  151.             }
  152.             printf("\n");
  153.         }
  154.         printf("--------------------------------------------------\n");
  155.     }
  156. }
  157. int add(Table *table, void *data)
  158. {
  159.     int location = -1; // A variable to save the location of the hash value.
  160.     int *data_int; // A pointer in-case the data-type is integer.
  161.     char *data_str; // A pointer in-case the data-type is string.
  162.     Object *current_object; // A pointer to the current object.
  163.     Object *new_object; // A pointer to the new object creeated.
  164.     if (table->dataType == INT_TYPE) // In-case the data-type is integer, allocate memory for data_int, and calculate the hash value.
  165.     {
  166.         data_int = (int *)calloc(1, sizeof(int));
  167.         if (data_int == NULL)
  168.         {
  169.             printf("Error: failure in memory allocation.\n");
  170.             return -1;
  171.         }
  172.         *data_int = *((int *)(data));
  173.         location = table->ratio * intHashFun(data_int, table->originalSize);
  174.     }
  175.     else if (table->dataType == STR_TYPE) // In-case the data-type is string, allocate memory for data_str, and calculate the hash value.
  176.     {
  177.         data_str = (char *)calloc(strlen((char*)data)+1, sizeof(char));
  178.         if (data_str == NULL)
  179.         {
  180.             printf("Error: failure in memory allocation.\n");
  181.             return -1;
  182.         }
  183.         strcpy(data_str, ((char *)(data)));
  184.         location = table->ratio * strHashFun(data_str, table->originalSize);
  185.     }
  186.     else
  187.     {
  188.         printf("Error: Invalid data type. \n");
  189.         return -1;
  190.     }
  191.     for (int i = location; i < location + table->ratio; i++) // Scan the array through the indexes given by the ratio variable and the hash variable.
  192.     {
  193.         current_object = table->arr[i];
  194.         if (current_object == NULL) // If there's an empty list, figure out what is the data-type and accordingly add the object to the array as the list's head.
  195.         {
  196.             if (table->dataType == INT_TYPE)
  197.             {
  198.                 new_object = createObject(data_int);
  199.                 table->arr[i] = new_object;
  200.                 return i;
  201.             }
  202.             else
  203.             {
  204.                 new_object = createObject(data_str);
  205.                 table->arr[i] = new_object;
  206.                 return i;
  207.             }
  208.         }
  209.         else if (listLength(current_object) < table->listLen) // If there is a list and it's not filled yet, go down the list and add the new object as the last element.
  210.         {
  211.             if (table->dataType == INT_TYPE)
  212.             {
  213.                 new_object = createObject(data_int);
  214.                 while (current_object->nextObj != NULL)
  215.                     current_object = current_object->nextObj;
  216.                 current_object->nextObj = new_object;
  217.                 return i;
  218.             }
  219.             else
  220.             {
  221.                 new_object = createObject(data_str);
  222.                 while (current_object->nextObj != NULL)
  223.                     current_object = current_object->nextObj;
  224.                 current_object->nextObj = new_object;
  225.                 return i;
  226.             }
  227.         }
  228.     } // If reached this area
  229.     duplicateTable(table);
  230.  
  231.     if (table->dataType == INT_TYPE)
  232.     {
  233.         location = table->ratio * intHashFun(data_int, table->originalSize);
  234.         new_object = createObject(data_int);
  235.         table->arr[location + 1] = new_object;
  236.         return location + 1;
  237.     }
  238.     else
  239.     {
  240.         location = table->ratio * strHashFun(data_str, table->originalSize);
  241.         new_object = createObject(data_str);
  242.         table->arr[location + 1] = new_object;
  243.         return location + 1;
  244.     }
  245. }
  246. int isEqual(int type, void *data1, void *data2)
  247. {
  248.     if (type == STR_TYPE)
  249.     {
  250.         return strcmp((char *)data1, (char *)data2);
  251.     }
  252.     else if (type == INT_TYPE)
  253.     {
  254.         if (*((int *)(data1)) == *((int *)(data2)))
  255.             return 0;
  256.         else
  257.             return 1;
  258.     }
  259.     else
  260.     {
  261.         printf("Error: Invalid data type. \n");
  262.         return -1;
  263.     }
  264. }
  265. Object *search(Table *table, void *data)
  266. {
  267.     int location = -1;
  268.     Object *current_object;
  269.     if (table->dataType == INT_TYPE)
  270.         location = table->ratio * intHashFun(((int *)(data)), table->originalSize);
  271.     else
  272.         location = table->ratio * strHashFun((char *)(data), table->originalSize);
  273.     for (int i = location; i < location + table->ratio; i++)
  274.     {
  275.         current_object = table->arr[i];
  276.         if (listLength(table->arr[i]) > 0)
  277.         {
  278.             while (current_object != NULL)
  279.             {
  280.                 if (table->dataType == INT_TYPE)
  281.                 {
  282.                     if (isEqual(table->dataType, (int *)(data), current_object->data) == 0)
  283.                         return current_object;
  284.                 }
  285.                 else
  286.                 {
  287.                     if (isEqual(table->dataType, (char *)(data), current_object->data) == 0)
  288.                         return current_object;
  289.                 }
  290.                 current_object = current_object->nextObj;
  291.             }
  292.         }
  293.     }
  294.     return NULL;
  295. }
  296. int removeObj(Table *table, void *data)
  297. {
  298.     int location = -1;
  299.     Object *temp_object;
  300.     Object *temp_next;
  301.     if (table->dataType == INT_TYPE)
  302.         location = table->ratio * intHashFun(data, table->originalSize);
  303.     else
  304.         location = table->ratio * strHashFun(data, table->originalSize);
  305.     for (int i = location; i < location + table->ratio; i++)
  306.     {
  307.         temp_object = table->arr[i];
  308.         if (temp_object == NULL)
  309.             continue;
  310.         else if(table->dataType == INT_TYPE && isEqual(INT_TYPE,temp_object->data,data)==0 && temp_object->nextObj!=NULL)
  311.         {
  312.             table->arr[i]= temp_object->nextObj;
  313.             freeObject(temp_object,INT_TYPE);
  314.             return i;
  315.         }
  316.         else if(table->dataType == STR_TYPE && isEqual(STR_TYPE,temp_object->data,data)==0 && temp_object->nextObj!=NULL)
  317.         {
  318.             table->arr[i]= temp_object->nextObj;
  319.             freeObject(temp_object,STR_TYPE);
  320.             return i;
  321.         }
  322.         else if (temp_object->nextObj == NULL)
  323.         {
  324.             if (table->dataType == INT_TYPE)
  325.             {
  326.                 if (isEqual(INT_TYPE, temp_object->data, data) == 0)
  327.                 {
  328.                     freeObject(table->arr[i], INT_TYPE);
  329.                     table->arr[i] = NULL;
  330.                     return i;
  331.                 }
  332.             }
  333.             else
  334.             {
  335.                 if (isEqual(STR_TYPE, temp_object->data, data) == 0)
  336.                 {
  337.                     freeObject(table->arr[i], STR_TYPE);
  338.                     table->arr[i] = NULL;
  339.                     return i;
  340.                 }
  341.             }
  342.         }
  343.         else
  344.         {
  345.             while (temp_object->nextObj != NULL)
  346.             {
  347.                 if (table->dataType == INT_TYPE)
  348.                 {
  349.                     if (isEqual(INT_TYPE, temp_object->nextObj->data, data) == 0)
  350.                     {
  351.                         temp_next=temp_object->nextObj->nextObj;
  352.                         freeObject(temp_object->nextObj,INT_TYPE);                        
  353.                         temp_object->nextObj = temp_next;
  354.                         return i;
  355.                     }
  356.                 }
  357.                 else
  358.                 {
  359.                     if (isEqual(STR_TYPE, temp_object->nextObj->data, data) == 0)
  360.                     {
  361.                         temp_next=temp_object->nextObj->nextObj;
  362.                         freeObject(temp_object->nextObj,STR_TYPE);
  363.                         temp_object->nextObj = temp_next;
  364.                         return i;
  365.                     }
  366.                 }
  367.                 temp_object = temp_object->nextObj;
  368.             }
  369.         }
  370.     }
  371.     return -1;
  372. }
  373. void freeObject(Object *obj, int type)
  374. {
  375.     if(obj!=NULL)
  376.     {
  377.         free(obj->data);
  378.         free(obj);
  379.     }
  380. }
  381. void freeTable(Table* table)
  382. {
  383.     Object* temp;
  384.     Object* current_object;
  385.     for(int i = 0; i < table->currentSize; i++)
  386.     {
  387.         if(table->arr[i] != NULL)
  388.         {
  389.             current_object = table->arr[i];
  390.             if(listLength(table->arr[i])==1)
  391.             {
  392.                 freeObject(table->arr[i],table->dataType);
  393.                 continue;
  394.             }
  395.             else if(listLength(table->arr[i]) > 1)
  396.             {
  397.                 for(int j = 0; j < listLength(table->arr[i]);j++)
  398.                 {
  399.                     temp = current_object->nextObj;
  400.                     freeObject(current_object,table->dataType);
  401.                     current_object=temp;
  402.                 }
  403.                 //freeObject(table->arr[i],table->dataType);
  404.             }
  405.         }
  406.     }
  407.     free(table->arr);
  408.     free(table);
  409. }
  410. int main()
  411. {
  412.     int a = 8;
  413.     int b = 16;
  414.     int c = 24;
  415.     int d = 5;
  416.     int e = 9;
  417.     int f = 13;
  418.     int g = 6;
  419.     int h = 10;
  420.     int i = 14;
  421.     int j = 104;
  422.     char *str1 = "aaaaaaaaaa";
  423.     char *str2 = "b r r r r e ";
  424.     char *str3 = "cwjxcn cwnjcwj";
  425.     char *str4 = "dwcnjwc njcwnjwc";
  426.     char *str5 = "ecwwc wcwc cwcw";
  427.     char *str6 = "f";
  428.     char *str7 = "ew33f";
  429.     Table *temp = createTable(8, 0, 2);
  430.     add(temp, (void *)&a);
  431.     add(temp, (void *)&b);
  432.     add(temp, (void *)&c);
  433.     add(temp, (void *)&d);
  434.     add(temp, (void *)&e);
  435.     add(temp, (void *)&f);
  436.     add(temp, (void *)&g);
  437.     add(temp, (void *)&h);
  438.     add(temp, (void *)&i);
  439.     printTable(temp);
  440.     Object *xyz = search(temp, (void *)&a);
  441.     if(xyz != NULL){
  442.         printf("a = %d\n", *(int*)xyz->data);
  443.     }
  444.     else{printf("NULL\n");}
  445.     xyz = search(temp, (void *)&c);
  446.     if(xyz != NULL){
  447.         printf("c = %d\n", *(int*)xyz->data);
  448.     }
  449.     else{printf("NULL\n");}
  450.     xyz = search(temp, (void *)&j);
  451.     if(xyz != NULL){
  452.         printf("j = %d\n", *(int*)xyz->data);
  453.     }
  454.     else{printf("NULL\n");}
  455.         xyz = search(temp, (void *)&f);
  456.     if(xyz != NULL){
  457.         printf("f = %d\n", *(int*)xyz->data);
  458.     }
  459.     else{printf("NULL\n");}
  460.     int x =removeObj(temp,(void*)&a);
  461.     int xx =removeObj(temp,(void*)&j);
  462.     int xxx =removeObj(temp,(void*)&a);
  463.     int y = removeObj(temp,(void*)&c);
  464.     int z = removeObj(temp,(void*)&i);
  465.     xyz = search(temp, (void *)&a);
  466.     printTable(temp);
  467.     if(xyz != NULL){
  468.         printf("a = %d\n", *(int*)xyz->data);
  469.     }
  470.     else{printf("NULL\n");}
  471.     xyz = search(temp, (void *)&f);
  472.     if(xyz != NULL){
  473.         printf("f = %d\n", *(int*)xyz->data);
  474.     }
  475.     else{printf("NULL\n");}
  476.     xyz = search(temp, (void *)&b);
  477.     if(xyz != NULL){
  478.         printf("b = %d\n", *(int*)xyz->data);
  479.     }
  480.     else{printf("NULL\n");}
  481.     printf("\n%d %d %d %d %d\n\n",x,xx,xxx,y,z);
  482.     Table *tempO = createTable(4, 1, 3);
  483.     add(tempO, (void *)str1);
  484.     add(tempO, (void *)str2);
  485.     add(tempO, (void *)str3);
  486.     add(tempO, (void *)str4);
  487.     add(tempO, (void *)str5);
  488.     add(tempO, (void *)str6);
  489.     printTable(tempO);
  490.     xyz = search(tempO, (void *)str1);
  491.     if(xyz != NULL){
  492.         printf("str1 = %s\n", (char*)xyz->data);
  493.     }
  494.     else{printf("NULL\n");}
  495.     xyz = search(tempO, (void *)str2);
  496.     if(xyz != NULL){
  497.         printf("str2 = %s\n", (char*)xyz->data);
  498.     }
  499.     else{printf("NULL\n");}
  500.     xyz = search(tempO, (void *)str3);
  501.     if(xyz != NULL){
  502.         printf("str3 = %s\n", (char*)xyz->data);
  503.     }
  504.     else{printf("NULL\n");}
  505.     add(tempO, (void *)str1);
  506.     add(tempO, (void *)str2);
  507.     add(tempO, (void *)str3);
  508.     add(tempO, (void *)str4);
  509.     add(tempO, (void *)str5);
  510.     add(tempO, (void *)str6);
  511.     printTable(tempO);
  512.     int x1 =removeObj(tempO,(void*)str6);
  513.     int xx1 =removeObj(tempO,(void*)str3);
  514.     int xxx1 =removeObj(tempO,(void*)str6);
  515.     int y1 = removeObj(tempO,(void*)str1);
  516.     int z1 = removeObj(tempO,(void*)str7);
  517.     printTable(tempO);
  518.     printf("\n%d %d %d %d %d\n\n",x1,xx1,xxx1,y1,z1);
  519.         xyz = search(tempO, (void *)str1);
  520.     if(xyz != NULL){
  521.         printf("str1 = %s\n", (char*)xyz->data);
  522.     }
  523.     else{printf("NULL\n");}
  524.     xyz = search(tempO, (void *)str2);
  525.     if(xyz != NULL){
  526.         printf("str2 = %s\n", (char*)xyz->data);
  527.     }
  528.     else{printf("NULL\n");}
  529.     xyz = search(tempO, (void *)str3);
  530.     if(xyz != NULL){
  531.         printf("str3 = %s\n", (char*)xyz->data);
  532.     }
  533.     else{printf("NULL\n");}
  534.     freeTable(temp);
  535.     freeTable(tempO);
  536.     return 0;
  537. }
  538. /*int main()
  539. {
  540.     Table *t = createTable(4, STR_TYPE, 2);
  541.     char *c1 = "a";
  542.     char *c2 = "b";
  543.     char *c3 = "c";
  544.     char *c4 = "d";
  545.    
  546.     add(t, (void *)c1);
  547.     add(t, (void *)c1);
  548.     add(t, (void *)c1);
  549.     add(t, (void *)c1);
  550.     //printTable(t);
  551.     add(t, (void *)c2);
  552.     add(t, (void *)c2);
  553.     add(t, (void *)c2);
  554.     add(t, (void *)c2);
  555.     //printTable(t);
  556.     add(t, (void *)c3);
  557.     add(t, (void *)c3);
  558.     add(t, (void *)c3);
  559.     add(t, (void *)c3);
  560.     //printTable(t);
  561.     add(t, (void *)c4);
  562.     add(t, (void *)c4);
  563.     add(t, (void *)c4);
  564.     add(t, (void *)c4);
  565.     printTable(t);
  566.   //  printf("%s\n", ((char *)(search(t, c4)->data)));
  567.     removeObj(t,c4);
  568.    // printTable(t);
  569.     //removeObj(t,(char *)(search(t, c4)->data));
  570.     //removeObj(t,(char *)(search(t, c4)->data));
  571.     //removeObj(t,(char *)(search(t, c4)->data));
  572.    // removeObj(t,(char *)(search(t, c4)->data));
  573.     //printTable(t);
  574.     freeTable(t);
  575. }
  576. */
  577.  

Replies to Untitled rss

Title Name Language When
Re: Untitled Baby Teal c 2 Months ago.