dictionary.c 1.7 KB

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