SHARE
TWEET

Untitled

a guest Nov 22nd, 2019 75 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. FILE *fin, *fout;
  6.  
  7. #define TABLE_SIZE 10069
  8.  
  9. typedef struct entry_t {
  10.     char *key;
  11.     char *value;
  12.     struct entry_t *next;
  13. } entry_t;
  14.  
  15. typedef struct {
  16.     entry_t **entries;
  17. } ht_t;
  18.  
  19. unsigned int hash(const char *key) {
  20.     int ikey = atoi(key);
  21.     unsigned int value = abs(ikey) % TABLE_SIZE;
  22.     return value;
  23. }
  24.  
  25. entry_t *ht_pair(const char *key, const char *value) {
  26.     entry_t *entry = malloc(sizeof(entry_t) * 1);
  27.     entry->key = malloc(strlen(key) + 1);
  28.     entry->value = malloc(strlen(value) + 1);
  29.  
  30.     strcpy(entry->key, key);
  31.     strcpy(entry->value, value);
  32.  
  33.     entry->next = NULL;
  34.  
  35.     return entry;
  36. }
  37.  
  38. ht_t *ht_create(void) {
  39.     ht_t *hashtable = malloc(sizeof(ht_t) * 1);
  40.  
  41.     hashtable->entries = malloc(sizeof(entry_t*) * TABLE_SIZE);
  42.  
  43.     int i = 0;
  44.     for (; i < TABLE_SIZE; ++i) {
  45.         hashtable->entries[i] = NULL;
  46.     }
  47.  
  48.     return hashtable;
  49. }
  50.  
  51. char *ht_find(ht_t *hashtable, const char *key) {
  52.     unsigned int slot = hash(key);
  53.  
  54.     entry_t *entry = hashtable->entries[slot];
  55.  
  56.     if (entry == NULL) {
  57.         return "false";
  58.     }
  59.  
  60.     while (entry != NULL) {
  61.         if (strcmp(entry->key, key) == 0) {
  62.             return "true";
  63.         }
  64.  
  65.         entry = entry->next;
  66.     }
  67.  
  68.     return "false";
  69. }
  70.  
  71. void ht_insert(ht_t *hashtable, const char *key, const char *value) {
  72.  
  73.         unsigned int slot = hash(key);
  74.  
  75.         entry_t *entry = hashtable->entries[slot];
  76.  
  77.         if (entry == NULL) {
  78.             hashtable->entries[slot] = ht_pair(key, value);
  79.             return;
  80.         }
  81.         entry->value;
  82.  
  83.         entry_t *prev;
  84.  
  85.         while (entry != NULL) {
  86.             if (strcmp(entry->key, key) == 0) {
  87.                 free(entry->value);
  88.                 entry->value = malloc(strlen(value) + 1);
  89.                 strcpy(entry->value, value);
  90.                 return;
  91.             }
  92.  
  93.             prev = entry;
  94.             entry = prev->next;
  95.         }
  96.  
  97.         prev->next = ht_pair(key, value);
  98.      
  99. }
  100.  
  101. void ht_delete(ht_t *hashtable, const char *key) {
  102.     unsigned int bucket = hash(key);
  103.  
  104.     entry_t *entry = hashtable->entries[bucket];
  105.  
  106.     if (entry == NULL) {
  107.         return;
  108.     }
  109.  
  110.     entry_t *prev;
  111.     int idx = 0;
  112.  
  113.     while (entry != NULL) {
  114.         if (strcmp(entry->key, key) == 0) {
  115.             if (entry->next == NULL && idx == 0) {
  116.                 hashtable->entries[bucket] = NULL;
  117.             }
  118.  
  119.             if (entry->next != NULL && idx == 0) {
  120.                 hashtable->entries[bucket] = entry->next;
  121.             }
  122.  
  123.             if (entry->next == NULL && idx != 0) {
  124.                 prev->next = NULL;
  125.             }
  126.  
  127.             if (entry->next != NULL && idx != 0) {
  128.                 prev->next = entry->next;
  129.             }
  130.  
  131.             free(entry->key);
  132.             free(entry->value);
  133.             free(entry);
  134.  
  135.             return;
  136.         }
  137.  
  138.         prev = entry;
  139.         entry = prev->next;
  140.  
  141.         ++idx;
  142.     }
  143. }
  144.  
  145. int main() {
  146.     ht_t *ht = ht_create();
  147.  
  148.     fin = fopen("set.in", "r");
  149.     fout = fopen("set.out", "w");
  150.  
  151.     char buffer[10], key[12];
  152.     while (fscanf(fin, "%s", buffer) != EOF) {
  153.         switch (buffer[0])
  154.         {
  155.             case 'i':
  156.                 fscanf(fin, "%s", &key);
  157.                 ht_insert(ht, key, key);
  158.                 break;
  159.             case 'd':
  160.                 fscanf(fin, "%s", &key);
  161.                 ht_delete(ht, key);
  162.                 break;
  163.             case 'e':
  164.                 fscanf(fin, "%s", &key);
  165.                 fprintf(fout, "%s\n",ht_find(ht, key));
  166.                 break;
  167.         }
  168.     }
  169.     return 0;
  170. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top