dictionary.c 2.1 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879
  1. #include <string.h>
  2. #include "dictionary.h"
  3. //form hash value for string s
  4. //this produces a starting value in the dictionary array
  5. unsigned hash(const char *s) {
  6. unsigned hashval;
  7. for (hashval = 0; *s != '\0'; s++)
  8. hashval = *s + 31 * hashval;
  9. return hashval ;
  10. }
  11. //Performs search for a key in the hashtable.
  12. //if the string s is in the dictionary, it is in the list of blocks
  13. //beginning in array entry hash(s).
  14. //if lookup finds entry for s, it returns a pointer to the node
  15. //if not - it returns NULL
  16. DNode * lookup (DNode ** dictionary, int hash_size, const char *key) {
  17. DNode * np;
  18. unsigned int hashval = hash(key);
  19. for (np = dictionary [hashval % hash_size]; np !=NULL; np = np->next)
  20. if (strcmp (key, np->key) == 0)
  21. return np; //found
  22. return NULL; //not found
  23. }
  24. //insert uses lookup to detemine whether key is already in the dictionary
  25. //if not, a new entry is created
  26. DNode * insert (DNode ** dictionary, int hash_size, const char * key) {
  27. unsigned int hashval;
  28. DNode *np;
  29. if ((np = lookup (dictionary, hash_size, key)) == NULL ) { //
  30. np = (DNode *) malloc (sizeof (*np));
  31. if (np == NULL || (np->key = copystr (key)) == NULL)
  32. return NULL;
  33. hashval = hash (key) % hash_size;
  34. //now links itself on top of array entry
  35. np->next = dictionary [hashval];
  36. dictionary [hashval] = np;
  37. }
  38. return np;
  39. }
  40. void free_dictionary (DNode ** dictionary, int hash_size) {
  41. int i;
  42. for (i=0; i<hash_size; i++) { //iterate over hash array
  43. if (dictionary [i]!=NULL) { //if there is an entry at position i
  44. DNode *head = dictionary[i]; //find the head of the linked list
  45. DNode *current = head;
  46. while (current != NULL) {
  47. DNode * temp = current;
  48. current = current->next;
  49. if (temp->key !=NULL)
  50. free (temp->key);
  51. free (temp);
  52. }
  53. dictionary[i] = NULL; //BUG fix
  54. }
  55. }
  56. }
  57. char *copystr(const char *s) { /* make a duplicate of s */
  58. char *p;
  59. int len = strlen(s);
  60. p = (char *) malloc(len+1); /* +1 for �\0� */
  61. if (p != NULL)
  62. strncpy(p, s, len);
  63. p[len] = '\0';
  64. return p;
  65. }