Advertisement
Jodyone

optimized load

Oct 23rd, 2014
153
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 3.44 KB | None | 0 0
  1. b/****************************************************************************
  2.  * dictionary.c
  3.  *
  4.  * Computer Science 50
  5.  * Problem Set 5
  6.  *
  7.  * Implements a dictionary's functionality.
  8.  ***************************************************************************/
  9. #include <stdio.h>
  10. #include <stdbool.h>
  11. #include <stdlib.h>
  12. #include "dictionary.h"
  13. #include <ctype.h>
  14. #include <string.h>
  15. #include <sys/mman.h>
  16. #include <sys/stat.h>
  17. #include <unistd.h>
  18. #include <fcntl.h>
  19.  
  20. #define SIZE 250000
  21.  
  22. typedef struct node
  23. {
  24.     char word[LENGTH + 1];  
  25.     struct node* next;
  26. }
  27. node;
  28.  
  29. // Make a hash table
  30. node* hashtable[SIZE];
  31. char temp_word[LENGTH + 1];
  32. unsigned int word_ctr = 0;
  33. // this hash function is from delipity on reddit
  34. int hash_d(char* word)
  35. {  
  36.     unsigned int hash = 0;
  37.     for (int i = 0, n = strlen(word); i < n; i++)
  38.     {
  39.         hash = (hash << 2) ^ word[i];
  40.     }
  41.      
  42.     return hash % SIZE;
  43. }
  44. /**
  45.  * Returns true if word is in dictionary else false.
  46.  */
  47. bool check(const char* word)
  48. {
  49.     // TODO
  50.     char new_word[LENGTH + 1];
  51.     for (int i = 0, n = strlen(word); i <= n; i++)
  52.     {
  53.         new_word[i] = word[i];
  54.         new_word[i] = tolower(new_word[i]);
  55.     }
  56.      
  57.     // determine the correct hash position
  58.     int y = hash_d(new_word);
  59.  
  60.     // point the cursor to the first item in the list we identified
  61.     node* cursor = hashtable[y];
  62.    
  63.     // search the linked list
  64.     while (cursor != NULL)
  65.     {
  66.         if (strcmp(cursor->word,new_word) == 0)
  67.         {  
  68.             return true;
  69.         }
  70.         else
  71.         {
  72.             cursor = cursor->next;
  73.         }
  74.     }
  75.     return false;
  76. }
  77.  
  78. /**
  79.  * Loads dictionary into memory.  Returns true if successful else false.
  80.  */
  81. bool load(const char* dictionary)
  82. {
  83.     // TODO
  84.     // do some prep work
  85.    
  86.        struct stat buf;
  87.     if (stat(dictionary, &buf))
  88.         return false;
  89.  
  90.     // map file into memory
  91.     int fd = open(dictionary, O_RDONLY);
  92.     if (fd < 0)
  93.         return false;
  94.    
  95.     char *map = mmap(0, buf.st_size, PROT_READ, MAP_SHARED, fd, 0);
  96.     if (map == MAP_FAILED)
  97.     {
  98.         close(fd);
  99.         return false;
  100.     }
  101.    
  102.     // iterate over array
  103.     for (int i = 0; i < strlen(map); i++)  // here is were im stuck on logic
  104.                                            // the dictionary at this point is in *map every word has a \n seperating
  105.                                            //  it.                      
  106.                                            // not sure if i should change the \n to \0 and put it in another array
  107.                                            // or what ? i know that it needs to be put into the hashtable ?
  108.                                            // i believe the idea is to not use scanf to read and not malloc for the
  109.                                            // new-node->word?
  110.     // do some cleanup work
  111.     close(fd);
  112.     return true;
  113.  }
  114. /**
  115.  * Returns number of words in dictionary if loaded else 0 if not yet loaded.
  116.  */
  117. unsigned int size(void)
  118. {
  119.     // TODO
  120.     return word_ctr;
  121. }
  122.  
  123. /**
  124.  * Unloads dictionary from memory.  Returns true if successful else false.
  125.  */
  126. bool unload(void)
  127. {
  128.     // TODO
  129.  
  130.     for (int i = 0; i < SIZE ; i++)
  131.     {
  132.         node* cursor = hashtable[i];
  133.         while (cursor != NULL)
  134.         {
  135.             node* temp = cursor;
  136.             cursor = cursor->next;
  137.             free(temp);
  138.         }
  139.     }
  140.     return true;
  141. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement